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 ...
user avatar
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.
user avatar
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 ...
user avatar
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: "...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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)...
user avatar
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 ...
user avatar
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)...
user avatar
  • 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 ...
user avatar
  • 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$ ...
user avatar
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. ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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.
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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: ...
user avatar
  • 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 ...
user avatar
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.
user avatar
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=\...
user avatar
  • 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}...
user avatar
  • 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-...
user avatar
  • 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} ...
user avatar
  • 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 ...
user avatar
  • 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})$.
user avatar
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 ...
user avatar

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