[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Bug fix for $((x**y)) algorithm on 64+ bits machines.
From: |
Nicolas ARGYROU |
Subject: |
Re: Bug fix for $((x**y)) algorithm on 64+ bits machines. |
Date: |
Sat, 17 Sep 2011 04:10:17 -0700 (PDT) |
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 <nargy@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 <opengeometry@yahoo.ca>
To: Nicolas ARGYROU <nargy@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 <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;
> }
>
Re: Bug fix for $((x**y)) algorithm on 64+ bits machines., Chet Ramey, 2011/09/19