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 c...@case.edu http://cnswww.cns.cwru.edu/~chet/