Large integer algorithms

[Claudio L.]

(06-13-2015 07:00 AM)Marcus von Cube Wrote:  The decNumber library supports arbitrary precision. We use it in the 34S. External (register) formats have a fixed number of digits but the internal format allows for thousands of digits (if needed). The memory format for the latter isn't very memory effective, it's more suited to processing. Hence the distinction between the two.

Thanks, we used decNumber way back in the HPGCC days, and I'm well aware of its pros and cons. mpdecimal is superior in many ways, but has the same basic traits when it comes to memory management. The internal format is quite similar, with 9-digit radix in a 32-bit integer (decNumber is configurable at compile time, but this is the format by default on a 32-bit processor).
Some things are strange, as the words are ordered with the highest significant word first, but little endian processors can be more effective with the opposite ordering. Makes sense only for printing a number, but not for calculations.
For example, you could add two words at once in a 64-bit operation, then propagate the carry, and would be faster than having to do two 32-bit operations because the words are inverted in memory.
So a simple addition could be almost twice as fast if using the opposite order.

I wrote a couple of basic arithmetic routines, and they work, but I'm thinking it's a big task to do them all, guarantee proper rounding for all corner cases, etc.
I think I'll stick to mpdecimal for the time being so the project can progress in other areas.

Perhaps I'll try to optimize it in some key routines but keep the bulk.