>> 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 mo...@rodents-montreal.org / \ Email! 7D C8 61 52 5D E7 2D 39 4E F1 31 3E E8 B3 27 4B
