Menu
▾
▴
Tree [f4c3ea] default tip / History
Read Me
This is a fork of Colin Benner's Frobenius benchmarking. https://github.com/yzhs/frobenius-test The intent here is more of a testbed for comparing the efficacy of certain routines, i.e. are they accurate? are they fast? The Quadratic Frobenius (primality) Test, QFT, developed by Grantham requires testing for squares at the outset and also recommends sieving with small primes -- Benner uses 49999, and I go to 50599. Both these steps are relatively slow. In another project, Hash-val-4-Bloom, filters were developed that can reduce the number of square-root evaluations significantly. Those are tested here. In yet another project, effort was put in to partitioning the small primes in order to minimize the number of divisions (and thereby reduce run-time). Further effort here was put in to parallelize sieving. The square root routine does show potential, but is decidedly slower than GMP's built-in mpz_perfect_square_p(). The parallel sieve is faster than a serial version, but appears to be merely equal if not slower than just repetitive mpz_divisible_p(). Lastly, the mpz_probab_prime_p() uses the Baillie-PSW test and is properly optimized. So the QFT, as written here, does not compare well against it. As a "testbed" while thought and effort was taken to make things fast it is not close to optimal. Recall B. Kernighan's wisdom (and I paraphrase) "make it run, make it right, make it fast." So ... this runs 8)
