I'm glad it pleases you. I'm amazed also how fast it deals with large numbers. Feel free to use it. :)
I came up with a version that is slightly more precise in the comments, and that uses 3 registers instead of 4 (though gcc can optimize that): // Copyright 2011: Nicolas Argyrou <na...@yahoo.com>, public domain. template<typename T> inline T ipow(register /* unsigned */ T x, register /* unsigned */ 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 xy = 1; for(; y; y>>=1, x *= x) if (y & 1) xy *= x; return xy; } I doubt I can came up with a more concise and precise version. Thank you, Nicolas Argyrou ----- Original Message ----- From: William Park <opengeome...@yahoo.ca> To: Nicolas ARGYROU <na...@yahoo.com> Cc: "bug-bash@gnu.org" <bug-bash@gnu.org> Sent: Saturday, September 17, 2011 2:17 AM Subject: Re: Bug fix for $((x**y)) algorithm on 64+ bits machines. 145557834293068928043467566190278008218249525830565939618481 is awfully big number! :-) -- William ----- Original Message ----- > From: Nicolas ARGYROU <na...@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: na...@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 <na...@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; > } >