The tag has no wiki summary.

learn more… | top users | synonyms

2
votes
2answers
104 views

Where does the lg(lg(N)) factor come from in Schönhage–Strassen's run time?

According to page 53 of Modern Computer Arithmetic (pdf), all of the steps in the Schönhage–Strassen Algorithm cost $O(N \cdot lg(N))$ except for the recursion step which ends up costing $O(N\cdot ...
7
votes
2answers
101 views

Why is the transform in Schönhage–Strassen's multiplication algorithm cheap?

The Schönhage–Strassen multiplication algorithm works by turning multiplications of size $N$ into many multiplications of size $lg(N)$ with a number-theoretic transform, and recursing. At least I ...
7
votes
1answer
688 views

Why doesn't Knuth's linear-time multiplication algorithm “count”?

The wikipedia page on multiplication algorithms mentions an interesting one by Donald Knuth. Basically, it involves combining fourier-transform multiplication with a precomputed table of ...
3
votes
1answer
79 views

Fast algorithm for matrix chain multiplication in special case

An exercise from the book Foundations of Algorithms Using Java Pseudocode: Write an efficient algorithm that will find an optimal order for multiplying $n$ matrices $A_1 \times A_2 \times \ldots ...
6
votes
2answers
93 views

Understanding Intel's algorithm for reducing a polynomial modulo an irreducible polynomial

I'm reading this Intel white paper on carry-less multiplication. It describes multiplication of polynomials in $\text{GF}(2^n)$. On a high level, this is performed in two steps: (1) multiplication of ...
1
vote
1answer
78 views

NFA for right left multiplication

Given the following multiplication table how could one construct an NFA such that it accepts all strings that have a certain product (say a) ? The string "abcb" would be evaluated as (a(b(cb))) = a ...
2
votes
3answers
112 views

Does the performance of matrix multiplication depend on the storage of the array?

Two matrices can be stored in either row major or column major order in contiguous memory. Does the time complexity of computing their multiplication vary depending on the storage scheme? That is, I ...
3
votes
1answer
449 views

Shift-and-or multiplication operation

Continuing in the same vein as Carry-free multiplication operation, a followup question is as follows (differences in bold): Let $r = p \oplus q$ be an operation similar to multiplication, but ...
3
votes
2answers
142 views

Carry-free multiplication operation

In long-multiplication, you shift and add, once for each $1$ bit in the lower number. Let $r = p \otimes q$ be an operation similar to multiplication, but slightly simpler: when expressed via ...