Floating Point vs. Fixed Point Arithmetics

Floating Point vs. Fixed Point Arithmetics

·

5 min read

Welcome back to our "PicoLisp for beginner's series"!

Now that we know the basic functions, let's try to understand now how calculations are done internally in PicoLisp. This text got inspiration from this blogpost.


If you read the previous posts carefully, you might have already wondered because something seems missing: Floating point numbers!

In reverse, this means: All calculations are integer calculations. Let's try it out:

:(sqrt 2)
-> 1

:(+ 1.7 2.4)
-> 4

But what does that mean? We cannot do precise calculations? Of course we can. The idea behind is that the scale needs to be defined by the programmer first. For example, if we set a scale of 3, every number with a decimal point will be internally multiplied by 10^3. This means, we gain higher precision but the numbers obviously get longer.

In the real world, this is nothing special: For example let's assume you are a Swiss Clockmaker. It means you would be dealing with tiny tiny parts and the scale of our blueprint will certainly be in millimeter. This is just the same like multiplying all values by 10^3. Another example: The yearly water bill is calculated in m³, but we buy our milk in liters, and medicine in milliliters. We count calories, pay electricity bills in kWh and drive cars with horsepower. In order to get from one dimension to the other, we usually need to multiply by some kind of scaling factor (very often magnitudes of 10).


Addition and Subtraction

Okay, so let's set the scale to 3 (=10^3) and see what happens. (The scale is set in the global variable *Scl and can also be accessed by calling scl.)

: (scl 3)
-> 3
: (setq A 3)
-> 3
: (setq B 3.0)
-> 3000
: (+ A B)
-> 3003
: (+ B B)
-> 6000

What is happening here? First we set variable A to 3. Since there is no dot in the number, the reader interprets it as "normal" integer, i. e. "3". Then we set variable B to 3.0. The reader interprets this as 3.0*10^3, i.e. "3000". So if we add A and B, we get 3003, and the last three digits are decimal places. So we make a mental note: All numbers within a calculation should contain the decimal point.

One more note: values are automatically rounded.

: 0.33453
-> 335

So, for addition and subtraction it's fairly easy: We just keep in mind that we are calculating in another scale and that's it. No need to do more.

Multiplication and Division

However when we talk about multiplication and division, we need to be more careful because the scaling factor is inherited (think about converting cubic meters to liters or hectare to mm² - it's a little bit tricky).

If we just naively try to calculate 3.0*3.0, this is what we get:

: (* 3.0 3.0)
-> 9000000

9 Million! This is wrong for sure. This is because the scaling factor has also been multiplied, so actually what we have done is this: (3*3)*(10^3*10^3) = 9*10^6.

For this purpose, PicoLisp has a multiply-divide function called */ built in. It multiplies all numbers except for the last one, and then divides the result by the last one. In our example:

:(*/ 3.0 3.0 1.0)
-> 9000

And the quotient of A and B can be computed as (*/ 1.0 A B).

: (*/ 1.0 2.0 5.0) 
-> 400

Looks better, right? (...If you cannot honestly answer with "YES", go back to the beginning and think through it again! It's not what we're used to, and it takes some time to overcome that.)


In order to fix our square root example from above, we now understand what to do. Square root calculations can be interpreted are some kind of division, and for this purpose the sqrt function takes another parameter to divide the result:

: (scl 3)
-> 3
: (sqrt 2.0 1.0)
-> 1414

Formatting

Sometimes we might still want to read the number without scaling factor, for example to double-check the value, or for some printing output. For this, PicoLisp has two built-in functions: format or round. format returns the value as a string or vice versa (with some formatting options, see docs), round rounds it to the number of digits specified according to the given scale.

: (scl 3)
-> 3
: (format (*/ 2.5 3.5 1.0) *Scl)  
-> "8.750"
: (round (*/ 2.5 3.5 1.0))
-> "8.750"
: (round (*/ 2.5 3.5 1.0) 1)
-> "8.8"


Congratulations, now you have mastered the key points of fixed point arithmetics!


...still, you might ask yourself:

...OKAY, BUT WHY THE TROUBLE?!

Basically, there are two main reasons:

  • Reason #1. Simplicity is Beauty
  • Reason #2. Scaled integer arithmetics are exact, floating point numbers are not.

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)

prints

10000000.100000

which is correct.


Fun fact for linguists

Fixed point arithmetics are not a Lisp feature. In fact, the */ function as well as some other minimalistic PicoLisp concepts are heavily inspired by the programming language Forth that is still maintained today and used for hardware applications that require flexibility, speed and compact source code.


Sources

Cover: pixabay.com/de/users/mylene2401-10328767
the-m6.net/blog/fixed-point-arithmetic-in-p..
software-lab.de/doc/index.html
en.wikipedia.org/wiki/Forth_(programming_la..