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.

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.

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 F_{12} - F_{28}

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 F_{28} 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 F_{28}:.

Small and average Fermat numbers F_{28} ~ F_{2000}

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 ~F_{2000} ~ F_{500000}

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 ...