Questions tagged [integers]
Questions about properties of, working with and algorithms on integers.
137
questions
24
votes
2answers
729 views
Efficient algorithm for 'unsumming' a set of sums
Given a multiset of natural numbers X, consider the set of all possible sums:
$$\textrm{sums}(X)= \left\{ \sum_{i \in A} i \,|\, A \subseteq X \right\}$$
For example, $\textrm{sums}(\left\{1,5\right\...
22
votes
3answers
1k views
Algorithm to minimize surface area, given volume
Consider the following algorithmic task:
Input: a positive integer $n$, along with its prime factorization
Find: positive integers $x,y,z$ that minimize $xy+yz+xz$, subject to the restriction that $...
21
votes
3answers
11k views
What is the most efficient way to compute factorials modulo a prime?
Do you know any algorithm that calculates the factorial after modulus efficiently?
For example, I want to program:
...
15
votes
3answers
4k views
Determine missing number in data stream
We receive a stream of $n-1$ pairwise different numbers from the set $\left\{1,\dots,n\right\}$.
How can I determine the missing number with an algorithm that reads the stream once and uses a memory ...
14
votes
2answers
5k views
Representing Negative and Complex Numbers Using Lambda Calculus
Most tutorials on Lambda Calculus provide example where Positive Integers and Booleans can be represented by Functions. What about -1 and i?
13
votes
1answer
824 views
Overflow safe summation
Suppose I am given $n$ fixed width integers (i.e. they fit in a register of width $w$), $a_1, a_2, \dots a_n$ such that their sum $a_1 + a_2 + \dots + a_n = S$ also fits in a register of width $w$.
...
13
votes
4answers
2k views
Comparing rational numbers
Given $a,b,c,d \in \mathbb N$ and $b,d \notin \{0\}$,
$$
\begin{eqnarray*}
\frac a b < \frac c d &\iff& ad < cb
\end{eqnarray*}
$$
My questions are:
Given $a,b,c,d$
Assuming we can ...
11
votes
3answers
5k views
What data structure would efficiently store integer ranges?
I need to keep a collection on integers in the range 0 to 65535 so that I can quickly do the following:
Insert a new integer
Insert a range of contiguous integers
Remove an integer
Remove all ...
11
votes
4answers
4k views
Most efficient algorithm to print 1-100 using a given random number generator
We are given a random number generator RandNum50 which generates a random integer uniformly in the range 1–50.
We may use only this random number generator to ...
11
votes
3answers
449 views
Number of multisets such that each number from 1 to $n$ can be uniquely expressed as a sum of some of the elements of the multiset
My problem. Given $n$, I want to count the number of valid multisets $S$. A multiset $S$ is valid if
The sum of the elements of $S$ is $n$, and
Every number from $1$ to $n$ can be expressed uniquely ...
10
votes
5answers
1k views
Language of the values of an affine function
Write $\bar n$ for the decimal expansion of $n$ (with no leading 0). Let $a$ and $b$ be integers, with $a > 0$. Consider the language of the decimal expansions ...
asked Mar 22 '12 at 1:54
Gilles 'SO- stop being evil'
40.9k7 gold badges108 silver badges172 bronze badges
10
votes
2answers
252 views
9
votes
1answer
436 views
What algorithms exist for solving natural number linear systems?
I'm looking at the following problem:
Given $n$-dimensional vectors of natural numbers $v_1, \ldots, v_m$ and some input vector $u$, is $u$ a linear combination of the $v_i$'s with natural number ...
9
votes
3answers
304 views
Test if there exists an integer k to add to one sequence to make it a subsequence of another sequence
Suppose that sequence $A$ contains $n$ integers $a_1,a_2,a_3,\ldots,a_n$ and sequence $B$ contains $m$ integers $b_1,b_2,b_3,\ldots,b_m$. We know that $m \geq n$. We assume without loss of generality ...
9
votes
1answer
2k views
Algorithm for multiplying multivariate polynomials
Let $R$ be a commutative ring. Let $f(x_1, \dots, x_n), g(x_1, \dots, x_n)$ be two multidimensional polynomials in $R$ with maximal total degree $\delta$.
How fast can we compute the product of $f$ ...
8
votes
2answers
7k views
Algorithm to find optimal currency denominations
Mark lives in a tiny country populated by people who tend to over-think things. One day, the king of the country decides to redesign the country's currency to make giving change more efficient. The ...
8
votes
2answers
1k views
How can I find minimum number required to add to sequence such that their xor becomes zero
Given a sequence of natural numbers, you can add any natural number to any number in the sequence such that their xor becomes zero. My goal is to minimize the sum of added numbers.
Consider the ...
8
votes
2answers
711 views
Detecting overflow in summation
Suppose I am given an array of $n$ fixed width integers (i.e. they fit in a register of width $w$), $a_1, a_2, \dots a_n$. I want to compute the sum $S = a_1 + \ldots + a_n$ on a machine with 2's ...
asked Apr 22 '12 at 1:16
Gilles 'SO- stop being evil'
40.9k7 gold badges108 silver badges172 bronze badges
7
votes
2answers
8k views
Algorithm to return largest subset of non-intersecting intervals
I need an efficient algorithm that takes input a collection of intervals and outputs the largest subset of non-intersecting intervals.
i.e. Given a set of intervals $I = \{I_1, I_2, \ldots, I_n\}$ ...
7
votes
2answers
442 views
Understanding Intel's algorithm for reducing a polynomial modulo an irreducible polynomial
I'm reading this Intel white paper on carry-less multiplication. It describes multiplication of polynomials in $\text{GF}(2^n)$. On a high level, this is performed in two steps: (1) multiplication of ...
7
votes
3answers
479 views
Unreachable Real Numbers - Randomness & Computability
I've recently read that there were many real numbers that would never be reachable by humanity. The explanation itself says that we can write as many programs as integers which is infinite, but there ...
6
votes
3answers
1k views
What is the bitwise xor of an interval?
Let $\oplus$ be bitwise xor. Let $k,a,b$ be non-negative integers. $[a..b]=\{x\mid a\leq x, x\leq b\}$, it is called a integer interval.
What is a fast algorithm to find
$\{ k\oplus x\mid x\in [a..b]...
6
votes
3answers
1k views
Converting function to bitwise only?
I have a function to count upper bits of a 32 bit value. So if a number is 11100011111..., the result is 3 as there are 3 ones in the most significant place before a 0 is hit.
I need to convert the ...
6
votes
3answers
2k views
Space complexity for storing integers in Python
So I was watching this mock interview by an Airbnb engineer on interviewing.io (https://youtu.be/cdCeU8DJvPM?t=1224) and around ~20:11 seconds he raises an interesting point.
The question that the ...
6
votes
1answer
741 views
Complexity of Linear Diophantine equations
My question is simply, can linear Diophantine equations be solved in polynomial time? Specifically, I am looking at equations of the form $a_1 x_1+a_2 x_2 + ... + a_n x_n = k$, where $a_i,x_i,k$ are ...
6
votes
1answer
379 views
Division by a constant
After skimming Multiplication by a Constant is Sublinear (PDF), (slides (PDF), slides with notes (PDF)) I was wondering if this could be extended to division by a constant in sublinear time?
...
6
votes
3answers
287 views
Find the minimum range
Given a list of numbers as L, how do you find the minimum value m such that L can be made ...
6
votes
1answer
1k views
Fastest square root method with exact integer result?
I am dealing with the problem of computing $ s = \lfloor sqrt(x)\rfloor$ with $x \in [0,30000^2]$. The common sqrtf(x) on C language is too slow for this case, ...
6
votes
2answers
198 views
Isn't std::bernoulli_distribution inefficient? Designing a bit-parallel Bernoulli generator
C++11 has a convenient Bernoulli RNG, illustrated at
http://en.cppreference.com/w/cpp/numeric/random/bernoulli_distribution .
However, distilling an entire random integer into a single random bit ...
5
votes
3answers
369 views
Why is the addition function exponential for k-bit integers providing only zero, equality and the successor functions?
I'm currently reading the elements of programming book and have come across a section I don't quite understand
A computational basis for a type is a finite set of procedures that enable the ...
5
votes
2answers
104 views
Quick calculation for $(x^y) \bmod z$
What are the possible ways to calculate $(x^y) \bmod z$ quickly for very large integers?
Integers $x,y \lt 10^{10000}$ and $z \lt 10^6$.
5
votes
1answer
486 views
Difference in Sorting 32- and 64-bit Integers
In 2007, Barrack Obama was interviewed at Google.
The question was, "What is the best way to sort a million 32-bit integers?" Does the fact that the size range of the integer was specified elude to a ...
5
votes
2answers
1k views
Find 8 numbers whose sum is closest to a defined value
I have a file that has a number (a positive integer) on each row.
Given a number $q$, I want to find a value that's a sum of some 8 numbers in the file, and is as close to $q$ as possible.
So, ...
5
votes
2answers
162 views
Numeral systems other than unary used in nature or in animal and human behaviours
Representing numeric values using positional notation is one of the milestones in the history of arithmetic. Babylons used a base 60 system, Maya a base 20 system; base 10 system became "the standard" ...
5
votes
1answer
133 views
Checking whether an integer is a square or higher power
Is there an algorithm to check whether an integer $n$ is a square? What about higher powers, e.g., testing whether $n$ is a $k$th power?
I understand that the Jacobi symbol $\left(\frac{b}{n}\right)$...
5
votes
1answer
186 views
Practical Implementation for Refinement Order on Integer Partitions
The refinement order on partitions of an integer $n$ can be defined as follows: $\lambda=(\lambda_1,\dots,\lambda_k)\leq\mu=(\mu_1,\dots,\mu_\ell)$ if there is a partition of the parts of $\lambda$ ...
5
votes
0answers
86 views
What are applications to sort plain integer arrays?
A lot of research and engineering effort is put into finding fast methods
to sort an array of integers; e.g., Java's runtime library has highly-tuned
methods to sort arrays of each primitive type (see ...
5
votes
0answers
541 views
Best complexity of parity/comparison in the Residue Number System
Let:
$\left\{m_1, ~...~, m_k\right\}$ be a set of coprime natural numbers,
$M=\prod_{i=1}^{k} m_i$
$X$ be a natural integer, such that $X < M$
Then $X$ can be expressed in the Residue Number ...
4
votes
2answers
1k views
How are Signed integers different from unsigned integers once compiled
How are Signed integers different from unsigned integers once compiled?
I already know about twos compliment and the like but my question is how can you tell the difference when looking at 8 bit ...
4
votes
2answers
516 views
Are nearly all natural numbers compressible?
A simple counting argument shows most strings can't be compressed to shorter strings. But, compression is usually defined using Kolmogorov complexity. A string is compressible if its Kolmogorov ...
4
votes
3answers
190 views
Language of the graph of an affine function
Write $\bar n$ for the decimal expansion of $n$ (with no leading 0). Let : be a symbol distinct from any digit. Let $a$ and $b$ ...
asked Mar 22 '12 at 1:55
Gilles 'SO- stop being evil'
40.9k7 gold badges108 silver badges172 bronze badges
4
votes
3answers
11k views
What are two's complement integers?
Can someone explain in plain English what "two's complement integer" means? I read this:
in Java long is a 64-bit signed two's complement integer
4
votes
1answer
313 views
Given a RxC grid, how to generate N 2D points randomly such that no 3 points are collinear?
Context, I have a geometric algorithm that is sensitive to collinear points and receives as input a list of points in 2D generated randomly. Suppose that I have a Boolean function nonCollinear(x,y,z) ...
4
votes
1answer
29 views
Compactly representing integers when allowed a multiplicative error
Consider the problem of representing in memory numbers in the range $\{1,\ldots,n\}$.
Obviously, exact representation of such number requires $\lceil\log_2(n)\rceil$ bits.
In contrast, assume we are ...
4
votes
1answer
99 views
Reversible Merge of Integer Hash Values
Context:
I am working with a tree-like data structure. I would like every node in the tree to have an integer hash value that is the result of combining the integer hash values for the node's ...
4
votes
1answer
97 views
Do there exist fast multiplication algorithms for two integers with one of them being static?
Let N and M be arbitrary 1024+ bit integers.
The objective is to compute the product of N and M (2048+ bits)
There exist various multiplication algorithms for various bit lengths (ex library: GMP). ...
3
votes
1answer
383 views
Where can I find an original reference for this integer square root algorithm
As an exercise, I converted an old method I learned for calculating square roots on a rotary decimal hand calculator to binary.
I'm sure this is not original; can anyone provide a reference?
...
3
votes
2answers
95 views
How to find the closest N to the power of X to the given number?
Let's say we have number 4920 and we want to find the closest $n^x$ to 4920
2 ^ 12 = 4096 but it's not the closest possible $n^x$, for example 17 ^ 3 = 4913 is closer to 4920
The question is, how do ...
3
votes
1answer
5k views
Complexity of Integer Division
My favourite algorithm textbook: The Algorithm Design Manual S. Skiena.pdf
had this interesting problem:
1-28. [5] Write a function to perform integer division without using either the / or * ...
3
votes
4answers
780 views
Get specified bit in addition of two large binary numbers
I am performing an addition operation on two large binary numbers that have an equal number of bits. Both numbers are stored in an array of length $N$, which is rather large.
At first I tried running ...
