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

Question

So now I am reading Earth Lisp, and Lisp is completely different than the other programming languages ​​I have seen.

In any case, the book contains code that we would like to introduce 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 main goal is to create a number guessing game in which the user / player selects the number, and then the computer tries to guess the number. It performs a “binary search” to find the player’s number, informing the player whether the computer exceeds the number or less than the player’s number.

I am a bit confused about the ash function. I understand that this is vital for binary search, but I'm not quite sure why. The book explains somewhat what it does, but it is a bit confusing.

What does the ash function do? Why did he pass the *small* parameters added to *big* and -1 ? How it works? What is the purpose of binary search?

Answer 1

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

Answer 2

Thanks to Basile Starynkevitch for helping me ...

In any case, ash performs an arithmetic shift operation .

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

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

 8 * 1 = 8 4 * 1 = 4 2 * 0 = 0 1 * 1 = 1 8 + 4 + 0 + 1 = 13 

The start (ash 13 -1) will look at binary representation 13 and perform an arithmetic shift of -1, shifting all bits to the right by 1. This will lead to binary output 110 (chopping 1 at the end of the original number). 110 in binary equivalent is equivalent to 6 in decimal, which can be calculated as follows:

 4 * 1 = 4 2 * 1 = 2 1 * 0 = 0 4 + 2 + 0 = 6 

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

This is because binary is base 2.

Answer 3

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

It performs a bit shift operation, more precisely an arithmetic shift, as explained / presented graphically for the Lisp special case:

 > (ash 51 1) 102 

When you do this (ash 51 1) it will shift the binary number 51, i.e. 110011 to 1 bit place to the left, and as a result 1100110 that will give you 102 in decimal. (the process of converting binary to decimal is explained in this answer )

Here it adds 0 in the free most right place (named L east S, ignoring B it).

 > (ash 51 -1) 25 

When you do this (ash 51 -1) it will shift the binary code 51, i.e. 110011 by 1 bit to the right side (a negative value means the opposite direction) and as a result 11001 that will give you 102 in decimal.

Here it discards the excess LSB.

In a specific example of the guss-my-number game illustrated in Land of Lisp, we are interested in halving the range by half or medium. So, (ash (+ *small* *big*) -1)) doubles 100 + 1 = (ash (+ *small* *big*) -1)) to get 50. We can check this 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 

It is interesting to note that you can double the value of an integer by shifting left by 1 bit, and (approximately) double it by moving right by 1 bit.