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

[Nicolas ARGYROU]

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