Small challenge

[robve]

(04-23-2023 08:00 AM)EdS2 Wrote:  There must be several ways to compute x^10:
raise to power ten
raise to power 5 then square
square then raise to power 5
and in each case, do this using repeated multiplication, or by the power operator.

How differently accurate are each of those 6 ways on the machines considered?

Hang on, it's more than 6 - the squares and fifth powers can also be done in at least two ways, perhaps even three ways if x^2 is available.

(And there's also the less-accurate option of using log and exp and multiplication.)

Indeed! It is common to find exponentiation by squaring for integer powers, which tends to be more accurate than repeated multiplication and log*exp closed forms.

It's pretty straightforward to do. Here is the way I've implemented it in Forth850 MATH.FTH:

Code:

: F**       ( r1 r2 -- r3 )
  \ r1 and r2 cannot be both zero
  2DUP F0= IF 2OVER F0= IF -46 THROW THEN THEN
  2DUP 2DUP FTRUNC F= IF
    \ exponentiation by squaring
    2DUP F0< >R \ r2 is negative
    FABS F>D 1E0 2SWAP \ -- r1 1 ud
    IF -46 THROW THEN \ error when exponent ud exceeds 16 bits
    >R
    BEGIN
      R@ 1 AND IF 2OVER F* THEN
      R> 1 RSHIFT \ -- r1^n product u>>1
    DUP WHILE
      >R
      2SWAP 2DUP F* 2SWAP \ -- r1^n^2 product u>>1
    REPEAT
    DROP 2SWAP 2DROP \ -- product
    R> IF 1E0 2SWAP F/ THEN \ r2 was negative
  ELSE
    F^ \ performs 2SWAP FLN F* FEXP ;
  THEN ;

x^10 is broken down to three squarings and one multiplication \( \left(x\left((x^2)^2\right)\right)^2 \) hence 4 multiplications suffice.

- Rob