[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Bug fix for $((x**y)) algorithm on 64+ bits machines.

From: Chet Ramey
Subject: Re: Bug fix for $((x**y)) algorithm on 64+ bits machines.
Date: Mon, 19 Sep 2011 09:27:11 -0400
User-agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.6; rv:6.0.2) Gecko/20110902 Thunderbird/6.0.2

On 9/16/11 4:39 PM, Nicolas ARGYROU wrote:

> Bash Version: 4.0
> Patch Level: 33
> Release Status: release
> Description:
>     The algorithm used to calculate x to the power of y: x**y
>     takes O(y) time which is way too long on systems using 64 bits.
>     Calculating for exemple $((3**2**62)) freezes the shell at
>     argument parsing time.
> Repeat-By:
>     bash -c 'echo $((3**2**62))'
> Fix:
>     This fix uses an alorithm that takes O(log(y)) time, which is way
>     faster. But it is still about 30 times slower with random numbers
>     than a single multiplication, on 64 bits systems. The fix is written
>     as a C++ template working on any unsigned integer type, and doesn't
>     need any external resource:

Thanks for the report.  This looks like an independent reimplementation of
the "exponentiation by squaring" method.  I did a little looking around,
and it's the best algorithm out there.  I used a slightly different but
equivalent implementation.

``The lyf so short, the craft so long to lerne.'' - Chaucer
                 ``Ars longa, vita brevis'' - Hippocrates
Chet Ramey, ITS, CWRU    address@hidden    http://cnswww.cns.cwru.edu/~chet/

reply via email to

[Prev in Thread] Current Thread [Next in Thread]