Seth Troisi <brain...@gmail.com> writes: > In order to profile parts of this I also added tune/speed support for > mpz_nextprime > https://github.com/sethtroisi/libgmp/pull/6/files > Note that I change the behavior of s->size to mean size bits instead > of limbs for for measuring mpz_nextprime, as the function is slow (in the > worstcase it can take >5 second for a 1500 bit input, and >90 seconds for a > ~2700 bit input)
Good. I imagine mpz_nextprime performance has some room for improvement. For benchmarking, maybe one should use something other than arithmetic mean for averaging, since some numbers will be much slower than others? > For implementing mpz_prevprime, I tried to reuse as much code as possible > with a macro for the function body, I'm not sure how readable it ended up. > it also possible this could be speed up if I used separate code for each of > the functions, by calculating the negative modulo and using unsigned > integers everywhere. I'm open to hearing how folks thinks code could be > better reused / structured. Maybe it would make sense to generalize a bit further, and write a function to find the first prime (if any) in an arithmetic sequence. I.e., find the smallest k >= such that A + kB is prime (if any). A corresponds the current input to mpz_nextprime, and B could be either a signed long or a bignum. Implementation strategy would be roughly the same: Consider the sequences A + kB (mod p) for some list of small primes, and find first k so that they all are non-zero, then do a heavier primality test (or a compositeness test, if we want to make that distinction). One would also need some initial checks to identify inputs for which there is no such prime. > Finally for mpz_prevprime(rop, op <= 2) it's not clear what rop should be > set to, so I use the smallest prime (2). I'd prefer using the function return value to indicate success/failure. Regards, /Niels -- Niels Möller. PGP-encrypted email is preferred. Keyid 368C6677. Internet email is subject to wholesale government surveillance. _______________________________________________ gmp-devel mailing list gmp-devel@gmplib.org https://gmplib.org/mailman/listinfo/gmp-devel
