13

(This answer was initially posted by the asker jonaprieto inside the question.) I remember Wilson's theorem, and I noticed little things: In the above program, it is better if I write: $$\begin{align} (p-1)! &\equiv -1 &\pmod p\\ (p-2)! &\equiv (p-1)! (p-1)^ {-1} \equiv \bf{1} &\pmod p\\ (p-3)! &\equiv (p-2)! (p-2)^ {-1} \equiv \bf{(p-2)...


12

By using the fast Fourier transform, multiplications on $k$-bit numbers can be done in time $\tilde{O}(k)$ (where the tilde signifies that we're ignoring polylogarithmic factors). By repeated squaring, we can compute $n^{n^2}$ with $O(\log n)$ multiplications, and each multiplication involves no number larger than $n^{n^2}$, which has roughly $n^2 \log_2 n$ ...


9

Very simple: Suppose numbers are written in decimal (other bases are handled by a trivial modification). Build a DFA, with $a$ states 0, 1, ..., $a - 1$. Start state is 0, and from state $q$ on input the digit $d$ go to state $(10 q + d) \bmod a$. Accepting state is $b \bmod a$ (might need a tweak if $b > a$).


9

I suggest you use a binary search tree, augmented so that leaves can contain an interval (a run of consecutive integers). Maintain the invariant that the intervals do not overlap and are in order (following the search tree invariant). (This can be considered a special case of an interval tree or a segment tree, for the special case where the intervals do ...


9

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 = \{s_1,\ldots,s_n\}, T$ of Subset Sum (is there a subset of $S$ summing to $T$?), we construct an instance $v_1,\ldots,v_{2n},u$ of your problem as follows. For ...


8

Division by a constant can always be recast as multiplication by a constant followed by a shift. The relevant papers are: Robert Alverson, "Integer Division Using Reciprocals," IEEE Int'l Symp Comp Arithmetic, (ISCA-10):186-190, 1991. Torbjörn Granlund and Peter L. Montgomery, "Division by Invariant Integers using Multiplication," ACM Conf on Prog Lang ...


8

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, since there are polynomial-time algorithms to compute the gcd. In addition, if a solution exists, one can be found using the extended Euclidean algorithm.


8

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 both wikipedia and the question are very similar to Martin Guy's widely circulated C implementation [b]. which contains a comment: From a book on programming ...


7

Notations: I'll use the C notations for bitwise operations: $a \mathbin\& b$ (bitwise and), $a \mathbin| b$ (bitwise or), $a \mathbin\ll b$ (shift left), $a \mathbin\gg b$ (shift right). The shift operators are left-associative (e.g. $x \mathbin\gg m \mathbin\gg n = (x \mathbin\gg m) \mathbin\gg n$). The shift operations put zeroes in newly created bit ...


7

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 case of this particular question, one crucial inference you can draw is that all million 32-bit integers would fit into RAM, so it would be appropriate to use an ...


7

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, two's complement makes signedness transparent in most operations (addition, substraction, multiplication), but some are different: the bitwise shift may preserve ...


7

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 fastest known algorithm, due to Harvey and van der Hoeven, runs in time $O(n\log n)$. However, this algorithm isn't practical (it is not fast in practice, since ...


6

This is related to the well-known change-making problem. So well-studied, in fact, that this question has been investigated for $m \leq 7$ [1] using brute force. As of 2003, the hardness of finding optimal denominations appears to be an open problem. If you check the articles citing Shallit, it seems as if denominations enabling greedy change-making ...


6

My current research: Initial attempt at some general rules One can try to make some general rules for solving the rational comparison: Assuming all positive $a,b,c,d$: $$ a < b \wedge c \ge d \Longrightarrow \frac a b < \frac c d\\ $$ This basically means, if the left side is less than one, and the right side is at least one, the left side is ...


6

There is an $O(n \log n)$ time algorithm (which in some models is optimal, because of the bounds for the element distinctness problem). We first sort the intervals by their right end point. Suppose the sorted order is $I_1, I_2, \ldots, I_n$. Now for each interval, we try to compute the size of the largest possible non-intersecting set, with that interval ...


6

Two's complement is the most commonly used way to represent signed integers in bits. First, consider unsigned numbers in 8 bits. Notice that $2^8 = 256 = 100000000_2$ does not fit into 8 bits and will thus be represented as 0000 0000. Therefore $255 + 1 =$ 1111 1111 + 0000 0001 = 0000 0000 and in that sense 1111 1111 acts as if it was $-1$. Two's complement ...


6

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 polynomial of degree $128$, say $x^{128}+x^7+x^2+x^1+x^0$. The magic constants $7,2,1,0$ come from this particular irreducible polynomial. You don't see $0$ ...


6

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 lie within some bounded range.


6

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 factorization is in NP, and so reducible to any NP-complete problem (by definition). There are specialized algorithms for integer factorization which are ...


6

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$ in bits (so $n = \Theta(\log m)$). If $2^b > m$ then there is no point to check any $b_0 > b$, hence we only need to check $O(\log m) = O(n)$ many ...


6

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 no possible way to store all the information you need with fewer bits than this. So I recommend a straightforward bitmap. In other words, a simple array of ...


6

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 size of input in bits. In this assumption, the sum of the input can be represented with 1 word, so the space complexity is $O(1)$ words. Measured in bits, the ...


5

From what you said, I suppose that you consider complexity in terms of number of bits of the input. Say you add up two numbers $a$ and $b$, with respectively $n_1$ and $n_2$ bits, then the result is at most $\max(n_1, n_2) + 1$ bits since $a + b \leq 2 \times \max(a, b)$. For the multiplication, the result is at most $2 \times \max(n_1, n_2)$ bits since $...


5

Your error is that you add your constant to the left-hand side of the equality multiple times, and only once to the right side. For example, $1+1=2$ clearly holds. If you add $8$ to both sides of it, you get $1+1+8=10$ which also holds. Erroneously you might add it twice to the left hand side and get $9+9=10$, which does not hold. In your case, $0$ should ...


5

You do not need an exact method, anything with error less than 1 is OK. Say you want to compute $\lfloor \sqrt{x} \rfloor$. This is the largest integer $y$ such that $y^2 \leq x$. Say you have an algorithm $\mathcal{A}$ which on input $x$ outputs $z = \mathcal{A}(x)$ such that $|z - \sqrt{x}| < 1$. You can just: Compute $z = \mathcal{A}(x)$ Let $z_0 = \...


5

I am following the idea of @vonbrand: Hint 1: Solve first for $b=0$. You might use the Myhill-Nerode Theorem. Hint 2: Solve the general case, reuse the automaton induced by the $b=0$ case.


5

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 intervals in increasing order of their finishing times, still denoted as $\mathcal{I}$. while ($\mathcal{I} \neq \emptyset$) choose the first $I \in \mathcal{I}...


5

First of all, your question is very poorly worded, if for no other reason because "quickly" doesn't mean much. You'll need to provide some metric of what "quick" means. Beyond that, when trying to come up with a design for a problem you need to first understand the problem very well and ask a lot of additional questions. Relevant questions in this case ...


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