Samuel Tardieu @ rfc1149.net

Small is beautiful

,

A friend of mine challenged me today to the number game. This is a classical one, where you have to guess a number between 0 and 999, and the computer will tell you whether you were right on or if you were above or below the chosen number.

Instead of doing dichotomy by hand or with a calculator, I wrote the following Forth snippet using the gforth interpreter:

: guess 2dup + 2/ dup . ;
: init 0 999 guess ;
: big nip guess ;
: small -rot big ;

Here is the transcript of an interactive session (what I typed is in black, what was printed by gforth is in red):

init 499 ok
small 749 ok
small 874 ok
big 811 ok
big 780 ok
big 764 ok
small 772 ok
big 768 ok
big 766 ok
big 765 ok

For those not well-versed in Forth, here is how it works:

  • guess takes the low bound and the high bound from the stack, put them back there and adds the middle value as well, and prints it.
  • init starts a session by putting 0 and 999 on the stack and calls guess to print the initial value to be entered.
  • big removes the high bound from the stack, leaving only the low bound and the previous middle value, then calls guess to get a new value.
  • small replaces the low bound on the stack by the previous middle value, and calls guess. The stack manipulation and the call of guess would be done using ~~rot nip guess, and I took advantage of big by factoring it into ~~rot big.

That’s it. Who could now pretend that small isn’t beautiful?

blog comments powered by Disqus