9 Aug
2015
9 Aug
'15
7:33 p.m.
Are you aware
of faster-than-n^2 multiplication algorithms [...]
Actually, when the algorithm is
to square a value, the difficulty
reduces to ONLY ( n^2 + n ) / 2 which is IN ADDITION, it is the Lucas-Lehmer primality test:
I should look it up someday. (The Wikipedia link is of no use to me
because Wikipedia is no longer willing to serve content over HTTP as
far as I can tell.)
that I wish to implement (so I can understand the
details along with
being able to enjoy the challenge).
I can understand that. I've done that with various things myself.
So the series of one billion bit multiplications must
be repeated
(one billion - 2) times.
...ouch!
I understand both the Karatsuba and Toom-Cook
algorithms sufficiently
to EVENTUALLY implement both at this point.
I've implemented Karatsuba. I looked into it and decided that, for my
purposes, even Toom-3 wasn't worth the bother, so I didn't investigate
enough to learn how to implement it - one of the doc files for the
program in question says, after explaining Karatsuba,
| It is possible to split A and B into more than two pieces and pull
| basically the same trick, leading to an even further reduction in the
| exponent - this is Toom-Cook multiplication. However, what partial
| products are needed and how to combine them get correspondingly more
| complicated. While the larger splitting factors do give asymptotically
| faster algorithms, the overhead is high enough that the point at which
| they become faster in practice rapidly exceeeds the size of numbers
| this program is intended for, to the point where it's not worth the
| bother of going Toom-Cook (and definitely not worth using
| Sch?nhage-Strassen or Furer).
"[T]he size of numbers this program is intended for" maxes out
somewhere around 15K bits, nowhere near what you're working with.
If I can perform each squaring operation in just one
second, it
should take only about 5 years to perform the squaring one billion
times.
That doesn't sound right. A mean year is 365.2425 * 24 * 60 * 60
seconds, which my calculator program says is 31556952. Dividing this
into 1000000000, I get 31.6887+, not "about 5". Did I miss something?
Unfortunately, the Sch?nhage-Strassen algorithm is
still beyond my
capability. However, I hope to master it eventually and implement
the code.
I hope to too. But I currently am nowhere near that; my understanding
is that the current state of the art in multiplication is FFT-based
things, and I have never truly understood FFTs - I still don't entirely
understand even continuous Fourier transforms.
If anyone can comment on my question regarding the
[DLLs]
Also, a link to information about how to implement
the
Sch?nhage-Strassen algorithm [...]
I can't really help you with either one. Sounds as though you've
already gone further than I have in this direction, so I would be more
likely to follow you than lead you.
/~\ The ASCII Mouse
\ / Ribbon Campaign
X Against HTML mouse at rodents-montreal.org
/ \ Email! 7D C8 61 52 5D E7 2D 39 4E F1 31 3E E8 B3 27 4B