LINKS
CONTACTS



 
Productivity
Comparative characteristic of various algorithms realized today.
The formula is approximate to the experimental data and computed on a Intel Core i5 processor clocked at 3.00 GHz.

Compare relative speed of different processors with this Excel file.
George Woltman's mmff.exe works for 27<N<223.

 

K per second
CPU Only GPU
n Fermat GMP-Fermat pmfs Feromant gfndsieve+pfgw FeromantCUDA mmff ppsieve+pfgw
29 30,000,000 48,000,000 1,900,000,000
32 27,000,000 46,780,000 9,000,000 40,760,870 637,000,000 1,820,000,000 50,000
36 24,000,000 43,660,000 8,000,000 40 588 808 625,000,000 1,600,000,000 60,000
40 21,000,000 40,760,000 7,015,195 40,262,485 625,000,000 1,000,000,000 65,000
44 16,500,000 38,630,000 6,100,000 39,968,771 581,000,000 900,000,000 75,000
48 3,300,000 36,440,000 5,380,321 39,497,981 408,000,000 800,000,000 65,000
54 3,000,000 33,850,000 5,000,000 38,814,351 402,000,000 750,000,000 50,000
60 2,600,000 31,800,000 4,645,618 38,209,357 386,000,000 650,000,000 45,000
80 1,400,000 17,380,000 3,422,943 20,343,562 309,000,000 350,000,000 40,000
100 1,250,000 14,140,000 2,497,638 19,959,482 309,000,000 300,000,000 33,000
150 530,000 6,600,000 1,615,000 11,018,064 203,000,000 130,000,000 25,000
200 375,000 5,700,000 1,075,416 11,106,808 24,500 167,000,000 90,000,000 23,000
300 175,000 1,360,000 579,399 4,128,563 21,000 90,200,000 20,000
400 95,000 810,000 397,688 2,761,195 15.000 48,300,000 15,000
600 39,000 266,000 196,240 984,174 14,200 26,200,000 13,750
800 20,000 107,000 105,529 275,754 13,000 12,500
1000 11,000 60,000 69.944 158,454 12,000 11,574
2000 2,000 9,000 15,269 25,646 5,000 3,858
3000 680 2,600 5,788 7,779 3,000 2,315
5000 180 350 1,624 1,666 1,500 1,052
10000 18 45 293.78 209 1,000 429
20000 2.6 6 50.78 26 500 223
30000 0.91 0.94 19.15 9 160 109
50000 5.92 2 30 25
100000 0.8735 0.4 1.5 1.2

 

Factor search for very small Fermat numbers F12 - F28

Richard Crandall, George Woltman and now Fermatsearch, maintain a project to search factors for small Fermat numbers using ECM (Elliptic Curve Method).

The divisor can have up to 60 digits. Prime95, written by George Woltman, and GMP-ECM, are the best programs for ECM.

Numbers up to F28 are tested using the ECM up to a limit where other factorization methods are useless (see this link),
so we use modular arithmetics for Fermat numbers greater than F28:.

Small and average Fermat numbers F28 ~ F2000

When N grows, scholar mltiplicatio becomes inefficient. Other faster multiplication algorithms are chosen.

One of the most used multiplication algorithms on this range is the modular Montgomery algorithm for both multiplication and exponentiation.

Other more efficient methods are Toon, Karatsuba and FFT multilication; they are faster but harder to implement. Programs based on GMP library automatically choose the best algorithm for the actual problem.

Large and very large Fermat numbers ~F2000 ~ F500000

For such superhuge numbers, modular arithmetics is not enough. Square multiplying becomes time-critical.

For this task the program should use FFT (Fast Fourier Transform). The actual state of the art is reached using the following programs: gfndsieve or ppsieve (sieve) + latest PFGW.

If you use pre-sieved numbers, GeneFer is today the fastest program for the search for a 500,000+ digit prime.


Copyright MoreWare 2003 ...