|
2007-05-14, 07:39
|
#13 | |
Jun 2005
37310 Posts |
Quote:
|
|
|
|
|
2007-05-14, 16:56
|
#14 |
Jul 2005
1100000102 Posts |
Shame I don't have any spare time at the moment!
|
|
|
|
|
2007-05-15, 01:11
|
#15 | |
Jun 2003
63316 Posts |
Quote:
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 |
|
|
|
|
|
2007-05-15, 13:24
|
#16 |
|
Jul 2005
6028 Posts |
For proth_sieve, ask the original author: Mikael Klasson, his email address (as given on his own web page) is: mklasson T acm.org
|
|
|
|
|
2007-05-17, 23:37
|
#17 | |
Mar 2003
New Zealand
48516 Posts |
Quote:
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. |
|
|
|
|
|
2007-05-18, 03:53
|
#18 | |
|
Jun 2003
3·232 Posts |
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:
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 |
|
|
|
|
|
2007-05-20, 08:41
|
#19 |
|
Jun 2003
63316 Posts |
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 |
|
|
|
|
2007-05-21, 03:54
|
#20 |
|
Jun 2003
3×232 Posts |
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 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 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 |
|
|
|
|
2007-05-22, 02:30
|
#21 |
|
Mar 2003
New Zealand
13×89 Posts |
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. |
|
|
|
|
2007-05-22, 02:55
|
#22 |
|
Jun 2003
30638 Posts |
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 |
|
|
|
 |
| 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 |
