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
  • 141k
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
  • 141k
7 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
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

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

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,940
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
  • 34.1k
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
  • 141k
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

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,209
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

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,912
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

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
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

There are n numbers. Find the maximal set of pairwise NON coprime numbers

Your problem is NP-complete, I will show a reduction from maximum independent set to your problem. Let $G = (V, E)$ be an undirected graph, and let $G'$ be the complement graph of $G$. Label each edge ...
user avatar
  • 4,132
4 votes
Accepted

How to read off the set represented by a van-Emde-Boas tree?

If you haven't done so, I suggest you read chapter 20 from the beginning. They develop the final data structure bit by bit, supposedly for didactic reasons. In 20.3.1, they write: min stores the ...
user avatar
  • 70.9k
4 votes
Accepted

Algorithm for implementing the modulus "%" operator?

You don’t “implement the modulus operator”. You check wit the standards for your programming language how it is defined, and that’s what you implement. For languages like C, C++, Objective-C, Swift ...
user avatar
  • 25.2k
3 votes

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

The computational complexity of factorization is one of the biggest open problems in computer science. There's a summary of what's known on Wikipedia; the summary of the summary is that it's known to ...
user avatar
3 votes
Accepted

Find the minimum range

Below I try to prove that the greedy algorithm ($\mathcal{A}$) given by @norbertpy (and @Bergi) is correct. Please check it. Problem Definition: The algorithm $\mathcal{A}$ of @norbertpy is for a ...
user avatar
  • 9,209

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