Using 'ash' in LISP to perform a binary search?

Question

So, I'm reading Land of Lisp now, and Lisp is turning out to be quite different than other programming languages that I've seen.

Anyways, the book provides some code that we're meant to enter into the CLISP REPL:

(defparameter *small* 1)
(defparameter *big* 100)

(defun guess-my-number ()
    (ash (+ *small* *big*) -1))

(defun smaller ()
    (setf *big* (1- (guess-my-number)))
    (guess-my-number))

(defun bigger ()
    (setf *small* (1+ (guess-my-number)))
    (guess-my-number))

Now, the basic goal is to create a number guessing game wherein the user/player chooses a number, and then the computer tries to guess the number. It performs a "binary search", to find the player's number, by having the player report whether the computer-guessed number is higher or lower than the player's number.

I'm a little bit confused about the ash function. It's my understanding that this is vital to the binary search, but I'm not really sure why. The book somewhat explains what it does, but it's a little confusing.

What does the ash function do? Why is it passed the parameters of *small* added to *big* and -1? How does it work? What purpose does it serve to the binary search?

Trapper

See the HyperSpec entry on ASH: "ash performs the arithmetic shift operation on the binary representation of integer, which is treated as if it were binary." – Bland

Answer 1

Google gives you this page which explains that ash is an arithmetic shift operation. So (ash x -1) shift x by one bit to the right, so gives its integer half.

Jermayne

So it effectively finds the average of *small* and *big*, but it returns a whole number rather than a floating point? – Trapper

Yes, and it needs *small* and *big* to be integers. – Jermayne

It is actually not necessary to use ash to achieve integer division in Lisp, there are also the floor and truncate functions. You could therefore replace (ash x -1) with (floor x 2). – Precipitin

If you'd used the normal division operator, it would've returned a rational rather than a float (so (/2 5) is actually 2/5 rather than 0.4, might be significant, since floats have assorted round-off issues that rationals do not; on the other hand rationals do not usually have dedicated accelerators). – Yukikoyukio

Answer 2

Thanks to Basile Starynkevitch for the help on this one...

Anyhow, ash performs an arithmetic shift operation.

In the case of (ash x -1) it shifts x by one bit to the right, which ultimately returns the integer half.

For example, consider the binary number 1101. 1101 in binary is equivalent to 13 in decimal, which can be calculated like so:

8 * 1 = 8
4 * 1 = 4
2 * 0 = 0
1 * 1 = 1

8 + 4 + 0 + 1 = 13

Running (ash 13 -1) would look at the binary representation of 13, and perform an arithmetic shift of -1, shifting all the bits to the right by 1. This would produce a binary output of 110 (chopping off the 1 at the end of the original number). 110 in binary is equivalent to 6 in decimal, which can be calculated like so:

4 * 1 = 4
2 * 1 = 2
1 * 0 = 0

4 + 2 + 0 = 6

Now, 13 divided by 2 is not equivalent to 6, it's equivalent to 6.5, however, since it will return the integer half, 6 is the acceptable answer.

This is because binary is base 2.

Trapper

Answer 3

Q. What does the ash function do? Why is it passed the parameters of small added to big and -1? How does it work? What purpose does it serve to the binary search?

It does operation of of shifting bits, more precisely Arithmetic shifting as explained/represented graphically for particular case of Lisp:

> (ash 51 1)
102

When you do (ash 51 1) it will shift the binary of 51 i.e 110011 by 1 bit place towards left side and results in 1100110 which gives you 102 in decimal. (process of binary to decimal conversion is explained in this answer)

Here it adds 0 in the vacant most right place (called Least Significant Bit).

> (ash 51 -1)
25

When you do (ash 51 -1) it will shift the binary of 51 i.e 110011 by 1 bit place towards right side (negative value stands for opposite direction) and results in 11001 which gives you 102 in decimal.

Here it discards the redundant LSB.

In particular example of "guess-my-number" game illustrated in Land of Lisp, we are interested in halving the range or to average. So, (ash (+ *small* *big*) -1)) will do halving of 100+1 = 100 / 2 to result in 50. We can check it as follows:

> (defparameter *small* 1)
*SMALL*
> (defparameter *big* 100)
*BIG*
> 
(defun guess-my-number ()
    (ash (+ *small* *big*) -1))
GUESS-MY-NUMBER
> (guess-my-number)
50

An interesting thing to notice is you can double the value of integer by left shifting by 1 bit and (approximately) halve it by right shifting by 1 bit.

Grapnel