mersenneforum.org  

Go Back   mersenneforum.org > Prime Search Projects > Prime Sierpinski Project

Reply
 
Thread Tools
Old 2007-05-14, 00:51   #12
jasong
 
jasong's Avatar
 
"Jason Goatcher"
Mar 2005

5×701 Posts
Default

If you really think this will work, Citrix, you should be posting in the Seventeen or Bust sieving Forum to. Go here and scroll to the bottom to find the forum.

I'm pretty sure you already have an account there?
jasong is offline   Reply With Quote
Old 2007-05-14, 07:39   #13
hhh
 
hhh's Avatar
 
Jun 2005

22·3·31 Posts
Default

Quote:
Originally Posted by jasong View Post
If you really think this will work, Citrix, you should be posting in the Seventeen or Bust sieving Forum to. Go here and scroll to the bottom to find the forum.

I'm pretty sure you already have an account there?
That's one way to say it. One could say: read Greenbanks post, as well. H.
hhh is offline   Reply With Quote
Old 2007-05-14, 16:56   #14
Greenbank
 
Greenbank's Avatar
 
Jul 2005

2×193 Posts
Default

Shame I don't have any spare time at the moment!
Greenbank is offline   Reply With Quote
Old 2007-05-15, 01:11   #15
Citrix
 
Citrix's Avatar
 
Jun 2003

2×787 Posts
Default

Quote:
Originally Posted by hhh View Post
That's one way to say it. One could say: read Greenbanks post, as well. H.
Actually there is an error in that post. Geoff's sieve uses SPH but only for the initial smooth numbers. (upto 16).

Could some one provide me the source code of proth_sieve or jjsieve, I can try to modify it to the above algorithm. Let me know and I can PM you my email address.

Thanks.

Last fiddled with by Citrix on 2007-05-19 at 22:31
Citrix is offline   Reply With Quote
Old 2007-05-15, 13:24   #16
Greenbank
 
Greenbank's Avatar
 
Jul 2005

2×193 Posts
Default

For proth_sieve, ask the original author: Mikael Klasson, his email address (as given on his own web page) is: mklasson T acm.org
Greenbank is offline   Reply With Quote
Old 2007-05-17, 23:37   #17
geoff
 
geoff's Avatar
 
Mar 2003
New Zealand

13×89 Posts
Default

Quote:
Originally Posted by Citrix View Post
Actually there is an error in that post. Geoff's sieve uses SPH but only for the initial smooth numbers. (upto 720).
So would it help to test your idea if I just made the Sieve of Eratosthenes sieve numbers 4x+1 without otherwise changing the sr2sieve algorithm?

From my way of looking at the algorithm, that would mean only primes which allow a quartic residue test to be performed will be sieved.
geoff is offline   Reply With Quote
Old 2007-05-18, 03:53   #18
Citrix
 
Citrix's Avatar
 
Jun 2003

2·787 Posts
Default

It is possible to do some preliminary testing using your program. But the real boost will come when the whole idea is implemented.

I did some calculations and if this idea is used we can find ~3,000 factors for PSP alone in range (4-5M) ie 15% less work, in a very short time.

Quote:

sr2sieve only uses small factors of p-1 implicitly: to check whether k is a cubic residue for p it needs first to check whether p=1 (mod 3). That is equivalent to determining whether 3 is a factor of p-1, but since only 3,4,5,8,9,16-power residues are checked, all the needed factors can be found by a single lookup into a table indexed by p%720.
Can we test greater than 16? may be upto 1000?
Here is an idea that you can use to calculate small factors and not use alot of memory.
-create an array and store all the values in it. (array_n=3,4,5,8,....)
-For current prime calculate p%array_n=p%3,P%4... (array_p)
-once done with current prime, find next prime and calculate the difference since the last prime
So array_p= (array_p+diff)%array_n
You will be doing some modular additions, approx 200 of them.. should not slow program down very much.

Basically we only need to look at primes in which work done is less than 256 steps.
Work done = 2*sqrt(factor1)+2*sqrt(factor2)+...2*sqrt(bpgs size)
So you can calcualate workdone for factors less than 1000 and for the rest can be done via BSGS. But only those numbers where work done is less than 256 helps.

Alternatively you can just calculate p%all primes 1-1000 and if a prime divides p then test prime^2 and so on. so if p%2==0, test p%4==0 and then p%8==0 and continue...
Then do BSGS on remaining portion.
Main point is to test only those primes that have work done to be less than 256.

Another speed up is in Sieve of Eratosthenes, is to only generate primes that have work to be done less than 256. So you don't have to waste time filtering candidates to test.

This should speed things up.
(I hope this makes sense, sorry the post got a little bit unorganized).

Last fiddled with by Citrix on 2007-05-18 at 03:55
Citrix is offline   Reply With Quote
Old 2007-05-20, 08:41   #19
Citrix
 
Citrix's Avatar
 
Jun 2003

62616 Posts
Default

Geoff,

Just to clarify some stuff.
Your program needs to find all factors less than 12.(at bare minimum)

so 2,3,5,7,11 and higher powers of 2 and 3 only. Program can look at bitmap of p-1 in base 2 and base 3 to figure this out.

The more factors and their higher powers you can include, the better it is, but the program should not slow down considerably. With this limited range we can do some preliminary testing.

This portion should be done using SPH.
The remaining needs to be done using BSGS.
The total work done for any prime should not exceed 256.

It would be really nice if the user could choose these values per run. Since these values will vary from project to project.

Using this we will be able to look at 20% of the factors. I have a 80 Kb file that contains about 25,000 numbers.. which you can use for the sieve step, so you don't have to filter numbers by calculating square roots. Let me know if you need it?

Infact if you could just add step #3 (The total work done for any prime should not exceed 256.) into your program and change nothing else, we can do some preliminary testing.


Thanks

edit: 256 cutoff is for a range of 2.5M. For a 50M range as PSP uses the cutoff will be 4000. (testing 79% primes). If possible could you implement both or give the user a choice of the cutoff.

Last fiddled with by Citrix on 2007-05-20 at 09:36
Citrix is offline   Reply With Quote
Old 2007-05-21, 03:54   #20
Citrix
 
Citrix's Avatar
 
Jun 2003

157410 Posts
Default

On further analysis we only need to look at factorization of p-1%720.

Here is p-1%720 and the amount of work needs to be done. So depending on the cutoff the user chooses you only need to look at certain values. This is for n=50M. I can generate this for any value needed.

Code:
p-1%720 work done
2 10006
4 7079
6 5781
8 5009
10 4482
12 4092
14 3790
16 3547
18 3347
20 3176
22 3029
24 2900
26 2788
28 2687
30 2596
32 2516
34 10005
36 2372
38 10005
40 2252
42 2198
44 2148
46 10005
48 2058
50 2016
52 1978
54 1940
56 1906
58 10005
60 1842
62 10005
64 1785
66 1756
68 7079
70 1707
72 1682
74 10005
76 7079
78 1618
80 1599
82 10005
84 1560
86 10005
88 1524
90 1507
92 7079
94 10005
96 1461
98 1446
100 1434
102 5781
104 1404
106 10005
108 1378
110 1366
112 1355
114 5781
116 7079
118 10005
120 1308
122 10005
124 7079
126 1278
128 1269
130 1259
132 1248
134 10005
136 5008
138 5781
140 1214
142 10005
144 1198
146 10005
148 7079
150 1173
152 5008
154 1158
156 1151
158 10005
160 1138
162 1132
164 7079
166 10005
168 1110
170 4482
172 7079
174 5781
176 1086
178 10005
180 1073
182 1068
184 5008
186 5781
188 7079
190 4482
192 1040
194 10005
196 1032
198 1027
200 1022
202 10005
204 4092
206 10005
208 1001
210 995
212 7079
214 10005
216 984
218 10005
220 975
222 5781
224 965
226 10005
228 4092
230 4482
232 5008
234 947
236 7079
238 3790
240 933
242 3029
244 7079
246 5781
248 5008
250 2016
252 913
254 10005
256 906
258 5781
260 900
262 10005
264 892
266 3790
268 7079
270 883
272 3547
274 10005
276 4092
278 10005
280 868
282 5781
284 7079
286 859
288 857
290 4482
292 7079
294 847
296 5008
298 10005
300 839
302 10005
304 3547
306 3347
308 828
310 4482
312 823
314 10005
316 7079
318 5781
320 814
322 3790
324 808
326 10005
328 5008
330 801
332 7079
334 10005
336 795
338 2788
340 3176
342 3347
344 5008
346 10005
348 4092
350 1707
352 777
354 5781
356 7079
358 10005
360 768
362 10005
364 765
366 5781
368 3547
370 4482
372 4092
374 3029
376 5008
378 751
380 3176
382 10005
384 745
386 10005
388 7079
390 740
392 738
394 10005
396 733
398 10005
400 1599
402 5781
404 7079
406 3790
408 2900
410 4482
412 7079
414 3347
416 718
418 3029
420 714
422 10005
424 5008
426 5781
428 7079
430 4482
432 705
434 3790
436 7079
438 5781
440 698
442 2788
444 4092
446 10005
448 693
450 690
452 7079
454 10005
456 2900
458 10005
460 3176
462 681
464 3547
466 10005
468 677
470 4482
472 5008
474 5781
476 2687
478 10005
480 670
482 10005
484 2147
486 1132
488 5008
490 662
492 4092
494 2788
496 3547
498 5781
500 1434
502 10005
504 653
506 3029
508 7079
510 2596
512 649
514 10005
516 4092
518 3790
520 645
522 3347
524 7079
526 10005
528 640
530 4482
532 2687
534 5781
536 5008
538 10005
540 632
542 10005
544 2515
546 630
548 7079
550 627
552 2900
554 10005
556 7079
558 3347
560 622
562 10005
564 4092
566 10005
568 5008
570 2596
572 616
574 3790
576 614
578 10005
580 3176
582 5781
584 5008
586 10005
588 607
590 4482
592 3547
594 604
596 7079
598 2788
600 602
602 3790
604 7079
606 5781
608 2515
610 4482
612 2372
614 10005
616 594
618 5781
620 3176
622 10005
624 592
626 10005
628 7079
630 588
632 5008
634 10005
636 4092
638 3029
640 585
642 5781
644 2687
646 10005
648 579
650 579
652 7079
654 5781
656 3547
658 3790
660 575
662 10005
664 5008
666 3347
668 7079
670 4482
672 571
674 10005
676 1978
678 5781
680 2252
682 3029
684 2372
686 1446
688 3547
690 2596
692 7079
694 10005
696 2900
698 10005
700 559
702 558
704 558
706 10005
708 4092
710 4482
712 5008
714 2198
716 7079
718 10005
720 553
Here is the savings at different cutoff's

Code:
cutoff Speed up in time per factor  %of prime looked at
10000 1.38698 80
7078 1.66448 70
5780 1.89791 63
5008 1.91563 63
5007 2.11982 58
4481 2.32368 54
4091 2.52119 51
3789 2.68082 48
3546 2.8217 45
3346 2.96318 43
3175 3.14768 42
3028 3.32137 40
2899 3.40677 38
2787 3.59237 37
2686 3.73418 36
2595 3.88714 35
2515 3.95489 35
2514 3.98061 34
2371 4.07149 33
2251 4.21509 33
2197 4.23308 32
2147 4.30813 32
2057 4.32357 31
2015 4.47795 31
1977 4.49083 30
1939 4.57224 30
1905 4.65514 30
1784 4.66079 29
1755 4.74285 29
1681 4.82589 28
1617 4.90984 28
1559 4.98971 27
1460 5.06256 26
1433 5.22728 25
1403 5.32309 25
1354 5.39906 24
1268 5.46464 23
1258 5.56673 23
1197 5.63048 22
1150 5.68516 21
1137 5.79461 21
1109 5.85274 20
1085 5.96904 20
1039 6.02104 19
1021 6.06733 18
1000 6.19549 18
974 6.24028 17
932 6.27497 16
912 6.41581 16
891 6.44211 15
882 6.59546 15
856 6.61666 14
827 6.62676 13
822 6.8017 13
800 6.8076 12
764 6.99579 11
737 7.19402 10
689 7.36305 8
644 7.47925 6
626 7.72594 5
593 7.77084 3
If you can extend your code beyond 16... we can have a much larger speed up.

If we only look at 4x+1 as you suggested we would be 1.4 (sqrt 2) times faster. So find 1.4 times as many factors per day. So if we are looking for 4x+1 do we use SPH upto 4*360=720*2=1440? If we only look at 16x+1 then we are 2.75 times faster.

But if you could use any of the above cutoff's then it would help more than restricting to 4x+1.

The best thing would be to give the user the choice of n in 2^n*x+1 and then looking at 2^n*360 values deep. For the 360 values giving the user a choice of min cutoff and max cutoff and look in that range of cutoff.

Last fiddled with by Citrix on 2007-05-21 at 21:04
Citrix is offline   Reply With Quote
Old 2007-05-22, 02:30   #21
geoff
 
geoff's Avatar
 
Mar 2003
New Zealand

115710 Posts
Default

Sorry I have not had time to do much with this. There is a modified sr2sieve here that accepts a -y switch: `sr2sieve -y Y ...' will only use numbers p=1 (mod 2^Y) in the Sieve of Eratosthenes.

A little testing shows that with Y=2 (so p=4x+1) the sieve speed on the comibed SoB.dat goes from 100 kp/s to 250 kp/s, so it should find 50% of the factors in only 40% of the time.

I haven't checked all of the possible overflow conditions, so there may be bugs if large values of Y are used.

It is easy to extend the power residue tests: To add tests for 32nd power residues just increase the value of LIMIT_BASE and POWER_RESIDUE_LCM in sr5sieve.h from 720 to 1440, and set the POWER_RESIDUE_DIVISORS to 60 (the number of divisors of 1440). The problem is that this will dramatically increase memory use and initialisation time as the value increases, but testing 256th power residues might be feasible.

(Actually some earlier testing showed that increasing to 1440 was faster for SoB.dat anyway, but it was slower for riesel.dat and sr5data.txt so I made 720 the default).

Adding 7th and 11th power residues as well would be possible in principle, but I think the extra memory used would make it impractical. The memory is used for lists of subsequences, and even if there is enough it will become very fragmented.
geoff is offline   Reply With Quote
Old 2007-05-22, 02:55   #22
Citrix
 
Citrix's Avatar
 
Jun 2003

2×787 Posts
Default

Thank you for the program, I will test it a little. Any chance of implementing the cutoff model I posted above?
Could you provide the power residue stuff as a switch, I don't know how to compile sr5sieve under windows. Anyone know how to?

Last fiddled with by Citrix on 2007-05-22 at 07:30
Citrix is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Windows 10 in Ubuntu, good idea, bad idea, or...? jasong jasong 8 2017-04-07 00:23
Idea (as always) Dubslow Forum Feedback 7 2016-12-02 14:26
Advantage of lattice sieve over line sieve binu Factoring 3 2013-04-13 16:32
idea ? science_man_88 Homework Help 0 2010-04-23 16:33
An Idea ThomRuley Lone Mersenne Hunters 5 2003-07-15 05:51

All times are UTC. The time now is 22:50.

Tue Oct 20 22:50:45 UTC 2020 up 40 days, 20:01, 0 users, load averages: 1.90, 2.26, 2.11

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.