[quote=cheesehead;151192]Multiplication can approach O(n) by using more complicated methods than we are using in GIMPS (or by dedicating more and more gates on the CPU chip to multiplication). Knuth explains those approaches later in the chapter ("4.3.3 E. Multiplication in real time"). "4.3.3 C. Discrete Fourier transforms" covers what GIMPS uses.[/quote]
A friend of mine showed me that although it was still nlogn
that with enough memory you could beat heapsort or quicksort
into a cocked hat.

[QUOTE=davieddy;151260]A friend of mine showed me that although it was still nlogn
that with enough memory you could beat heapsort or quicksort
into a cocked hat.[/QUOTE]

What does that mean, in English?:huh:

[quote=axn;151262]What does that mean, in English?:huh:[/quote]
What part of English don't you understand?

[quote=cheesehead;151192]Multiplication can approach O(n) by using more complicated methods than we are using in GIMPS (or by dedicating more and more gates on the CPU chip to multiplication). Knuth explains those approaches later in the chapter ("4.3.3 E. Multiplication in real time"). "4.3.3 C. Discrete Fourier transforms" covers what GIMPS uses.[/quote]
The obvious question is where is the point at which the
"complicated method" starts to win.

[QUOTE=davieddy;151276]The obvious question is where is the point at which the
"complicated method" starts to win.[/QUOTE]

The obvious answer is: "It depends..." :smile:

...on the word length
...on the microcode
...on the compiler optimizations
...on the bus width
...on the memory and network latency

As you know, Karatsuba / FFT methods become useful for numbers with more than 60/70 digits.

Luigi

[quote=davieddy;151260]A friend of mine showed me that although it was still nlogn
that with enough memory you could beat heapsort or quicksort
into a cocked hat.[/quote][quote=davieddy;151275][quote=axn;151262]What does that mean, in English?:huh:[/quote]What part of English don't you understand?[/quote]The part [I]I[/I]'d ask about would be: what is the connection between heapsort/quicksort and fast multiplication?

But someone who hadn't studied sorting might be asking: what is the meaning of "heapsort" and "quicksort"? (Google is their friend, but not everyone feels like socializing with an online search engine every time they have a question. :-)

Yes. It was not a point worth labouring, so I didn't:smile:

and ... the connection between heapsort/quicksort and fast multiplication?

(I really am curious.)

Sorry, the only connection was algorithms going as nlogn
and possible improvements thereto.

(I did warn against labouring the point:smile:)

David

About whether one will actually get done: Yes, I hope so, because if not, it means my computer got destroyed in a horrible way.

Thanks for this thread :) I totally thought that the last time I asked, someone told me the amount of time it would take to finish an assignment was a year!! That totally made sense to me because I was doing 10M LLs in three weeks or so. I just did a timing, and it said 4.5 years if I use both CPUs!! I totally just switched to doing one exponent at a time :)

\\EDIT: At least one 100M mersenne has been finished by SOMEONE, right? I tried to find it on primenet but didn't find it. Does anyone have info on this question?

[QUOTE=dominicanpapi82;154330]\\EDIT: At least one 100M mersenne has been finished by SOMEONE, right? I tried to find it on primenet but didn't find it. Does anyone have info on this question?[/QUOTE]If you mean an exponent of 100M then the answer is yes. It was StarQwest that did 100,000,007. See [url]http://mersenneforum.org/showthread.php?t=6389[/url] for some details.