division

[Lloyd Zusman]

In article <321 at lfm.fpssun.fps.com> lfm at fpssun.fps.com (Larry Meadows) writes:

   In article <650 at wsccs.UUCP>, val at wsccs.UUCP (Val Kartchner) writes:
   > 
   >      I have written some long integer math routines (ADD, SUB, MUL), but I
   >      need to know the most efficient way to divide.  Assume that you have
   >      two character strings of arbitrary length.

   I assume you want a non-binary integer division routine.  Binary is
   easy, just a shift & subtract.  The best arbitrary precision division
   routine I have seen is in D.E. Knuth, Seminumerical Algorithms
   (A.ofC.P. Vol 2).  I'd give the page # but don't have that volume here
   at "work".

I tried to send mail to you (Val Kartchner), but I had a lot of
trouble getting it out and I'm not sure if it ever made it to you.
So, I'm reposting here, since it has the complete Knuth reference
mentioned above by Larry Meadows:

I have written a set of math routines that do infinite-precision math
on character-string-like data.  For division, I used the algorithm in
Knuth, "The Art of Computer Programming, Volume II: Seminumerical
Algorithms, Second Edition, 1981, pp. 255-260."  This is basic, old-
fashioned long division, and Knuth claims his algorithm is the most
efficient known for general, arbitrary precision division.  I posted a
query similar to yours to the net about a year ago, and no one was
able to offer anything better.  If you hear of anything faster, I'd
appreciate it if you'd let me know.

By the way, my infinite-precision math package is almost in a state
where I can send it out to the world.  When I am done with it, I'd
be happy to send you a copy, if you're interested.

Sincerely,

--
  Lloyd Zusman                  Internet:  ljz at fx.com
  Master Byte Software                  or ljz%fx.com at ames.arc.nasa.gov
  Los Gatos, California                 or fxgrp!ljz at ames.arc.nasa.gov
  "We take things well in hand."    uucp:  ...!ames!fxgrp!ljz
  [ our Internet connection is down: use uucp or mail to the entry above it ]