17
While the algorithm you mention appears in Knuth's TAOCP, it is certainly not due to Knuth, and is more widely known as the Schönhage–Strassen algorithm; Knuth even attributes this algorithm to them in the text. This algorithm indeed runs in linear time in the so-called RAM machine, in which variables are allowed to hold integers of size $O(\log n)$, where $...
13
There is a conditional $\Omega(n\log n)$ lower bound due to Afshani, Freksen, Kamma, Green Larsen, Lower Bounds for Multiplication via Network Coding.
12
Modular exponentiation is a well-known algorithm. It is routinely available in libraries and languages that can manipulate large integers, including Wolfram Alpha.
When making computations modulo a large number, one does not first make the whole computation in $\mathbb{N}$ and then take the remainder of the result, because for something like an ...
answered Nov 26 '14 at 22:42
Gilles 'SO- stop being evil'
40.9k7 gold badges108 silver badges172 bronze badges
9
No nontrivial lower bound for the multiplcation is known (clearly, it is $\Omega(n)$) and David Harvey himself does not know if a complexity of $O(n\log(n))$ is the best possible: in his own words: "in this sense, our work is expected to be the end of the road for this problem, although we don't know yet how to prove this rigorously". See also the original ...
8
In multiplier design an (n,k) counter takes an n bit input and produces a k bit output which is the binary representation of the number of input bits that are 1s. That is: it counts the number of input bits set to 1.
A (3,2) counter is just a full adder.
A (7,3) counter is a circuit with 7 input bits and 3 output bits. The 3 output bits tell you (in ...
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
Strassen, in his paper describing Strassen's algorithm (Gaussian elimination is not optimal) mentions
the result of Klyuyev and Kokovkin-Shcherbak [1] that Gaussian elimination for solving a system of linear equations is optimal if one restricts oneself to operations upon rows and columns as a whole.
The reference is to
Klyuyev, V. V., and N. I. ...
6
I don't see the relevance.
New multiplication algorithms only offer a practical improvement for numbers with huge numbers of bits and probably don't beat existing algorithms until you're dealing with numbers with thousands or even millions of bits. For an extreme example, Fürer's algorithm, which runs in time $O(n\log n\, 2^{O(\log^*n)})$ will only ...
5
It's not faster (asymptotically). You can reduce general matrix multiplication down to three "adjoint-squarings".
Suppose we're given an adjoint-squaring function $\mathfrak{F}$ where $\mathfrak{F}(M) = M \cdot M^\dagger$. Consider that:
$\mathfrak{F}(A + B) = (A+B) \cdot (A+B)^\dagger = AA^\dagger + BB^\dagger + A B^\dagger + B A^\dagger$
$\mathfrak{F}(A ...
5
Here, $B = 10$ and $n = 3$. The Karatsuba method works for any $m < n$. With $m = 2$ :
$a = 2 * 10^2 + 34$
and
$b = 8 * 10^2 + 57$
; thus, $a_1 = 2$, $a_0 = 34$, $b_1 = 8$ and $b_0 = 57$.
It follows that $ab = z_2 B^{2m} + z_1 B^m + z_0$ where $z_2 = a_1 b_1 = 16$, $z_1 = a_1 b_0 + a_0 b_1 = 386$ and $z_0 = a_0 b_0 = 1938$.
Thus, $ab = 16 \cdot 10^{2*2}...
5
The sticking point is the size of the integers in the recursive step, which is not quite $\sqrt{n}$, but rather twice as large, since the product of two $t$-bit integers has size $2t$. Assuming that we break the original $n$-bit integer into $\sqrt{n}$ parts of length $\sqrt{n}$, the running time recursion is
$$ T(n) = n\log n + \sqrt{n}T(2\sqrt{n}), $$
and ...
5
According to the Wikipedia article, at each step the length of the integers is reduced from $N$ to (roughly) $\sqrt{N}$, and there are (roughly) $\sqrt{N}$ of them, and so the additions only cost $O(N)$. There is a detailed analysis of the running time in the final paragraph of the linked section, copied here in case it changes:
In the recursive step, the ...
5
Your operation is multiplication of polynomials over $GF(2)$, i.e., multiplication in the polynomial ring $GF(2)[x]$.
For instance, if $p=101$ and $q=1101$, you can represent them as $p(x)=x^2+1$, $q(x)=x^3+x^2+1$, and their product as polynomials is $p(x) \times q(x) = x^5+x^4+x^3+1$, so $p \otimes q = 111001$.
If $p,q$ are $r$ bits long, this polynomial ...
5
The asymptotic complexity will not change with relation to how the matrices are laid out in memory, but the actual running time of the matrix multiplication will be very dependent upon the memory layout. There are two papers that I know of that go into detail about this, one by McKellar in 1969 and another by Prokop in 1999. Prokop's paper defines the ...
5
If you want to use lookup tables, and you have 4GB of memory, you'll only be able to use a lookup table with about $2^{32}$ entries or fewer, so you'll only be able to handle multiplication of numbers that are at most 16 bits long. If you want to multiply larger numbers, you won't be able to use lookup tables for multiplication. Typically we want to ...
4
No, the complexity remains the same.
The main difference between row-major and column-major order is memory access patterns - for example if you iterate by column then row-major order would be jumping around memory, which is bad for CPUs because they cannot read-ahead/cache memory.
This is because transferring data from RAM to the CPU on modern processors ...
4
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^3 + x^2 + x,$$ and
$$B = [0100|0101|0111] = x^{10} + x^6 + x^4 + x^2 + x + 1.$$
The multiplication of $A$ and $B$ over $\text{GF}(2)$ is then
$$C = [0000|0000|...
4
It's hard to tell what anyone means by "comparable" in a specific context. I would take it to mean "of the same order", so something like $n^2$, maybe $100\cdot n^2$ or $0.0001\cdot n^2$, but not $n$ or $n^3$.
The final addition is doing (roughly) $n$ additions of numbers of (roughly) non-$\_$ $n$ digits, and each of those additions takes (roughly) $n$ ...
4
The paper All pairs shortest paths using bridging sets and rectangular matrix multiplication by Uri Zwick shows that the APSP problem can be solved in subcubic time, given a bound on the edge-weights. The APSP problem uses a $(\min,+)$-matrix product. Since $\max_{A} \sum_{a\in A} a = -\min_{A} -\sum_{a\in A}a = -\min_A \sum_{a\in A}-a$, we can express a $(\...
4
You want to multiply x by y, where both are 32 bit numbers.
The result is the sum of 32 numbers. The first number is x if bit #31 of y is 1, and 0 if bit #31 of y is 0. This number is shifted by 31 bits. The second number is x if bit #30 of y is 1, and 0 if bit #30 of y is 0. This number is shifted by 30 bits. And so on. The last number is x if bit #0 of y ...
4
Remainder modulo 10 instead of last digit
What is the last digit of -206? It is 6 by convention. It is not 4, the least positive remainder of -206 divided by 10.
For simplicity, we will compute the value of polynomial modulo 10. We will just say "the remainder of some number" to mean the least positive remainder of that number divided by 10. (The ...
4
It should be "10 superscript{n/2}" meaning $10^{n/2}$. For example, if $n=4$, then "6#2" would represent $6\cdot10^2=600$. All he's doing is shifting a decimal number to the left.
4
From context it's just exponentiation. I don't know why it's written with a subscript instead of a superscript, but with older papers you sometimes had a professional typesetter who might not have understood the material. (Of course nowadays typically do their own typesetting.)
4
No, it's not helping.
You can do n bit multiplication in O (log n) time, not O (n log n). The only problem is that you need an enormous amount of hardware to do this, growing as O (n^2), while this paper describes multiplication with a fixed amount of hardware.
But since a CPU typically just has only a 64 bit multiply unit, that O (n^2) space is no big ...
4
Consider the product $ABC$, where
$A$ is $5\times 2$
$B$ is $2\times 3$
$C$ is $3\times 100$
Your algorithm first computes $BC$ (600 products) and then $A(BC)$ (1000 products), for a total of 1600 products.
The optimal solution first computes $AB$ (30 products) and then $(AB)C$ (1500 products), for a total of only 1530 products.
Suppose that $A$ is $a\...
3
Let's say we have inputs $x, y$ and $c$, where $c$ is either 0 or 1, 0 = no swap, 1 = swap. We can make a conditional swap function like this:
notc = 1 + (-1)*c
x' = notc*x + c*y
y' = c*x + notc*y
Even if you have no negative integers, as long as your integers are modulo $2^n$, you can use $-1 \equiv 2^n - 1 \mod 2^n$ and everything works out.
3
There is nothing special about 2×2 matrices. In fact you can do much better using larger matrices. The reason that you are only being explained the 2×2 algorithm is that it is simple to describe. The special thing about 2×2 matrices are that they are the smallest square matrices which are larger than 1×1.
You can read more in this recent survey by Dumas and ...
3
Your question hits at the main part of the faster algorithm presented in the paper. Many people know the usual (base-2) "repeated squaring" algorithm to compute $g^n$ is to write $n$ in binary:
$$
n=\sum_{i=0}^m e_i2^i\qquad e_i\in\{0,1\}
$$
so
$$
g^n=g^{e_02^0+e_12^1+e_22^2+\dotsm}=(g^{2^0})^{e_0}(g^{2^1})^{e_1}(g^{2^2})^{e_2}\dotsm
$$
and observe that $g^{...
3
There's an excellent explanation of exactly what's going on, including how the size of the field goes down as you progress, in GMP's documentation: 15.1.6 FFT Multiplication.
A more theoretically in-depth overview starts on page 55 of Modern Computer Arithmetic (pdf) (well... the browser says page 71 but the page itself says 55). It explains the algorithm's ...
3
The issue is that the expansion factor inside the recursive term is not less than 2, and that causes the bound to fail. Define:
$T_c(n) = n \log n + \sqrt n T(c \sqrt n)$
I claim that $T_{2-\epsilon}$ is $O(n \log n)$, but $T_{2}$ isn't. This is probably most obvious when trying to prove the $n \log n$ bound by induction. Assume that $T_c(n_0) \leq 100 n_0 ...
Only top voted, non community-wiki answers of a minimum length are eligible