Questions tagged [integers]
Questions about properties of, working with and algorithms on integers.
113
questions
23
votes
2answers
686 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\...
21
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 $...
19
votes
3answers
9k 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:
...
14
votes
2answers
4k 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?
14
votes
3answers
3k 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 ...
13
votes
1answer
469 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$.
...
12
votes
4answers
1k 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
4answers
3k 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
330 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 ...
10
votes
3answers
4k 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 ...
10
votes
2answers
231 views
9
votes
1answer
362 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
1answer
1k 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
826 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
536 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 ...
7
votes
2answers
286 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 ...
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
2answers
6k 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\}$ ...
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
1answer
398 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
276 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
375 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
238 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
159 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
333 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
97 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
420 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
680 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
146 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
141 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
1answer
119 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
0answers
82 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
497 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
660 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
3answers
183 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$ ...
4
votes
2answers
424 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
6k 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
22 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
250 views
Optimal quantization of histogram
I have a histogram of occurrences, as a list of counts (non-negative integers). For the purposes of a compression algorithm (specifically arithmetic coding) I must quantize these occurrences into a ...
3
votes
2answers
84 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
247 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
4answers
666 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 ...
3
votes
1answer
67 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) ...
3
votes
2answers
92 views
Can one increment an $n$ bit integer using fewer than $2 - 2^{1-n}$ bit inspections on average?
Given an $n$-bit integer, I am interested in performing an increment operation using as few bit reads as possible. The standard binary code (standard binary representation of numbers), requires $n$ ...
3
votes
2answers
104 views
Remove divisors from a set of integers
I have a set $S$ of integers. I want to remove all elements of $S$ that are divisors of another element of $S$. In other words, I want to compute $T = \{y \in S : \forall d \in S . d \nmid y \}$.
...
3
votes
1answer
803 views
How can repeated addition/multiplication be done in polynomial time?
I can see how adding 2 unsigned $n$-bit values is $O(n)$. We just go from the rightmost digits to the leftmost digits and add the digits up sequentially. We can also perform multiplication in ...
3
votes
2answers
999 views
Carry-free multiplication operation
In long-multiplication, you shift and add, once for each $1$ bit in the lower number.
Let $r = p \otimes q$ be an operation similar to multiplication, but slightly simpler: when expressed via long-...
