Questions about properties of, working with and algorithms on integers.
0
votes
1answer
44 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
104 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
12 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
108 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\}$ ...
1
vote
1answer
51 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
114 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 ...
0
votes
1answer
87 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 ...
5
votes
3answers
283 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
131 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 ...
4
votes
1answer
257 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
157 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
271 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
149 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
70 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
196 views
5
votes
2answers
363 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
323 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 ...
8
votes
4answers
656 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
229 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 ...
5
votes
3answers
304 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 ...
6
votes
2answers
429 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
408 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
120 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
822 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
1answer
147 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
144 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
148 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
355 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 ...
