Re: Another way to do x^n

Andrew Haley wrote:
Julian V. Noble <jvn@xxxxxxxxxxxx> wrote:
John Doty wrote:
Julian V. Noble wrote:
I haven't seen this one (or if I have, I've forgotten :-( !!)
but I like it because it exposes the underlying algorithm
transparently:

\ raise float to positive integer power
\ algorithm: x^n = (x^2)^[n/2] * x^[n mod 2]

: f^2 FDUP F* ;

: (power) ( f: x -- x^n) ( n --) \ n assumed >= 0
DUP 0= IF DROP FDROP 1e0 EXIT THEN
DUP 1 = IF DROP EXIT THEN
DUP FDUP 2 MOD ( f: x x ) ( n n mod 2) RECURSE
FSWAP f^2 2/ ( f: x^[n mod 2] x^2) ( n/2) RECURSE
( f: x^[n mod 2] [x^2]^[n/2] ) F*
;

: power ( f: x -- x^n) ( n--)
FDUP F0= IF DROP FDROP 0e0 EXIT THEN
(power)
;

Anyway, it's for the people who always claim we never post
any code.

But it doesn't address the more serious problem: the code posted is often excessively difficult for any but an ANS Forth expert to read.

1. 12 (!) stack adjustments. Yikes!

2. (power) is an incomprehensible 25 words long!

3. Recursion unnecessarily obfuscates the algorithm.

I really don't believe that. Far from obfuscating it, the recursion
expresses the algorthm. Rewritten in straightforward ANS Forth, it's:

\ power(x,0) = 1
\ power(x,1) = x
\ power(x,n) = power(x*x,n/2) * power(x, n mod 2 )

: square ( f - f') fdup f* ;
: pow ( n) ( f - f')
?dup 0= if fdrop 1e0 exit then
dup 1 = if drop exit then
2 /mod fdup square recurse fswap recurse f* ;

And this is a simple transformation of the algorithm. It certainly is
nowhere near requiring auxiliary variables.

This isn't quite pure ANS because it relies on a separate
floating-point stack, but trying to code around a mixed stack is such
a pain that I'm happy to have that as a dependency.

0^0 is 1, by the way.
^^^^^^^^^^^^^^^^^^^^^
Not necessarily -- depends on the order of limits.


Andrew.



--
Julian V. Noble
Professor Emeritus of Physics
University of Virginia
.

Relevant Pages

  • Re: Another way to do x^n
    ... \ raise float to positive integer power ... FDUP F0= IF DROP FDROP 0e0 EXIT THEN ... Recursion unnecessarily obfuscates the algorithm. ...
    (comp.lang.forth)
  • Re: Where now for the DUP?
    ... DUP and Sinn Fein sharing power in a manner that has never been before ... Either a United Ireland, forced upon the majority, or, a system of joint rule with the Republic and the UK Governments, or agree a power sharing alternative. ...
    (soc.culture.irish)
  • Re: Another way to do x^n
    ... FORTH> test-all ... if fswap fover f* fswap then ... dup 1 and if fdup fdup f* fswap else fdup f* 1e0 then ...
    (comp.lang.forth)
  • Re: Another way to do x^n
    ... if fswap fover f* fswap then ... have to do are repetitive fover f* operations the correct number ... dup 1 and if fdup fdup f* fswap else fdup f* 1e0 then ...
    (comp.lang.forth)
  • Re: to Matt,
    ... algorithm that can run BWT in linear time (with respect to the input ... Quantum computers are thing of past, ... I can use Jules' random compression ... drill a power cord from WB's super nuclear power plant to Sachin's ...
    (comp.compression)
Loading