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?