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

[Chet Ramey]

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.

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