strange exponentiation performance

Discussion in 'Python' started by Jeff Davis, Nov 23, 2003.

  1. Jeff Davis

    Jeff Davis Guest

    I was doing some thinking about exponentiation algorithms along with a
    friend, and I happened upon some interesting results. Particularly, I was
    able to outperform the ** operator in at least one case, with a recursive
    algorithm. This leads me to believe that perhaps the ** operator should
    tune it's algorithm based on inputs or some such thing. Here is my data:


    >>> def h(b,e):

    .... if(e==0): return 1
    .... if(e==1): return b
    .... t = h(b,e >> 1)
    .... return t*t*h(b,e & 1)
    ....

    Above is the recursive exponentiation algorithm. I tried some test data
    and it appears to work. This just popped into my head out of nowhere and I
    optimized it with some trivial optimizations (I used e>>1 instead of e/2;
    I used e&1 instead of e%2).

    >>> def f(b,e):

    .... n = 1
    .... while(e>0):
    .... if(e & 1): n = n * b
    .... e >>= 1
    .... b *= b
    .... return n
    ....

    I then made this algorithm which I thought basically unwrapped the
    recursion in h(). It seems to work also.

    Then, the more trivial exponentiation algorithm:

    >>> def g(b,e):

    .... n = 1
    .... while(e>0):
    .... n *= b
    .... e -= 1
    .... return n
    ....

    For consistency, I wrapped ** in a function call:

    >>> def o(b,e):

    .... return b**e
    ....

    then I made a test function to time the computation time:

    >>> def test(func,b,e):

    .... t1 = time.time()
    .... x = func(b,e)
    .... t2 = time.time()
    .... print t2-t1
    ....


    now, I compared:

    >>> test(f,19,100000)

    0.765542984009
    >>> test(g,19,100000)

    11.4481400251
    >>> test(h,19,100000)

    0.370787024498
    >>> test(o,19,100000)

    0.457986950874

    now, g() was blown out of the water, as expected, but the others were
    close enough for another test at a higher "e" value.

    >>> test(f,19,500000)

    8.02366995811
    >>> test(h,19,500000)

    3.66968798637
    >>> test(o,19,500000)

    5.29517292976
    >>>


    Now, that is the interesting part. How did ** not measure up to h()? It's
    also interesting that f(), which is supposed to be a more efficient
    version of h(), is lagging behind.

    I would like help explaining the following:
    (1) How did my less-than-perfectly-optimized recursive algorithm win
    against the ** operator?
    (2) How can I unwrap and optimize h()? From what I understand, recursion
    is never supposed to be the most efficient. I suspect there are some
    hidden inefficiencies in using while(), but I'd like to know the specifics.

    If my algorithm h() is better, why can't ** use a quick test to change
    algorithms based on inputs? Or is mine better in all cases?

    BTW: python2.3.2 compiled with gcc 3.3.2 on linux2.4.19 all on debian &
    i386. I have an AMD athlon xp 1800+.

    I ran all test cases several times and results were very consistant.

    Also note that I'm not exactly an algorithms expert, I just happened upon
    these results while chatting with a friend.

    Regards,
    Jeff Davis
    Jeff Davis, Nov 23, 2003
    #1
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Steven T. Hatton

    An exponentiation function for int?

    Steven T. Hatton, Oct 13, 2004, in forum: C++
    Replies:
    14
    Views:
    730
    JXStern
    Oct 16, 2004
  2. Tim Peters
    Replies:
    1
    Views:
    425
    Jeff Davis
    Nov 24, 2003
  3. elventear

    Decimal and Exponentiation

    elventear, May 19, 2006, in forum: Python
    Replies:
    7
    Views:
    629
    Tim Peters
    May 20, 2006
  4. exponentiation operator (lack of)

    , Dec 22, 2005, in forum: C Programming
    Replies:
    67
    Views:
    1,467
    Dave Thompson
    Jan 4, 2006
  5. Jon

    Stopping number exponentiation

    Jon, Jul 8, 2008, in forum: ASP General
    Replies:
    1
    Views:
    130
    Bob Barrows [MVP]
    Jul 8, 2008
Loading...

Share This Page