Fixed-point Arithmetic in Picolisp

rick, 2016-08-27

For the impatient

Here’s the lowdown.

Picolisp is a cool, very small language that exemplifies KISS.
Picolisp does not have floating point numbers.
You can use integers to do most of what you use floating point numbers for.

Before we start, if you’re belly-aching or whining about not having floating point numbers to work with, don’t worry. What we’re about to do is not difficult at all or even terribly inconvenient. So, let’s “put our big boy pants on” and get started.

First, decide how many digits to the right of the decimal point you want your program to keep track of. This is called the scale. Say, you want to keep track of 3 digits to the right of the decimal point. You just call the scl function like this. (By the way, scl sets a global called *Scl to the value of its argument.)

: (scl 3)
-> 3

Next, you enter numbers as normal, i.e. put a decimal point in the number. Let’s try entering 19.46.

: 19.46
-> 19460

You can see here that picolisp interprets this as the integer 19460. The lower-order 3 digits are the fractional part. Simple.

Now, be careful of the automatic rounding.

: 0.2237683
-> 224

OK, here’s how you add and subtract numbers.

: (+ 123.435 98134.349)
-> 98257784
: (- 123.435 98134.349)
-> -98010914

One more “gotcha”: the representation of numbers with no fractional part should still contain a decimal point. Here’s how not to add 42 to 78.231.

: (+ 42 78.231)
-> 78273

And here’s how to do that correctly.

: (+ 42.0 78.231)
-> 120231

Multiplying and dividing is not as straight-forward as addition and subtraction. To do it, we rely on a very interesting primitive function in picolisp called */. Using this, the product of X and Y can be computed as (*/ X Y 1.0).

: (*/ 32.1 1.056 1.0)  # 32.1 * 1.056 = 33.8976
-> 33898

And the quotient of N and D can be computed as (*/ 1.0 N D).

: (*/ 1.0 91.8 1.323)  # 91.8 / 1.323 = 69.38775510...
-> 69388

Here’s how you format output so that it is “human readable”.

: (format (*/ 32.1 1.056 1.0) *Scl)  # again, 32.1 * 1.056 = 33.8976
-> "33.898"

Finally, you can control more rounding in the final formatting with the round function. Let’s round to the tenths place.

: (round (*/ 32.1 1.056 1.0) 1)
-> "33.9"

Does some of this code look a bit wordy or busy to you? Well, it’s Lisp; so, make some convenience functions. (Remember: big boy pants.) Now, go forth and create glorious hacks!

TL;DR¹

Picolisp is a nice language that has simplicity at the core of its (or I should say, its author’s) design philosophy. That’s one of its aspects that makes it beautiful, in my view. And so, its simplicity with regard to the intrinsic data types leads us to an interesting issue: picolisp does not have floating point numbers, only integers. So, how does one, say, divide 1 by 2 to yield one-half?

As one sharp denizen of #picolisp on freenode put it, one could always “use fractions”, which is to say, develop a fraction data-type/object and proceed with this. Even though he was joking when he said that, for some applications, the use of a fraction data-type can be very appropriate, if not, convenient. However, for most applications, most people feel more comfortable expressing those numbers with a decimal point; or, to be fair, the least we could say is that it seems that we all are very accustomed to such expressions. As evidence, notice how frequently we receive data from others that are in files that contain sequences of characters that look like “4.2” or “-0.42”, and not such expressions as “³⁄₄” or “3i + 4j”.²

Fixed-point arithmetic

So what does one do with this kind of data when using a language that only has integers as a numeric type?

Well, they might “follow their nose” and use integers to represent numbers with fractional values. People in the wider world of computing had already devised ways of representing such values with integers and performing certain arithmetic operations on them. Their methods fall under the rubric of fixed-point arithmetic. To get a feel for this, let’s start with a motivational example.

For instance, if I’m just adding dollars and cents on a calculator, I might type in the decimal point each time I enter an addend. I don’t know about you, but I consider that a wasted motion — just don’t type in the decimal point. This means that instead of entering dollars and cents, you are expressing the same value in cents only. So for a value like $4.25, enter 425. Then you keep track of the implicit decimal place yourself. So, if after adding a long list of prices in this way you end up with the number (integer) 132283, then what is your total? If you said, $1322.83, then give yourself a cigar!

Well, what did we just do? We used integers to represent numbers with fractional parts and performed arithmetic on them. That’s the basic idea behind fixed-point arithmetic.

The same method works for subtraction (when one admits signed integers). Now, the challenge is how to handle multiplication and division. But let’s get into that issue in the context of picolisp computations in the sections that follow.

But, before we proceed, note that the picolisp reference, when referring to fixed-point numbers, calls them “fixpoint numbers”. Not to worry, as both terms refer to the same thing; I will continue to use the term “fixed-point” here.

The `.` reader macro

There are some facilities in picolisp which make it very convenient to write code that handles fixed-point arithmetic.

The first is the . reader macro. When the picolisp reader sees a number expressed with a decimal point — that is, the way we naturally write decimal numbers, e.g. 4.25 or 0.831 — it will convert it to an integer.

Having the reader convert such numbers into integers is not only a useful convenience, but as we will discuss later, yields at least one advantage in avoiding some hard-wiring of our code (hard-coding).

Now, “that’s all well and good” that the reader will convert such expressions for you, but how does it know that, say, 1946 is meant to represent the fixed-point number 19.46 and not 1.946? Well, there is this idea of scale which is related to how many places to the right of the decimal point one wants to keep (depending on what is appropriate for the application of course). In picolisp, this is kept in a global called *Scl, and is usually set by the intrinsic function scl. An example is in order.

$ pil
: 1.946
-> 2
: (scl 3)
-> 3
: 1.946
-> 1946
: (scl 2)
-> 2
: 1.946
-> 195
: 19.46
-> 1946

Here’s the play-by-play.

We start picolisp at the shell prompt $, and enter the REPL whose prompt is :.
When we first enter 1.946 at the REPL, the scale is set to 0 (by default), and picolisp reads the number as a fractional decimal and simply rounds to the nearest integer, and the REPL returns the value 2. By the way, the REPL prefixes its response value with ->.
We set the scale to 3, meaning that we would like picolisp to keep track of the fractional part up to 3 places.
Then, we see that the same input 1.946 is now represented by the integer 1946.
When we change the scale to 2,
this time 1.946 is represented by the integer 195; note the effect of rounding.
Finally, the input 19.46 is represented by the integer 1946.

So we can see where this idea of scale gets its name: in order to determine its integer representation, the decimal point number is conceptually “scaled up” by *Scl orders of magnitude (and then rounded to the nearest integer).

This is a good time to re-emphasize that it is only the reader — and not the evaluator — that is doing this conversion.³

: (scl 2)
-> 2
: (quote 19.46)
-> (1946)

Also, note that we can enter either 4.25 or 425 — the latter being similar to how we entered numbers in our calculator example — and picolisp will interpret this as the same number, namely 425.

Addition and subtraction

Now that we have the help of the reader for input of numbers with an embedded decimal point and the “scale facility” (i.e. scl and *Scl), adding and subtracting such numbers is fairly easy.

: (scl 3)
-> 3
: (+ 1092.339 933.29 -7.764382)
-> 2017865

The exact answer — given arbitrary precision — is 2017.864618. (Or, ^1008932309⁄₅₀₀₀₀₀ if you have fractions. :) However, we had only asked to keep, and round to, the nearest thousandth, i.e., we said (scl 3).

Here’s how to enter the same expression the way we did in the calculator example.

: (+ 1092339 933290 -7764)
-> 2017865

Notice that I manually rounded the last addend, simulating the rounding (to *Scl “fractional digits”) that the picolisp reader would have done for us if we had instead entered -7.764382.

: -7.764382
-> -7764

If there is any “gotcha” to be concerned about, it is the one we mentioned in the first section: the representation of numbers with no fractional part (like a whole number) should be expressed with a zero fractional part. Recall this example from that section.

: (+ 42 78.231)
-> 78273

Oops, I had meant to add 42 to some number slightly greater than 78, so I thought the answer would be some number slightly greater than 120. How come this answer is still only slightly greater than 78? Hopefully, if you got caught in the “gotcha” as I did, at this point you remembered that the scale was, and is still now, set to 3; so, all numbers need to have three lower-order digits that represent the fractional part. So, 42 should be represented as 42000, or if you like 42.0 (and picolisp will convert it for you). And so, we finally conjure up the following, and once again, all is right with the world.

: (+ 42.0 78.231)
-> 120231

Multiplication and division

Multiplying and dividing these types of numbers is only slightly more involved than adding and subtracting.

To understand the method we are going to employ, let’s try a simple example: let’s multiply 0.6 by 7 giving (hopefully) 4.2, and let’s use scale 4 (more than enough “room” on the fractional side).

: (scl 4)
-> 4
: (* 0.6 7.0)
-> 420000000

Oops, that’s 42,000 (in “scale 4 land”). Do you see the problem? Since each factor in the product is scaled up by 10^4, our answer is off by 4 orders of magnitude. To compensate, we need to divide the product by 10^4.

There’s a similar problem when we divide. Let’s try dividing 4.2 by 0.6 to give 7.

: (/ 4.2 0.6)
-> 7

Ah, we got the right answer! … NO! Remember: we are in “scale 4 land” and so 7 is a representation of 0.0007, not 7; so actually we’re four orders of magnitude off (again!). We need to compensate, this time by multiplying the quotient by 10^4.

Almost.

Look at this division example.

: (/ 4.2 7.0)
-> 0

Dang. We lost some critical information due to the integer divide. Now, if we “compensate” by multiplying the quotient by 10^4, as we said before, it does us no good: we’ll still get zero.

To do this correctly, we will need to multiply the numerator by 10^4 first, then do the (integer) divide.

: (/ (* 4.2 10000) 7.0)
-> 6000

That’s correct: 6000 is the integer representation of 0.6 in “scale 4”. Here’s a better way.

: (/ (* 4.2 1.0) 7.0)
-> 6000

In fact, using 1.0 in your code in this situation is much better than using 10000, which is scale-specific. When you use 1.0, you are letting picolisp do the scale conversion for you. Think about it: if you write an application using fixed-point arithmetic and you have “buyer’s remorse” later and want to change the scale, you can simply change the scale once, and you don’t have to change any other part of your source, if you used 1.0 for your conversion (“compensation”) factor. If instead you peppered your code with the conversion factor of, say, 10000 (because you used scale 4), if you ever changed the scale, you’d have to chase down all the scale-specific factors and change them also.

Making things a bit easier

Finally, let’s consider a primitive function in picolisp that will make multiplication and division a bit easier (and interestingly, which was borrowed from the programming language Forth⁴). It’s called */ and it computes the product of all its arguments except for the last argument, and then divides this product by the last argument (and rounds, if necessary). Thus, (*/ 8 6 4) is 12.

So now, the product of fixed-point numbers X and Y can be computed by (*/ X Y 1.0) and the quotient of fixed-point numbers N and D can be computed by (*/ 1.0 N D).

Here is a reprise of the examples from the first section.⁵

: (*/ 32.1 1.056 1.0)  # 32.1 * 1.056 = 33.8976
-> 33898
: (*/ 1.0 91.8 1.323)  # 91.8 / 1.323 = 69.38775510...
-> 69388

Also note that the */ function rounds its final result. By the way, this is in contrast to the / function which simply truncates its final result.

: (*/ 11 3)
-> 4
: (/ 11 3)
-> 3

Finally, it should be noted that doing fixed-point arithmetic in picolisp with the */ operator is binary only, meaning that */ does not provide for variadic multiplication or division.

Formatting output

After your program is finished continually frobbing its fixed-point numbers, you will need it eventually to report results in the output in a “human readable” way — which is to say, in conventional terms with decimal points. Picolisp provides two functions that help you accomplish this.

The first is called format. In action:

: (scl 6)
-> 6
: (format 100123456 *Scl)
-> "100.123456"

The format function also does the inverse operation: converts string representations of numbers into integers. See the relevant reference entry for details.

For more control over the rounding in the final formatted output, see the round function.

: (round 100123456 4)
-> "100.1235"
: (round 100123456 2)
-> "100.12"

Considering only their respective output functionality, round can be viewed as a generalization of format.

: (round 100123456 *Scl)
-> "100.123456"

Check out the money function if you need accounting or financial output.

Final thoughts

The sqrt function in picolisp also supports fixed-point numbers.

: (scl 4)
-> 4
: (sqrt 64.0 1.0)
-> 80000

Having this function is convenient when we want to, say, compute the Euclidean distance in R^2.⁶

One more caveat. We can’t express fixed-point numbers with scientific notation, as we can with floating point numbers. For instance, 1e12 is not the integer 1 x 10^12 or 1,000,000,000,000.⁷ The picolisp reader doesn’t do anything special with, say, 1e12 as it does with, say, 1.12. So, the lesson is: just stick with expressing fixed-point numbers as numbers with embedded decimal points.

Fixed-point representations are more than just a language design trade-off that nods to simplicity, or even, ascetic austerity. I hope that this discussion has demonstrated enough examples to get a feel for how far one can go with these kind of very common computations for which we usually reach for floating point numbers, and when in fact they are not necessary. There is also a nice list of applications here which include games, graphics engines, and financial software, whose developers decided to forgo floating point calculations for fixed-point calculations.

A reason why these developers may have chosen to use fixed-point operations — that we did not discuss and that I wasn’t going to originally address — is that of the exactness of fixed-point arithmetic as opposed to floating point arithmetic. I have included an appendix at the end of this article that illustrates the “exactness” issue with an example provided by picolisp’s author Alexander Burger.

Happy hacking!

Appendix

Writes Alexander Burger:

Besides simplicity (and the slight inconveniences), scaled integer arithmetic has the advantage of absolute exactness for addition, subtraction and multiplication. This is a feature of integers in general, in contrast to floating point numbers.

Floats cannot represent most numbers exactly, but round them to 56 bits (in case of double precision numbers). This may cause errors to be accumulated. For example, this C program

int main(void) {
   double d = 0.1;
   int i;

   for (i = 0; i < 100000000; ++i)
      d += 0.1;
   printf("%9lf\n", d);
}

prints

10000000.081129

while a corresponding picolisp program

(scl 6)

(let D 0.1
   (do 100000000
      (inc 'D 0.1) )
   (prinl (format D *Scl)) )

(bye)