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

learn more… | top users | synonyms

6
votes
2answers
73 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 ...
1
vote
1answer
114 views

Algorithm to decide if $n \le m!$

This is an assignment of an introductory course of complexity theory and I need to find a way to do the following: Given $n,m \in \Bbb N$, is $n \le m!$ ? The idea is to provide a Post Machine that ...
4
votes
2answers
65 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$.
1
vote
2answers
56 views

Computing a histogram with the number of extant values not known in advance

(This may be more fitting for CSTheory, I'm not sure.) I'm looking for an practical or theoretical work (that is, academic papers, online jots, pseudocode or code) regarding efficient algorithms for ...
3
votes
1answer
446 views

Shift-and-or multiplication operation

Continuing in the same vein as Carry-free multiplication operation, a followup question is as follows (differences in bold): Let $r = p \oplus q$ be an operation similar to multiplication, but ...
3
votes
2answers
127 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 ...
3
votes
0answers
204 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 ...
5
votes
1answer
103 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
2answers
77 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 ...
6
votes
3answers
390 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 ...
1
vote
2answers
170 views

Filling Rows of a Matrix Subject to Conditions

I'm seeking to write an algorithm which, given a value of N, will fill a matrix consisting of (N+1)(N+2)(N+3)/6 rows and 4 columns with the integers from 0, ... , N, subject to the conditions that: ...
10
votes
3answers
123 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 ...
3
votes
2answers
219 views

How should I store and sort a large number of 64-bit integers?

I have about 500,000,000 64-bit integers, so these numbers could be very large. I want to sort them as quickly as possible. I have a couple of questions: What data structure do you suggest for ...
4
votes
2answers
64 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 \}$. ...
0
votes
1answer
364 views

Algorithm to determine if a number is perfect on a Turing Machine

I've been trying for a while now to find a solution for the problem in the title: determining if a number is perfect using a Turing Machine. I only had one class on the TM and while I did "get" how it ...
1
vote
3answers
724 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
0
votes
1answer
19 views

VAR autoincrement with constant space consumption for super large tables

Assume there was a database system that had a data type called VARINT or some variant that allowed instead of fixed-length INTs ...
4
votes
1answer
496 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\}$ ...
2
votes
1answer
106 views

Solve Integer Factoring in randomized polynomial time with an oracle for square root modulo $n$

I'm trying to solve exercise 6.5 on page 309 from Richard Crandall's "Prime numbers - A computational perspective". It basically asks for an algorithm to factor integers in randomized polynomial time ...
0
votes
3answers
123 views

How to guess the value of $j$ at the end of the loop?

for ( i = n , j = 0 ; i > 0 ; i = i / 2 , j = j + i ) ; All variables are integers.(i.e. if decimal values occur, consider their floor value) Let ...
1
vote
1answer
233 views

Shifting subset sum solution by constant positive integer

While reading the Wikipedia article about the subset sum problem I came across this example: "is there a non-empty subset whose sum is zero? For example, given the set $\{ −7, −3, −2, 5, 8 \}$, the ...
6
votes
3answers
453 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 ...
2
votes
1answer
173 views

Calculate storage requirements for a data set

I have a simple problem. I can't seem to even find the right search terms to get me pointed in the direction I need to be heading. I'm writing a bunch of integers to disk. Lot's of them. Starting ...
5
votes
2answers
98 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" ...
4
votes
1answer
589 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, ...
3
votes
4answers
378 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 ...
5
votes
3answers
436 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 ...
3
votes
1answer
199 views

How to compute linear recurrence using matrix with fraction coefficients?

What I'm trying to do is generate Motzkin numbers mod a large number $10^{14} + 7$ (not prime), and it needs to compute the $n$th Motzkin number as fast as possible. From Wikipedia, the formula for ...
2
votes
1answer
74 views

Run time of product of polynomially bounded numbers

Let $M$ denote a set of $n$ positive integers, each less than $n^c$. What is the runtime of computing $\prod_{m \in M} m$ with a deterministic Turing machine?
8
votes
2answers
206 views

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

What is the complexity of computing $n^{n^2},\;n \in \mathbb{N}$?
7
votes
2answers
1k 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 ...
2
votes
2answers
715 views

Partition of a set of integer into 3 subsets of approximately equal sum

I'm having a very hard time trying to figure out how to solve this problem efficiently. Let me describe how it goes: "A hard working mom bought several fruits with different nutritional values for ...
10
votes
4answers
945 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 ...
5
votes
3answers
336 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 ...
6
votes
3answers
408 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 ...
7
votes
2answers
899 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?
10
votes
3answers
591 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 ...
1
vote
2answers
145 views

From FACTOR To KNAPSACK

If there were an algorithm that factored in polynomial time by means of examining each possible factor of a complex number efficiently, could one not also use this algorithm to solve unbounded ...
11
votes
1answer
2k 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: ...
7
votes
2answers
202 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 ...
10
votes
1answer
171 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$. ...
3
votes
3answers
158 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$ ...
7
votes
5answers
522 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 multiples of $a$ plus a ...