# Questions tagged [integers]

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

151 questions
Filter by
Sorted by
Tagged with
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
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 ...
• 111
1 vote
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 ...
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 ...
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 ...
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 ...
• 8,947
1 vote
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 ...
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 ...
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
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
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
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
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 ...
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 vote
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 ...
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$ ...
• 149
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
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
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\...
• 101
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
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
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
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 ...
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
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). ...
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
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
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: ...
• 13
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].
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 ...
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 ...
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
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
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 ...
28 views

• 131
1 vote
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
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
68 views

### Why are floats converted from different integers sometimes equal?

I'm trying to understand the following algorithm: ...
• 103
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