# Questions tagged [integers]

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

20 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
83 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 ...
523 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 ...
45 views

### Quick calculation for $x^y \bmod 2^d$

I need to calculate $x^y \bmod 2^d$ in $O(d)$ summations/bitwise operations and $1$ multiplication by $y$. $x$ is restricted to be odd, $d\geq 3$. $a$-bit arithmetic (for any $a$) is allowed, as this ...
43 views

23 views

### String to small integer mapping without collision

Is there any good approach to devise a mapping of limited number of strings $N_1 << 2^{15}$ to integers less than $2^{15}$ without conflicts? Strings are quite often of the form of prefix + ...
22 views

### Is finding a sum of two squares representation for a number computationally assymptotically equivalent to integer factorization?

I have been wondering this question because given a number $n$ with prime factors of the form $4k+3$ when we square $n$ and find a sum of two squares which should reveal these types of factors (as ...
52 views

### Are there any practical drop-in replacements for BSTs in the case where data are integers?

There are a number of specialized data structures that implement ordered dictionaries for integer keys: van Emde Boas trees, y-Fast tries, fusion trees, etc. Each of these data structures implement ...
510 views

180 views

### How does prefix summing the count histogram in counting sort result in an array of output indices?

My implementation of counting sort is based on the description I found here. I've also included my code in this REPL, but here it is: ...
27 views

### How computer understand to either represent the original bits or two's complement as value?

Important note I know that this question may seem too simple for you scientists; however, here is the best place that I know to post it. Question Suppose we have an ...
22 views

### Quantization in deep neural networks

I am following this tutorial about quantization in tensorflow. tutorial 1 tutorial 2 Tutorial 1, describes the quantization formula as: My question is, if you have 3 floating point values ...