Re: Recursive Functions

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

Date: Wed, 29 Oct 2003 10:29:15 -0500

Richard Heathfield wrote:
>
> Hmmm. I raised 7 to the power 7777 using recursion and iteration. (Since the
> result occupies over 6500 decimal digits, I won't display it here!)
>
> The recursive calculation took 0.22 seconds, and the iterative version 1.06
> seconds - almost five times slower. Perhaps you could demonstrate an
> iterative version that can hold a candle to the recursive technique?

        SomeType my_power(SomeType x, unsigned int n) {
            /* This is the right-to-left binary method used
             * by the O.P., expressed iteratively rather
             * than recursively. A similar left-to-right
             * method would use one less multiplication
             * (note that the first multiplication in this
             * method is always by unity, and thus wasted),
             * but needs extra code to find the high-order
             * 1-bit of `n'. Other methods are faster for
             * certain values of `n' (e.g., 15), but are
             * also more complicated. See Knuth, "The
             * Art of Computer Programming, Volume II:
             * Seminumerical Algorithms" Section 4.6.3;
             * this is Algorithm A from that section.
             */
            SomeType y = 1;

            /* Optional: Make an explicit test for x==0 here.
             * As things stand, my_power(0,0) -> 1.
             */

            for (;;) {
                if (n & 1)
                    y *= x;
                if ((n >>= 1) == 0)
                    return y;
                x *= x;
            }
        } 

-- 
Eric.Sosman@sun.com

Relevant Pages

  • Re: Recursive Functions
    ... >> the result occupies over 6500 decimal digits, I won't display it here!) ... >> The recursive calculation took 0.22 seconds, ...
    (comp.lang.c)
  • RE: BoundField and DataFormatString in ASP.NET 2.0 - Bug ?
    ... I have turned one column display invisible but left its header visible. ... > formatted with the Euro sign and 2 decimal digits. ... > formatted like price 3 with Euro sign and with varying decimal digits. ...
    (microsoft.public.dotnet.framework.aspnet.webcontrols)
  • Re: Price Data Formatting
    ... I suggested that instead of looking for the number of decimal digits that MOST of the data items use you should instead, with the specific "rider" I mentioned, look for the MAXIMUM number of decimal digits in the data list. ... What I AM arguing with is your suggestion regarding how you should initially decide on how many decimal digits you need to display. ...
    (microsoft.public.vb.general.discussion)
  • Re: Task Duration
    ... to input duration in minutes. ... but if you did it via an Excel spreadsheet, you can display any number ... of decimal digits you want. ... > entry to the nearest 15 minutes and simplify billing. ...
    (microsoft.public.project)
  • Gimp - Tile small images to create large image?
    ... use it as a wallpaper, it occupies the central part of the display. ... create large tiled image from this small image? ...
    (comp.os.linux.x)