Large integer algorithms

06112015, 02:36 PM
Post: #1




Large integer algorithms
Anyone here has done some testing or has knowledge of notsolarge 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 stateoftheart 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 NewtonRaphson 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. 

06132015, 07:00 AM
Post: #2




RE: Large integer algorithms
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.
Marcus von Cube Wehrheim, Germany http://www.mvcsys.de http://wp34s.sf.net http://mvcsys.de/doc/basiccompare.html 

06132015, 06:54 PM
Post: #3




RE: Large integer algorithms
(06132015 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 9digit radix in a 32bit integer (decNumber is configurable at compile time, but this is the format by default on a 32bit 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 64bit operation, then propagate the carry, and would be faster than having to do two 32bit 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. 

« Next Oldest  Next Newest »

User(s) browsing this thread: 1 Guest(s)