Re: division problem


David T. Ashley wrote:
<dcorbit@xxxxxxxxx> wrote in message
news:1167146673.002013.64670@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

To do division efficently, the classical solution is to use Newton's
methd.
http://en.wikipedia.org/wiki/Division_(digital)
It might be a bit crunchy to use it on integers, so why not just
perform a double division and then assign it? I guess that it is a
lot faster than emulating hardware.

The IBM Jikes Compiler has a 64 bit number class for 32 bit machines.
It is C++ but it would not be too hard to convert it to be C function
calls.

It appears that the method won't pay off over classic division until the
operands are fairly large:

http://www.swox.com/list-archives/gmp-discuss/2006-November/002549.html

For the kind of work I do, 64 bits is a HUGE integer (eight bytes, wow!). I
need to read up on this.

They are not comparing Newton's method to classic method.
See:
http://swox.com/gmp/devel/
in the section: "New division code"

If you use the floating point hardware to approximate the answer, and
then use the approximation given (it will be good to about 15 digits on
most machines) then one iteration of Newton's method would give you 30
digits of precision, two iterations of Newton's method would give you
60 digits, three iterations 120 digits, etc.

.

Relevant Pages

  • Re: Convergance checking of log
    ... really takes some hundreds of iterations to converge. ... After every iteration you will have 6 times as many correct digits. ... It's probably not a great way to compute logarithms, ... converging series" I think it will be hard to beat. ...
    (sci.math)
  • Re: HHC 2011 videos
    ... of computers, iterative tasks can be carried out, e.g. lengthly ... simulations - and it is during those iterations that the number of ... available digits becomes important. ... are many ARM opcodes which which would require several Saturn ...
    (comp.sys.hp48)
  • Re: "Elementary" number theory problem
    ... > I am working thru some notes on Elem. ... and l the number obtained by putting the digits in increasing ... > Each number goes thru 12 iterations. ... mapped to itself by the stated operation since 7641-1467=6174] ...
    (sci.math)
  • Re: Adding digits together
    ... multiple iterations -- which is a far more difficult problem. ... times (SumN based on N; SumSumN based on SumN; SumSumSumN based on SumSumN, ... >> arbitrary number of digits in the source number. ... > mod9 solution dodges that) ...
    (comp.databases.filemaker)
  • Re: Taking the bull by its horns [was background]
    ... They were a mainframe series derived from the Whirlwind project, an IBM military contract. ... The 70Xs were vacuum tube machines and were introduced at the same time as the 650 -- the 70X0s were the later transistorized versions. ... In this case, the 7070 retained the basic 650 word architecture of ten decimal digits plus a sign, and continued to use two-digit op-codes and four-digit addresses. ...
    (comp.lang.ruby)