val@wsccs.UUCP (Val Kartchner) (09/16/88)
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. They are too large to put
in a long, and I can't lose precision by putting them in a float or a
double. What would be the best way to do this?
--
---- /\ ----------------------------------------------------------------
/\/\ . /\ | Val Kartchner {UT@WSC} | 'vi' must go, this
/ \/ \/\/ \ | #include <disclaimer.h> | is non-negotiable.
===/ U i n T e c h \===!ihnp4!utah-cs!utah-gr!uplherc!sp7040!obie!val===== lfm@fpssun.fps.com (Larry Meadows) (09/20/88)
In article <650@wsccs.UUCP>, val@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". -- Larry Meadows @ FPS ...!tektronix!fpssun!lfm ...!nosun!fpssun!lfm
ljz%fxgrp.fx.com@ames.arc.nasa.gov (Lloyd Zusman) (09/22/88)
In article <321@lfm.fpssun.fps.com> lfm@fpssun.fps.com (Larry Meadows) writes: In article <650@wsccs.UUCP>, val@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@fx.com Master Byte Software or ljz%fx.com@ames.arc.nasa.gov Los Gatos, California or fxgrp!ljz@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 ]