exponentiation-by-squaring.fs

\ cf.:
\ Algorithm: http://en.wikipedia.org/wiki/Exponentiation_by_squaring
\ Other examples: http://canonical.org/~kragen/sw/inexorable-misc/exponent.fs

variable the-exp

: do-exp ( x -- x^the-exp )
	>r

	the-exp @ 0= if rdrop 1 exit then

	the-exp @
		dup 2 mod if 1- r@ >r else 1 >r then
	2/ the-exp !

	r> r>
	recurse
	dup * *
	;

: exp ( x n -- x^n )
	the-exp ! do-exp ;

3 4 exp . cr bye