9 votes
Accepted

What algorithms exist for solving natural number linear systems?

Your problem is NP-complete, by reduction from Subset Sum (it is in NP since the fact that everything is non-negative bounds the coefficients of the solution sufficiently well). Given an instance $S = ...
user avatar
9 votes
Accepted

Where can I find an original reference for this integer square root algorithm

The wikipedia article on Methods of computing square roots: base 2 presents a strikingly similar snippet of C-code [a], but the link to the source is dead. Let's try to do better. The snippets from ...
8 votes

How are Signed integers different from unsigned integers once compiled

There is no way to tell if 8 bits in memory are a signed integer, an unsigned integer, a character, or part of a bigger data. The knowledge is put in the instructions. As stated by David Richerby, ...
user avatar
  • 965
8 votes

Complexity of Linear Diophantine equations

Yes, this class of equations can be solved in polynomial time. In particular, there exists a solution if and only $\gcd(a_1,\dots,a_n)$ divides $k$. That condition can be tested in polynomial time, ...
user avatar
  • 140k
7 votes
Accepted

Difference in Sorting 32- and 64-bit Integers

Yes. For instance, sorting a million 5-bit integers is a lot easier: use counting sort. And sorting a million long strings is a different question than sorting a million 32-bit integers. In the ...
user avatar
  • 140k
7 votes
Accepted

Complexity of Integer Division

Wikipedia has a nice page about the complexity of mathematical operations, and there is also a dedicated page about division. Asymptotically, division has the same complexity as multiplication. The ...
user avatar
7 votes
Accepted

Space complexity for storing integers in Python

It depends on the model of computation. In the transdichotomous model, which is the standard model in the analysis of algorithms, we assume that the word size is $w=O(\log n)$ bits, where $n$ is the ...
user avatar
  • 1,319
6 votes
Accepted

How are Signed integers different from unsigned integers once compiled

For simple types, you can't tell by looking at the bits in memory. Because the source specifies that the data is of a particular type, the compiler generates code that interprets the bits in memory as ...
user avatar
6 votes
Accepted

Understanding Intel's algorithm for reducing a polynomial modulo an irreducible polynomial

The Galois field $GF(2^{128})$ has many different "concrete" representations. One popular representation is using polynomials in $GF(2)[x]$ (i.e. with coefficients in $GF(2)$) modulo some irreducible ...
user avatar
6 votes

Are nearly all natural numbers compressible?

For every $n$ there is a "busy beaver" machine (i.e., a Turing machine on the tape alphabet $\{0,1\}$ run on the empty tape) which outputs $1^n$ using $O(\log n/\log\log n)$ states, which is ...
user avatar
6 votes
Accepted

Efficient algorithm for getting from 1 to n with 3 specific operations

Find the shortest path from $1$ to $n$ on an appropriate graph on vertices $\{1, \dots, n\}$. This approach will work whenever it's guaranteed that intermediate values in the calculations will ...
user avatar
6 votes
Accepted

Complexity class of integer factorization

Integer factorization (or rather, an appropriate decision version) is not known to be NP-complete. In fact, it is conjectured not to be NP-complete. However, any reasonable decision version of integer ...
user avatar
6 votes

How to find the closest N to the power of X to the given number?

Here is a general solution for the following problem: Given a positive integer $m$, find positive integers $a,b \geq 2$ such that $a^b$ is as close as possible to $m$. Let $n$ be the length of $m$ ...
user avatar
6 votes
Accepted

Given a RxC grid, how to generate N 2D points randomly such that no 3 points are collinear?

For simplicity , assume the grid is a square $N \times N$ grid and $N$ is a prime. Its easy to see that from each row we can pick $\leq 2$ points only , so the maximum number of points we can chose ...
user avatar
  • 111
6 votes
Accepted

Efficient data structure for storing integers in a range?

Since you know you're going to have to deal with all $2^{32}$ values eventually, you're going to need at least $2^{32}$ bits of memory, one for each value. The pigeonhole principle means that there's ...
user avatar
  • 6,920
6 votes

Batch rounding with preservation of a sum

There are many rounding methods that round an integer to the nearest integer, all of which are the same except on the half-integers. The sum of integers returned will be close to the sum of the ...
user avatar
  • 33k
5 votes
Accepted

Find 8 numbers whose sum is closest to a defined value

Dynamic programming One approach is to use dynamic programming. If you have $n$ numbers ($n$ rows in the file), and each number is in the range $1..m$, then the obvious dynamic programming algorithm ...
user avatar
  • 140k
5 votes
Accepted

Unreachable Real Numbers - Randomness & Computability

In a nutshell: Printing a random non-computable real is a meaningless task, for precise technical reasons. The meaningful problem is to print non-computable numbers precisely identified by some unique ...
user avatar
  • 19.1k
5 votes

Algorithm to return largest subset of non-intersecting intervals

This is called the "Interval Scheduling" problem in the book [1]. The greedy algorithm, along with an example, is as follows (please find the correctness proof in the book mentioned above): sort the ...
user avatar
  • 9,179
5 votes

Quick calculation for $(x^y) \bmod z$

Computation with large integers is one of the topics of Knuth's "Seminumerical Algorithms" (volume 2 of "The Art of Computer Programming"). Results in elementary number theory, like the properties of ...
user avatar
  • 13.6k
5 votes

Why is the addition function exponential for k-bit integers providing only zero, equality and the successor functions?

From the Wikipedia article on time complexity: In computer science, the time complexity of an algorithm quantifies the amount of time taken by an algorithm to run as a function of the length of the ...
user avatar
  • 276
5 votes

Batch rounding with preservation of a sum

A "stateless" approach (i.e. the same value always rounding the same way) cannot work. To see why, consider a sum of always the same number. After n terms, the error will equal n times the ...
user avatar
  • 3,338
4 votes

Understanding Intel's algorithm for reducing a polynomial modulo an irreducible polynomial

For completeness, I'll flesh out Yuval's answer a bit more through an example of multiplication of two polynomials $A$ and $B$ in $\text{GF}(2^{16})$. Let $$A = [0001|1100|1110] = x^8 + x^7 + x^6 + x^...
user avatar
  • 477
4 votes
Accepted

Algorithm to decide if $n \le m!$

Here is a different solution than the one I suggested in the comments. Compute the sequence of factorials $1!,2!,3!,4!,\ldots$ until you get a number which is at least $n$. Since $(k+1)!/k! = O(\log (...
user avatar
4 votes
Accepted

Quick calculation for $(x^y) \bmod z$

Here is the quickest way I can think. Assume first that $x$ and $z$ are coprime. Factor $z = \prod_i p_i^{a_i}$ and calculate $\varphi(z) = \prod_i p_i^{a_i-1} (p_i-1)$. Compute $x' = x \pmod{z}$ and ...
user avatar
4 votes
Accepted

What is the complexity of finding the two prime numbers a composite number (used in RSA Protocol) is made of?

Large numbers are factored with the General Number Field Sieve, which is, as of now, the fastest non-quantum algorithm. You can find the heuristic runtime in the linked Wikipedia-article. Also in use ...
user avatar
  • 1,841
4 votes
Accepted

Checking whether an integer is a square or higher power

The standard algorithm for determining whether an integer $n$ is a perfect power goes like this. We check whether it is a perfect $k$th power for $k \in \{2,\ldots,\log n\}$; as an optimization, it ...
user avatar
4 votes

Why is the addition function exponential for k-bit integers providing only zero, equality and the successor functions?

The average magnitude $m$ of a number of $k$ binary digits is an exponential function of $k$ (because $k= \lfloor{\log_2{m}}\rfloor + 1$, $ m>0$). Using only zero, equality, and the successor ...
user avatar

Only top scored, non community-wiki answers of a minimum length are eligible