Multiple-length Long Division

[Home]   [Puzzles & Projects]    [Delphi Techniques]   [Math topics]   [Library]   [Utilities]

 

 

Search

Search WWW

Search DelphiForFun.org

As of October, 2016, Embarcadero is offering a free release of Delphi (Delphi 10.1 Berlin Starter Edition ).     There are a few restrictions, but it is a welcome step toward making more programmers aware of the joys of Delphi.  They do say "Offer may be withdrawn at any time", so don't delay if you want to check it out.  Please use the feedback link to let me know if the link stops working.

 

Support DFF - Shop

 If you shop at Amazon anyway,  consider using this link. 

     

We receive a few cents from each purchase.  Thanks

 

Support DFF - Donate

 If you benefit from the website,  in terms of knowledge, entertainment value, or something otherwise useful, consider making a donation via PayPal  to help defray the costs.  (No PayPal account necessary to donate via credit card.)  Transaction is secure.

Mensa® Daily Puzzlers

For over 15 years Mensa Page-A-Day calendars have provided several puzzles a year for my programming pleasure.  Coding "solvers" is most fun, but many programs also allow user solving, convenient for "fill in the blanks" type.  Below are Amazon  links to the two most recent years.

Mensa® 365 Puzzlers  Calendar 2017

Mensa® 365 Puzzlers Calendar 2018

(Hint: If you can wait, current year calendars are usually on sale in January.)

Contact

Feedback:  Send an e-mail with your comments about this program (or anything else).

Search DelphiForFun.org only

 

 

 

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)

Download DFF Library source ( DFFLibV15 )

Download executable 

 

 

 

 

        

  [Feedback]   [Newsletters (subscribe/view)] [About me]
Copyright © 2000-2018, Gary Darby    All rights reserved.