Sunday, November 11, 2007

Slices of Weekend Pi

Irrational numbers seem to have their hooks into nature somehow. Clearly, they are the product of something fundamental, but I think they also point out limits in the way we represent ideas. The really special ones get a symbol that we use without regard for the unique abundance they represent.

There is also a bit of irony in irrational numbers. Mathematics was first designed to track finances and military forces in an attempt to add great stablity. Imagine the surprise when even the simiplest of systems could produce absolute chaos and uncertainty.

Pi(π) is the most famous irrational number and countless lifetimes have been spent in it's study and popularization. Yesterday I spent a couple hours devising an x86 version of the BBP algorithm:
; NOTE: This isn't the fastest way to compute pi approximations.
; confirmed valid for all input [0,10000]
; digit time (1.6Ghz Dothan)
; ------------------------------------------
; 10^4 16 ms
; 10^5 219 ms
; 10^6 2860 ms 6C65D566
; 10^7 33938 ms
; 10^8 407828 ms
; Pi hex digit extraction:
; 243F6 A8885 A308D 31319 8A2E0 37073 44A40 93822
; 299F3 1D008 2EFA9 8EC4E 6C894 52821 E638D 01377

; 16^EBP MOD ECX=8k+z
; Special cases:
; EBP=0, return 1
; ECX=1, return 0
; EDX is return value
mpow: xor edx,edx
cmp ecx,1
je .x
bsr ebx,ebp
mov edx,1
jne .1
.x: retn

.0: mul eax
div ecx
.1: bt ebp,ebx
mov eax,16
jnc .2
mul edx
div ecx
.2: dec ebx
mov eax, edx
jns .0

xor edi,edi ; fraction
.1: call mpow ; 16^EBP mod ECX
xor eax,eax
div ecx ; EDX:0 / 8k+m
add ecx,8 ; 8k+m, k[0,EBP]
add edi,eax
dec ebp
jns .1

mov ebp,10000000h
.2: mov eax,ebp
xor edx,edx
div ecx
add ecx,8
shr ebp,4
cmp ecx,ebp
lea edi,[edi+eax]
jna .2

mov ebp,[esp+36]
mov ecx,1
call series
lea esi,[edi*4]

mov ebp,[esp+36]
mov ecx,4
call series
sub esi,edi
sub esi,edi

mov ebp,[esp+36]
mov ecx,5
call series
sub esi,edi

mov ebp,[esp+36]
mov ecx,6
call series
sub esi,edi
mov [esp+28],esi
retn 4

invoke PiHexDigit, 1000000
(FASM Syntax)

No comments: