Programming Challenge: Powers and Roots

[Patrick]

Through the evil of eBay, I recently managed to pick up a pristine copy of the HP-15C Advanced Functions Handbook. I've only had a half hour or so to read it so far, but it appears to be quite excellent.

One of the interesting numerical oddities that they point out surrounds the function obtained by taking the square root of a number 50 times and then taking the square or the result 50 times. While mathematically you should end up with the identity function (f(x) = x, for x >= 0), numerically you end up with something quite different.

The little challenge that I propose is to write the shortest program to compute the function described. You may only use square roots, squares and arithmetic functions. No y^x, no log/ln, no e^x, etc.

In order to make the problem non-trivial, I impose the additional constraint that you may not use any conditional tests, such as [x=0?], [ISG], [DSE], or [F?].

A secondary question is how large the number 50 can be increased to on your selected platform using only these self same functions.

Since I only know RPN, not RPL, I'd be primarily interested in seeing the solution done using the former method. I suggest the HP-11C and HP-15C as the platforms to use since I happen to like them the best, but others would work equally well.

[Dave Shaffer (Arizona)]

Am I missing something in your challenge?

re: "One of the interesting numerical oddities that they point out surrounds the function obtained by taking the square root of a number 50 times and then taking the
square or the result 50 times. While mathematically you should end up with the identity function (f(x) = x, for x >= 0), numerically you end up with something quite
different."

Unless you do something fancy to maintain precision (maybe that's the challenge?), if you take the square root 50 times (I assume you mean the equivalent of hitting the square root key 50 times in a row), unless you start with a very big - or very small - number, you wind up with 1.000000000! No matter how many times you square that, you're gonna get 1. (I just tried with my '32SII: 99*10^99 goes to 1.000000000 on the display after about 40 square root pushes.)

[Patrick]

Well, my challenge hasn't touched upon the numerical lessons (yet). I've only asked for an algorithm to compute the function in the shortest number of steps. Taking advantage of the numerical oddities wasn't what I had in mind, but your point is certainly valid.

[Vieira, Luiz C. (Brazil)]

Hi;

the example exactly illustrates something that cannot be computed with the Voyagers available range.

I'd suggest to write an algorithm or program to compute the uncertainty of the result. Something like the value placed in the Y-register after a numerical integration.

The Advanced Functions Handbook deals with accurate, errors and error recovering/detection in an HP15C when using advanced functions - integration, SOLVE, complex numbers and matirces - as you have already seen. You can perform many of the examples in the hP42S and check for the difference/correctness obtained when internal 15 digits take place, instead of 12 internal digits available in the HP15C. You may also see that many examples focus unusual situations, say, regular users unusual situations.

Just to add a few more information.

Luiz C. Vieira - Brazil

[Michael F. Coyle]

I observed the same thing...it takes only 38 square roots to get from 9.999999999E99 to 1.0 on the HP-11C, and only 39 square roots to get from 1.0E-99 to 1.0. Still, even though it's therefore useless, I present a solution anyway, in only 32 steps. (Two of which are optional.) To make it more fun, I will present it without comment and (sadistically) leave it as an exercise to the reader to puzzle out.

- Michael

f LBL A      (This step's optional!)

GSB 5

GSB 4

sqrt x

sqrt x

f PSE        (This one too!)

g x^2

g x^2

GSB 8

GSB 8

f LBL 8

GSB 7

f LBL 7

GSB 6

f LBL 6

g x^2

g x^2

g x^2

g x^2

g RTN

f LBL 5

GSB 4

f LBL 4

GSB 3

f LBL 3

GSB 2

f LBL 2

sqrt x

sqrt x

sqrt x

sqrt x

g RTN