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;
}
