Lucas-Lehmer Test (Was Classic programming)
mouse at Rodents-Montreal.ORG
Sun Aug 9 21:33:15 CDT 2015
>> 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
...still O(n^2). :-)
> 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.
> 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
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
More information about the cctalk