mersenneforum.org  

Go Back   mersenneforum.org > Other Stuff > Archived Projects > Octoproth Search

 
 
Thread Tools
Old 2006-01-19, 04:11   #45
Kosmaj
 
Kosmaj's Avatar
 
Nov 2003

1110001001102 Posts
Default Re: dodeca3

R. Gerbicz
Thanks for your quick reaction! The new version is indeed up to 2 times faster than before. I'll now check whether it correctly detects already known DodecaProths.

Once I wrote a similar program to search for a long arithmetic progression of primes so I have some /limited/ experience.
Kosmaj is offline  
Old 2006-01-20, 12:23   #46
Greenbank
 
Greenbank's Avatar
 
Jul 2005

18216 Posts
Default Dodecaproth n 'weights'

I'm defining the 'weight' of an n as the number of PRP tests that dodeca_30 needs to perform when checking that n for a range of 0,10T.

The lower the weight the faster it will be to check that n.
The higher the weight the slower it will be.

n=80 weight=45489
n=81 weight=50735
n=82 weight=36134
n=83 weight=31322
n=84 weight=79800
n=85 weight=11925
n=86 weight=71370
n=87 weight=46678
n=88 weight=10297
n=89 weight=452294
n=90 weight=19023
n=91 weight=31650
n=92 weight=57436
n=93 weight=18424
n=94 weight=76983
n=95 weight=17651
n=96 weight=23206
n=97 weight=72811
n=98 weight=77654
n=99 weight=86727

n=89 sticks out somewhat! And I've already taken n=88 :-)
Greenbank is offline  
Old 2006-01-20, 16:19   #47
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

2·743 Posts
Default

Quote:
Originally Posted by Greenbank
n=89 weight=452294

n=89 sticks out somewhat! And I've already taken n=88 :-)
See my benchmarks for n=89, comparing dodeca_2_5 and 3_0 ( just for [0T,1T] ):
dodeca_2_5:
Number of Prp tests=1225
Time=46 sec.

dodeca_3_0
Number of Prp tests=45391
Time=23 sec.

So it isn't very important the number of prp tests, see my mpz_powm() instruction for n=89 bits modulus takes about say 50000 clock cycles, so if we are checking 45391 prp tests, then that take about 2*10^9 clock cycles or about 1.3 sec. for my pc ( 1.7 GHz ), so the prp testing time is about 5% of the total time, 95% is the sieving time!
That was the reason why I've decreased all parameters in 2_5 version of dodeca program.
I've also defined the weight of n ( for dodeca numbers ). See post #28 in this thread.

Last fiddled with by R. Gerbicz on 2006-01-20 at 16:21
R. Gerbicz is offline  
Old 2006-01-24, 22:01   #48
Kosmaj
 
Kosmaj's Avatar
 
Nov 2003

2·1,811 Posts
Default R.Gerbicz

Why is k maxed to 2^60 in dodeca.c? There are 4 more bits in 8-byte unsigned int and furthermore, if you keep k/105 instead of k, the range can be extended to 105*(2^64-1) without using gmp variables, not so?
Kosmaj is offline  
Old 2006-01-24, 22:02   #49
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

148610 Posts
Default new dodeca program version 4.0

In this version there is no limitation on k, and I've also decreased prime_limit from 2000 to 1000 ( and try also -O1 optimization flag ).
See the attachment for the code. Or download exe from http://www.robertgerbicz.tar.hu/dodeca_4_0.exe
Attached Files
File Type: txt dodeca_4_0.txt (18.3 KB, 254 views)
R. Gerbicz is offline  
Old 2006-01-25, 14:27   #50
Kosmaj
 
Kosmaj's Avatar
 
Nov 2003

2×1,811 Posts
Default

My first tests indicate that ver.4 is about 30% slower than ver.3. Please tell me, can I use ver.3 to test n=103 for k<2^60 (by removing the n>=100 condition from the source).
Kosmaj is offline  
Old 2006-01-25, 14:49   #51
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

2·743 Posts
Default

Quote:
Originally Posted by Kosmaj
My first tests indicate that ver.4 is about 30% slower than ver.3. Please tell me, can I use ver.3 to test n=103 for k<2^60 (by removing the n>=100 condition from the source).
In some cases it is possible because it is using sieve_limit=1000. Yes you can change ver.3, by removing that condition.

Note that in all of the new programs now you can change sieve_limit in the source and to do this you have to change also number_of_primes, because there is an error checking for this in the program, you can also change block_length and magic_constant, and of course magic_constant>=block_length>=sieve_limit has to be true . But note that in hexadeca program you can change only sieve_limit ( and number_of_primes ), don't change block_length otherwise the program won't search for the whole interval for n=76 ( there is no magic_constant for this hexadeca ).

I've changed the source in dodeca_4_0 to use sieve_limit=2000 and number_of_primes=303 but this was still slower by 7% for n=99. I don't know why perhaps because we are using in that part mpz_t integers and not long variables.
R. Gerbicz is offline  
 

Thread Tools


All times are UTC. The time now is 21:12.


Sat Jul 31 21:12:45 UTC 2021 up 8 days, 15:41, 0 users, load averages: 1.63, 2.05, 2.87

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.