Calculating the floor of y**(1/m)

• URL: http://arxiv.org/abs/2607.03462v1
• Date: Fri, 03 Jul 2026 16:20:37 GMT
• Title: Calculating the floor of y**(1/m)
• Abstract summary: We present two algorithms based on the Newton-Raphson method to calculate the floor of y** (1/m) for natural integer numbers y>2 and m >1.<n>One could use such an algorithm to establish whether y is an integer power of an integer in number theory problems, even though binary search methods are traditionally considered simpler to implement.
• Score: 51.56484100374058
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We present two algorithms based on the Newton-Raphson method to calculate the floor of y**(1/m) for natural integer numbers y>2 and m >1. One could use such an algorithm to establish whether y is an integer power of an integer in number theory problems, even though binary search methods are traditionally considered simpler to implement.

Related papers

• A Summation-Based Algorithm For Integer Factorization [0.0]
  This paper introduces a new method that converts an integer into a sum in base-2.<n>It plays a crucial role in modern cryptography, notably, in the security of RSA encryption.
  arXiv  Detail & Related papers  (2025-04-29T20:35:43Z)
• Arbitrary state creation via controlled measurement [49.494595696663524]
  This algorithm creates an arbitrary $n$-qubit pure quantum superposition state with precision of $m$-decimals.<n>The algorithm uses one-qubit rotations, Hadamard transformations and C-NOT operations with multi-qubit controls.
  arXiv  Detail & Related papers  (2025-04-13T07:23:50Z)
• Provable Scaling Laws for the Test-Time Compute of Large Language Models [84.00141420901038]
  We propose two algorithms that enjoy provable scaling laws for the test-time compute of large language models.<n>One is a two-stage knockout-style algorithm, where each candidate is evaluated by its average win rate against multiple opponents.<n>The other is a two-stage league-style algorithm, where each candidate is evaluated by its average win rate against multiple opponents.
  arXiv  Detail & Related papers  (2024-11-29T05:29:47Z)
• An average case efficient algorithm for solving two-variable linear Diophantine equations [0.0]
  We revisit two algorithms to solve two-variable linear Diophantine equations.<n>We propose an iterative version of the Extended Euclid's algorithm.<n>We find that the average number of iterations by our algorithm is less than that of two existing algorithms.
  arXiv  Detail & Related papers  (2024-09-21T07:51:12Z)
• Computing $\varphi(N)$ for an RSA module with a single quantum query [0.0]
  We give a computation time algorithm to compute $varphi(N)$ for an RSA module $N$ using as input the order modulo $N$ of a randomly chosen integer.
  arXiv  Detail & Related papers  (2024-06-06T13:30:18Z)
• Distributed Shor's algorithm [1.7396274240172125]
  Shor's algorithm is one of the most important quantum algorithms proposed by Peter Shor. We use two quantum computers separately to estimate partial bits of $dfracsr$ for some $sin0, 1, cdots, r-1$. Compared with the traditional Shor's algorithm that uses multiple controlling qubits, our algorithm reduces nearly $dfracL2$ qubits and reduces the circuit depth of each computer.
  arXiv  Detail & Related papers  (2022-07-13T06:00:03Z)
• An Efficient Summation Algorithm for the Accuracy, Convergence and Reproducibility of Parallel Numerical Methods [0.0]
  We have introduced a new parallel algorithm for summing a sequence of floating-point numbers. This algorithm which scales up easily with the number of processors, adds numbers of the same exponents first. In this article, our main contribution is an extensive analysis of its efficiency with respect to several properties.
  arXiv  Detail & Related papers  (2022-05-11T08:31:48Z)
• Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
  Bilevel optimization has been widely applied in many important machine learning applications. We propose two new algorithms for bilevel optimization. We show that both algorithms achieve the complexity of $mathcalO(epsilon-1.5)$, which outperforms all existing algorithms by the order of magnitude.
  arXiv  Detail & Related papers  (2021-06-08T21:05:30Z)
• An integer factorization algorithm which uses diffusion as a computational engine [0.0]
  We develop an algorithm which computes a divisor of an integer $N$, which is assumed to be neither prime nor the power of a prime. By comparison, Shor's algorithm is known to use at most $O(log N)2log (log N) log (log log N)$ quantum steps on a quantum computer.
  arXiv  Detail & Related papers  (2021-04-23T14:11:33Z)
• Quantum Algorithms for String Processing [58.720142291102135]
  We provide a quantum algorithm for the String matching problem that uses exponentially less quantum memory than existing ones. Using the same ideas, we provide two algorithms for the String comparing problem. The second algorithm works exponentially faster than the existing one.
  arXiv  Detail & Related papers  (2020-12-01T09:59:06Z)
• An Optimum Algorithm for Quantum Search [4.043829277196036]
  Grover's algorithm can be improved whenever number of 0's and number 1's are not equal. One interesting application is that Dicke state preparation, which in Grover's algorithm is P on average, can be made poly-efficient.
  arXiv  Detail & Related papers  (2020-10-07T09:58:19Z)
• Second-order Conditional Gradient Sliding [70.88478428882871]
  We present the emphSecond-Order Conditional Gradient Sliding (SOCGS) algorithm.<n>The SOCGS algorithm converges quadratically in primal gap after a finite number of linearly convergent iterations.<n>It is useful when the feasible region can only be accessed efficiently through a linear optimization oracle.
  arXiv  Detail & Related papers  (2020-02-20T17:52:18Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.