## Friday, August 21, 2009

### A small puzzle

I got this from Marshall Spight today.
```(define (f a b)
(if (zero? b)
a
(f (logxor a b)
(* (logand a b) 2))))
```

Q: F is better known as ______ ?

You may need these auxiliary functions.
```
(define (logand a b)
(cond ((zero? a) 0)
((zero? b) 0)
(else
(+ (* (logand (floor (/ a 2)) (floor (/ b 2))) 2)
(if (or (even? a)
(even? b))
0
1)))))

(define (logxor a b)
(cond ((zero? a) b)
((zero? b) a)
(else
(+ (* (logxor (floor (/ a 2)) (floor (/ b 2))) 2)
(if (even? a)
(if (even? b) 0 1)
(if (even? b) 1 0))))))

```
And please don't just post a spoiler. If you just want ‘first credit’, email me directly.

What's amusing to me is that it isn't obvious if F even terminates.

1. Aren't logand and logxor just bitwise-and and bitwise-xor?

This isn't intended to be a spoiler, but the function is pretty much a straightforward translation of what it would look like in hardware.

2. Nice. It should be obvious, but I didn't recognize it until after I tried a few inputs.

3. Stelian Ionescu sent in the solution first at 8:33 PDT. Bob Miller sent his solution in at 9:22 PDT.

The function is very similar to what is commonly built in hardware, but not exactly the same. The hardware would do it one bit at a time through combinational logic. The straightforward translation of this algorithm to hardware would involve iteratively applying the steps.

4. logand and logxor are also defined in srfi-60, if your implementation supports it (,open srfi-60 in scheme48).