Search Results
| Search type | Search syntax |
|---|---|
| Tags | [tag] |
| Exact | "words here" |
| Author |
user:1234 user:me (yours) |
| Score |
score:3 (3+) score:0 (none) |
| Answers |
answers:3 (3+) answers:0 (none) isaccepted:yes hasaccepted:no inquestion:1234 |
| Views | views:250 |
| Code | code:"if (foo != bar)" |
| Sections |
title:apples body:"apples oranges" |
| URL | url:"*.example.com" |
| Saves | in:saves |
| Status |
closed:yes duplicate:no migrated:no wiki:no |
| Types |
is:question is:answer |
| Exclude |
-[tag] -apples |
| For more details on advanced search visit our help page | |
Results tagged with multiplication
Search options questions only
not deleted
user 535
1
vote
1
answer
70
views
Are there efficient probabilistic multiplication algorithms that use O(n log n) gates?
Recently Harvey and Hoeven published a paper proving that integer multiplication can be performed using at most O(n log n) operations. … But suppose that we only wanted a probabilistic multiplication circuit, which returned the wrong result with probability at most epsilon. …
- 5,902
6
votes
2
answers
4k
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 \l …
- 5,902
8
votes
2
answers
1k
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. …
- 5,902
3
votes
0
answers
123
views
Quantum circuits for multiply-accumulation
Classically, multiplication can be done in $O(n \ \lg(n) \ 8^{\lg^* n})$ steps on a multi-tape Turing machine via Fürer's algorithm. …
- 5,902
14
votes
1
answer
3k
views
Why doesn't Knuth's linear-time multiplication algorithm "count"?
The wikipedia page on multiplication algorithms mentions an interesting one by Donald Knuth. … The article acts like this algorithm somehow doesn't count as a "true" multiplication algorithm. …
- 5,902
5
votes
1
answer
239
views
Is matrix "adjoint-squaring" faster than general matrix multiplication?
The best known algorithm(s) for matrix multiplication of $n$-dimensional matrices take $O(n^{2.37})$ time. However, that's for matrices with totally independent contents. … I was wondering if knowing $V = U^\dagger$, i.e. that $V$ is the conjugate transpose of $U$, allowed for asymptotically faster matrix multiplication. …
- 5,902