2011-09-19, 09:27(-04), 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. [...]
FYI, ksh93 uses pow(3). So does zsh, but only in floating point mode. Probably better and more efficient than reinventing the wheel. -- Stephane
