# Tag Info

### 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$". ...
• 22.3k
Accepted

• 39.1k

### 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 ...

### 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 ...

### 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 ...
• 4,272
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 ...
• 30.7k
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 ...
• 72.6k
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 ...
• 29.5k
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 ...
• 618
Accepted

• 278k
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 ...
• 162k
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 ...
• 162k

### 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 ...
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 ...
• 162k