Thread: GIMPS progress
View Single Post
Old 2018-12-16, 17:03   #11
kriesel's Avatar
Mar 2017
US midwest

13A916 Posts
Default GIMPS minor milestone progress versus year

The million-value progression of first test and verification, deltas, and ratios are tabulated by calendar year. The difference (lag) between first test and verify is growing, but the ratio is remarkably stable since 2010.

First test progress averaged from 2012-2018, 6 million annually.
Verify progress averaged from 2012-2018, 3.3 million annually.

A rough linear extrapolation from those figures (always an iffy proposition over long time frames; million-mulriple milestones) made in late December 2018 is:
year test verify
2019 87M 49M (matched)
2020 94M 52M (exceeded; 100M and 54M)
2021 100M 56M (100M reached 4 December 2020; 56M tbd)
2022 106M 59M
2025 124M 69M
2029 148M 82M
2030 154M 86M
2040 214M 119M (DC becomes largely moot with widespread adoption of PRP-proof and completing LL DC backlog; PRP DC backlog is smaller so will likely complete much sooner)
2050 274M 152M
2060 334M 185M
2070 394M 218M
2080 454M 251M
2090 514M 284M
2100 574M 317M
2110 634M 350M
2120 694M 383M
2130 754M 416M
2140 814M 449M
2150 874M 482M
2160 934M 515M
2170 994M 548M
2171 1000M 551M current limit reached by first tests.
2307 1816M 1000M current limit reached by verifications.
3671 10000M 4501M 10G first tests
5034 18178M 10000M 10G verified

(assumes PRP does not dramatically change verification workload)

2171-2018 = 153. About six Mersenne primes are expected in that span. That implies future discoveries once in 153/6 =~25 years on average.

The above extrapolation contains an implicit assumption that while the exponents become much more computationally intensive over time, evolutionary increases in computing power, software improvements, and historical increases in participant numbers will offset that to an extent that the rate of advance on exponent value annually is about constant. While computing a primality test for a 10 times larger exponent is more than 100 times harder, ten years of development provides significantly faster hardware. The projection therefore may be quite pessimistic. On the other hand, shrinking integrated circuit feature size as a means of continuing Moore's law can not continue indefinitely. (Size of atoms and onset of quantum effects limit feature shrink; heat dissipation limits clock rates; practical considerations limit die size, die count, and system count.)

The long time spans in the table above imply certain assumptions allowing the project to continue, including personnel succession plans, and economic and societal stability sufficient for effort, electrical power, computing equipment manufacture, and internet communications to continue.

A second tabulation of GIMPS historical minor milestones made more recently is also attached.

Note, the projection predates the following developments that may each accelerate progress somewhat:
The introduction of the Radeon VII gpu
Dramatic performance improvements in the gpuowl fft code
Ben Delo first primality testing throughput
Dmbeeson LL DC throughput
PRP DC reduction in effort by ~99%, by introduction of prp proof
P-1 reduction in cost possible through the approach in
Reduction in TF and P-1 bounds in response to the near elimination of DC effort

Since the work to primality test a single exponent scales as ~p2.1 for current wavefront and code, a sudden doubling in computing power is absorbed easily. The doubled rate of primality testing at p declines to same-rate at ~1.39p. (2(1/2.1)~1.391)

Top of reference tree:
Attached Files
File Type: pdf milestones.pdf (42.4 KB, 4 views)
File Type: pdf gimps progress and rate.pdf (51.7 KB, 4 views)

Last fiddled with by kriesel on 2021-04-11 at 14:21 Reason: updated attachments for 55M DC
kriesel is offline