7
\$\begingroup\$

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.

\$\endgroup\$
  • 2
    \$\begingroup\$ 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). \$\endgroup\$ – Renzo May 11 at 19:45
  • \$\begingroup\$ Thanks! I forget about decf too often. \$\endgroup\$ – Martin Buchmann May 13 at 9:58
3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Very helpful hint to use check-type. \$\endgroup\$ – Martin Buchmann May 13 at 10:00
  • \$\begingroup\$ @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. \$\endgroup\$ – coredump May 13 at 10:27
  • \$\begingroup\$ For most cases fixnum should be sufficient, i guess. \$\endgroup\$ – Martin Buchmann May 13 at 12:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.