Knuth Arithmetic (multiplication and division)
I have a side project where I am implementing a set of routines to do arithmetic on arbitrary sized integers.
There are several such projects scattered around the Internet. One I particularly like is at cpp-bigint.sourceforge.net, but I wanted to write my own so I could investigate the issues involved with this topic.
As a preliminary step, I implemented C++ routines to perform multiplication and division using the algorithms invented and described in Donald Knuth's
"Art of Computer Programming, Volume 2" in the "Classical algorithms" section.
I can't claim I understand these algorithms as well as he does, but I can follow a recipe and understand enough (I think) to get it right.
So I offer these routines for others to examine. They use a radix of 10 (decimal) for the number systems and store the numbers as character strings.
They also cheat a little. The multiplication routine uses the computer's multiply instruction to multiply single digits (as does Knuth's algorithm) and the division routine uses both single digit multiplication and division. Additionally, the division algorithm makes a special case of single digit divisors (I've still to divine what Knuth's intent was; his algorithm will crash with single digit divisors). My plan, when I implement these in my upcoming large integer routines, is to replace these with functions that do acceptable (i.e. non-overflowing) arithmetic operations. I can get away with it in the sample routines included here because I'm working in radix (a.k.a. base) 10 and that is small enough so that single digit operations will not overflow.
There are two routines, knuthmult.cpp and knuthdiv.cpp. As C++ programs they are far from well-formed. They are written assuming the reader has Knuth's book with its description of the algorithms handy. Variable names used in the routines are the same (mostly) as in the book and, for simplicity, are defined as global variables. Also, because Knuth describes his algorithm as a series of steps and goto's; these programs work the same way. (When I implement them for the large integer routines, I'll use better structured, go-to less routines and a lot more comments.)
Dependencies: These programs, as written, use my debugging file ydebug.hpp, which can be found here.