View Single Post
Old 2013-06-15, 22:32   #73
paulunderwood's Avatar
Sep 2002
Database er0rr

5×829 Posts

Thanks for all those tests. I wonder why it does not run on your Nexus S's default browser. Does it support JavaScript? Maybe not fully?

p10047 takes a long time finding the right "x" for a strong discriminant.

I have been testing version 0.8.4. Here is a result on Chrome at 2.7GHz:
PRP 2^69337-3: 3456571ms

That is just under an hour. It hardly touches the O(n^2) partialModReduction(). I guess it is O(n) for that particular number. Most of the time is going to be in O(n^1.585) karatsuba().

I have made improvements to the sumArray() and put the karatsuba threshold back to 64 words. I can't see what can be improved next. Toom-Cook-n will only complicate the program.

Clearly, a native implementation is going to win by many miles, and it is good to see BPSW wins overall. Maybe I should try to convert my JavaScript code into C, to see if it is any faster than GMP

Version 0.8.4:
Attached Files
File Type: zip (8.6 KB, 312 views)

Last fiddled with by paulunderwood on 2013-06-15 at 22:41
paulunderwood is offline   Reply With Quote