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 <font color="red">499 ok</font><br /> small <font color="red">749 ok</font><br /> small <font color="red">874 ok</font><br /> big <font color="red">811 ok</font><br /> big <font color="red">780 ok</font><br /> big <font color="red">764 ok</font><br /> small <font color="red">772 ok</font><br /> big <font color="red">768 ok</font><br /> big <font color="red">766 ok</font><br /> big <font color="red">765 ok</font><br />

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