How to check if the result of a calculation is a natural number?

Question

For another Project Euler struggle (using SBCL 1.3.17) I want to test if a number is a pentagonal number. This can be easily tested if the result of

(/ (+ 1 (sqrt (+ 1 (* 24 number)))) 6)

is a natural number. Ignoring that a natural number is not just an integer because number will have only positive values, I started using intergerp as a predicate but it did not work out for all tested numbers. So I came up with the following:

(defun is-pentagonal-p (number)
  "Returns T if NUMBER is a pentagonal number."
  (multiple-value-bind (n m)
      (floor (/ (+ 1 (sqrt (+ 1 (* 24 number)))) 6))
    (declare (ignore n))
    (when (zerop m) t)))

Which worked fine for simple examples, i.e. low number but failed again for high numbers as 1533776805. After quite a while I remembered my old Fortran days and ended up with:

(defun is-pentagonal-p (number)
  "Returns T if NUMBER is a pentagonal number."
  (multiple-value-bind (n m)
      (floor (/ (+ 1.0d0 (sqrt (+ 1.0d0 (* 24.0d0 number)))) 6.0d0))
    (declare (ignore n))
    (when (zerop m) t)))

which explicitly lower the rounding errors and gives the right results but leaves me with the feeling that I must have missed something much simpler and more lispy. Is this just paranoia?

Answer 1

Substance

If you use CLISP, you will get

(defun pentagonal-side (number)
  (/ (+ 1 (sqrt (+ 1 (* 24 number)))) 6))
(pentagonal-side 51)
==> 6
(pentagonal-side 1533)
==> 32.135838
(pentagonal-side 1533776805)
==> 31977

This is because ANSI CL permits sqrt to return rationals and CLISP does that. Thus you can use integerp:

(integerp (pentagonal-side 1533776805))
==> T

If your lisp (SBCL) always returns a float, you need to use sufficient precision, e.g.:

(pentagonal-side 1533776805d0) ; double-float
==> 31977.0d0
(pentagonal-side 1533776805f0) ; single-float
==> 31977.0
(pentagonal-side 1533776805s0) ; short-float
==> 31976.8s0

So, in your case, just pass an appropriate float:

(zerop (mod (pentagonal-side 1533776805d0) 1))
==> T

Caveat

It seems that single-float is enough, right?

(zerop (mod (pentagonal-side 1533776805f0) 1))
==> T

Nope!

(zerop (mod (pentagonal-side (1+ 1533776805f0)) 1))
==> T

Use "roundtrip"

It is not always easy to guess in advance which float type is appropriate. Moreover, it is quite imaginable that your number will be too large even for your Lisp's long-float. (CLISP has arbitrary float precision, most lisps do not, and even then you need to decide which precision to use in advance.)

Thus it is easier to stick with integers: make sure that the pentagonal-side that you calculate corresponds to the original number via roundtrip:

(defun pentagonal-side-int (area)
  (/ (+ 1 (isqrt (+ 1 (* 24 area)))) 6))
(defun pentagonal-area (side)
  (/ (- (* 3 side side) side) 2))
(pentagonal-side-int 1533776805)
==> 31977
(pentagonal-area 31977)
==> 1533776805
(defun pentagonal-number-p (number)
  (let ((side (pentagonal-side-int number)))
    (and (integerp side)
         (= number (pentagonal-area side)))))
(pentagonal-number-p 1533776805)
==> T
(pentagonal-number-p 1533776804)
==> NIL
(pentagonal-number-p 1533776806)
==> NIL

Style

Names

It is not a very good idea to mix styles. is-... is the C/Java style. ...-p is the Lisp style. I suggest that you stick with the latter for your Lisp code.

Float contagion

No need to convert all your numbers to floats:

(defun pentagonal-side-double (number)
  (/ (+ 1 (sqrt (+ 1 (* 24 (float number 1d0))))) 6))

should make all your calculations use double-float.

Return value

Use (zerop m) instead of (when (zerop m) t). Generally speaking, when is used in "procedural context", when the return value is discarded. If you use the value, you should use if instead, and (if (zerop m) t nil) is precisely identical to (zerop m).

Multiple values

You should probably use nth-value instead of multiple-value-bind plus ignore.

Standard functions

It is more readable to write (1+ ...) than (+ 1 ...).