S&SMC #7: My Solutions And Comments [LOOOOONG]
Message #22 Posted by Valentin Albillo on 8 July 2004, 8:49 a.m.,
in response to message #1 by Valentin Albillo
Thanks to all of you interested in my Challenge, whether 'posters' or 'lurkers'. Questions have been answered correctly and some working programs
have been produced, though some of you 'cheated' and found the answers by
analyzing the test cases I gave, instead of actually implementing h(n) as defined, which was the intended exercise. Well, so much for giving test cases, now for my solution and comments:
Note: All the code herein is for the HP-71B because its English-like BASIC syntax makes it very easy
to understand and vey easy to translate to RPN/RPL, while the reverse isn't exactly true. Also, even if you haven't got an HP-71B, you can try and run all the code and examples featured here by using Emu71, Jean-François Garnier's superb HP-71B emulator which you can download for free from that link.
First part: The Program
The Challenge required you to implement h(n) defined for integer n > 0
as follows:
h(1) = 1
h(3) = 3
h(2n) = h(n)
h(4n+1) = 2*h(2n+1)-h(n)
h(4n+3) = 3*h(2n+1)-2*h(n)
If your HP machine does natively support recursion, this is very easy to implement, like this HP-71B version, which defines a user-defined function FNH(N) which computes h(n) by making recursive calls to itself:
10 DEF FNH(N) @ IF N=1 OR N=3 THEN FNH=N @ END
20 ON RMD(N,4)+1 GOTO 30,40,30,50
30 FNH=FNH(N/2) @ END
40 FNH=2*FNH((N+1)/2)-FNH((N-1)/4) @ END
50 FNH=3*FNH((N-1)/2)-2*FNH((N-3)/4) @ END DEF
Implementing h(n) in an HP calc without recursion is much more tricky,
and usually requires dealing with stacks to keep the parameters and
returns for the ever deeper recursive calls, but once you get the knack
of it, it's actually fairly straightforward.
However, for this particular challenge, where implementing the function is just for the sake of using it to do the sleuthing and answer the questions,
we can make do with a much simpler technique, which will allow us to instantly get the value of h(n) for a range of n values large enough for our purposes, and does not require recursion at all so it can be easily
implemented in most any HP calculator this side of the HP-67 or so.
Instead of recursion, we'll use a suitably dimensioned array (or range
of registers) to keep the function values, which will be constantly
reused to generate further values, substituting recursion for direct
array lookup, like this:
10 DESTROY ALL @ OPTION BASE 1 @ INTEGER H(1000)
20 FOR N=1 TO 1000 @ IF N=1 OR N=3 THEN H(N)=N @ GOTO 70
30 ON RMD(N,4)+1 GOTO 40,50,40,60
40 H(N)=H(N/2) @ GOTO 70
50 H(N)=2*H((N+1)/2)-H((N-1)/4) @ GOTO 70
60 H(N)=3*H((N-1)/2)-2*H((N-3)/4) @ GOTO 70
70 NEXT N @ DISP "Ready: Use FNH(n) (1 <= n <= 1000)" @ END
80 DEF FNH(N)=H(N)
Notice just how closely does this mimic the recursive version, only
using H(n) (the array) instead of FNH(n) (the recursive call). This
version does pre-compute h(1) to h(1000) and stores the results in
array H, to be used by the user-defined function FNH(n), just like
in the recursive version. Actually, you could use just H(n) directly,
instead of FNH(n), but this way both versions work alike and the
following examples using them are the same. Don't forget to RUN this
version for it to generate the values (RUN is not needed for the recursive defininition).
This makeshift, non-recursive version generates all 1000 values very
fast, and using FNH afterwards is much, much faster; however, it does take more
memory (to store the values) and is limited to the range 1-1000, while
the recursive version doesn't have any such limitation. But for quickly
and effortlessly implementing a recursive definition in a hurry, this
array technique does deliver the goods !
Second part: The Questions
Using our newly implemented FNH, we can do some sleuthing to try and
answer the questions, namely:
- "What's the value of h(2^n) ? ditto h(2^n + 1) ? h(2^n - 1) ? h(m * 2^n) ?"
For the first question, we will try this, from the command line:
FOR N=1 TO 5 @ X=2^N @ DISP X,FNH(X) @ NEXT N
You'll get all 1's, so it seems that h(2^n) = 1.
Similar command lines will quickly reveal that h(2^n+1) = 2^n+1 and
h(2^n-1) = 2^n-1. As for h(m*2^n), sampling a few values like this:
FOR M=14 TO 18 @ FOR N=1 TO 3 @ X=M*2^N @ DISP M;FNH(M);X;FNH(X) @ NEXT N @ NEXT M
will make it crystal-clear that h(m*2^n) = h(m).
- "For which n is h(n) = 100 ?"
Sampling any random values or range of values makes it obvious that
h(n) in always odd, so it can never be an even value like 100.
- "For which n is h(n) even ?"
Ditto. h(n) is always odd.
- "If n is odd and m = h(n), what's the value of h(m) ?"
Sampling a random range of odd n values, like this:
FOR N=431 TO 451 STEP 2 @ DISP N;FNH(FNH(N)) @ NEXT N
makes it absolutely clear that in this case h(m) = n.
- "What are the values of h(h(n)) ?"
Ditto. As we've seen in the previous question, if n is odd then
h(h(n)) = n. If n is even, then h(h(n)) is n with all factors 2 casted out.
- "For which values of n do we get h(n) = n ?"
This one is tricky. As we've seen in question (1) above, if n is a
power of two plus or minus one, then h(n)=n. But are there any other
values apart from these ? Let's try, add these lines to the program:
100 FOR N=100 TO 300 @ IF FNH(N)=N THEN DISP N;
110 NEXT N @ DISP
Now running it (using RUN 100, to avoid clearing the array in the case
of the non-recursive version), produces at once:
107 119 127 129 153 165 189 195 219 231 255 257 273 297
where the powers of 2 plus/minus one do appear (127-129, 255-257), plus
a host of other values, but though it's evident that there's some structure
to it all, it isn't clear what it might be.
However, there are some signs here and there waiting for us to notice. Though the function's definition doesn't seem to have much to do with powers of 2, we've found that such arguments are indeed special. Exact powers of 2 are always smashed to 1, while their predecessors and successors are returned intact. Might it be the case that working in base-10 is actually
confusing the issue ? How would it all look if we used base-2 instead, where powers of 2 are very 'round' numbers (10,100,1000,10000, ...) ?
Let's try ! We'll show both arguments and results in base-2 and see how
it all looks like. Altering line 100 above like this:
100 FOR N=100 TO 300 @ IF FNH(N)=N THEN DISP N;BSTR$(N,2)
and running it again (using RUN 100), we get these results:
107 1101011
119 1110111
127 1111111
129 10000001
153 10011001
165 10100101
189 10111101
195 11000011
219 11011011
231 11100111
255 11111111
257 100000001
273 100010001
297 100101001
where it is obvious that all n being returned intact by h(n) share a
common trait: their binary representations are palindromic ! Reversing
their bit-order leaves them unchanged, they are the mirror images of
themselves.
Second part encore: The Big Question [tm]
"Just what on Earth does h(n) do to n ??"
Well, once we've empirically explored how h(n) works and with our intuition
sharpened by our previous findings, it's only natural for us to make a bold final statement:
Given an argument n, h(n) massages it a little while and then simply, in three
words, reverses its bits.
As further confirmation, this command line:
FOR N=121 TO 137 STEP 2 @ DISP N,BSTR$(N,2),FNH(N),BSTR$(FNH(N),2) @ NEXT N
produces:
n n (base2) h(n) h(n) (base2)
-----------------------------------------
121 1111001 79 1001111
123 1111011 111 1101111
125 1111101 95 1011111
127 1111111 127 1111111
129 10000001 129 10000001
131 10000011 193 11000001
133 10000101 161 10100001
135 10000111 225 11100001
137 10001001 145 10010001
which clearly shows the bit-reversal at work for odd n. Even n are
treated likewise, but as they end in one or more zeroes, these
are rendered non-significant upon reversal, and do not show up in the
output, for instance:
n = 136 = 10001000 -> h(n) = 00010001 = 10001 = 17
Conclusion
Of course now that we fully know what h(n) does, we can then proceed to write a new, non-recursive, non-array implementation of h(n), like this:
10 DEF FNF(N)=BVAL(REV$(BSTR$(N,2)),2)
That's all there's to it. This single-line (more like half-line) user-defined function will do the same as our previous recursive implementation (reversing the binary bits of its argument), only orders of magnitude faster (a mere hundredths of a second for any legal argument), and using orders of magnitude less memory (neither recursion nor arrays involved, though it does use BVAL and BSTR$, which are keywords from the Math ROM, and REV$ which is a very popular keyword featured in a number of LEX files).
Well, that's as far as it gets. I hope you've found all this interesting and enjoyable
and perhaps even enlightening. Whatever the case, I'm sure you'll
agree with me that having such a perfecty normal-looking recursive
function definition actually perform a bit-reversal of its argument
is quite unexpected and kind of surprising, to say the least !
As I see it, it is like this function, instead of changing the arithmetic value
of its argument, it rather does alter its shape instead, its physical orientation
in some sense, disregarding the actual value being involved.
Mathematics are so beautiful. And these wonderful HP machines can serve
us well to sharpen our insights, our intuition, in this amazing journey.
As for the 'prize', all of you who have posted your ideas, programs and insights to this thread and wish to receive a copy of the 1280 x 1024 image in the mail, please send me an e-mail to my e-mail address listed here and I'll send it back to you at once.
Best regards from V.
Edited: 8 July 2004, 10:12 a.m.
|
Go back to the main exhibit hall