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 [email protected] http://cnswww.cns.cwru.edu/~chet/
