Questions tagged [integers]
Questions about properties of, working with and algorithms on integers.
167
questions
3
votes
0
answers
52
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
498
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 ...
- 3,088
2
votes
1
answer
799
views
4-partition elements summation NP completeness
How can we prove that the following problem $A$ is NP complete?
Given a set of integers $S={a_1, ..., a_n}$ and a number $D$, is it possible to find disjoint sets $S_1, S_2, S_3, S_4$ such that $S_1 \...
CommunityBot
- 1
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 ...
- 11
2
votes
1
answer
36
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
2k
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 ...
- 29.5k
1
vote
0
answers
57
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,401
4
votes
0
answers
144
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 + ...
- 283
0
votes
1
answer
47
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 ...
- 30k
3
votes
1
answer
884
views
How to read off the set represented by a van-Emde-Boas tree?
I'm reviewing my background in Algorithms and DS design. Specifically I never went through the van Emde Boas Tree. Though I can undestand the proto-vEB with related picture. I'm struggling to ...
- 39k
1
vote
1
answer
71
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, ...
- 7,138
4
votes
1
answer
129
views
Reversible Merge of Integer Hash Values
Context:
I am working with a tree-like data structure. I would like every node in the tree to have an integer hash value that is the result of combining the integer hash values for the node's ...
D.W.♦
- 159k
2
votes
2
answers
1k
views
Efficient data structure for storing integers in a range?
Say I'm constantly given integers from the range $[1,2^{32}]$ in a random order and have to store these so that when a duplicate arrives I can deal with it. By the end of this algorithm all $2^{32}$ ...
- 170
2
votes
2
answers
4k
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 ...
- 39k
0
votes
1
answer
26
views
Merge Sort meaning of a bit part of code
I am studying this part for a merge sort implementation:
...
CommunityBot
- 1
1
vote
0
answers
23
views
Structure of numbers in descriptive complexity
Descriptive complexity is a useful way to free yourself from computational considerations when studying complexity. One of those considerations is the encoding of the structures you are working on.
...
- 362
1
vote
0
answers
53
views
Partitioning the columns of a matrix
I thought about this problem for a while now and am not able to find a solution for it, be it a direct algorithm or a reduction to a known problem, so I'm asking here:
Suppose you have a matrix $A\in\...
- 131
1
vote
0
answers
462
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:
...
- 111
2
votes
0
answers
40
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 ...
- 217
0
votes
1
answer
72
views
Why are floats converted from different integers sometimes equal?
I'm trying to understand the following algorithm:
...
D.W.♦
- 159k
0
votes
0
answers
200
views
Using half float to represent scaled short (int16), do I lose precision comparing to using double?
A device is generating 14-bit integer which is stored as int16 (short), a scaling process will then scale the data to value of order 10E-3.
Does it then matter if I store these number with half float ...
- 1
5
votes
2
answers
2k
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, ...
- 30k
5
votes
1
answer
561
views
Given a RxC grid, how to generate N 2D points randomly such that no 3 points are collinear?
Context, I have a geometric algorithm that is sensitive to collinear points and receives as input a list of points in 2D generated randomly. Suppose that I have a Boolean function nonCollinear(x,y,z) ...
- 111
2
votes
3
answers
1k
views
Computing a histogram with the number of extant values not known in advance
(This may be more fitting for CSTheory, I'm not sure.)
I'm looking for an practical or theoretical work (that is, academic papers, online jots, pseudocode or code) regarding efficient algorithms for ...
- 965
21
votes
3
answers
12k
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:
...
- 30k
2
votes
1
answer
1k
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 ...
- 1
8
votes
2
answers
1k
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 ...
0
votes
1
answer
2k
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
3
votes
0
answers
67
views
Sets whose decimal expansions form a regular language
Write $\bar n$ for the decimal expansion of $n$ (with no leading 0). For a set $S$ of natural numbers, let its set of expansions (in base 10) be $\bar S = \{\bar n \...
0
votes
0
answers
67
views
Improving an integer factoring algorithm
I've written an algorithm for integer factorization (specifically RSA-like coprimes - products of two large primes, roughly of the same number of decimal digits) which is not based on QS, GNFS or any ...
- 105
3
votes
0
answers
120
views
Given two arrays of length n and n - 1, order the first array such that no partial sum is in the second array
Two arrays of natural numbers are given of length $n$ and $n - 1$:
e.g.
$A: [a_0, a_1,..., a_{n-1}, a_n]$
$B: [b_0, b_1, ..., b_{n-2}, b_{n-1}]$
All elements of $A$ are unique (can be in $B$), all ...
- 39
2
votes
2
answers
116
views
Find all pairs (i, j), such that i + (i+1) + (i+2) + ... + j = n
We have give positive integer $n$, and we want to find all the pairs $(i, j), i\leq j$ such that: $$i + (i+1) +(i+2)+(i+3)+ \dots + j = n$$
Clearly we can try all possible pairs in $O(N^2)$, but that ...
D.W.♦
- 159k
0
votes
1
answer
143
views
Mistake in the Algorithm Design Manual?
Look at this excerpt from the Algorithm Design Manual by Skiena, 2nd Edition
The sum of the first $n$ even integers? Surely, the two sums given do not include only even numbers, right? Is this a ...
- 156
17
votes
3
answers
4k
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 ...
- 101
3
votes
1
answer
442
views
Linear time multiplication on RAM machine?
This page says following:
Integer Multiplication has an O-optimal linear-time algorithm on a RAM or SMM
Is this page fooling me or how can we multiply 2 numbers in linear time (bitwise complexity) ...
- 4,511
1
vote
1
answer
225
views
Compress 32 bit integer into a normalized float
and sorry if this is a duplicate of some sort, my poor technical vocabulary doesn't get me very far with google.
I am trying to implement some well-known PRNG algorithms. For the time, the algorithm ...
- 277k
3
votes
2
answers
101
views
How to find the closest N to the power of X to the given number?
Let's say we have number 4920 and we want to find the closest $n^x$ to 4920
2 ^ 12 = 4096 but it's not the closest possible $n^x$, for example 17 ^ 3 = 4913 is closer to 4920
The question is, how do ...
- 277k
3
votes
1
answer
1k
views
How can repeated addition/multiplication be done in polynomial time?
I can see how adding 2 unsigned $n$-bit values is $O(n)$. We just go from the rightmost digits to the leftmost digits and add the digits up sequentially. We can also perform multiplication in ...
- 916
2
votes
1
answer
104
views
Swap elements using integer addition and multiplication gates
I need to swap two integers using only integer addition and multiplication gates.
I can't subtract them. I'm dealing with a sorting network, so I need to compare and swap. The compare and swap ...
- 13.4k
1
vote
1
answer
132
views
Gray-like code with maximum value <= maximum value of original symbol
I want to iterate through the numbers $0,1,2,\dots,n-1$ in some order, where each number in the sequence differs by only one bit from the previous bit. I'm going to be using each number as an index ...
D.W.♦
- 159k
3
votes
0
answers
101
views
Low-level division operator implementation
A few weeks ago, I asked this question on the implementation of the shift operator for an architecture that implements boxing. Reviewing my implementation I found out that the division operator wasn't ...
CommunityBot
- 1
3
votes
1
answer
74
views
Low-level shift operator implementation
I want a shift operator for an architecture that implements boxing. Basically, the high-level constructs represent integers as 31 bits followed by 1 bit set to one as a tag (so to represent binary int ...
- 2,194
5
votes
0
answers
554
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 ...
CommunityBot
- 1
2
votes
1
answer
184
views
How to uniquely encode a vector of non-increasing positive integers
Given a vector of positive integers $A=[a_1, \cdots, a_n]$, where $\sum_{1 \leq i \leq n}a_i = n(n-1)$ and $a_i \geq a_j$ iff $i \geq j$, I am interested in encoding the vector, maintaining the ...
CommunityBot
- 1
1
vote
1
answer
152
views
How to determine the carry vector of an integer addition
An integer addition can be represented as following:
$A + B = A \oplus B \oplus carry_{vector}$
My question is how to determine the carry vector from $A$ and $B$ (not from the result)?
- 741
5
votes
0
answers
94
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 ...
- 4,536
1
vote
1
answer
687
views
There are n numbers. Find the maximal set of pairwise NON coprime numbers
I have to take input in an array(no. of elements in array <=10^5).
For ex:- Let the array be {2,3,4,16,9,45,81,27}
Now I need to find the order of the maximal set such that any pair of elements in ...
- 72.4k
2
votes
4
answers
836
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 ...
CommunityBot
- 1
3
votes
1
answer
375
views
Complexity class of integer factorization
Is integer factorization confirmed to be an NP-complete problem? If not, then if one could transform IF into an equivalent problem which is already proved to be NP-complete, would it mean that IF is ...
- 277k
5
votes
1
answer
230
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$ ...
- 72.4k