Small challenge

[J-F Garnier]

(04-28-2023 07:13 AM)J-F Garnier Wrote:  

(04-28-2023 12:52 AM)Gerson W. Barbosa Wrote:  HP 12C Platinum:
23 ENTER 10 y^x EEX 13 ÷ 10 × g FRAC f PREFIX -> 4265112136

hp 33s:
23 ENTER 10 y^x right-shift SHOW -> 414265112136

So the 12C Platinum, the 33S and the 35S are in the same class.
Maybe are they using a square and multiply method for integer powers. Does anybody know?

I decided to have a closer look at this question. Below are my results.

Summary

The 35S, and presumably the 12CP and 33S too, are using a square and multiply method for exponentiation with positive integer powers up to about 127.

Method

I measured the duration of the 2^x calculation for different values of the power x on both the HP-32S (Saturn) and HP-35S.
Here is my test program for the 32S/35S:

Code:

A01 LBL A
    STO B
    2
    STO A
    100
    STO C
    RCL A
    ENTER
    ENTER
    ENTER
A11 RCL B
B01 LBL B
    y^x
    CLx
    LASTx
    y^x
    CLx
    LASTx
    y^x
    CLx
    LASTx
    y^x
    CLx
    LASTx
    y^x
    CLx
    LASTx
    DSE C
B18 GTO B

On the 32S, the execution time is almost independent from the power value, and is about 22s for the 500 y^x evaluations.

On the 35S, there is a big difference between a positive integer power and a fractional/negative power, and the execution time increases with larger integer powers, more precisely with the number of bits '1' in the binary representation.

Results for 2^x on the 35S

 x  time (500x)
  4  17s     positive power
 -4  38s     negative power
  4.5 31s     non-integer power
  7  19s     3 bits in binary representation of the power
  8  19s
 15  23s     4 bits ...
 16  21s
 31  27s     5 bits ...
 32  23s
 63  31s     6 bits ...
 64  25s
100  29s
120  32s
127  34s     7 bits ...
128  35s
>128 35s

The execution time is then quite constant for powers beyond 128.

These results strongly suggest an exponentiation by squaring for positive powers up to 127.

Benefit ?

The question is: what is the benefit of implementing the exponentiation in this way for these limited special cases, between 2 and 127?
As the initial challenge demonstrated, there are a few cases where the exponentiation by squaring provides better results, but this is globally rare.
Moreover, and more importantly, better results are not granted for the exponentiation by squaring.

Here is a counter example:
.96279338^63
32S:    9.17455514137e-2
35S:    9.17455514136e-2
exact:  9.174555141365119..e-2

For this case, the 32S provides the correct rounded value, but not the 35S.

So definitively the accuracy is not significantly improved, the only small benefit is a faster result for small positive integer powers.

More historic notes

I showed above that the HP 9825/35/45 series machines (1976-78) were using exponentiation by squaring for integer powers between -32768 and 32767.
The reason is quite clear, it is due to the modest accuracy of the log/exp function of these machines, without guard digits as were the early HP handhelds too.
Example on the 9845:
2^3 = 8 exact (exponentiation by squaring)
but 4^1.5 = 7.99999999988

However, the exp/log implementation became soon accurate enough on the later Series 80 (1980) and Series 200 BASIC (1981), so the exponentiation by squaring was abandoned and the exponentiation y^x solely relied on the formula exp(x*log(y)) for all power values even for x=2.
The accuracy was similar to the exponentiation by squaring method, in the range of +/1 ULP for not-too-large results, with a few worst cases for larger numbers.

Interesting enough, the HP BASIC manuals for the Series 200 (for instance here, dated 1982) included a section "Exponentiation vs. Multiply and SQR" in the chapter "Efficient Use of the Computer's Resources":

Quote:Exponentiation is very slow when compared to other mathematical operations. [...]
The most common examples are squaring a number or finding a square root. [...]
... dramatic savings can be gained when raising numbers to an integer power. [...] [by using] repeated multiplication.

J-F