Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- Since this horse has not been beaten to death yet, I'll follow up on a previous posting where I predicted that Drew's original code, and all the other versions I have looked at so far, would regret not cutting off the possible factors of the candidate for primeness at sqrt(candidate). I have a hunch that cutting and pasting what follows into a blog reply may look pretty doggy, so I'll try to get the non-timing content in early. Rather than print all of the first N primes, I just calculated them, and printed a short summary. Here, for N=1,000,000, is the summary, split over two lines to hedge against doggy appearance.
- p[1000000]=15485863
- (p[isq=546]=3943)**2=15547249
- The first line just asserts that the millionth prime is 15485863. The second line gets to the essence of cutting off search early. It says that the 546th prime is 3943. If a candidate is composite (not a prime), it has a factor, hence a *least* factor. If the *least* factor is 3943, then the candidate must be at least 3943*3943, which is 15547249. Stated differently, if the candidate is less than 15547249, if it doesn't have a factor less than 3943, it cannot have a factor at all, so it must be prime. As we get near the "end game" for the first million primes, all the algorithms I have seen so far (except mine) are checking for divisibility by nearly one million prime factors, all the (prime) elements of p discovered so far. I'm checking for 546 possible factors. I'm saving a lot of useless testing. The bigger N gets, the bigger the savings. Extra processors won't keep pace.
- In the timings that follow, there's a "stutter" at 2,000,000. That's because my program started dropping core when I tried to go above 1,000,000. I traced the blame to
- primes[0] = 2;
- a rather benign looking statement. It seems that attempting to allocate primes[N] on the stack for larger N makes the array unaddressable. I regard this as a borderline compiler error (It should be detectable at compile time), but I got around it by forcing 32-bit integers, which got me as far as 2,000,000 and even sped things up a bit. Then I realized it could be fixed by making the array external, so I restored the longer integer types, causing the slow-down at the new run for 2,000,000.
- I was able to push on for 10**7 and 10**8, but I lack the patience to try 10**9, particularly since my motivation was mostly to demonstrate the importance of algorithm over language.
- +Michael Murphy: I like the go code. I think it can be modified to do the sqrt pruning. Instead of pushing the filter onto the chain as soon as a new prime is identified, save the unpushed primes, and add them to the chain only when their square is (incorrectly) reported as a prime.
- real user sys
- primesp[20]=71 (p[isq=4]=11)**2=121 0m0.00s 0m0.00s 0m0.00s
- primesp[100]=541 (p[isq=9]=29)**2=841 0m0.00s 0m0.00s 0m0.00s
- primesp[1000]=7919 (p[isq=23]=89)**2=7921 0m0.00s 0m0.00s 0m0.00s
- primesp[10000]=104729 (p[isq=66]=331)**2=109561 0m0.00s 0m0.00s 0m0.00s
- primesp[100000]=1299709 (p[isq=189]=1151)**2=1324801 0m0.08s 0m0.08s 0m0.00s
- primesp[1000000]=15485863 (p[isq=546]=3943)**2=15547249 0m2.25s 0m2.24s 0m0.00s
- primesp[1000000]=15485863 (p[isq=546]=3943)**2=15547249 0m2.25s 0m2.24s 0m0.00s
- primesp[2000000]=32452843 (p[isq=750]=5701)**2=32501401 0m6.10s 0m6.09s 0m0.01s
- primesp[2000000]=32452843 (p[isq=750]=5701)**2=32501401 0m10.09s 0m10.08s 0m0.00s
- primesp[10000000]=179424673 (p[isq=1587]=13397)**2=179479609 1m42.51s 1m42.39s 0m0.08s
- primesp[100000000]=2038074743 (p[isq=4687]=45161)**2=2039515921 48m54.11s 48m50.69s 0m0.66s
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
