17
votes
Accepted
Why doesn't Knuth's linear-time multiplication algorithm "count"?
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 ...
- 270k
13
votes
Accepted
Proof that no O(n) multiplication algorithm exists
There is a conditional $\Omega(n\log n)$ lower bound due to Afshani, Freksen, Kamma, Green Larsen, Lower Bounds for Multiplication via Network Coding.
- 270k
12
votes
How can I compute an exponential modulo a large integer?
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 ...
9
votes
Proof that no O(n) multiplication algorithm exists
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: "...
- 800
8
votes
Accepted
In fast multiplier circuits, what is the difference between a Counter and a Compressor?
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 ...
- 17.3k
6
votes
Lower Bound of Matrix Multiplication
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 ...
- 270k
6
votes
Accepted
Could all CPU instructions get fundamentally faster if a better multiplication method was developed
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 ...
- 80.2k
5
votes
Karatsuba multiplication on numbers with odd length
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 ...
- 751
5
votes
Accepted
Why is the transform in Schönhage–Strassen's multiplication algorithm cheap?
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)...
- 270k
5
votes
Accepted
Where does the lg(lg(N)) factor come from in Schönhage–Strassen's run time?
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 ...
- 270k
5
votes
Accepted
Is matrix "adjoint-squaring" faster than general matrix multiplication?
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)...
- 5,722
5
votes
Why don't integer multiplication algorithms use lookup tables?
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 ...
D.W.♦
- 141k
4
votes
How many basic operations are there in an algorithm for the simple multiplication of two numbers of equal length?
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$ ...
4
votes
Accepted
$(max,+)$ matrix product with limited number of values
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. ...
- 6,978
4
votes
Difficulty understanding the faster multiplication hardware
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 ...
- 25.2k
4
votes
Last digit of polynomial value
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 ...
- 34.1k
4
votes
Accepted
Number of computations for multiplication
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.
- 14.6k
4
votes
Number of computations for multiplication
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 ...
- 732
4
votes
Could all CPU instructions get fundamentally faster if a better multiplication method was developed
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 ...
- 25.2k
4
votes
Accepted
Matrix chain multiplication: Greedy approach
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 ...
- 270k
3
votes
Accepted
Swap elements using integer addition and multiplication gates
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:
...
- 12.3k
3
votes
Accepted
Can Strassen's multiplication algorithm be improved if we divide matrices to 3x3 or axa in general?
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 ...
- 270k
3
votes
Lower bound on multiplication
There is a lower bound for multiplication of $\Omega(n\log{n})$ conditional on a conjecture in network coding. There is also an algorithm matching this bound.
3
votes
Accepted
Fixed base exponentiation with precomputations
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=\...
- 14.6k
3
votes
Where does the lg(lg(N)) factor come from in Schönhage–Strassen's run time?
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}...
- 5,722
3
votes
Why is the transform in Schönhage–Strassen's multiplication algorithm cheap?
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-...
- 5,722
3
votes
Necessity of convolution operations for product of two polynomials via brute force method
In the reference linked, in order to get product of these two polynomials, $c(x) = p(x)q(x)$, via brute force, we have to compute new coefficients via convolution $\left(c_k = \sum_{i=0}^k a_i b_{k-i} ...
- 2,072
3
votes
Accepted
Necessity of convolution operations for product of two polynomials via brute force method
Given two polynomials $P_n(x)$, $Q_n(x)$, you can obviously calculate the value $P_n(x) · Q_n(x)$ in $O(n)$ for every x. The document asks about calculating the coefficients, which is a very different ...
- 25.2k
3
votes
Is there any bitwise multiplication algorithm that is sub O(n^2)?
Is Karatsuba algorithm simple enough? It's complexity is $O(n^{1.59})$.
3
votes
Karatsuba Multiplication Rule in dividing a Number in two parts
The most common approach is to take the longest number, and divide it in half (rounding an odd number of digits arbitrarily). So for
x = 12345
y = 2478
you would ...
Only top scored, non community-wiki answers of a minimum length are eligible