20180202, 00:33  #1 
Jan 2018
2^{2} Posts 
Sublinear complexity of trial division?
I noticed that for trial division in a given range (2^68  2^69 for example), larger exponents seem to take less time (and are awarded with less GHz * Days). I assume that the divisors remain the same since they come from the same range. What optimization does Prime95 use to make division a sublinear time operation?

20180202, 00:46  #2  
"Forget I exist"
Jul 2009
Dumbassville
2^{6}×131 Posts 
Quote:
Last fiddled with by science_man_88 on 20180202 at 00:51 

20180202, 00:55  #3 
Jan 2018
2^{2} Posts 

20180202, 00:59  #4  
"Forget I exist"
Jul 2009
Dumbassville
2^{6}×131 Posts 
Quote:
Last fiddled with by science_man_88 on 20180202 at 01:00 

20180202, 01:11  #5  
Basketry That Evening!
"Bunslow the Bold"
Jun 2011
40<A<43 89<O<88
7221_{10} Posts 
That thread is an excellent reference for the detailed optimizations level, but the simpler more overarching concept is this:
Quote:
But the actual division itself of the candidates is linear in the number of candidates, same as for nonMersenne numbers. Last fiddled with by Dubslow on 20180202 at 01:11 

20180202, 02:49  #6 
Jun 2003
2·5·479 Posts 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Mersenne trial division implementation  mathPuzzles  Math  8  20170421 07:21 
trial division over a factor base  Peter Hackman  Factoring  7  20091026 18:27 
P95 trial division strategy  SPWorley  Math  8  20090824 23:26 
Trial division software for Mersenne  SPWorley  Factoring  7  20090816 00:23 
Need GMP trialdivision timings  ewmayer  Factoring  7  20081211 22:12 