View Single Post
Old 2018-12-14, 19:54   #2
kriesel's Avatar
Mar 2017
US midwest

809110 Posts
Default PRP run time scaling for low p

Run time is fitted as approximately proportional to p2.094, for 86243 <= p <= 2976221. LL run time is expected to scale very similarly. For comparison a theoretical fft convolution based primality tester scales as p2 log p log log p, which over the interval fits as p2.117. Overhead at low exponents lowers the power on a fit. Declining cache effectiveness at higher exponents due to their larger fft lengths will raise the power on a fit.

Top of reference tree:
Attached Files
File Type: pdf prp run times low Mp.pdf (15.9 KB, 476 views)

Last fiddled with by kriesel on 2023-07-16 at 17:06 Reason: footer edit
kriesel is online now