Questions tagged [integers]

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

Filter by
Sorted by
Tagged with
2
votes
2answers
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 ...
1
vote
1answer
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). ...
0
votes
0answers
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 ...
2
votes
1answer
23 views

Maximizing integer sets intersection (with integer delta)

There are two sets of integers with different numbers of items in them. ...
1
vote
1answer
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: ...
0
votes
1answer
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].
0
votes
1answer
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 ...
-2
votes
1answer
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 ...
3
votes
0answers
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 ...
9
votes
3answers
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 ...
2
votes
1answer
442 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 \...
6
votes
3answers
1k 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 ...
1
vote
1answer
22 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 \...
0
votes
0answers
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 ...
2
votes
1answer
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 ...
1
vote
0answers
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 ...
2
votes
0answers
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 + ...
0
votes
1answer
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 ...
2
votes
1answer
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 ...
1
vote
1answer
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, ...
2
votes
1answer
3k views

Complexity of Integer Division

My favourite algorithm textbook: The Algorithm Design Manual S. Skiena.pdf had this interesting problem: 1-28. [5] Write a function to perform integer division without using either the / or * ...
4
votes
1answer
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 ...
2
votes
2answers
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}$ ...
2
votes
2answers
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 ...
0
votes
1answer
23 views

Merge Sort meaning of a bit part of code

I am studying this part for a merge sort implementation: ...
1
vote
0answers
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. ...
1
vote
0answers
37 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\...
1
vote
0answers
182 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: ...
2
votes
0answers
23 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 ...
0
votes
1answer
57 views

Why are floats converted from different integers sometimes equal?

I'm trying to understand the following algorithm: ...
0
votes
0answers
53 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 ...
5
votes
2answers
1k 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, ...
4
votes
1answer
147 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) ...
2
votes
3answers
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 ...
20
votes
3answers
10k 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: ...
2
votes
1answer
988 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 ...
8
votes
2answers
942 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
1answer
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 ...
3
votes
0answers
43 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
0answers
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 ...
3
votes
0answers
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 ...
1
vote
2answers
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 ...
0
votes
1answer
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 ...
14
votes
3answers
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 ...
3
votes
1answer
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) ...
1
vote
1answer
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 ...
3
votes
2answers
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 ...
3
votes
1answer
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 ...
2
votes
1answer
74 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 ...
1
vote
1answer
29 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 ...