Lispology

About me

Feeds

Improving truncate

28th August 2025

As an example of simple recursion I recently wrote a function to reverse the digits of an integer:

(defun reversedigits (n &optional (a 0))
  (cond
   ((zerop n) a)
   (t (reversedigits
       (truncate n 10)
       (+ (* 10 a) (mod n 10))))))

I was a bit shocked when, for a particular input, it gave the wrong result:

> (reversedigits 123456789)
997654321

I checked on an implementation of Common Lisp, and it gave the expected answer:

CL-USER 1 > (reversedigits 123456789)
987654321

I couldn't imagine what could be causing this problem, but it turned out to be less trivial to solve than I expected.

The problem

In my uLisp interpreter I was evaluating:

(truncate n m)

by evaluating:

(truncate (/ n m))

which seemed perfectly reasonable. However:

(/ 123456789 10)

when expressed as a 32-bit floating-point number doesn't have the 8 digits of precision to give the correct answer of 12345678. You can demonstrate this in Common Lisp by evaluating:

CL-USER 1 > (truncate 12345678.9)
12345679

So how does Common Lisp manage to get the following correct:

CL-USER 1 > (truncate 123456789 10)
12345678

The answer is that it stores (/ 123456789 10) as the exact rational 123456789/10, rather than as a 32-bit floating-point number which would lose precision ^[1].

uLisp is a compact subset of Common Lisp and doesn't include rational numbers, so what should truncate do?

The solution

I concluded that it should give the most accurate answer possible for the parameters its given. I can't fix the case of:

(truncate (/ 123456789 10))

but in the case of:

(truncate 123456789 10)

where the parameters are 32-bit integers, it's possible to return a precise result.

Implementing ceiling

It affects floor and ceiling too, and they are slightly more complicated, so here's the new algorithm to implement ceiling using the C function ceil(). Note that the C function ceil() returns a floating-point argument:

If there is only one argument: if it's an integer return it, otherwise return (int)ceil(arg1).
If there are two arguments and they are not both integers return (int)ceil(arg1/arg2).
If there are two arguments and they are both integers:

Calculate the integer quotient and remainder: quo = arg1/arg2, and rem = arg1-(quo*arg2).
If arg1 and arg2 are different signs or rem=0 return quo; otherwise return quo+1.

The implementation of floor and truncate is similar.

Latest release

The latest releases of uLisp (ARM uLisp 4.8e and ESP uLisp 4.8f) implement new versions of truncate, floor, and ceiling; all three functions now give exact results for two integer parameters.

So now reversedigits gives the correct answer:

> (reversedigits 123456789)
987654321

^ Thank you to Rainer Joswig for a discussion that helped me understand this.

Previous: Multiplying matrices using functional programming