From: "Dann Corbit" Subject: Re: The fastest method to multipy and divide integers Date: Tue, 9 Nov 1999 14:26:42 -0800 Newsgroups: sci.math Keywords: Using Newton's method to divide using multiplication Jean-Christophe Bossu wrote in message news:02om7pil9cdm@forum.swarthmore.edu... > Dann Corbit wrote : > > You can use Newton's method to reduce division to multiplication. > > On which function shall we apply Newton's method? http://www-ee.eng.hawaii.edu/Courses/EE361.S95/Lectures/Lec40/lec40.2.html -- C-FAQ: http://www.eskimo.com/~scs/C-faq/top.html "The C-FAQ Book" ISBN 0-201-84519-9 C.A.P. Newsgroup http://www.dejanews.com/~c_a_p C.A.P. FAQ: ftp://38.168.214.175/pub/Chess%20Analysis%20Project%20FAQ.htm ============================================================================== From: Lynn Killingbeck Subject: Re: The fastest method to multipy and divide integers Date: Tue, 09 Nov 1999 17:59:30 -0600 Newsgroups: sci.math Jean-Christophe Bossu wrote: > > Dann Corbit wrote : > > You can use Newton's method to reduce division to multiplication. > > On which function shall we apply Newton's method? f(x) = 1/x - a = 0 f'(x) = -1/x^2 x <-- x - f/f' = x - (1/x - a) / (-1/x^2) = x + (x - a * x^2) = x + x * (1 - a * x) Viola'! Division, without a divde in sight! It's often best to leave it in that form, since the added term is a good estimator of the error. Note that if a * x is 1, the error is zero, and you have perfect convergence. If you want to be more clever, try increasing the accuracy at each iteration, since the number of bits of accuracy roughly doubles at each iteration. I think this, and more, is covered in both Knuth's and Press et al's books. Lynn Killingbeck ============================================================================== From: spellucci@mathematik.tu-darmstadt.de (Peter Spellucci) Subject: Re: Division.. Date: 8 Nov 1999 14:47:35 GMT Newsgroups: sci.math.num-analysis In article <382322b3@ant.wmin.ac.uk>, "Ediz Cetin" writes: |> Does anybody know a way of converting division into multiplication. I have |> E=(F1)/(conj(F2)+F1), where F1 and F2 are both complex. Is there a way of |> converting this division into multiplication. |> you first write it as a quotient with real denominator, as shown by virgil. for the real division 1/a you may substitute an iterative process using only multiplication: solve 1/x-a=0 via Newtons method: x_{k+1}=x_k*(2-a*x_k) k=0,1,2, ... with a reasonable initial x_0 since you may restrict a to [0.5,1] by proper multiplication with 2 or 1/2, x_0=1.33 may be such a guess 9there are of course better ones, e.g. by linear interpolation, chebyshev approxiamtion etc). Fike's book on computing the elementary functions contains a lot of such tricks. hope this helps peter