[Home] [Puzzles & Projects] [Delphi Techniques] [Math Topics] [Library] [Utilities]
Of the 4 basic operations of arithmetic, (+, -, X, and /), division is by far the most complex. I had that brought home recently when I decided to rewrite the integer divide procedure in our Big Integer Arithmetic unit.
The "BigInt" unit can manipulate integers with hundreds of decimal digits. The original procedure for division used multiple subtractions within each digit to accomplish the task. I decided to rewrite it to more closely simulate what we humans do when we perform long division with pencil and paper. 4th graders learn to do it, so how hard can it be? After several days, and several restarts, I found out. Once again the amazing abilities of our minds was brought home.
I finally "cheated" and started searching the Internet for other's solutions to the problem. The best one I found is in the tutorial "Multiple-length Division Revisited: a Tour of the Minefield" written in 1994 by Dr. Per Brinch Hansen and published in the journal Software Practice and Experience, Vol24(6), June 1994.
In his Memoirs, page 173, Dr. Hansen writes
"I thought it would be easy to find a textbook that includes a simple algorithm for multiple-length division with a complete explanation. Much to my surprise, I was unable to find such a book. I ended up spending weeks on this "well-known" problem and finally wrote a tutorial that includes a complete Pascal algorithm (Brinch Hansen 1994). I mention this unexpected difficulty to illustrate what happens when a standard algorithm is not published as a well-structured program in an executable language."
No wonder I was having trouble! The Hansen paper largely solved the problem for me because, not only does he explain the algorithms for long division, he thoughtfully includes Pascal code for an implementation.
I'm not going to try to explain the details, download the paper and spend a few hours working through hid 23 page tutorial if you are interested. You can also download the source for my program and check the DivideRem procedure in UBigIntsV2 unit to see my implementation. I mainly wanted to pass along the fact that such a clear explanation existed and to point out once again what a marvelous thing is the human mind compared to current computer technology.
Below are links to download source and executable for the test program I wrote to compare results and timing of the old and new versions of my large integer division procedure.
I have incorporated the revised Big Integer unit into our Big Float unit (floating point arithmetic) and reposting the programs on DFF that use these units. Check the Big Integers link above for details.
Addendum April 12, 2005: The UBigIntsV2 unit has moved to the recently implemented DFF Library. From the users perspective, this just means that you will need both units if you want to recompile the program.
Running/Exploring the Program
Download source code (Requires DFF Library Source DFFVLibV02 or later)
Copyright © 2000-2013, Gary Darby
All rights reserved.