Lucas-Lehmer Test (Was Classic programming)

[Mouse]

>> 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.

...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