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.
