# Tag Info

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

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

### 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: "...
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 ...

### 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  that Gaussian elimination for solving a system ...
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 ...

### 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 ...
Accepted

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

### 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$ ...
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. ...

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

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

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

### 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 ...
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 ...
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: ...
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 ...

### 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.
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=\...

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 ...
Is Karatsuba algorithm simple enough? It's complexity is $O(n^{1.59})$.