# prime::namespace

function templates

Version 0.61

# Speed Improvement for prime::isprime(mpz_cass)

Proofing a huge number that is greater than 2^{128} for being a prime requires testing possible divisors above 2^{64}. Thus the divisor itself must be an mpz_class object or, as internally used for better performance, the divisor must be stored into the corresponding c-type which is actually a pointer. This is obviously more complex and as such slower than using the basic data type unsigned long long int

for the divisor. That's why I decided to use the basic data type as possible divisor with the faster mpz_divisible_ui()-function until ULLONG_MAX is reached. On my little notebook this takes approximately 1500 years. Only if after that we need to test by even larger divisors we switch to the (slower) mpz c-type.

Besides I reviewed the code. The seperation of the templates into .hpp headers and .cpp implementations is abandoned, because this seperation makes no sense for templates. Some code that was implemented for testing the correctness of the code has been removed and some comments in the code are improved.

Version 0.6

# Efficient Multi-Threading Prime Factorization

I didn't know what I was getting into when I started to write a function that does prime factorization by multi-threading. I thought that it can not be very difficult to do something, which is very easy in single-threading, faster by multi-threading. After failing four times with different algorithms that were hardly faster or even slower than single-threading, I am happy to finally present a solution that on my 2core/4thread notebook machine runs up to 3x faster than the single-threading algorithm. See the documentation here for a detailed analysis of the two core problems that must be solved for efficient multi-threading prime factorization.

With this update comes an improved (and of course extended) documentation. And I finally made what I should have done right from the start: Split all templates in seperate files. I promise to make never ever a single file mess again.

Version 0.5

# Speed Update for mpz_class

Speed improvement for big numbers: Switched internally to the C-style `mpz_t`

functions instead of using the gmplib c++ class interface all the way. The `isprime()`

function now works almost twice as fast! I think the reason for this astonishing improvement is that operator overloading in the c++ class interface and must be resolved many times. By using the C-style function we save this work. The table below shows the time (in seconds) needed to call `isprime()`

for the first 100 odd numbers above `uint_64`

, measured on my Intel i5-7200U:

prime v04 | prime v05 | |

clang++ | 280.1 | 152.2 |

g++ | 281.2 | 148.5 |

Beside this speed improvement small improvements for `nextprime()`

and `prevprime()`

have been implemented. A bug in `mpz_class`

functions got solved. It occured if you try to prove a very large number being a prime. The function would not state any wrong result, but hang in an infinite loop if it tries to proof a prime.

Version 0.4

# First Launch!

This is the first version of the function template that I actually release online. The `prime::isprime()`

is fully functional. This version adds `std::string`

support to `nextprime()`

and `prevprime()`

.