# Questions tagged [integers]

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

121 questions
Filter by
Sorted by
Tagged with
902 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 ...
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" ...
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, ...
682 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 ...
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 ...
257 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 ...
83 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?
233 views

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

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