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 32,000,000 637,000,000 1,820,000,000 50,000
36 24,000,000 43,660,000 8,000,000 32,000,000 625,000,000 1,600,000,000 60,000
40 21,000,000 40,760,000 7,015,195 32,000,000 625,000,000 1,000,000,000 65,000
44 16,500,000 38,630,000 6,100,000 32,000,000 581,000,000 900,000,000 75,000
48 3,300,000 36,440,000 5,380,321 32,000,000 408,000,000 800,000,000 65,000
54 3,000,000 33,850,000 5,000,000 35,000,000 402,000,000 750,000,000 50,000
60 2,600,000 31,800,000 4,645,618 32,000,000 386,000,000 650,000,000 45,000
80 1,400,000 17,380,000 3,422,943 25,000,000 309,000,000 350,000,000 40,000
100 1,250,000 14,140,000 2,497,638 15,310,000 309,000,000 300,000,000 33,000
150 530,000 6,600,000 1,615,000 12,200,000 203,000,000 130,000,000 25,000
200 375,000 5,700,000 1,075,416 9.100,000 24,500 167,000,000 90,000,000 23,000
300 175,000 1,360,000 579,399 3,000,000 21,000 90,200,000 20,000
400 95,000 810,000 397,688 1,000,000 15.000 48,300,000 15,000
600 39,000 266,000 196,240 500,000 14,200 13,750
800 20,000 107,000 105,529 200,000 13,000 12,500
1000 11,000 60,000 69.944 113,000 12,000 11,574
2000 2,000 9,000 15,269 17,000 5,000 3,858
3000 680 2,600 5,788 4,025 3,000 2,315
5000 180 350 1,624 1,500 1,052
10000 18 45 293.78 1,000 429
20000 2.6 6 50.78 500 223
30000 0.91 0.94 19.15 160 109
50000 5.92 30 25
100000 0.8735 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 ...