Fixed point type not multiplying correctly

Question

I'm new to Ada, and have been trying out the fixed-point "delta" types. Specifically, I've created a 32-bit delta type range 0.0 .. 1.0. However, when I try to square certain values, I get a CONSTRAINT_ERROR. As far as I know, that should't happen with my specified range. The threshold for this error appears to be sqrt(1/2). I'm using GNAT from MinGW-w64 version 4.8.0.

Test code (all of it compiles in the form of gnatmake <file> with no warnings/errors):

types.ads:

pragma Ada_2012;

with Ada.Unchecked_Conversion;
with Ada.Text_IO;

package Types is
    type Fixed_Type is delta 1.0 / 2**32 range 0.0 .. 1.0
        with Size => 32;
    type Modular_Type is mod 2**32
        with Size => 32;
    function Fixed_To_Mod is new Ada.Unchecked_Conversion(Fixed_Type, Modular_Type);
    package MIO is new Ada.Text_IO.Modular_IO(Modular_Type);
    package FIO is new Ada.Text_IO.Fixed_IO(Fixed_Type);
end Types;

specifics.adb:

pragma Ada_2012;

with Ada.Text_IO;

with Types; use Types;

procedure Specifics is
    package TIO renames Ada.Text_IO;

    procedure TestValue(val: in Fixed_Type) is
        square : Fixed_Type;
    begin
        square := val * val;
        TIO.Put_Line("Value " & Fixed_Type'Image(val) & " squares properly.");
        TIO.Put_Line("Square: " & Fixed_Type'Image(square));
        TIO.New_Line;
    exception
        when Constraint_Error =>
            TIO.Put_Line("Value " & Fixed_Type'Image(val) & " does not square properly.");
            TIO.Put_Line("Square: " & Fixed_Type'Image(val * val));
            TIO.Put_Line("Not sure how that worked.");
            TIO.New_Line;
    end TestValue;

    function ParseFixed(s: in String; last: in Natural; val: out Fixed_Type) return Boolean is
        l : Natural;
    begin
        FIO.Get(s(s'First..last), val, l);
        return TRUE;
    exception
        when others =>
            TIO.Put_Line("Parsing failed.");
            return FALSE;
    end ParseFixed;

    buffer : String(1..20);
    last : Natural;
    f : Fixed_Type;
begin
    loop
        TIO.Put(">>> ");
        TIO.Get_Line(buffer, last);
        exit when buffer(1..last) = "quit";
        if ParseFixed(buffer, last, f) then
            TestValue(f);
        end if;
    end loop;
end Specifics;

Output of specifics.adb:

>>> 0.1
Value  0.1000000001 squares properly.
Square:  0.0100000000

>>> 0.2
Value  0.2000000000 squares properly.
Square:  0.0399999998

>>> 0.4
Value  0.3999999999 squares properly.
Square:  0.1599999999

>>> 0.6
Value  0.6000000001 squares properly.
Square:  0.3600000001

>>> 0.7
Value  0.7000000000 squares properly.
Square:  0.4899999998

>>> 0.75
Value  0.7500000000 does not square properly.
Square: -0.4375000000
Not sure how that worked.

>>> quit

Somehow, multiplying val by itself yielded a negative number, which explains the CONSTRAINT_ERROR... but never mind that, why am I getting a negative number in the first place?

I then decided to test for the point at which squaring the numbers started failing, so I wrote the following snippet:

fixedpointtest.adb:

pragma Ada_2012;

with Ada.Text_IO;

with Types; use Types;

procedure FixedPointTest is
    package TIO renames Ada.Text_IO;

    test, square : Fixed_Type := 0.0;
begin
    while test /= Fixed_Type'Last loop
        square := test * test;
        test := test + Fixed_Type'Delta;
    end loop;
exception
    when Constraint_Error =>
        TIO.Put_Line("Last valid value: " & Fixed_Type'Image(test-Fixed_Type'Delta));
        TIO.Put("Hex value: ");
        MIO.Put(Item => Fixed_To_Mod(test-Fixed_Type'Delta), Base => 16);
        TIO.New_Line;
        TIO.Put("Binary value: ");
        MIO.Put(Item => Fixed_To_Mod(test-Fixed_Type'Delta), Base => 2);
        TIO.New_Line;
        TIO.New_Line;
        TIO.Put_Line("First invalid value: " & Fixed_Type'Image(test));
        TIO.Put("Hex value: ");
        MIO.Put(Item => Fixed_To_Mod(test), Base => 16);
        TIO.New_Line;
        TIO.Put("Binary value: ");
        MIO.Put(Item => Fixed_To_Mod(test), Base => 2);
        TIO.New_Line;
        TIO.New_Line;
end FixedPointTest;

and got the following output:

Last valid value:  0.7071067810
Hex value: 16#B504F333#
Binary value: 2#10110101000001001111001100110011#

First invalid value:  0.7071067812
Hex value: 16#B504F334#
Binary value: 2#10110101000001001111001100110100#

So, sqrt(1/2), we meet again. Could someone please explain to me why my code is doing this? Is there a way to make it multiply properly?

Answer 1

I think you are asking for 1 more bit of precision than is actually available "under the hood".

Your declaration

   type Fixed_Type is delta 1.0 / 2**32 range 0.0 .. 1.0
       with Size => 32;

is only accepted because GNAT has used a biased representation; there's no room for a sign bit. You can see this because 0.7071067810 is represented as 16#B504F333#, with the most significant bit set. So, when you multiply 0.71 by 0.71, the result has the most significant bit set; and the low-level code thinks that this must be the sign bit, so we have an overflow.

If you declare Fixed_Type as

   type Fixed_Type is delta 1.0 / 2**31 range 0.0 .. 1.0
       with Size => 32;

all should be well.

A further point: in your report of the behaviour of specifics with an input of 0.75, you quote the result

>>> 0.75
Value  0.7500000000 does not square properly.
Square: -0.4375000000
Not sure how that worked.

I rebuilt with gnatmake specifics.adb -g -gnato -bargs -E, and the result is now

>>> 0.75
Value  0.7500000000 does not square properly.

Execution terminated by unhandled exception
Exception name: CONSTRAINT_ERROR
Message: 64-bit arithmetic overflow
Call stack traceback locations:
0x100020b79 0x10000ea80 0x100003520 0x100003912 0x10000143e

and the traceback decodes as

system__arith_64__raise_error (in specifics) (s-arit64.adb:364)
__gnat_mulv64 (in specifics) (s-arit64.adb:318)
specifics__testvalue.2581 (in specifics) (specifics.adb:20)        <<<<<<<<<<
_ada_specifics (in specifics) (specifics.adb:45)
main (in specifics) (b~specifics.adb:246)

and specifics.adb:20 is

     TIO.Put_Line("Square: " & Fixed_Type'Image(val * val));

in the exception handler, which involves the problematic square again (not a good thing to do in an exception handler). You can see that the value 0.75 was printed without any problem in the line above: and in fixedpointtest.adb there was no problem in the additions leading to the last valid value 0.7071067810.

I was rather surprised to find that -gnato detects this error, since I'd thought it only applied to integer arithmetic; but in fact there's a discussion in the GNAT User Guide which states that it applies to fixed-point arithmetic too. It turns out that you can avoid the constraint error and get the correct arithmetic result by using -gnato3:

>>> 0.75
Value  0.7500000000 squares properly.
Square:  0.5625000000

but only at the cost of using arbitrary multiple-precision arithmetic - not a good idea for a time-constrained system!