Re: [OT] Re: Recursive Functions

From: Eric Sosman (Eric.Sosman_at_sun.com)
Date: 10/29/03 

Date: Wed, 29 Oct 2003 11:39:16 -0500

Marcus Lessard wrote:
>
> "Glen Herrmannsfeldt"
> ...
> >
> > If n is a power of two, such as 2**m, it will square the number m times.
> >
> > I suppose as an example for recursive algorithms it is a little better
> than
> > factorial.
> >
> > -- glen
>
> From a mathematical point of view there is no difference in breaking up the
> computation into a set of squares and then multiplying. What is going on in
> the underlying processing that makes using the squares more efficient than
> just multiplying x by itself n times?

    Count the multiplications:

        x*x*x*...*x*x*x = x^128

        x*x = x^2, x^2*x^2 = x^4, ..., x^64*x^64 = x^128

Which do you think will be faster: 127 multiplications or 7? 

-- 
Eric.Sosman@sun.com

Relevant Pages

  • Re: [OT] Re: Recursive Functions
    ... "Glen Herrmannsfeldt" ... > I suppose as an example for recursive algorithms it is a little better ... computation into a set of squares and then multiplying. ...
    (comp.lang.c)
  • Re: help with diophantine equation
    ... > It's a difference of squares, i.e. after multiplying every term ... One need not blindly test all those possibilities. ... This excludes factorizations into negative factors, ...
    (sci.math)
  • Re: Factoring problem solution
    ... because you are just guessing at what quadratics to ... >> use and, if they don't work, guessing again. ... which if all the 'e's" are even gives you a difference of squares. ... Adding rows is multiplying the corresponding "x^2 - N" and subtracting ...
    (sci.crypt)
  • Re: Factoring problem solution
    ... because you are just guessing at what quadratics to ... >> use and, if they don't work, guessing again. ... which if all the 'e's" are even gives you a difference of squares. ... Adding rows is multiplying the corresponding "x^2 - N" and subtracting ...
    (sci.math)