# Questions tagged [integers]

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

137 questions
Filter by
Sorted by
Tagged with
537 views

418 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 ...
29 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 ...
383 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? ...
131 views

### Sum to a certain value of a group of integers

Take a group filled with an arbitrary number of random integers. Is there any way of finding out whether it is possible for the sum of the integers can equal a certain number, with the condition that ...
108 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$ ...
701 views

### Counting an integer's divisors without just enumerating them (or estimating if not possible)?

I'm trying to count the number of divisors an integer $n$ has. The simple way to do this is to just enumerate all integers from 1 to $\sqrt{n}$, and count how many integers evenly divide $n$. For ...
186 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$ ...
1k views

53 views

### "Most Similar Vector Problem" on an Integer Lattice

I am currently working on problem that I think could be expressed as an integer lattice problem, and hoping to find some guidance on this forum. Given $u \in \mathbb{R}^n$ and a bounded integer ...
31 views

### Complexity of finding these original parameters

I am given (or rather, generate randomly) three positive integers $a, b, c$. I want to know if there exist integers $m \ge 2, s \ge 1$ such that $ms+m = a, ms+1 = b, 2s+1 = c$. If there are multiple ...
369 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 ...
1k 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, ...
2k 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$ ...
286 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 ...
479 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 ...
67 views

### Integer factorization: comparing with floor

While working on integer factorization algorithm I came to the next problem: $$\frac{a}{ex} = \lfloor{\frac{a}{ex}\rfloor} + c$$ $a$ the number I want to factor $x$ factor of $a$ $e$ positive ...
89 views

### Rounding errors when converting floats to integers

Is it possible to have a rounding error when you convert a floating point number which can only be in increments of 0.01 to an integer by multiplying by 100 first? I would think that the lack of ...