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

[Stephane CHAZELAS]

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