# Calculating the cube root

Inspired by a question on SO I was checking how to calculate the cube root of an integer and found a C-ish solution on Hacker's Delight:

// Program for computing the integer cube root.
// Max line length is 57, to fit in hacker.book.
#include <stdio.h>
#include <stdlib.h>     //To define "exit", req'd by XLC.

// Execution time is 3 + (11 + mul)11 = 124 + 11*mul (avg) cycles.
// ------------------------------ cut ----------------------------------
int icbrt1(unsigned x) {
int s;
unsigned y, b;

y = 0;
for (s = 30; s >= 0; s = s - 3) {
y = 2*y;
b = (3*y*(y + 1) + 1) << s;
if (x >= b) {
x = x - b;
y = y + 1;
}
}
return y;
}


I tried to adapt this to Common Lisp and came up with this:

(defun icbrt (x)
"Returns the integer cube root of X."
(assert (plusp x) (x) "Please provide a positive integer! ~D < 0" x)
(loop for s downfrom 30 to 0 by 3
for y of-type integer = 0 then (* 2 y)
for b of-type integer = (ash (1+ (* 3 y (1+ y))) s)
when (>= x b)
do (incf y)
(setf x (- x b))
finally (return y)))


While it works I am still wondering if it could be express more idiomatic. I am especially unsure about the setf within the loop construct.

Any comment is gratefully acknowledged.

• I find the translation substantially correct and even idiomatic: a minor point is to change (setf x (- x b)) with the more concise (decf x b). – Renzo May 11 at 19:45
• Thanks! I forget about decf too often. – Martin Buchmann May 13 at 9:58

You can get rid of incf and setf; the varying x is replaced by a variable named z; I express the comparison as a boolean variable greater (for lack of a better name), which gives:

(defun icbrt (x)
"Returns the integer cube root of X."
(check-type x (integer 1))
(locally (declare (type (integer 1) x))
(loop
for s downfrom 30 to 0 by 3
for z of-type integer = x then (if greater (- z b) z)
for y of-type integer = 0 then (* 2 (if greater (1+ y) y))
for b of-type integer = (ash (1+ (* 3 y (1+ y))) s)
for greater = (>= z b)
finally (return y))))


Note also that I removed the assertion and used check-type instead. While the additional comment is nice in the assert expression, it adds to the things developers have to maintain (think consistency of error messages), whereas check-type is supposedly already displaying the right amount of information to the user, and throws the right kind of exception.

• Very helpful hint to use check-type. – Martin Buchmann May 13 at 10:00
• @MartinBuchmann Thanks. I did not suggest it first because I am not sure if it is correct, but maybe using more specific types like fixnums is possible here. – coredump May 13 at 10:27
• For most cases fixnum should be sufficient, i guess. – Martin Buchmann May 13 at 12:52