Skip to main content
17 votes

Is there an efficient algorithm to find whether an integer is a prime power?

See: Daniel J. Bernstein. Detecting perfect powers in essentially linear time, Mathematics of Computation 67 (1998), 1253–1283. Here, "linear" means "linear in $\log N $". ...
Pseudonym's user avatar
  • 22.3k
10 votes
Accepted

Correctness of FIPS 186-4 square test algorithm

This is more or less Newton's method applied to the function $f:x\to x^2 - C$. The algorithm finds $r = \left\lfloor \sqrt{C}\right\rfloor$ and check whether $r^2 = C$ or not. If we define $g(x) = x - ...
Nathaniel's user avatar
  • 15.8k
10 votes
Accepted

Is there an efficient algorithm to find whether an integer is a prime power?

Note that if a number $N$ is a power of a prime $p$ it will be of the form: $$N=p^i \ ,$$ Since $p$ is prime, $p \geq 2$ which implies $i \leq \log_2 N$. We can compute the $i$th roots of $N$ for each ...
SilvioM's user avatar
  • 933
9 votes
Accepted

Complexity class of integer factorization

Integer factorization (or rather, an appropriate decision version) is not known to be NP-complete. In fact, it is conjectured not to be NP-complete. However, any reasonable decision version of integer ...
Yuval Filmus's user avatar
9 votes
Accepted

Complexity of Integer Division

Wikipedia has a nice page about the complexity of mathematical operations, and there is also a dedicated page about division. Asymptotically, division has the same complexity as multiplication. The ...
Yuval Filmus's user avatar
8 votes
Accepted

Batch rounding with preservation of a sum

There are many rounding methods that round an integer to the nearest integer, all of which are the same except on the half-integers. The sum of integers returned will be close to the sum of the ...
John L.'s user avatar
  • 39.1k
7 votes
Accepted

Given a RxC grid, how to generate N 2D points randomly such that no 3 points are collinear?

For simplicity , assume the grid is a square $N \times N$ grid and $N$ is a prime. Its easy to see that from each row we can pick $\leq 2$ points only , so the maximum number of points we can chose ...
Rajat De's user avatar
  • 121
7 votes
Accepted

Space complexity for storing integers in Python

It depends on the model of computation. In the transdichotomous model, which is the standard model in the analysis of algorithms, we assume that the word size is $w=O(\log n)$ bits, where $n$ is the ...
Laakeri's user avatar
  • 1,339
7 votes

Probability of overflow in a summation of fixed-size signed integers

Calculate the average and variance of choosing a single signed 48 bit variable. Multiply by n to get the average and variance of choosing n 48 bit variables. The standard variation is roughly the ...
gnasher729's user avatar
  • 30.7k
6 votes

How to find the closest N to the power of X to the given number?

Here is a general solution for the following problem: Given a positive integer $m$, find positive integers $a,b \geq 2$ such that $a^b$ is as close as possible to $m$. Let $n$ be the length of $m$ ...
Yuval Filmus's user avatar
6 votes
Accepted

Efficient algorithm for getting from 1 to n with 3 specific operations

Find the shortest path from $1$ to $n$ on an appropriate graph on vertices $\{1, \dots, n\}$. This approach will work whenever it's guaranteed that intermediate values in the calculations will ...
David Richerby's user avatar
6 votes
Accepted

Efficient data structure for storing integers in a range?

Since you know you're going to have to deal with all $2^{32}$ values eventually, you're going to need at least $2^{32}$ bits of memory, one for each value. The pigeonhole principle means that there's ...
Draconis's user avatar
  • 7,148
6 votes
Accepted

Prove HAKMEM Item 23: connection between arithmetic operations and bitwise operations on integers

Bitlength and bound needed for two's complement Prove that for $A, B \in \mathbb{Z}$, $A + B$ $= (A\operatorname{\&}B) + (A \mid B)$ $= (A \oplus B) + 2(A\operatorname{\&}B)$ where $\...
John L.'s user avatar
  • 39.1k
5 votes

Batch rounding with preservation of a sum

Yves's answer will give you exactly the answer you are looking for. An alternative is to use stochastic rounding which will give you the rounded sum in expectation, and may have nicer properties for ...
A Schneider's user avatar
5 votes

Prove HAKMEM Item 23: connection between arithmetic operations and bitwise operations on integers

This answer isn't rigorous or starting from first principles, but I thought this was elegant so here it is anyway. Given that addition is commutative and associative and bit-shifting all summands left ...
Quitting Due To Antisemitism's user avatar
4 votes

There are n numbers. Find the maximal set of pairwise NON coprime numbers

Your problem is NP-complete, I will show a reduction from maximum independent set to your problem. Let $G = (V, E)$ be an undirected graph, and let $G'$ be the complement graph of $G$. Label each edge ...
quicksort's user avatar
  • 4,272
4 votes
Accepted

Algorithm for implementing the modulus "%" operator?

You don’t “implement the modulus operator”. You check wit the standards for your programming language how it is defined, and that’s what you implement. For languages like C, C++, Objective-C, Swift ...
gnasher729's user avatar
  • 30.7k
4 votes
Accepted

How to read off the set represented by a van-Emde-Boas tree?

If you haven't done so, I suggest you read chapter 20 from the beginning. They develop the final data structure bit by bit, supposedly for didactic reasons. In 20.3.1, they write: min stores the ...
Raphael's user avatar
  • 72.6k
4 votes
Accepted

Find the sum of numbers from an array closest to a number, where repetition of the numbers are allowed

This problem is NP-hard by a reduction from partition. Let $X = \{x_1, \dots, x_n\}$, be an instance of partition and let $2M = \sum_{x \in X} x$ (assume that $M$ is an integer as otherwise the ...
Steven's user avatar
  • 29.5k
4 votes
Accepted

Probability of overflow in a summation of fixed-size signed integers

Suppose the 48-bit signed integers are drawn uniformly randomly from $[-2^{47}, 2^{47}-1]$. To overflow, there must be at least $n = 2^{63}/2^{47} = 2^{16}$ integers drawn, so $n$ is large enough for ...
qwr's user avatar
  • 618
3 votes
Accepted

How to determine the carry vector of an integer addition

The generation of the carry vector is a recursive process where the results of lower bits factor into the current carry output. In general: $$ Carry_{n} = (A_{n} \bullet B_{n}) + ((A_{n} \oplus B_{n}...
Peter Camilleri's user avatar
3 votes

Find all pairs (i, j), such that i + (i+1) + (i+2) + ... + j = n

Another algorithm: Find all factorizations of $2n$ into a product of two integers, say $2n=r \times s$ with $r \le s$. Then find $i,j$ such that $j-i+1=r$ and $i+j=s$, i.e., $i=(s-r+1)/2$ and $j=(s+...
D.W.'s user avatar
  • 162k
3 votes
Accepted

Swap elements using integer addition and multiplication gates

Let's say we have inputs $x, y$ and $c$, where $c$ is either 0 or 1, 0 = no swap, 1 = swap. We can make a conditional swap function like this: ...
orlp's user avatar
  • 13.6k
3 votes
Accepted

Convert integer of mixed radix to standard positional numeral system and vice versa

If you have numbers $x_1,\ldots,x_n$ in the ranges $x_1 \in \{0,\ldots,b_1-1\},\ldots,x_n \in \{0,\ldots,b_n-1\}$, you can get a number in the range $\{0,\ldots,b_1\ldots b_n-1\}$ using the formula $$ ...
Yuval Filmus's user avatar
3 votes
Accepted

Find the duplicates in a list of floating point numbers

Sorting The simplest algorithm is to sort your floats, then compare adjacent entries. This will let you find all pairs that are $\le \frac1N$ apart in $O(N \lg N)$ time. Hashing It's also possible ...
D.W.'s user avatar
  • 162k
3 votes
Accepted

Problems that become far easier when restricted to only integer values

There's no single answer. Some algorithms are faster when dealing with small integers, because you can use small integers as the index into an array. Some algorithms are faster when dealing with ...
D.W.'s user avatar
  • 162k
3 votes

Space complexity for storing integers in Python

Resource usage always depends on your model of computation. If you're in a situation where integers can grow arbitrarily large then, yes, you need to take that into account. One way of doing this is ...
David Richerby's user avatar
3 votes
Accepted

Test if there exists an integer k to add to one sequence to make it a subsequence of another sequence

Here is a heuristic that won't always work, but should work with high probability if the integers in the arrays are chosen randomly from a large enough space. Initialize a hashtable of counts $C$ to ...
D.W.'s user avatar
  • 162k
3 votes
Accepted

Efficient Algorithm to Find the Closest Integer Representation, in the Form $A\times\frac{N}{D}$ for a Value

Generally speaking, this problem is called diophantine approximation. However, your inputs are not just real numbers but double-precision floating point (aka double)...
Vincenzo's user avatar
  • 3,317

Only top scored, non community-wiki answers of a minimum length are eligible