Questions tagged [integers]

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

Filter by
Sorted by
Tagged with
3 votes
3 answers
515 views

Probability of overflow in a summation of fixed-size signed integers

How can I estimate the probability that the sum $S_n$ of $n$ uniform random 48-bit signed integers overflows a 64-bit signed integer? Edit: the overflow can occur at any step, not only on the final ...
Aristide's user avatar
  • 323
1 vote
2 answers
131 views

Fast string-to-integer algorithm

I work with big integers that I need to convert to and from strings, and to and from different bases. In JavaScript, BigInt allows to convert an integer to a string in a chosen base by doing: ...
Zwyx's user avatar
  • 123
0 votes
0 answers
21 views

better ways to integer interpolation?

I made some code about "integer interpolation" for running approximate alpha blending at FPGA which have low quantities of logic gate. Let's refer to "II" as integer interpolation. ...
박성재's user avatar
0 votes
1 answer
41 views

What is the purpose of padding bits in primitive integer types?

The C standard carves out room for implementations which have padding bits in their integer types. Padding bits affect the size of an integer but not the number of possible values they can contain. I ...
user16217248's user avatar
2 votes
0 answers
127 views

Optimal reassociations is NP-hard?

Consider signed integers with common addition and multiplication. Reassociation of expression is another equivalent form. Say expressions: ...
Konstantin Vladimirov's user avatar
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 ...
glS's user avatar
  • 286
5 votes
5 answers
981 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 ...
Ntwali B.'s user avatar
  • 161
1 vote
2 answers
114 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: $...
Andrey Godyaev's user avatar
7 votes
1 answer
581 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 ...
fgrieu's user avatar
  • 519
0 votes
2 answers
148 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 ...
Ardita Morina's user avatar
0 votes
2 answers
213 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 ...
MYUN's user avatar
  • 11
0 votes
1 answer
50 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 ...
Ogiad's user avatar
  • 13
5 votes
3 answers
800 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....
Yarin's user avatar
  • 275
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&...
Exalted Toast's user avatar
0 votes
1 answer
93 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 ...
Florian Ingels's user avatar
0 votes
0 answers
96 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 ...
ISeekTheWisdom's user avatar
-2 votes
2 answers
81 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.
beartee's user avatar
1 vote
1 answer
874 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 ...
sahasrara62's user avatar
2 votes
0 answers
42 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 ...
Command Master's user avatar
-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 ...
Coo's user avatar
  • 109
-2 votes
1 answer
54 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 ...
imi kim's user avatar
  • 101
2 votes
0 answers
107 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 ...
templatetypedef's user avatar
3 votes
4 answers
1k 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 ...
Andrey Godyaev's user avatar
2 votes
1 answer
153 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 ...
user3472's user avatar
  • 207
-1 votes
1 answer
92 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 ...
lamba's user avatar
  • 107
0 votes
0 answers
58 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 ...
Mashup Transmitter's user avatar
1 vote
1 answer
55 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 ...
Daniel Donnelly's user avatar
1 vote
0 answers
294 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 ...
Adam Hoelscher's user avatar
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 ...
Johan's user avatar
  • 1
1 vote
1 answer
67 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 ...
Altitude5's user avatar
0 votes
1 answer
341 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$ ...
user8314628's user avatar
2 votes
2 answers
123 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$ ...
Mark Omo's user avatar
  • 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 ...
Alex R's user avatar
  • 165
0 votes
0 answers
46 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\...
Davide Valdo's user avatar
0 votes
1 answer
955 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 ...
x89's user avatar
  • 167
2 votes
1 answer
880 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 ...
PineLel's user avatar
  • 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 ...
iago-lito's user avatar
  • 195
0 votes
0 answers
43 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 ...
Suminda Sirinath S. Dharmasena's user avatar
0 votes
2 answers
201 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 ...
user avatar
4 votes
1 answer
133 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). ...
John Flemin's user avatar
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 ...
Naghi's user avatar
  • 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. ...
lazyden's user avatar
  • 123
1 vote
1 answer
396 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: ...
strajano's user avatar
0 votes
1 answer
741 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].
camille's user avatar
  • 103
0 votes
1 answer
52 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 ...
Daniel Donnelly's user avatar
-2 votes
1 answer
342 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 ...
Cassandra's user avatar
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 ...
lsparki's user avatar
  • 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 ...
iouvxz's user avatar
  • 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 ...
Sidharth Samant's user avatar
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 \...
Vincent's user avatar
  • 221