Calculating the cube root

Question

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.

• Renzo: 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).

Answer 1

There is not much to say about this code, it is fine.

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.

• Martin Buchmann: Very helpful hint to use check-type.
• coredump: @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.
• Martin Buchmann: For most cases fixnum should be sufficient, i guess.