xdiff's bogosqrt

bogosqrt.c

/* from libxdiff's xutils.c */

long xdl_bogosqrt(long n) {
	long i;

	/*
	 * Classical integer square root approximation using shifts.
	 */
	for (i = 1; n > 0; n >>= 2)
		i <<= 1;

	return i;
}

bogosqrt.scm

; uncomment if you're on repl.it

#(define (quotient a b)
    (/ (- a (mod a b)) b))

#(define (arithmetic-shift n count)
    (if (< count 0)
        (quotient n (expt 2 (- count)))
        (* n (expt 2 count))))

(define (<< a b) (arithmetic-shift a b))
(define (>> a b) (arithmetic-shift a (- b)))

(define (xdl_bogosqrt n)
  (let loop ([i 1] [n n])
    (if (<= n 0)
        i
        (loop (<< i 1) (>> n 2)))))