# Tag Info

Accepted

### In algorithms for matrix multiplication (eg Strassen), why do we say n is equal to the number of rows and not the number of elements in both matrices?

Here, n = 8 and we are doing n = 8 multiplications and n/2 = 4 additions. So even a naïve multiplication algorithm would yield a time complexity of O(n). That is wrong. It might work for a small ...
• 1,585
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.
• 278k

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

### In algorithms for matrix multiplication (eg Strassen), why do we say n is equal to the number of rows and not the number of elements in both matrices?

Short answer: because it's natural and convenient. Longer answer: The number of multiplications to multiply a matrix of size p,q with a matrix of size q,r is pqr with a naive algorithm, and something ...
• 530
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 ...
• 81.9k

### 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 ...
• 278k

### In algorithms for matrix multiplication (eg Strassen), why do we say n is equal to the number of rows and not the number of elements in both matrices?

For n = 100, the naive algorithm takes 1,000,000 multiplications and almost as many additions. If we let n = number of rows / columns, then it takes $n^3$ multiplications and $n^3 - n^2$ additions. If ...
• 30.6k

### 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 ...
• 162k

### 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 ...
• 771
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. ...
• 8,303

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

### 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 ...
• 39.1k

### 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 ...
• 30.6k

### 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 ...
• 30.6k
Accepted

### Why don't integer multiplication algorithms use lookup tables?

Some integer multiplication algorithms do use lookup tables. The IBM 1620 Model I "CADET" lacked a conventional ALU: addition and subtraction used a 100 digit table; multiplication used a ...
• 916
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 ...
• 278k
Accepted

### Complexity of multiplying bivariate polynomials of degree n

It suffices to describe how to evaluate $P(\omega^u,\omega^v)$ at the roots of unity. Suppose $P(X,Y)=\sum_{i,j} a_{i,j} X^i Y^j$. Let $$F_{b,c}(X,Y) = \sum_{i,j} a_{2i+b,2j+c} X^i Y^j$$ where the ...
• 162k
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: ...
• 13.6k

### 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})$.
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 ...
• 30.6k