Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!yale!umich!samsung!zaphod.mps.ohio-state.edu!rpi!leah!bingvaxu!kym
From: kym@bingvaxu.cc.binghamton.edu (R. Kym Horsell)
Newsgroups: comp.arch
Subject: Re: benchmark for evaluating extended precision (data, long)
Keywords: extended precision,multiply,benchmark,arithmetic
Message-ID: <4008@bingvaxu.cc.binghamton.edu>
Date: 13 Sep 90 19:59:14 GMT
References: <2114@charon.cwi.nl> <119983@linus.mitre.org> <3999@bingvaxu.cc.binghamton.edu> <120002@linus.mitre.org>
Reply-To: kym@bingvaxu.cc.binghamton.edu.cc.binghamton.edu (R. Kym Horsell)
Organization: SUNY Binghamton, NY
Lines: 20

In article <120002@linus.mitre.org> bs@linus.mitre.org (Robert D. Silverman) writes:
\\\
>There doesn't seem to be a recursive bisection algorithm similar to
>Karatsuba's that works for division. Methods based on FFT's are 
\\\

I am not sure about the Newton part of the obvious ``invert and
multiply'' using Kartsuba -- does this give you a practical technique
for high-precision divide O(n^lg(3)).

Another straightforward scheme, I haven't checked the literature
but I don't remember it, is to use

	1/(2^n a+b) approx= 2^-n 1/a (1 - 2^-2 b/a)

It _has_ been a long day so could someone point out to me
(I _know_ there are mathematicians out there) whether the
rhs requires 2*n-bit calcs?

-Kym Horsell