1

I need to define a lisp function iscube which takes an integer as an argument and returns T if n is a cube and nil otherwise.

I only know how to make a intger be a cube, but how to determine a integer is a cube ?

I am not allowed to use any special math functions such as log for this problem...

example iscube(8) will return true, same as iscube(-8) will return true.

MeiLin Xu
  • 33
  • 4
  • 5
    Welcome at Stackoverflow. It would be great if you could tell us what you have tried so far and what your code looks like. Stackoverflow is best used if you have a real programming problem with code, examples and a problem description. – Rainer Joswig Apr 23 '19 at 15:21

3 Answers3

1

You should notice that it is not so clever as it seems to get your homework done on SO. But as I have to fill my break with something fun you could start with this:

(defun is-cube-p (n)
   "Returns T if N is a cube number."
   (zerop (nth-value 1 (round (abs (expt n 1/3))))))

CL-USER> (is-cube-p -8)
T
CL-USER> (is-cube-p 8)
T
CL-USER> (is-cube-p 9)
NIL

I am neither a mathematician nor a CL professional, so there is no guarantee that this is the best way to solve your problem.

Martin Buchmann
  • 1,161
  • 7
  • 14
  • uh, it is not my homework actually.... it is just a final practice question. Anyway thank you for your solution ! – MeiLin Xu Apr 23 '19 at 19:08
  • You want to find the digital root of the number in question. Just google for digital root cubes – David Hodge Apr 23 '19 at 20:04
  • Sorry, but I don’t get it (I tried Google). How is the repeated digit sum connected to the cube root? Could you provide a reference? – Martin Buchmann Apr 24 '19 at 05:12
  • 2
    @Martin Buchmann, But note there is an issue with roundoff error for large numbers. For example, (is-cube-p 9261000) -> T, but (is-cube-p 9261001) -> T also. – davypough Apr 25 '19 at 01:28
  • @davypough Good point, I was expecting something like this and didn‘t claim that my code is production ready. I am curious if someone could provide a mathematically sound solution. – Martin Buchmann Apr 25 '19 at 12:53
  • 1
    @MartinBuchmann Try this https://stackoverflow.com/questions/32017356/fast-way-to-check-if-long-integer-is-a-cube-in-java – David Hodge Apr 26 '19 at 02:41
  • @DavidHodge Now I am at least closer to understand your first comment ;-) We can use the digital root to check quickly whether the number in question can be a perfect cube. The final proof must then follow using another method, e.g. checking the prime factors? – Martin Buchmann Apr 29 '19 at 18:42
  • 2
    Yep, you have it. Note that solutions using expt might suffer from floating point precision issues, especially for large numbers. – David Hodge Apr 29 '19 at 18:50
1

I'll give a solution similar to Martin's, and it will be slower. But it may be more understandable for some people.

(defun is-cube-p (n)
  (let* ((real-root (expt n 1/3))
         (real-root-int-part (round real-root))
         (m (expt real-root-int-part 3)))
    (= n m)))

The idea is to first calculate the cube root of n, then find the integer part the root. We cube the integer part back to m and compare m and n. If m == n then n is a cube.

larme
  • 71
  • 1
  • 3
  • This is the only solution using `(expt n 1/3)` here that actually works correctly. Note that `is-cube-p` does not handle negative inputs, but that is easily fixed. – ad absurdum Apr 02 '21 at 04:18
0

Some of the other answers on this page suffer from problems with floating point precision, and are thus incorrect; in particular, expt can return floating point approximations. As one commenter pointed out, this can lead to numbers which are not cubes being reported as cubes. The number 9,261,000 is a perfect cube (the cube of 210), but the number 9,261,101 is not a perfect cube; yet two of the three other answers here report that 9,261,101 is a perfect cube.

One good solution is to find the cube root of n, convert that to an integer, and to compare the cube of that integer with n, avoiding the precision issues.

Another solution is to use binary search with integer values. I include this solution here not because it is the best solution, but because it is good to remember that fundamental ideas like binary search can be widely applied. In a circumstance where you are unsure about how to handle floating point precision problems, a binary search over integers may get you to a correct result.

(defun cubep (n)
  (let ((n (abs n)))
    (flet ((midpoint (a b) (truncate (+ a b) 2))
           (closep (a b) (< (- b a) 2)))
      (labels ((bsearch (start end)
                 (let* ((mid (midpoint start end))
                        (mid-cubed (expt mid 3)))
                   (cond ((closep start end) nil)
                         ((< mid-cubed n)
                          (bsearch mid end))
                         ((> mid-cubed n)
                          (bsearch start mid))
                         (t t)))))
        (or (zerop n)  ; test ends of search range
            (= n 1)
            (bsearch 0 n))))))

Here, since non-negative numbers with cube roots correspond with negative numbers with cube roots, only the absolute value of n is considered. The integers between 0 and n are searched until the cube root of n is found, or until the search interval is too small to contain another integer.

CL-USER> (cubep 8)
T
CL-USER> (cubep -27)
T
CL-USER> (cubep 11)
NIL
CL-USER> (cubep 9261000)
T
CL-USER> (cubep 9261001)
NIL

The floating point precision problems mentioned earlier become noticeable when numbers begin to get large. Here is a function to compare the results of two implementations:

(defun compare (func1 func2 a b)
  (let ((failures (loop for n from a to b
                        unless (eql (funcall func1 n) (funcall func2 n))
                          collect n)))
    (if (null failures)
                     (format t "PASSED~%")
                     (format t "FAILURES: ~A~%" failures))))

Here are the results of comparing cubep with the incorrect cube-p; 12 numbers between 9,260,000 and 10,000,000 are mis-reported as perfect cubes due to mishandling of floating point numbers. These are large input numbers, but they aren't that large. The results are identical for the incorrect version of is-cube-p:

CL-USER> (compare #'cubep #'cube-p 9260000 10000000)
FAILURES: (9260999 9261001 9393930 9393932 9528127 9528129 9663596 9663598
           9800343 9800345 9938374 9938376)
ad absurdum
  • 19,498
  • 5
  • 37
  • 60