06-11-2015, 02:36 PM

Anyone here has done some testing or has knowledge of not-so-large integer arithmetic algorithms?

I'm analyzing the possibility of ditching the mpdecimal library (for newRPL) and develop my own algorithms for arbitrary precision integers and reals.

Why? A few reasons:

It works, but I'm wondering if we can do better on our own.

But the real question is about algorithms.

These "big" libraries all use advanced state-of-the-art algorithms for large numbers (integer or floating point, doesn't matter), so they are hard to beat, but...

The truth is, these algorithms usually have a big overhead and using a small number of digits they can underperform the most naive methods.

newRPL will use up to 2000 digits, with 36 digits being the default, and for example I've seen some tests on the internet where Newton-Raphson division breaks even at around 1000 digits with standard long division.

Has anyone here done or seen any research or testing of algorithms for < 2000 digits? Most tests I've seen online show results for 0, 5000, 10000 digits, etc. so they completely miss the interval I'm looking for, I want several data points between 0 and 2000 digits to really compare.

I'm analyzing the possibility of ditching the mpdecimal library (for newRPL) and develop my own algorithms for arbitrary precision integers and reals.

Why? A few reasons:

- Library was designed for VERY large numbers (in the millions of digits)
- Memory management not very well suited for embedded projects
- Algorithms optimized for processors with DIV instructions

It works, but I'm wondering if we can do better on our own.

But the real question is about algorithms.

These "big" libraries all use advanced state-of-the-art algorithms for large numbers (integer or floating point, doesn't matter), so they are hard to beat, but...

The truth is, these algorithms usually have a big overhead and using a small number of digits they can underperform the most naive methods.

newRPL will use up to 2000 digits, with 36 digits being the default, and for example I've seen some tests on the internet where Newton-Raphson division breaks even at around 1000 digits with standard long division.

Has anyone here done or seen any research or testing of algorithms for < 2000 digits? Most tests I've seen online show results for 0, 5000, 10000 digits, etc. so they completely miss the interval I'm looking for, I want several data points between 0 and 2000 digits to really compare.