Questions tagged [integers]
Questions about properties of, working with and algorithms on integers.
161
questions
6
votes
2
answers
3k
views
Is there an efficient algorithm to find whether an integer is a prime power?
There's a sentence in the current version of the Wikipedia page for Shor's algorithm which states: we can use efficient classical algorithms to check if $N$ is a prime power. No reference is provided ...
- 286
5
votes
5
answers
968
views
Prove HAKMEM Item 23: connection between arithmetic operations and bitwise operations on integers
Prove that for $A, B \in \mathbb{Z}$, $A + B = (A \operatorname{\&} B) + (A \mid B) = (A \oplus B) + 2(A \operatorname{\&} B)$ where $\&$ is bitwise AND, $|$ is bitwise OR and $\oplus$ is ...
- 161
1
vote
2
answers
112
views
Sampling from bins with ratio preservation
I have sequence of integers $a_1, a_2, .., a_n$,
let $S_a = \sum_{i=1}^{N}{a_i}$,
for any $k \in (0; 1)$ I need an algorthim to that maps every $a_i$ into another integer $b_i$ with 2 requirements:
$...
- 287
7
votes
1
answer
579
views
Correctness of FIPS 186-4 square test algorithm
Federal Information Processing Standard 186-4 appendix C.4 gives (without reference) an algorithm intended to test if a positive integer $C$ (which can be thousands bits) is a square:
Set $n$, such ...
- 519
0
votes
2
answers
138
views
Can you help me in finding an algorithm that finds the first unique number in an array with lowest position?
I have the following problem to solve:
Given a non-empty array A consisting of N integers, the task is to find the first unique number in the array. A unique number is defined as a number that occurs ...
0
votes
2
answers
188
views
Finding the time complexity of a prime factorization algorithm
In this question, I'm going to introduce a prime factorization algorithm which I'm working on as my personal project.
I may attach a Python code to introduce the algorithm. If it contravenes the rule ...
- 11
0
votes
1
answer
46
views
Math symbol to represent an operator to convert from double-precision to 32-bit integer value?
I'm looking for a good mathematical symbol to represent the conversion from a double-precision floating value to an unsigned 32-bit integer value. Does anyone have suggestions for a good Greek letter ...
- 13
5
votes
3
answers
530
views
Multiplying 2 positive integers using FFT and convolutions
I was trying to figure out how I can perform multiplication of 2 big integers using FFT and convolutions, I ran into the following article:
http://numbers.computation.free.fr/Constants/Algorithms/fft....
- 229
1
vote
1
answer
39
views
Is there a sub-NP algorithm to satisfy or prove unsatisfiable a set of a<b<c OR c<b<a constraints
This problem's been stumping me for the better part of a week:
You're given a set of triplets of variables. The variables are all distinct and ordered. Each triplet $a,b,c$ means that either $a<b&...
- 290
0
votes
1
answer
81
views
Complexity of multiplication when computing product of $m$ integers
I designed an algorithm where, at some point, I need to compute the product of a list of integers $n_1,\dots,n_m$ (possibly, there are repetitions in the list). The integers themselves do not depend ...
0
votes
0
answers
83
views
Using Hashing to count the number of occurrences of a pattern within an integer array
So I have a problem that is ,I have an integer array and first I define an interval as a good interval iff, within the interval every integer appears an even (including zero) number of times. I want ...
-2
votes
2
answers
73
views
How to check if an positive integer can be represented as a sum of integers
How to determine if an integer x > 0 can be represented as 20n + 50m + 100k, where n,m,k >= 0 and are integers.
- 3
1
vote
1
answer
640
views
time complexity to convert string to integer and vice a versa
just given solution on this post
i had mention the time complexity to convert string to int is O(n), also verifying this post
now in one of comment fellow SO user, corrected me with example also ...
- 111
2
votes
0
answers
40
views
Efficient algorithm to "lift" a number in CRT representation mod r to mod $r^2$
Integers between 0 and a square-free number $r$ minus one can be represented by their value modulo each of $r$'s prime factors, according the Chinese remainder theorem.
Given a number represented like ...
- 469
-2
votes
2
answers
63
views
Java | If a=250, b=3, c=(a + b/2)/b * b, Why doesn't c equal 251 but rather 249?
If
int a = 250;
int b = 3;
int c = (a + b/2)/b * b;
Why doesn't c equal 251, but rather 249?
How is it that ...
- 109
-2
votes
1
answer
51
views
Approximate x*(a/b)^(c/d) using integer arithmetic only (assembler)
0 < x,a,b,c,d < M are all positive integers (uint64).
also, a<b if that helps.
we have assembler (integer only) operations available (e.g. division only yields integers).
we want to ...
- 101
2
votes
0
answers
85
views
$y$-Fast Tries: Why not partition into groups of $\Theta(\log^2 M)$ elements?
The $y$-fast trie is a data structure for storing a sorted collection of $n$ integers from the range $[0, M)$. It builds on the $x$-fast trie, which also stores elements in this range.
The space usage ...
- 9,027
2
votes
3
answers
989
views
Batch rounding with preservation of a sum
I have a sequence of floating point numbers. I want to map each of them to one of their closest integers. There is one rule:
Sum of integers must be as close to the sum of original numbers as possible ...
- 287
2
votes
1
answer
138
views
Prove a greedy algorithm that obtains the minimum integer with at most k adjacent swaps is correct
This problem is from LeetCode.
You're given a string num representing the digits of a very large integer and an integer k. You are allowed to swap any two adjacent digits of the integer at most k ...
- 207
-1
votes
1
answer
89
views
Integer decomposition algorithm
Suppose I have a 32-bit integer $x$, I want to find $\{ x_i \}_{i \in 1\dots\ell}$ such that
$x = e + \sum_{i=1}^\ell x_i \cdot 2^{32 - B\cdot i}$
where the error $e$ is as small as possible. The ...
- 107
0
votes
0
answers
49
views
What is the size of the largest numbers (integers) that current supercomputers can handle?
I am interested in designing number theory experiments and interested in knowing current capabilities of supercomputers to handle extremely large numbers. I'm interested in learning the size of the ...
1
vote
1
answer
53
views
Efficient comparison, using only sum, product, difference, and conditional jump if zero
I was wondering how small we could make the instruction set of a typical machine that supports a single datatype: arbitrary integers. If you need a heap, you declare an integer variable $h$ where you ...
1
vote
0
answers
200
views
Can Radix Sort be modified for signed ints and/or floats?
A few months ago I learned about the magic that allows radix sort to run in O(n) time and space. Most tutorials on radix sort say it is useful for very large ...
- 111
0
votes
1
answer
41
views
Integer-only computation rounds down fractions in division require extra work?
In integer-only computation, a fraction like 5/2 is rounded down to 2. Is this any extra work at the ALU level, or, is the way it does division, at the level of logical gates, automatically outputting ...
- 1
1
vote
1
answer
46
views
What does it mean for an integer to belong to the halting problem?
I have come across the description of a function $F: \mathbb{N} \to \mathbb{N}$ where the function is defined one way for $n \in \mathcal{H}$ and another way for $n \notin \mathcal{H}.$ In this ...
- 13
0
votes
1
answer
242
views
How to represent $x$ in hexadecimal form where $x=2^n$?
When a value $x$ is a power of $2$, that is, $x = 2^n$ for some nonnegative integer
n, we can readily write $x$ in hexadecimal form by remembering that the binary
representation of $x$ is simply $1$ ...
- 149
2
votes
2
answers
102
views
Efficient Algorithm to Find the Closest Integer Representation, in the Form $A\times\frac{N}{D}$ for a Value
The Problem
I am working on a problem that boils down to finding the closest representation of an arbitrary number ($x$) in the form:
$$x = A\times\frac{N}{D}$$
Where $A$ is a 32-bit integer, and $N$ ...
- 123
1
vote
1
answer
47
views
How to rewrite a function such that integer division is applied before multiplication
Given the following function
$$
f(x,y) = (x \cdot y + 999)\; \text{div} \; 1000
$$
where $x \in \{0, 1, 2, \dots, 2^{63}-1\}$, $y \in \{1, 2, 3, \dots, 500\}$, and the div operator is defined to round ...
- 165
0
votes
0
answers
45
views
Given $n$ sets of matrices, find $n$ matrices that have the least number of LCDs among their entries
Let's say I have $n$ sets of matrices
$$
A = \left\{\begin{pmatrix}
2 & 4 & 17\\
5 & 6 & 9\\
\end{pmatrix}
\begin{pmatrix}
2 & 4 & 18\\
5 & 6 & 9\\
\end{pmatrix}
\right\...
- 101
0
votes
1
answer
836
views
while loop for bitwise conversion program
int counter(char c){
int count = 0;
while (c!=0){
if((c & 1) !=0)
count++;
c = c >> 1;
}
}
I am trying to understand a ...
- 167
2
votes
1
answer
866
views
For two large (10^6) integers A and B, find the number of set bits in the result of their multiplication
I've recently stumbled upon a problem that I struggle realy hard with ever since.
There are two large decimal integers, order of magnitude $10^6$. The task is to find how many bits in the binary ...
- 21
0
votes
0
answers
66
views
Efficient triangular decomposition of an integer
Euclidean division is an iterative process
that has been made super-efficient at the CPU level, right?
Its specification is that if I do (q, r) = f(n, d), I get ...
- 195
0
votes
0
answers
38
views
What is the currently know fastest algorithms to convert each individual Java primitive and Number types to a Char Array/String
What is the currently know fastest algorithms to convert each individual Java primitive and Number types to a Char Array/String number representation while ...
0
votes
2
answers
192
views
How would it be possible that primality testing is in P, but not factorization?
Suppose that P != NP. Then there exists 3SAT formulas such that their satisfiability is computationally "evil" (i.e, the satisfiability can be exponentially hard to determine in the size of ...
user102180
4
votes
1
answer
127
views
Do there exist fast multiplication algorithms for two integers with one of them being static?
Let N and M be arbitrary 1024+ bit integers.
The objective is to compute the product of N and M (2048+ bits)
There exist various multiplication algorithms for various bit lengths (ex library: GMP). ...
- 41
0
votes
0
answers
30
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 ...
- 101
2
votes
1
answer
34
views
Maximizing integer sets intersection (with integer delta)
There are two sets of integers with different numbers of items in them.
...
- 123
1
vote
1
answer
368
views
Overlapping between two intervals: reasoning / algorithm to find the set of disjoint and overlapping intervals
Consider the positive integers {1, 2, 3, 4, ...} and the corresponding Integer Number Line.
Suppose we have four integer numbers, A, B, C and D.
For example:
...
- 13
0
votes
1
answer
651
views
pseudocode to split number value to array of numbers
How to write a pseudocode to split a number value to array of numbers? Let's say the number value is 12345. I need to convert it into [1,2,3,4,5].
- 103
0
votes
1
answer
48
views
What computational model supports arbitrarily sized integers?
I want to do some research, but I don't think it's important the number of bits it takes to represent the integer input and arithmetic on the abstract machine. So what is the model that addresses ...
-2
votes
1
answer
290
views
Algorithm for smallest number in array larger than threshold
We define the problem SmallestAbove as follows:
Given an array $A$ of $n$ integers and a value $v$, compute the smallest value in $A$ that is strictly greater than $v$. Return $\infty$ if no such ...
3
votes
0
answers
50
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 ...
- 156
9
votes
3
answers
477
views
Test if there exists an integer k to add to one sequence to make it a subsequence of another sequence
Suppose that sequence $A$ contains $n$ integers $a_1,a_2,a_3,\ldots,a_n$ and sequence $B$ contains $m$ integers $b_1,b_2,b_3,\ldots,b_m$. We know that $m \geq n$. We assume without loss of generality ...
- 61
7
votes
3
answers
2k
views
Space complexity for storing integers in Python
So I was watching this mock interview by an Airbnb engineer on interviewing.io (https://youtu.be/cdCeU8DJvPM?t=1224) and around ~20:11 seconds he raises an interesting point.
The question that the ...
- 295
2
votes
1
answer
31
views
Names of power-of-two bit operations on bitsets that would not assume any number interpretation
Three commonly used functions when it comes to bit manipulation are :
is_pow2: Checking that an integer is a power-of-two (only one bit is set): $00010000 \...
- 221
2
votes
1
answer
1k
views
Find the sum of numbers from an array closest to a number, where repetition of the numbers are allowed
I would like to find the sum of values from a given number array, where the repetition of numbers are allowed, closest to a target but the sum cannot exceed the target. If there are more solution, I'd ...
1
vote
0
answers
49
views
Does integer matrix multiplication with its transpose (A^T)*A have more efficient parallel algorithm than the use of symmetricity?
Integer matrix multiplication with its transpose (A^T)A gives symmetric matrix, so, only one half of it should be computed. Besides, the formula for the resulting element rik=Sum[aijajk, j] reduces to ...
- 1,381
4
votes
0
answers
92
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 + ...
- 273
0
votes
1
answer
32
views
For signed integers, why don't representative the smallest number as all zeros in binary, and the largest as all ones?
I'm reading up on bitwise operators, complements, and two's complements, and I'm wondering why the lower limit of a range (aka lowest negative number) isn't all zeroes in binary, and the upper limit ...
- 103
1
vote
1
answer
61
views
What is the equivalent of the integers symbol Z for n bit only integers?
We refer to the set of all integers as $\mathbb{Z}$. Now suppose we have a set of integers that can be held within a computer variable of $n$ bits width. Clearly they can only be of $2^{n}$ range, ...
- 1,602