Questions tagged [integers]

Questions about properties of, working with and algorithms on integers.

Filter by
Sorted by
Tagged with
24
votes
2answers
692 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 $...
20
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
532 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
352 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
232 views

Complexity of computing $n^{n^2}$

What is the complexity of computing $n^{n^2},\;n \in \mathbb{N}$?
9
votes
1answer
370 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
270 views
+150

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
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
877 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
559 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
303 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
3answers
960 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
445 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
288 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
391 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
245 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
164 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
339 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
99 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
2answers
443 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 ...
5
votes
1answer
446 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
791 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
148 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
147 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
508 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
726 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
184 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
3answers
7k 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
84 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
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 ...
3
votes
2answers
88 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
264 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
674 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
2answers
93 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
105 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
869 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 ...