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

[William Park]

145557834293068928043467566190278008218249525830565939618481
is awfully big number! :-)
-- 
William



----- Original Message -----
> From: Nicolas ARGYROU <nargy@yahoo.com>
> To: "bug-bash@gnu.org" <bug-bash@gnu.org>
> Cc: 
> Sent: Friday, September 16, 2011 4:39:41 PM
> Subject: Bug fix for $((x**y)) algorithm on 64+ bits machines.
> 
> From: nargy@yahoo.com
> To: bug-bash@gnu.org
> Subject: Bug fix for $((x**y)) algorithm on 64+ bits machines.
> 
> Configuration Information [Automatically generated, do not change]:
> Machine: x86_64
> OS: linux-gnu
> Compiler: gcc
> Compilation CFLAGS:  -DPROGRAM='bash' -DCONF_HOSTTYPE='x86_64' 
> -DCONF_OSTYPE='linux-gnu' 
> -DCONF_MACHTYPE='x86_64-mandriva-linux-gnu' 
> -DCONF_VENDOR='mandriva' -DLOCALEDIR='/usr/share/locale' 
> -DPACKAGE='bash' -DSHELL -DHAVE_CONFIG_H   -I.  -I. -I./include 
> -I./lib   -O2 -g -pipe -Wformat -Werror=format-security 
> -Wp,-D_FORTIFY_SOURCE=2 
> -fexceptions -fstack-protector --param=ssp-buffer-size=4
> uname output: Linux localhost.localdomain 2.6.31.14-desktop-1mnb #1 SMP Wed 
> Nov 
> 24 10:42:07 EST 2010 x86_64 AMD Athlon(tm) 64 X2 Dual Core Processor 6000+ 
> GNU/Linux
> Machine Type: x86_64-mandriva-linux-gnu
> 
> 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:
> 
> // Copyright 2011: Nicolas Argyrou <nargy@yahoo.com>, public domain.
> template<typename T>
> inline T ipow(register T x, register T y)
> {
>     if (x == 0 && y != 0) return 0;
>     // 1: ipow(x,y) = x ** y = Product [i=0; i<log2(y)] (x ** 
> (((y>>i)&1)*2**i))
>     // 2: x**(2**i) = x**(2**(i-1)) * x**(2**(i-1))
>     register T X = x; register T xy = 1;
>     for(; y; y>>=1, X *= X)
>         if (y & 1)
>             xy *= X;
>     return xy;
> }
>