The code that I’ve posted about so far has been pretty light-weight. Here are a couple of open-source classes that I hope could be useful in actual production code.
I have an unbounded integer and a big decimal that are intended to be C++ equivalents of SQL’s NUMERIC and DECIMAL types for use in a database access library that I’m working on. They’re basically for storing big numbers and maybe doing a little bit of arithmetic. The efficiency of my implementation might not be good enough for serious numerical work.
That’s particularly true for division. I’m not as competent as I’d like to be in numerics; and when I tried to read about multi-word division in Knuth Vol. 2*, my eyes glazed over; and I had to revert to the good old “long division” routine that I learned in fourth grade. I get a first trial divisor for each new digit of the quotient reasonably quickly; but if I guess wrong, which is likely, it takes linear time to get from that point to the right value. If there’s a numerics expert out there who knows of a good way to do multi-word division, and if it turns out that I can comprehend it, I’d love to hear about it.
The two documentation papers, all the source code for both classes, and the open-source license are zipped up here.
*Knuth, Donald E., The Art of Computer Programming, Volume 2: Seminumerical Algorithms, Third Edition
I can’t speak to the efficiency, but assuming that division is a particularly heavy operation it may not be unreasonable, but I think the following is understandable. (It might be considered inelegant.)
Assume positive integers for ease of explication; it shouldn’t be hard to extend it to positive and negative integers.
If the divisor is 0 the result is NaN.
Optionally, otherwise, if the dividend is less that the divisor the result is 0.
Optionally, otherwise, if the dividend and divisor are equal the result is 1.
Otherwise, provided the numbers aren’t too large for the native floating point type, convert the unbounded integers to floating point and divide the floating point numbers. If the floating point numbers have sufficient significant figures just take the floor to get the integer part, and do a subtraction to get the remainder if that’s wanted. If the floating point numbers don’t have sufficient significant figures the result is an upper and lower bound. Multiple the lower bound by the divisor, subtract the result form the dividend, and then divide this by the divisor. Add the result to the lower bound. Repeat as required.
Loss of precision on conversion to floating point potentially introduces errors. Using the floating point numbers bracketing the unbounded integers gives upper and lower bounds – a(+)/b(-) >= a/b >= a(-)/b(+); n(-) being defined as the largest floating point number less than n, and n(+) the smallest floating point number greater than n. So in the above replace a(naive)/b(naive) by a(-)/b(+).
If the numbers are too large for the native floating point type first divide each number by a sufficient power of 10 to get them in range.
If the quotient is too large for the native floating point type (i.e. by the time you’ve got the dividend in range the divisor has been reduced to zero) you have to resort to whatever you are already doing.
This algorithm generates multiple digits of the quotient at a time, so it should be faster than the manual long division algorithm.
You’d want to confirm that edge cases (such as when the quotient approaches the limit of what floating point numbers can represent) are stable.
——————————————————————————————————————————–
Alternately look at github to see what other people have done. The one I looked at wasn’t obvious at a glance.
The divide-step method produces the quotient one bit at a time and returns the remainder when done. I’ve used it and the corresponding multiply-step method on low-end PICs that didn’t have a multiply opcode, let alone divide. The one-bit-at-a-time methods have the charm of being easy to implement. And the obvious lack of charm of being slow.
I started trying to write division 8-bits at a time on an ARM 32-bit CPU. (In assembly because that’s what I do.) And gave it up because it started being more work and less interesting than I had anticipated. If someone were paying, I would have persisted.
For inspiration you might want to look at the GNU multiprecision bignum library.