For my application (an ethereum miner), the prime check is only necessary when generating a cache and DAG, which is about every 5 days (or every time the miner application is restarted). I am curious to see how you implemented the table lookup. Is the code posted somewhere?
On Sunday, 4 March 2018 09:54:32 UTC-4, Michael Jones wrote: > > ProbablyPrime() is for when the number is too big to test authoritatively. > For numbers smaller than that, there are two schools of thought. > > The first is to do what you did, doing a primality test for the number at > hand. > > The second is to use a table of results.The table generally needs to be of > size N bits, square root (N) bits, or cube root N bits long depending on > how much work you are willing to do for each lookup. The Goldilocks size of > sqrt is generally best, so for 2^32 that's 2^16 ==> less than 8k bytes. > This is small enough that one might have a static table and just use it for > 1-2ns prime tests in 0<N<2^32. Or you can build it. My code > takes 25538575ns which is ~1/39th of a second. This is easily done in an > init() function. > > The fastest way is determined by the number of different values that you > need to test. > > On Sun, Mar 4, 2018 at 1:40 AM, Jan Mercl <0xj...@gmail.com <javascript:>> > wrote: > >> On Sun, Mar 4, 2018 at 7:27 AM <ralphdo...@gmail.com <javascript:>> >> wrote: >> >> > It still has room for optimization, but it is much faster than >> ProbablyPrime(0) for 32-bit integers. >> > >> http://nerdralph.blogspot.ca/2018/03/fast-small-prime-checker-in-golang.html >> >> You may want to give the primality checking functions of >> http://github.com/cznic/mathutil a try. >> >> Running at a Intel® Core™ i5-4670 CPU @ 3.40GHz × 4 machine: >> >> ~/src/github.com/cznic/mathutil> go test -v -run @ -bench IsPrime |& tee >> log >> goos: linux >> goarch: amd64 >> pkg: github.com/cznic/mathutil >> BenchmarkIsPrime-4 20000000 70.2 ns/op >> BenchmarkIsPrimeUint64-4 500000 2558 ns/op >> BenchmarkIsPrimeUint16-4 2000000000 0.28 ns/op >> PASS >> ok github.com/cznic/mathutil 23.360s >> ~/src/github.com/cznic/mathutil> >> >> -- >> >> -j >> >> -- >> You received this message because you are subscribed to the Google Groups >> "golang-nuts" group. >> To unsubscribe from this group and stop receiving emails from it, send an >> email to golang-nuts...@googlegroups.com <javascript:>. >> For more options, visit https://groups.google.com/d/optout. >> > > > > -- > Michael T. Jones > michae...@gmail.com <javascript:> > -- You received this message because you are subscribed to the Google Groups "golang-nuts" group. To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
