# Questions tagged [integers]

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

128 questions
Filter by
Sorted by
Tagged with
578 views

### Algorithm for implementing the modulus “%” operator?

How can an efficient modulus operator be implemented? Here's a naive way of defining A % B: given $(a,b) \in \mathbb{Z}$ (represented as ...
68 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). ...
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 ...
23 views

### Maximizing integer sets intersection (with integer delta)

There are two sets of integers with different numbers of items in them. ...
56 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: ...
41 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].
37 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 ...
99 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 ...
46 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 ...
293 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 ...
442 views

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 ...
89 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 ...
15 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 ...
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 + ...
24 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 ...
444 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 ...
29 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, ...
3k views

### Complexity of Integer Division

My favourite algorithm textbook: The Algorithm Design Manual S. Skiena.pdf had this interesting problem: 1-28.  Write a function to perform integer division without using either the / or * ...
71 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 ...
404 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}$ ...
3k 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 ...
23 views

### Merge Sort meaning of a bit part of code

I am studying this part for a merge sort implementation: ...
12 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. ...
37 views

53 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 ...
80 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 ...
63 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 ...
92 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 ...
3k 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 ...
221 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) ...
86 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 ...
95 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 ...
952 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 ...
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 ...