Questions tagged [integers]

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

Filter by
Sorted by
Tagged with
-2 votes
2 answers
50 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.
1 vote
1 answer
51 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 ...
1 vote
0 answers
34 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 ...
-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 ...
-2 votes
1 answer
48 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 ...
2 votes
0 answers
55 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 ...
1 vote
3 answers
518 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 ...
2 votes
1 answer
88 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 ...
-1 votes
1 answer
59 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
24 views

Why doesn't Karatsuba multiplication break numbers into word size blocks?

So under the WORD RAM model of computation, the word size w is at least log of the input size and arithmetic operations on words take constant time. So rather than dividing an n bit number into bits, ...
  • 83
0 votes
0 answers
37 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
103 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 ...
0 votes
1 answer
34 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
36 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 ...
0 votes
1 answer
103 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$ ...
2 votes
2 answers
75 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
46 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\...
0 votes
1 answer
361 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
719 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
64 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 ...
  • 205
0 votes
0 answers
22 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
146 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 ...
  • 683
4 votes
1 answer
116 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
0 answers
29 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
31 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
285 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
1 answer
425 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
1 answer
44 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
184 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
378 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 ...
2 votes
1 answer
28 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 \...
  • 209
2 votes
1 answer
949 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
28 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,351
3 votes
0 answers
45 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
1 answer
30 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 ...
1 vote
1 answer
53 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,592
4 votes
1 answer
114 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 ...
  • 155
2 votes
2 answers
873 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}$ ...
1 vote
0 answers
21 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. ...
  • 352
1 vote
0 answers
52 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
0 answers
386 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
36 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
68 views

Why are floats converted from different integers sometimes equal?

I'm trying to understand the following algorithm: ...
2 votes
2 answers
3k 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,891
0 votes
0 answers
108 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
1 answer
404 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) ...
  • 265