131–140 of 152 posts
Does the article just end after describing the problem for me only? I am left wanting for more.
if you want a little more in depth explanation of the whole multiplication thing Ican recommend TAOCP volume 2. it has a section called 'How fast can we multiply?' it should provide more insight. there is a paper from djb (Daniel J Bernstein),which I can also recommemd: https://cr.yp.to/lineartime/multapps-20080515.pdf
Earlier quoted context omitted.
Maybe I'm not communicating the point clearly. In order to use a table to do the whole multiplication it has to be much larger than the largest number you would want to multiply with it. A lot of the analysis of algorithms, especially multiplication as discussed here, is about astronomically large numbers, so you don't want the existence of an even more astronomically large table as a prerequisite.
We are talking about mathematicians. We are not talking about computer engineers trying to implement a physical GPU that can multiply matrices as fast as possible. You don't have to physically build the astronomically look up table by hand. One can simply state that it exists. Proofs do not have to be clean to be a proof. You might not "want" something in a proof, but if it works then it works.
I was under the impression that because the grade school technique we learn is really just convolution over the digits, the fastest algorithms achieve o(n logn) via fourier transforms. Is that not the case?
Of course, there are also implementation considerations. For example you can speed up Strassen by recursively breaking down the matrix into sub-matrices in parallel, but only down to a point - once the sub-matrices get small enough, it becomes faster to simply do a straight Strassen computation. And it depends on your hardware. For something seemingly so simple, you can go pretty far down a rabbit hole!
For anyone interested in digging, check out Karatsuba's algorithm ( https://en.wikipedia.org/wiki/Karatsuba_algorithm ), Strassen matrix multiplication ( https://en.wikipedia.org/wiki/Strassen_algorithm ), and Toom-Cook multiplication ( https://en.wikipedia.org/wiki/Toom–Cook_multiplication ). Of course, there are also implementation considerations. For example you can speed up Strassen by recursively breaking down t…
the next rabbit hole starts when you try to start lifting F_2 into Z for a given tensor.
Earlier quoted context omitted.
To make both addition and multiplication O(n), you can store numbers as their residues modulo a bunch of different primes and appeal to the Chinese Remainder Theorem. However, then size comparison becomes difficult.
I think the problem comes when you do a multiplication and you need more primes for uniqueness.
k bits digits
10 319 96
20 639 192
30 959 288
40 1279 385
50 1599 481
75 2399 722
100 3199 963
150 4799 1444
250 7999 2408
500 15999 4816
1000 31999 9632
k bits digits
10 159 48
20 319 96
30 479 144
40 639 192
50 799 240
75 1199 361
100 1598 481
150 2397 721
250 3991 1201
500 7967 2398
1000 15868 4776
k bits digits
10 78 23
20 152 45
30 220 66
40 281 84
50 327 98
54 334 100Earlier quoted context omitted.
You might want to learn about recursion. It'll blow your mind.
… which needs a terminating case, which cannot be not defined as the same recursion.
Btw, your recursion doesn't necessarily need a terminating case.
See eg this definition of the list of Fibonacci numbers in Haskell:
fibs :: [Integer]
fibs = 1 : 1 : zipWith (+) fibs (tail fibs)Earlier quoted context omitted.
… which needs a terminating case, which cannot be not defined as the same recursion.
When talking informally, people often omit mentioning the base case when it's obvious or trivial. Btw, your recursion doesn't necessarily need a terminating case. See eg this definition of the list of Fibonacci numbers in Haskell: fibs :: [Integer] fibs = 1 : 1 : zipWith (+) fibs (tail fibs)