Does anyone know how Nicely's code works. Does it actually contain a BPSW test? I see an extra strong Lucas test. Is that it or is it the strong Lucas-Selfridge test?
Assuming it is the strong Lucas-Selfridge test, here are the times: 1) primes is_probabprime_BPSW: bits = 1, min time is 61.985 cycles, max time is 62.614 cycles bits = 2, min time is 527.511 cycles, max time is 5794.675 cycles bits = 3, min time is 3663.343 cycles, max time is 3687.511 cycles bits = 4, min time is 4294.546 cycles, max time is 4968.830 cycles bits = 5, min time is 3340.450 cycles, max time is 7610.115 cycles bits = 6, min time is 4843.608 cycles, max time is 8898.315 cycles bits = 7, min time is 4602.178 cycles, max time is 8144.019 cycles bits = 8, min time is 5991.857 cycles, max time is 10905.638 cycles bits = 9, min time is 9210.771 cycles, max time is 9667.430 cycles bits = 10, min time is 10746.994 cycles, max time is 12086.393 cycles bits = 11, min time is 11384.925 cycles, max time is 12423.267 cycles bits = 12, min time is 11719.608 cycles, max time is 14783.253 cycles bits = 13, min time is 12960.525 cycles, max time is 16329.370 cycles bits = 14, min time is 15416.198 cycles, max time is 19028.253 cycles bits = 15, min time is 15875.115 cycles, max time is 18912.795 cycles bits = 16, min time is 17351.400 cycles, max time is 19415.205 cycles bits = 17, min time is 14884.879 cycles, max time is 23171.126 cycles bits = 18, min time is 18249.552 cycles, max time is 24481.687 cycles bits = 19, min time is 16524.305 cycles, max time is 25484.811 cycles bits = 20, min time is 19145.499 cycles, max time is 25808.695 cycles bits = 21, min time is 21565.467 cycles, max time is 25776.237 cycles bits = 22, min time is 22635.634 cycles, max time is 28931.901 cycles bits = 23, min time is 23726.787 cycles, max time is 27372.267 cycles bits = 24, min time is 25403.599 cycles, max time is 31869.257 cycles bits = 25, min time is 26707.197 cycles, max time is 30901.039 cycles bits = 26, min time is 28002.360 cycles, max time is 34222.443 cycles bits = 27, min time is 26586.521 cycles, max time is 35404.423 cycles bits = 28, min time is 26935.495 cycles, max time is 32165.829 cycles bits = 29, min time is 28738.478 cycles, max time is 33661.467 cycles bits = 30, min time is 30764.129 cycles, max time is 38157.429 cycles bits = 31, min time is 31418.702 cycles, max time is 41914.745 cycles bits = 32, min time is 34986.466 cycles, max time is 40663.985 cycles bits = 33, min time is 33149.081 cycles, max time is 38600.911 cycles bits = 34, min time is 36955.474 cycles, max time is 44849.733 cycles bits = 35, min time is 38962.378 cycles, max time is 44244.165 cycles bits = 36, min time is 38973.405 cycles, max time is 50842.834 cycles bits = 37, min time is 40406.078 cycles, max time is 51502.526 cycles bits = 38, min time is 45536.006 cycles, max time is 52824.271 cycles bits = 39, min time is 43522.231 cycles, max time is 51041.969 cycles bits = 40, min time is 45643.077 cycles, max time is 52261.289 cycles bits = 41, min time is 46506.247 cycles, max time is 59813.040 cycles bits = 42, min time is 48651.298 cycles, max time is 55844.345 cycles bits = 43, min time is 47439.573 cycles, max time is 57396.933 cycles bits = 44, min time is 48550.958 cycles, max time is 57405.117 cycles bits = 45, min time is 49595.547 cycles, max time is 64121.119 cycles bits = 46, min time is 55459.707 cycles, max time is 62772.953 cycles bits = 47, min time is 54178.707 cycles, max time is 65096.654 cycles bits = 48, min time is 54454.526 cycles, max time is 62244.953 cycles bits = 49, min time is 54683.784 cycles, max time is 71340.881 cycles bits = 50, min time is 56204.393 cycles, max time is 65542.275 cycles bits = 51, min time is 52629.024 cycles, max time is 66244.498 cycles bits = 52, min time is 61295.839 cycles, max time is 65937.984 cycles bits = 53, min time is 59369.534 cycles, max time is 69865.293 cycles bits = 54, min time is 59775.480 cycles, max time is 67337.133 cycles bits = 55, min time is 63530.397 cycles, max time is 74050.306 cycles bits = 56, min time is 57579.288 cycles, max time is 70048.920 cycles bits = 57, min time is 64289.054 cycles, max time is 73008.003 cycles bits = 58, min time is 70346.503 cycles, max time is 74402.325 cycles bits = 59, min time is 61098.374 cycles, max time is 81539.259 cycles bits = 60, min time is 70055.465 cycles, max time is 76438.111 cycles bits = 61, min time is 72445.190 cycles, max time is 81103.286 cycles bits = 62, min time is 75068.187 cycles, max time is 82614.466 cycles bits = 63, min time is 72253.289 cycles, max time is 79274.808 cycles bits = 64, min time is 73485.597 cycles, max time is 84383.547 cycles 2) composites is_probabprime_BPSW: bits = 1, min time is 67.127 cycles, max time is 68.572 cycles bits = 2, min time is 5840.527 cycles, max time is 6012.120 cycles bits = 3, min time is 1716.754 cycles, max time is 6751.834 cycles bits = 4, min time is 363.321 cycles, max time is 5304.542 cycles bits = 5, min time is 527.223 cycles, max time is 3934.059 cycles bits = 6, min time is 2056.917 cycles, max time is 6729.626 cycles bits = 7, min time is 1399.546 cycles, max time is 5922.934 cycles bits = 8, min time is 6160.251 cycles, max time is 9922.790 cycles bits = 9, min time is 728.931 cycles, max time is 5263.279 cycles bits = 10, min time is 557.493 cycles, max time is 4596.654 cycles bits = 11, min time is 719.321 cycles, max time is 7177.680 cycles bits = 12, min time is 477.325 cycles, max time is 6349.264 cycles bits = 13, min time is 655.865 cycles, max time is 13961.245 cycles bits = 14, min time is 746.582 cycles, max time is 12047.142 cycles bits = 15, min time is 716.002 cycles, max time is 9826.946 cycles bits = 16, min time is 720.269 cycles, max time is 11631.801 cycles bits = 17, min time is 1020.101 cycles, max time is 19122.103 cycles bits = 18, min time is 961.358 cycles, max time is 13265.433 cycles bits = 19, min time is 473.537 cycles, max time is 21392.174 cycles bits = 20, min time is 10946.160 cycles, max time is 22015.622 cycles bits = 21, min time is 12148.591 cycles, max time is 26378.691 cycles bits = 22, min time is 8718.905 cycles, max time is 27389.578 cycles bits = 23, min time is 476.465 cycles, max time is 18610.256 cycles bits = 24, min time is 708.537 cycles, max time is 10990.865 cycles bits = 25, min time is 720.973 cycles, max time is 31767.435 cycles bits = 26, min time is 477.275 cycles, max time is 31715.201 cycles bits = 27, min time is 1391.393 cycles, max time is 27912.802 cycles bits = 28, min time is 10150.374 cycles, max time is 37506.648 cycles bits = 29, min time is 721.102 cycles, max time is 35302.515 cycles bits = 30, min time is 364.629 cycles, max time is 20789.167 cycles bits = 31, min time is 1097.990 cycles, max time is 39989.381 cycles bits = 32, min time is 552.910 cycles, max time is 38937.471 cycles bits = 33, min time is 901.282 cycles, max time is 31816.863 cycles bits = 34, min time is 13799.058 cycles, max time is 40163.921 cycles bits = 35, min time is 1162.162 cycles, max time is 20972.737 cycles bits = 36, min time is 14745.903 cycles, max time is 46513.869 cycles bits = 37, min time is 944.328 cycles, max time is 43435.270 cycles bits = 38, min time is 481.848 cycles, max time is 51622.586 cycles bits = 39, min time is 1402.947 cycles, max time is 23844.597 cycles bits = 40, min time is 1653.463 cycles, max time is 56029.587 cycles bits = 41, min time is 714.900 cycles, max time is 54112.584 cycles bits = 42, min time is 487.468 cycles, max time is 55815.712 cycles bits = 43, min time is 26897.830 cycles, max time is 54086.009 cycles bits = 44, min time is 2416.046 cycles, max time is 57456.274 cycles bits = 45, min time is 15769.202 cycles, max time is 55384.546 cycles bits = 46, min time is 1090.282 cycles, max time is 59227.625 cycles bits = 47, min time is 20467.273 cycles, max time is 59844.005 cycles bits = 48, min time is 20352.187 cycles, max time is 39489.627 cycles bits = 49, min time is 20038.603 cycles, max time is 22440.901 cycles bits = 50, min time is 31371.554 cycles, max time is 66357.717 cycles bits = 51, min time is 21082.753 cycles, max time is 67786.697 cycles bits = 52, min time is 718.490 cycles, max time is 65116.354 cycles bits = 53, min time is 22242.149 cycles, max time is 72314.181 cycles bits = 54, min time is 19225.343 cycles, max time is 74030.489 cycles bits = 55, min time is 1408.615 cycles, max time is 62320.858 cycles bits = 56, min time is 2011.250 cycles, max time is 71306.043 cycles bits = 57, min time is 715.596 cycles, max time is 48666.426 cycles bits = 58, min time is 1411.025 cycles, max time is 36619.221 cycles bits = 59, min time is 2130.261 cycles, max time is 79684.191 cycles bits = 60, min time is 1524.660 cycles, max time is 53533.928 cycles bits = 61, min time is 24257.240 cycles, max time is 78399.051 cycles bits = 62, min time is 23054.922 cycles, max time is 77868.319 cycles bits = 63, min time is 503.802 cycles, max time is 85392.977 cycles bits = 64, min time is 28290.290 cycles, max time is 55160.521 cycles This looks much worse, but then again, I have no idea whether I am supposed to be setting some #defines or what. Bill. 2009/12/4 Bill Hart <[email protected]>: > Whoops, I forgot to mention, being profiling code, it averages out > over lots of random values. So the min time there is not actually the > minimum time to check primality or otherwise of n, but the minimum > time the profile run takes. > > Each timing run works with sufficiently many *different* random values > n until a timing run takes a measurable amount of time, say 0.2s. But > for each n tried, the primality test is run on that same n 1000 times > and averaged over that 1000. > > For a higher number of bits there begins to be quite a lot of > difference in min and max because it needs to do very few timing runs > (i.e. use very few different values of n) to get a significant amount > of accumulated time. Thus it is only testing primality of relatively > few different values of n. Thus the values it chooses become > progressively more important in determining how long it takes, hence > the variability in timing. > > If I increase that 1000 to 1000000 then the composite min goes down to > 12 cycles for each bit size, because the minimum time is the time it > takes to check that an even number is not prime. If I decrease the > 1000 to about 3 then the max times become more accurate (but not > substantially different from what I reported). > > Bill. > > 2009/12/4 Bill Hart <[email protected]>: >> OK, I think I now have profiles for the BPSW test in FLINT-Lite for 1 >> to 64 bits: >> >> 1) n = n_randbits(bits); n = n_nextprime(n); - prime >> >> is_probabprime_BPSW: >> bits = 1, min time is 41.318 cycles, max time is 41.762 cycles >> bits = 2, min time is 157.077 cycles, max time is 211.797 cycles >> bits = 3, min time is 1521.374 cycles, max time is 1737.195 cycles >> bits = 4, min time is 1671.113 cycles, max time is 2991.291 cycles >> bits = 5, min time is 1837.207 cycles, max time is 3277.498 cycles >> bits = 6, min time is 2361.549 cycles, max time is 2907.369 cycles >> bits = 7, min time is 2688.065 cycles, max time is 4432.293 cycles >> bits = 8, min time is 3019.783 cycles, max time is 5556.871 cycles >> bits = 9, min time is 3405.127 cycles, max time is 5785.951 cycles >> bits = 10, min time is 1410.274 cycles, max time is 6117.360 cycles >> bits = 11, min time is 1367.475 cycles, max time is 1913.774 cycles >> bits = 12, min time is 1709.866 cycles, max time is 2046.679 cycles >> bits = 13, min time is 1445.799 cycles, max time is 2280.487 cycles >> bits = 14, min time is 1577.479 cycles, max time is 2475.494 cycles >> bits = 15, min time is 1622.289 cycles, max time is 1957.071 cycles >> bits = 16, min time is 1777.970 cycles, max time is 2261.688 cycles >> bits = 17, min time is 1819.906 cycles, max time is 2252.343 cycles >> bits = 18, min time is 1949.441 cycles, max time is 2763.886 cycles >> bits = 19, min time is 2052.178 cycles, max time is 2462.383 cycles >> bits = 20, min time is 2169.075 cycles, max time is 2770.822 cycles >> bits = 21, min time is 2307.915 cycles, max time is 3253.845 cycles >> bits = 22, min time is 2446.937 cycles, max time is 3018.096 cycles >> bits = 23, min time is 2471.630 cycles, max time is 3165.302 cycles >> bits = 24, min time is 2614.217 cycles, max time is 3080.465 cycles >> bits = 25, min time is 2748.463 cycles, max time is 3541.913 cycles >> bits = 26, min time is 2836.793 cycles, max time is 3259.786 cycles >> bits = 27, min time is 3006.309 cycles, max time is 3405.096 cycles >> bits = 28, min time is 3183.096 cycles, max time is 4558.008 cycles >> bits = 29, min time is 3315.902 cycles, max time is 4838.030 cycles >> bits = 30, min time is 3747.024 cycles, max time is 4762.286 cycles >> bits = 31, min time is 3831.069 cycles, max time is 5121.367 cycles >> bits = 32, min time is 3955.632 cycles, max time is 4833.267 cycles >> bits = 33, min time is 4003.467 cycles, max time is 4496.352 cycles >> bits = 34, min time is 4129.584 cycles, max time is 4987.810 cycles >> bits = 35, min time is 4202.160 cycles, max time is 4850.853 cycles >> bits = 36, min time is 4701.710 cycles, max time is 5708.133 cycles >> bits = 37, min time is 4661.753 cycles, max time is 5524.591 cycles >> bits = 38, min time is 4826.417 cycles, max time is 5515.176 cycles >> bits = 39, min time is 4928.194 cycles, max time is 5641.893 cycles >> bits = 40, min time is 5265.761 cycles, max time is 6197.842 cycles >> bits = 41, min time is 4956.504 cycles, max time is 6786.573 cycles >> bits = 42, min time is 4950.806 cycles, max time is 5951.421 cycles >> bits = 43, min time is 5412.518 cycles, max time is 5977.817 cycles >> bits = 44, min time is 5580.165 cycles, max time is 6455.061 cycles >> bits = 45, min time is 5759.976 cycles, max time is 6370.485 cycles >> bits = 46, min time is 5721.984 cycles, max time is 6381.789 cycles >> bits = 47, min time is 5907.189 cycles, max time is 6853.471 cycles >> bits = 48, min time is 6104.880 cycles, max time is 6870.645 cycles >> bits = 49, min time is 6088.687 cycles, max time is 6453.665 cycles >> bits = 50, min time is 6301.347 cycles, max time is 7475.510 cycles >> bits = 51, min time is 6440.674 cycles, max time is 6915.634 cycles >> bits = 52, min time is 6693.151 cycles, max time is 6843.871 cycles >> bits = 53, min time is 6810.957 cycles, max time is 8321.763 cycles >> bits = 54, min time is 7275.977 cycles, max time is 8676.069 cycles >> bits = 55, min time is 7425.243 cycles, max time is 8833.807 cycles >> bits = 56, min time is 7752.353 cycles, max time is 8618.054 cycles >> bits = 57, min time is 7959.816 cycles, max time is 9656.907 cycles >> bits = 58, min time is 7891.286 cycles, max time is 9424.985 cycles >> bits = 59, min time is 8092.786 cycles, max time is 8531.602 cycles >> bits = 60, min time is 8056.872 cycles, max time is 9400.306 cycles >> bits = 61, min time is 8154.384 cycles, max time is 8729.301 cycles >> bits = 62, min time is 8474.393 cycles, max time is 9675.010 cycles >> bits = 63, min time is 8511.110 cycles, max time is 8839.827 cycles >> bits = 64, min time is 8542.951 cycles, max time is 9547.522 cycles >> >> 2) n = n_randbits(bits) - likely composite >> >> is_probabprime_BPSW: >> bits = 1, min time is 12.060 cycles, max time is 44.057 cycles >> bits = 2, min time is 56.064 cycles, max time is 78.749 cycles >> bits = 3, min time is 262.825 cycles, max time is 443.345 cycles >> bits = 4, min time is 203.246 cycles, max time is 529.206 cycles >> bits = 5, min time is 353.365 cycles, max time is 597.048 cycles >> bits = 6, min time is 301.952 cycles, max time is 573.333 cycles >> bits = 7, min time is 330.889 cycles, max time is 781.560 cycles >> bits = 8, min time is 249.096 cycles, max time is 577.418 cycles >> bits = 9, min time is 369.734 cycles, max time is 537.382 cycles >> bits = 10, min time is 276.715 cycles, max time is 599.738 cycles >> bits = 11, min time is 327.437 cycles, max time is 1928.085 cycles >> bits = 12, min time is 373.757 cycles, max time is 681.569 cycles >> bits = 13, min time is 182.665 cycles, max time is 461.024 cycles >> bits = 14, min time is 502.922 cycles, max time is 1777.234 cycles >> bits = 15, min time is 520.193 cycles, max time is 1217.526 cycles >> bits = 16, min time is 403.329 cycles, max time is 2065.738 cycles >> bits = 17, min time is 313.534 cycles, max time is 1128.306 cycles >> bits = 18, min time is 262.136 cycles, max time is 1009.343 cycles >> bits = 19, min time is 485.613 cycles, max time is 2158.387 cycles >> bits = 20, min time is 492.557 cycles, max time is 1245.614 cycles >> bits = 21, min time is 532.513 cycles, max time is 1399.498 cycles >> bits = 22, min time is 535.313 cycles, max time is 1090.943 cycles >> bits = 23, min time is 245.650 cycles, max time is 1710.942 cycles >> bits = 24, min time is 589.800 cycles, max time is 1571.771 cycles >> bits = 25, min time is 432.478 cycles, max time is 1083.027 cycles >> bits = 26, min time is 278.344 cycles, max time is 2596.626 cycles >> bits = 27, min time is 349.594 cycles, max time is 918.408 cycles >> bits = 28, min time is 728.091 cycles, max time is 2080.855 cycles >> bits = 29, min time is 487.606 cycles, max time is 1466.496 cycles >> bits = 30, min time is 400.691 cycles, max time is 1680.162 cycles >> bits = 31, min time is 722.897 cycles, max time is 3292.601 cycles >> bits = 32, min time is 552.791 cycles, max time is 1608.576 cycles >> bits = 33, min time is 585.089 cycles, max time is 2224.639 cycles >> bits = 34, min time is 586.112 cycles, max time is 1634.890 cycles >> bits = 35, min time is 603.511 cycles, max time is 2306.277 cycles >> bits = 36, min time is 624.701 cycles, max time is 1864.858 cycles >> bits = 37, min time is 610.523 cycles, max time is 2245.095 cycles >> bits = 38, min time is 674.256 cycles, max time is 1864.166 cycles >> bits = 39, min time is 501.079 cycles, max time is 1884.893 cycles >> bits = 40, min time is 1078.399 cycles, max time is 1966.539 cycles >> bits = 41, min time is 537.093 cycles, max time is 2086.663 cycles >> bits = 42, min time is 736.394 cycles, max time is 2178.257 cycles >> bits = 43, min time is 1111.378 cycles, max time is 2823.583 cycles >> bits = 44, min time is 558.648 cycles, max time is 2281.134 cycles >> bits = 45, min time is 572.550 cycles, max time is 1543.973 cycles >> bits = 46, min time is 599.135 cycles, max time is 2606.099 cycles >> bits = 47, min time is 597.096 cycles, max time is 2440.546 cycles >> bits = 48, min time is 1186.891 cycles, max time is 4610.604 cycles >> bits = 49, min time is 855.699 cycles, max time is 3669.195 cycles >> bits = 50, min time is 669.112 cycles, max time is 2666.518 cycles >> bits = 51, min time is 1299.735 cycles, max time is 2758.073 cycles >> bits = 52, min time is 1332.624 cycles, max time is 3731.018 cycles >> bits = 53, min time is 1030.674 cycles, max time is 3372.115 cycles >> bits = 54, min time is 1466.748 cycles, max time is 3175.947 cycles >> bits = 55, min time is 1093.359 cycles, max time is 3165.907 cycles >> bits = 56, min time is 1501.320 cycles, max time is 7656.775 cycles >> bits = 57, min time is 1521.972 cycles, max time is 3303.411 cycles >> bits = 58, min time is 3246.638 cycles, max time is 3471.531 cycles >> bits = 59, min time is 1650.977 cycles, max time is 8608.049 cycles >> bits = 60, min time is 1619.892 cycles, max time is 3515.671 cycles >> bits = 61, min time is 1690.850 cycles, max time is 3546.489 cycles >> bits = 62, min time is 1686.543 cycles, max time is 3602.791 cycles >> bits = 63, min time is 1757.700 cycles, max time is 8525.469 cycles >> bits = 64, min time is 1867.281 cycles, max time is 3722.457 cycles >> >> Of course these "composite" times would be a lot lower if trial >> factoring were performed first (a factor of 2 is checked for already). >> >> In FLINT-Lite the likely_prime function first checks for perfect >> powers, which is super quick, then does a full primality test up to >> 10^16 using known combinations of bases for strong pseudoprimes. This >> is actually slower than doing a BPSW test as above, from about 24 bits >> up to 10^16 by a factor of up to 2, but the result is guaranteed up to >> that limit. From 10^16 it just runs a BPSW test from there on. >> >> For MPIR I guess we may as well just do trial division, then do BPSW, >> then over GMP_NUMB_BITS bits just do about 12 strong pseudo prime >> tests to random bases, i.e. just loop what we currently do about 12 >> times. >> >> I'm not sure I understand exactly what check you did up to 2^64. Did >> you take all the (composite) base 2 strong pseudoprimes and then test >> that BPSW eliminates them all? If you consider that to be a reliable >> result, I could use this in FLINT-Lite to give a guaranteed primality >> test up to 2^64 could I not? Was there some trial factoring done >> first? If so, what was the limit? >> >> Bill. >> >> 2009/12/4 Bill Hart <[email protected]>: >>> I've actually not done any timings of the BPSW code in FLINT. Using it >>> doesn't solve my problem, ha ha, but yeah we could use it in MPIR. I >>> consider it to be well tested by now. It is only for integers up to 64 >>> bits though (on a 64 bit machine). >>> >>> I'll run some timings on Selmer and post them. Perhaps we can get some >>> idea of how fast it is. The most optimised version is in FLINT Lite. >>> >>> Do we still have an optimised version of Nicely's code? I recall that >>> for the benchmark we were uninterested in all the optimisations, as >>> they weren't profiling MPIR itself, but Nicely's code. However I did >>> not keep track of whether we just benchmarked larger integers or >>> whether we hacked Nicely's code itself. >>> >>> Bill. >>> >>> 2009/12/4 Jeff Gilchrist <[email protected]>: >>>> On Fri, Dec 4, 2009 at 12:29 PM, Bill Hart <[email protected]> >>>> wrote: >>>>> Whoah, it just does trial division up to 1000 then uses a *single* >>>>> *random* base for a strong pseudoprime test! >>>>> >>>>> I have a definite problem with this. What is the probability of >>>>> returning a composite? Assuming the factors are bigger than 1000, it >>>>> is like 1/4. >>>> >>>> How fast is your BPSW code? From that project I have been working on >>>> I have confirmed there are no psp's up to 2^64 using BPSW so that >>>> should work quite well after the trial division assuming it doesn't >>>> take too long to run. >>>> >>>> Or we could even use the BPSW code from Thomas R. Nicely since he >>>> already gave us permission to use it for the benchmark code if it is >>>> faster than your implementation. >>>> >>>> Jeff. >>>> >>>> -- >>>> >>>> You received this message because you are subscribed to the Google Groups >>>> "mpir-devel" group. >>>> To post to this group, send email to [email protected]. >>>> To unsubscribe from this group, send email to >>>> [email protected]. >>>> For more options, visit this group at >>>> http://groups.google.com/group/mpir-devel?hl=en. >>>> >>>> >>>> >>> >> > -- You received this message because you are subscribed to the Google Groups "mpir-devel" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/mpir-devel?hl=en.
