[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
## Re: Bug fix for $((x**y)) algorithm on 64+ bits machines.

**From**: |
Stephane CHAZELAS |

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

**Date**: |
Wed, 28 Mar 2012 18:26:30 -0000 |

**User-agent**: |
slrn/pre1.0.0-18 (Linux) |

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

**Re: Bug fix for $((x**y)) algorithm on 64+ bits machines.**,
*Stephane CHAZELAS* **<=**