Why no 'Floor for fixed point types

Why no 'Floor for fixed point types

[Duncan Sands]

I think the subject says it all.  Just curious.

Duncan.

Re: Why no 'Floor for fixed point types

[Robert I. Eachus]

Duncan Sands wrote:
> I think the subject says it all.  Just curious.

For floating-point types, integer values are either model numbers or in 
a range limited by two integer model numbers.  (Or are IEEE infinities 
or NANs.)

But for fixed-point types, there may be few integer values that can be 
represented.  A typical example might be:

type Radians is delta Pi/1000 range -Pi..Pi;
for Radians'small use Pi/1000;

where the only integer value of the type is zero.

For type Radians what should Radians'Floor return? It doesn't make much 
sense for it to return a value that is approximately an integer, 
especially since Radians'Floor(Radians'Floor(X)) = Randians'Floor(X) 
could return false.  It might be nice to have a type conversion to 
Integer that truncated instead of rounding, but that is a different 
question.
-- 
                                            Robert I. Eachus

"Quality is the Buddha. Quality is scientific reality. Quality is the 
goal of Art. It remains to work these concepts into a practical, 
down-to-earth context, and for this there is nothing more practical or 
down-to-earth than what I have been talking about all along...the repair 
of an old motorcycle."  -- from Zen and the Art of Motorcycle 
Maintenance by Robert Pirsig

Re: Why no 'Floor for fixed point types

[Martin Dowie]

"Duncan Sands" <baldrick@free.fr> wrote in message
news:mailman.194.1066939697.25614.comp.lang.ada@ada-france.org...
> I think the subject says it all.  Just curious.

It only makes sense to convert to a float then to an integer - what
if there is no fixed point value that has the same magnitude as an
integer value? It is annoying though, when in 'real life' you don't
really care about the middle conversion, e.g.

My_Int := My_Int_Type (My_Float_Type'Floor (My_Fixed_Type'(1.5)));

My_Int should be 1.

I've just been throew this one myself and if you think long
and hard you will see the logic :-)

Re: Why no 'Floor for fixed point types

[Stephen Leake]

"Robert I. Eachus" <rieachus@comcast.net> writes:

> type Radians is delta Pi/1000 range -Pi..Pi;
> for Radians'small use Pi/1000;
> 
> where the only integer value of the type is zero.
> 
> For type Radians what should Radians'Floor return? 

An Integer, that is the truncated value.

Hmm, I guess it needs to be generic, so you can specify which integer
type to use for the result. 

-- 
-- Stephe

Re: Why no 'Floor for fixed point types

[Duncan Sands]

On Friday 24 October 2003 18:00, Stephen Leake wrote:
> "Robert I. Eachus" <rieachus@comcast.net> writes:
> > type Radians is delta Pi/1000 range -Pi..Pi;
> > for Radians'small use Pi/1000;
> >
> > where the only integer value of the type is zero.
> >
> > For type Radians what should Radians'Floor return?
>
> An Integer, that is the truncated value.
>
> Hmm, I guess it needs to be generic, so you can specify which integer
> type to use for the result.

Though given the amazing rules for multiplication of different fixed point
types (result type determined by the context), I doubt that would stop
a determined language designer...

Thanks for your comments,

Duncan.

Re: Why no 'Floor for fixed point types

[Nick Roberts]

Duncan Sands wrote:

> I think the subject says it all.  Just curious.
> 
> Duncan.

For a fixed point type Tf -- assuming it has a delta which is less than 1 
-- you can write:

    Scale: constant := 1/Tf'Small;

    type Ti is range Tf'First*Scale .. Tf'Last*Scale;

    function Scaled_Floor (X: in Tf) return Ti is
    begin
       return Ti(X*Scale) - Ti(X*Scale) mod Ti(Scale);
    end;

The basic idea is that with fixed point types, a 'floor' function will 
inevitably need to be scaled, and the integer type it returns needs to be 
customised to the fixed point type (its range and delta) and the chosen 
scale. I've shown a scale of 1/Tf'Small, but the chances are that the scale 
you will require in a certain situation will be different (it might be unity).

A little more information about your specific problem would enable us to 
give a more detailed diagnosis.

-- 
Nick Roberts

Re: Why no 'Floor for fixed point types

[Robert I. Eachus]

Nick Roberts wrote:

> For a fixed point type Tf -- assuming it has a delta which is less than 
> 1 -- you can write:
> 
>    Scale: constant := 1/Tf'Small;
> 
>    type Ti is range Tf'First*Scale .. Tf'Last*Scale;
> 
>    function Scaled_Floor (X: in Tf) return Ti is
>    begin
>       return Ti(X*Scale) - Ti(X*Scale) mod Ti(Scale);
>    end;
> 
> The basic idea is that with fixed point types, a 'floor' function will 
> inevitably need to be scaled, and the integer type it returns needs to 
> be customised to the fixed point type (its range and delta) and the 
> chosen scale. I've shown a scale of 1/Tf'Small, but the chances are that 
> the scale you will require in a certain situation will be different (it 
> might be unity).

Ignore this.  To quote RM 3.5.9(8): "The set of values of a fixed point 
type comprise the integral multiples of a number called the small of the 
type."  So the effect of all the code above can be better accomplished by:

   function Mantissa(X: in Tf) return Ti is
   begin return Ti(X/Tf'Small); end Mantissa;

-- Technically you could use the constant named Scale above, but there
-- are some potential rounding issues.  Writing it this way allows the
-- compiler to convert the division to a multiplication that gives the
-- same result, if it can.

-- Of course, any decent compiler should be able to recognize this
-- special case and do nothing.  If your compiler doesn't recognize this
-- you could rewrite Mantissa as an instance of Unchecked_Conversion.



-- 
                                                     Robert I. Eachus

"Quality is the Buddha. Quality is scientific reality. Quality is the 
goal of Art. It remains to work these concepts into a practical, 
down-to-earth context, and for this there is nothing more practical or 
down-to-earth than what I have been talking about all along...the repair 
of an old motorcycle."  -- from Zen and the Art of Motorcycle 
Maintenance by Robert Pirsig

Re: Why no 'Floor for fixed point types

[Nick Roberts]

Robert I. Eachus wrote:

> ...
> Ignore this.  To quote RM 3.5.9(8): "The set of values of a fixed point 
> type comprise the integral multiples of a number called the small of the 
> type."  So the effect of all the code above can be better accomplished by:
> 
>   function Mantissa(X: in Tf) return Ti is
>   begin return Ti(X/Tf'Small); end Mantissa;

No, Robert. Wrong! This function fails to do the 'floor' part of the 
calculation. The name 'Mantissa' is misleading, since the result will not 
be the mantissa (the decimal digits to the left of the decimal point) 
unless Tf'Small happens to be 1.0 (and I did explicitly exclude this case).

> -- Technically you could use the constant named Scale above, but there
> -- are some potential rounding issues.  Writing it this way allows the
> -- compiler to convert the division to a multiplication that gives the
> -- same result, if it can.

For a conforming compiler, there should be no rounding issues in the case 
Scale=1/Tf'Small, the division is a static expression (which should be 
calculated precisely at compile time), and I would expect the 
multiplications to be eliminated. For other scales, of course there will be 
rounding issues, which must be dealt with; this was rather the point I was 
trying to emphasise.

> -- Of course, any decent compiler should be able to recognize this
> -- special case and do nothing.  If your compiler doesn't recognize this
> -- you could rewrite Mantissa as an instance of Unchecked_Conversion.

Yuk! I would suggest you either put up with the redundant operation or get 
a new compiler.

Maybe an example would help.

Suppose we have a temperature in variable Temp, of type Temperature (in 
degrees celsius):

    type Temperature is delta 0.2 range -15.0 .. 90.0;

    Temp: Temperature := Read_Sensor(...);

Now suppose we have a subsystem that can display two decimal digits 
(perhaps on a 7-segment LED display), and we can use the following 
procedure to do it:

    type Two_Decimal_Digits is range 00..99;

    procedure Display (Digits: in Two_Decimal_Digits);

What we need to be able to do is to convert the fixed point type 
Temperature into the integer type Two_Decimal_Digits. It might be in the 
specification that the figure displayed should be the mantissa of the value 
in Temp; this implies a 'floor' function (rounding down to the nearest 
whole degree celsius).

Having declared:

    Scale: constant := 1/Temperature'Small;

    type Scaled_Temperature is
       range Temperature'First*Scale .. Temperature'Last*Scale;

    function Scaled_Floor (X: in Temperature) return Scaled_Temperature is
       subtype ST is Scaled_Temperature;
    begin
       return ST(X*Scale) - ST(X*Scale) mod ST(Scale);
    end;

    function Mantissa (T: in Temperature) return Two_Decimal_Digits is
    begin
       return Two_Decimal_Digits(Scaled_Floor(T)/Scaled_Temperature(Scale));
    end;

we can now conveniently write:

    Display( Mantissa(Temp) );

In general, the sequence of events in the calculation will be: scale the 
value; convert it to an integer; calculate the scaled floor (using integer 
arithmetic); rescale the result as required. In my example, the 
Scaled_Floor function scales the value, and the Mantissa function unscales 
it again. I hope this clarifies things a bit.

-- 
Nick Roberts

Re: Why no 'Floor for fixed point types

[Robert I. Eachus]

Nick Roberts wrote:
>I said:
>> Ignore this.  To quote RM 3.5.9(8): "The set of values of a fixed 
>> point type comprise the integral multiples of a number called the 
>> small of the type."  So the effect of all the code above can be better 
>> accomplished by:
>>
>>   function Mantissa(X: in Tf) return Ti is
>>   begin return Ti(X/Tf'Small); end Mantissa;
> 
> 
> No, Robert. Wrong! This function fails to do the 'floor' part of the 
> calculation. The name 'Mantissa' is misleading, since the result will 
> not be the mantissa (the decimal digits to the left of the decimal 
> point) unless Tf'Small happens to be 1.0 (and I did explicitly exclude 
> this case).

First, the mantissa is not "the decimal digits to the left of the 
decimal point."  For a number written in scaled notation: 1.2345E6 it is 
the part of the number before the exponent.  Since in your program you 
are attempting to remove the scaling from a fixed-point type, the name 
Mantissa seemed appropriate.  Change it if you wish.

But you didn't pay attention above.  The compiler allows you to think 
about fixed-point types as if they are real (non-integer) values.  But 
they are not implemented that way.  Any compiler that uses 
floating-point arithmetic to do fixed-point computations has a lot of 
bugs in it.   They just havent been found yet.  (And I think it was ACVC 
1.4 that added a lot of tests which found such bugs.)

Fixed point values are represented as integers.  Their "actual" value is 
the integer times a scale factor 'Small.  If you divide a fixed point 
number by its 'Small, you get an integer.  Doing the arithmetic right 
can be tricky in theory, but most compilers are smart enough to 
recognize that all they need to do is nothing.  That was why I advised 
you to write it that way--compilers are sensitive to that special case:

>> -- Of course, any decent compiler should be able to recognize this
>> -- special case and do nothing.  If your compiler doesn't recognize this
>> -- you could rewrite Mantissa as an instance of Unchecked_Conversion.

> Yuk! I would suggest you either put up with the redundant operation or 
> get a new compiler.

I assume that the Yuk! was about the reference to Unchecked_Conversion. 
  But I think you didn't understand why it was there.  I was not 
encouraging anyone to write that way, but to use 'Small in an idiom the 
compiler should recognize.  I only mentioned the Unchecked_Conversion 
possibility to help people recognize what is going on in this function: 
  NOTHING.  It is a notation to tell the compiler to switch from 
treating the value as having fixed-point type, and to instead look at 
the value as an integer.

> Maybe an example would help.

Okay.

> Suppose we have a temperature in variable Temp, of type Temperature (in 
> degrees celsius):
> 
>    type Temperature is delta 0.2 range -15.0 .. 90.0;
> 
>    Temp: Temperature := Read_Sensor(...);
> 
> Now suppose we have a subsystem that can display two decimal digits 
> (perhaps on a 7-segment LED display), and we can use the following 
> procedure to do it:
> 
>    type Two_Decimal_Digits is range 00..99;
> 
>    procedure Display (Digits: in Two_Decimal_Digits);
> 
> What we need to be able to do is to convert the fixed point type 
> Temperature into the integer type Two_Decimal_Digits. It might be in the 
> specification that the figure displayed should be the mantissa of the 
> value in Temp; this implies a 'floor' function (rounding down to the 
> nearest whole degree celsius).
> 
> Having declared:
> 
>    Scale: constant := 1/Temperature'Small;
> 
>    
>       range Temperature'First*Scale .. Temperature'Last*Scale;

At this point the compiler will give you an error message.  Let's say we 
  fix it:

        type Scaled_Temperature is
                  range Integer(Temperature'First/Temperature'Small)
                       ..Integer(Temperature'Last/Temperature'Small);

>    function Scaled_Floor (X: in Temperature) return Scaled_Temperature is
>       subtype ST is Scaled_Temperature;
>    begin
>       return ST(X*Scale) - ST(X*Scale) mod ST(Scale);
>    end;

...Now I understand the problem you think you are solving with this 
code.  With the fix above so it compiles, for lots of values of 
Temperature'Small you will end up dividing by zero.  With other values 
of Temperature'Small you will have overflows.  So the range where your 
method works is fairly small.  For this particular problem though,

     Integer(Float'Floor(Float(X)));

Should do what you want.  (Or what you should want, or something like that.)

-- 
                                                     Robert I. Eachus

"Quality is the Buddha. Quality is scientific reality. Quality is the 
goal of Art. It remains to work these concepts into a practical, 
down-to-earth context, and for this there is nothing more practical or 
down-to-earth than what I have been talking about all along...the repair 
of an old motorcycle."  -- from Zen and the Art of Motorcycle 
Maintenance by Robert Pirsig

Re: Why no 'Floor for fixed point types

[Randy Brukardt]

"Nick Roberts" <nick.roberts@acm.org> wrote in message
news:bnen7p$vjo06$1@ID-25716.news.uni-berlin.de...
> For a conforming compiler, there should be no rounding issues in the case
> Scale=1/Tf'Small, the division is a static expression (which should be
> calculated precisely at compile time), and I would expect the
> multiplications to be eliminated.

Not true if Tf is a generic formal type (and this is a common way to
implement such code). Moreover, if you use a code-sharing compiler such as
Janus/Ada, it won't be calculated at compile-time, either.

                   Randy.

Re: Why no 'Floor for fixed point types

[Randy Brukardt]

"Robert I. Eachus" <rieachus@comcast.net> wrote in message
news:3F9AFB67.5080401@comcast.net...
> But you didn't pay attention above.  The compiler allows you to think
> about fixed-point types as if they are real (non-integer) values.  But
> they are not implemented that way.  Any compiler that uses
> floating-point arithmetic to do fixed-point computations has a lot of
> bugs in it.   They just havent been found yet.  (And I think it was ACVC
> 1.4 that added a lot of tests which found such bugs.)

As usual with blanket statements, this is wrong. Janus/Ada in fact does use
floating-point arithmetic to implement fixed point in some cases (especially
the mixed multiply). We did the error analysis on these operations, and they
are fine - they'll get the right answer in all cases that Ada 95 requires
that. (There are some cases where no technique will get the "right" answer
as defined in Ada 83, and those of course we might get wrong for some bit
patterns. Many Ada 83 compilers simply avoided the issue by restricting
'Small to powers of two, which of course is trivial to get right. And rather
restrictive.) Since, in a generic, you don't know the 'Smalls involved, and
you don't know the magatude of the values, there isn't much else to do
except use the highest precision math that you have available. As with
everything, it depends on how you use it.

                        Randy.

                   Randy.

Re: Why no 'Floor for fixed point types

[Robert I. Eachus]

Randy Brukardt wrote:
> "Robert I. Eachus" <rieachus@comcast.net> wrote in message
> news:3F9AFB67.5080401@comcast.net...
> 
>>But you didn't pay attention above.  The compiler allows you to think
>>about fixed-point types as if they are real (non-integer) values.  But
>>they are not implemented that way.  Any compiler that uses
>>floating-point arithmetic to do fixed-point computations has a lot of
>>bugs in it.   They just havent been found yet.  (And I think it was ACVC
>>1.4 that added a lot of tests which found such bugs.) 
> 
> As usual with blanket statements, this is wrong. Janus/Ada in fact does use
> floating-point arithmetic to implement fixed point in some cases (especially
> the mixed multiply). We did the error analysis on these operations, and they
> are fine - they'll get the right answer in all cases that Ada 95 requires
> that. (There are some cases where no technique will get the "right" answer
> as defined in Ada 83, and those of course we might get wrong for some bit
> patterns. Many Ada 83 compilers simply avoided the issue by restricting
> 'Small to powers of two, which of course is trivial to get right. And rather
> restrictive.) Since, in a generic, you don't know the 'Smalls involved, and
> you don't know the magatude of the values, there isn't much else to do
> except use the highest precision math that you have available. As with
> everything, it depends on how you use it.

Actually, I think you are agreeing with me.  Trying to test even a small 
subset of all possible reasonable values of 'Small and fixed-point 
numbers just isn't reasonably possible without trillions of machines 
crunching for millions of years.   So your compiler probably has 
millions of errors in the low order bit that are just not practical to 
find, and of no real interest to anyone anyway.  From experience with 
fixed-point, the tough cases are of the form A := Fixed(B*C); where B 
and C are of two other types than Fixed, and there is no easy 
representation of Fixed'Small/(B_type'Small * C_type'Small).

In practice those cases are of little or no interest to anyone.  If your 
compiler correctly implements A := A * I; where I is an Integer, or A := 
B + C; where all three are of the same fixed-point type, then I and most 
other fixed-point users won't care about those painful cases.  Other 
than, of course, to note that they exist so that we can avoid them.

If you do use the three type multiplication operator, you should check 
whether it is an easy or hard case, and avoid the hard cases.  (Any 
conversion where the target type is the same as one of the multiplicand 
types counts as easy, since it can be done with a single division.)

I'm not trying to scare anyone here.  In fact one of the differences 
between Ada 83 and Ada 95 is that the error bounds on the hard cases 
were changed to make them easier to implement.  The hard cases do come 
up, and for example, one of the harder parts of the Euro conversion was 
to specify rules and error bounds for some of these three type 
conversions.  (Say from Marks to Kronar, using today's market rates for 
Marks to Euros and Euros to Kronar.)

-- 
                                           Robert I. Eachus

"Quality is the Buddha. Quality is scientific reality. Quality is the 
goal of Art. It remains to work these concepts into a practical, 
down-to-earth context, and for this there is nothing more practical or 
down-to-earth than what I have been talking about all along...the repair 
of an old motorcycle."  -- from Zen and the Art of Motorcycle 
Maintenance by Robert Pirsig

Re: Why no 'Floor for fixed point types

[Nick Roberts]

Robert I. Eachus wrote:

>> No, Robert. Wrong! This function fails to do the 'floor' part of the 
>> calculation. The name 'Mantissa' is misleading, since the result will 
>> not be the mantissa (the decimal digits to the left of the decimal 
>> point) unless Tf'Small happens to be 1.0 (and I did explicitly exclude 
>> this case).
> 
> First, the mantissa is not "the decimal digits to the left of the 
> decimal point."  For a number written in scaled notation: 1.2345E6 it is 
> the part of the number before the exponent.  Since in your program you 
> are attempting to remove the scaling from a fixed-point type, the name 
> Mantissa seemed appropriate.  Change it if you wish.

I'm sorry, you're right about the mantissa. In fact, in your example, I 
think the mantissa would strictly be 0.12345, and the exponent 7, but I 
wouldn't mind being set straight on this point.

> But you didn't pay attention above.  The compiler allows you to think 
> about fixed-point types as if they are real (non-integer) values.  But 
> they are not implemented that way.  Any compiler that uses 
> floating-point arithmetic to do fixed-point computations has a lot of 
> bugs in it.   They just havent been found yet.  (And I think it was ACVC 
> 1.4 that added a lot of tests which found such bugs.) Fixed point values
 > are represented as integers.

I understand that fixed point types are intended to be represented as 
integers, and that most Ada implementations do so. I also thought the idea 
was that the Ada 95 standard was framed to permit other representations. I 
have heard that on some machines it makes sense to use the native 
floating-point representation (because the machine has sufficient support 
for operations on this representation).

When you say 'bugs', I guess you mean 'inaccuracies'. I would honestly 
appreciate you saying a bit more on this subject (it is quite important to 
me, as a compiler writer!).

I'm also not really sure as to the point you really making, Robert, so -- 
at the risk of trying your patience -- I'd appreciate any clarification you 
can make.

> Their "actual" value is 
> the integer times a scale factor 'Small.  If you divide a fixed point 
> number by its 'Small, you get an integer.  Doing the arithmetic right 
> can be tricky in theory, but most compilers are smart enough to 
> recognize that all they need to do is nothing.  That was why I advised 
> you to write it that way--compilers are sensitive to that special case:

Well, from the point of view of the compiler I am writing, I would be 
grateful for more information on the tricky bits.

>>> -- Of course, any decent compiler should be able to recognize this
>>> -- special case and do nothing.  If your compiler doesn't recognize this
>>> -- you could rewrite Mantissa as an instance of Unchecked_Conversion.
> 
>> Yuk! I would suggest you either put up with the redundant operation or 
>> get a new compiler.
> 
> I assume that the Yuk! was about the reference to Unchecked_Conversion. 

Yes it was. Surely it is possible that there will be differences between 
the underlying integer an implementation uses for a fixed point type, and 
an apparently equivalent integer type. For example, the implementation may 
offset the value in the former. What works for one implementation is likely 
to be non-portable, and could suddenly fail in many other circumstances too.

>  But I think you didn't understand why it was there.  I was not 
> encouraging anyone to write that way, but to use 'Small in an idiom the 
> compiler should recognize.  I only mentioned the Unchecked_Conversion 
> possibility to help people recognize what is going on in this function: 
>  NOTHING.  It is a notation to tell the compiler to switch from treating 
> the value as having fixed-point type, and to instead look at the value 
> as an integer.

Okay, I understand that, and that is part of what I was trying to achieve 
with the Scaled_Floor I suggested.

The other part of what I was trying to achieve with this function was the 
'floor' part, where the value is rounded down to the nearest 1/Tf'Small. I 
was suggesting this second part should be done using integer arithmetic 
(after conversion). Are you saying that this part should be done using 
fixed-point arithmetic? (I think you might be right.)

>> Having declared:
>>
>>    Scale: constant := 1/Temperature'Small;
>>
>>       type Scaled_Temperature is
>>          range Temperature'First*Scale .. Temperature'Last*Scale;
> 
> 
> At this point the compiler will give you an error message.  Let's say we 
>  fix it:
> 
>        type Scaled_Temperature is
>                  range Integer(Temperature'First/Temperature'Small)
>                       ..Integer(Temperature'Last/Temperature'Small);

Oops! Well spotted. Possibly this mistake suggests that Scaled_Temperature 
should be a fixed point type, rather than an integer type (with delta 1.0). 
Do you agree?

>>    function Scaled_Floor (X: in Temperature) return Scaled_Temperature is
>>       subtype ST is Scaled_Temperature;
>>    begin
>>       return ST(X*Scale) - ST(X*Scale) mod ST(Scale);
>>    end;
> 
> ...Now I understand the problem you think you are solving with this 
> code.  With the fix above so it compiles, for lots of values of 
> Temperature'Small you will end up dividing by zero.

Is that so? Could you please illustrate. Remember, I did specifically say 
that Tf'Delta is less than 1.

> With other values 
> of Temperature'Small you will have overflows.  So the range where your 
> method works is fairly small.

Again, I'd appreciate more information about this.

 > For this particular problem though,
> 
>     Integer(Float'Floor(Float(X)));
> 
> Should do what you want.

But this begs the original question of this thread, doesn't it? Why doesn't 
Ada 95 provide the Floor attribute for fixed point types? I admit I never 
really answered this question, and it's a fair one, isn't it?

Also, is the above formulation (which I think we can assume really would 
convert the value to a floating-point representation, and then use some 
kind of iterative approximation scheme to compute the floor value, and then 
convert to Integer) reasonably efficient?

> (Or what you should want, or something like that.)

Hehe. Of course, the trick is always to know what you need, rather than 
what you want.

-- 
Nick Roberts

Re: Why no 'Floor for fixed point types

[Nick Roberts]

Robert I. Eachus wrote:

> ...  Trying to test even a small 
> subset of all possible reasonable values of 'Small and fixed-point 
> numbers just isn't reasonably possible without trillions of machines 
> crunching for millions of years.   So your compiler probably has 
> millions of errors in the low order bit that are just not practical to 
> find, and of no real interest to anyone anyway.

So possibly a question we should ask is "If nobody cares, does it count as 
an error (or bug)?" I admit, there might be a few Intel customers who'd 
like to know the answer to that one. :-)

> From experience with 
> fixed-point, the tough cases are of the form A := Fixed(B*C); where B 
> and C are of two other types than Fixed, and there is no easy 
> representation of Fixed'Small/(B_type'Small * C_type'Small).

What do you mean when you say these are tough cases? The RM95 essentially 
says that the result is either of the representable values (of the type 
Fixed here) which bound the precise result.

> In practice those cases are of little or no interest to anyone.  If your 
> compiler correctly implements A := A * I; where I is an Integer, or A := 
> B + C; where all three are of the same fixed-point type, then I and most 
> other fixed-point users won't care about those painful cases.  Other 
> than, of course, to note that they exist so that we can avoid them.

But why are the cases you refer to painful? Do they really need to be avoided?

I can certainly see that if a calculation causes a missile to hit someone's 
house (instead of the next door embassy), it might be quite painful for the 
occupants of the house. Are you saying that these cases are capable of 
being sources of nasty accidents, or are you saying that they are merely an 
academic curiosity, of no possible practical consequence? (And I realise 
this may be a slightly unfair question.)

> If you do use the three type multiplication operator, you should check 
> whether it is an easy or hard case, and avoid the hard cases.  (Any 
> conversion where the target type is the same as one of the multiplicand 
> types counts as easy, since it can be done with a single division.)

Would you please provide an example, to illustrate this point.

> I'm not trying to scare anyone here.  In fact one of the differences 
> between Ada 83 and Ada 95 is that the error bounds on the hard cases 
> were changed to make them easier to implement.  The hard cases do come 
> up, and for example, one of the harder parts of the Euro conversion was 
> to specify rules and error bounds for some of these three type 
> conversions.  (Say from Marks to Kronar, using today's market rates for 
> Marks to Euros and Euros to Kronar.)

I seem to dimly recall you mentioning this before, Robert. Was it in 
comp.lang.ada? I would like to review it on Google, if possible.

-- 
Nick Roberts

Re: Why no 'Floor for fixed point types

[Nick Roberts]

Randy Brukardt wrote:

> "Nick Roberts" <nick.roberts@acm.org> wrote in message
> news:bnen7p$vjo06$1@ID-25716.news.uni-berlin.de...
> 
>>For a conforming compiler, there should be no rounding issues in the case
>>Scale=1/Tf'Small, the division is a static expression (which should be
>>calculated precisely at compile time), and I would expect the
>>multiplications to be eliminated.
> 
> 
> Not true if Tf is a generic formal type (and this is a common way to
> implement such code). Moreover, if you use a code-sharing compiler such as
> Janus/Ada, it won't be calculated at compile-time, either.

Hmmmm, nasty. Is this (the non-staticness of things in generics) something 
that is likely to be addressed in the next revision, Randy? Do you think 
fixed point types should have a Floor attribute?

-- 
Nick Roberts

Re: Why no 'Floor for fixed point types

[Stephane Richard]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 3265 bytes --]

In the worlds of our common savior <- .oO( Yeah Right!!! ) Bill
Gates...hehehe....if nobody cares, it's a bug...if everyone cares, it's a
feature..;-)

-- 
St�phane Richard
"Ada World" Webmaster
http://www.adaworld.com


"Nick Roberts" <nick.roberts@acm.org> wrote in message
news:bnmc74$137bsk$1@ID-25716.news.uni-berlin.de...
> Robert I. Eachus wrote:
>
> > ...  Trying to test even a small
> > subset of all possible reasonable values of 'Small and fixed-point
> > numbers just isn't reasonably possible without trillions of machines
> > crunching for millions of years.   So your compiler probably has
> > millions of errors in the low order bit that are just not practical to
> > find, and of no real interest to anyone anyway.
>
> So possibly a question we should ask is "If nobody cares, does it count as
> an error (or bug)?" I admit, there might be a few Intel customers who'd
> like to know the answer to that one. :-)
>
> > From experience with
> > fixed-point, the tough cases are of the form A := Fixed(B*C); where B
> > and C are of two other types than Fixed, and there is no easy
> > representation of Fixed'Small/(B_type'Small * C_type'Small).
>
> What do you mean when you say these are tough cases? The RM95 essentially
> says that the result is either of the representable values (of the type
> Fixed here) which bound the precise result.
>
> > In practice those cases are of little or no interest to anyone.  If your
> > compiler correctly implements A := A * I; where I is an Integer, or A :=
> > B + C; where all three are of the same fixed-point type, then I and most
> > other fixed-point users won't care about those painful cases.  Other
> > than, of course, to note that they exist so that we can avoid them.
>
> But why are the cases you refer to painful? Do they really need to be
avoided?
>
> I can certainly see that if a calculation causes a missile to hit
someone's
> house (instead of the next door embassy), it might be quite painful for
the
> occupants of the house. Are you saying that these cases are capable of
> being sources of nasty accidents, or are you saying that they are merely
an
> academic curiosity, of no possible practical consequence? (And I realise
> this may be a slightly unfair question.)
>
> > If you do use the three type multiplication operator, you should check
> > whether it is an easy or hard case, and avoid the hard cases.  (Any
> > conversion where the target type is the same as one of the multiplicand
> > types counts as easy, since it can be done with a single division.)
>
> Would you please provide an example, to illustrate this point.
>
> > I'm not trying to scare anyone here.  In fact one of the differences
> > between Ada 83 and Ada 95 is that the error bounds on the hard cases
> > were changed to make them easier to implement.  The hard cases do come
> > up, and for example, one of the harder parts of the Euro conversion was
> > to specify rules and error bounds for some of these three type
> > conversions.  (Say from Marks to Kronar, using today's market rates for
> > Marks to Euros and Euros to Kronar.)
>
> I seem to dimly recall you mentioning this before, Robert. Was it in
> comp.lang.ada? I would like to review it on Google, if possible.
>
> -- 
> Nick Roberts
>

Re: Why no 'Floor for fixed point types

[Randy Brukardt]

"Nick Roberts" <nick.roberts@acm.org> wrote in message
news:bnmc74$137bsk$1@ID-25716.news.uni-berlin.de...
> Robert I. Eachus wrote:
>
> > ...  Trying to test even a small
> > subset of all possible reasonable values of 'Small and fixed-point
> > numbers just isn't reasonably possible without trillions of machines
> > crunching for millions of years.   So your compiler probably has
> > millions of errors in the low order bit that are just not practical to
> > find, and of no real interest to anyone anyway.
>
> So possibly a question we should ask is "If nobody cares, does it count as
> an error (or bug)?" I admit, there might be a few Intel customers who'd
> like to know the answer to that one. :-)

This is wrong (which was my original point). Ada requires such results to be
members of the "close result set", which is implementation-defined. Thus,
the only way for there to be actual "errors" or "bugs" in these result is if
we've defined that set incorrectly (implementation-defined stuff is supposed
to be documented). Of course, if it is proved that we've done that wrong,
it's highly unlikely that we'd change the compiler; just the documentation.
So in practice it means that such results have whatever accuracy the
compiler writer can easily support.

> > From experience with
> > fixed-point, the tough cases are of the form A := Fixed(B*C); where B
> > and C are of two other types than Fixed, and there is no easy
> > representation of Fixed'Small/(B_type'Small * C_type'Small).
>
> What do you mean when you say these are tough cases? The RM95 essentially
> says that the result is either of the representable values (of the type
> Fixed here) which bound the precise result.

Read G.2.3 to see what the RM says about the accuracy of fixed point. In
particular, read about the 'perfect result set' and the 'close result set'.
If you care about accuracy, you need to avoid operations which only require
a result in the 'close result set', because those are cases that the
compiler is allowed to be inaccurate.

                    Randy.

Re: Why no 'Floor for fixed point types

[Randy Brukardt]

"Nick Roberts" <nick.roberts@acm.org> wrote in message
news:bnmcoj$12vsv7$1@ID-25716.news.uni-berlin.de...
> > Not true if Tf is a generic formal type (and this is a common way to
> > implement such code). Moreover, if you use a code-sharing compiler such
as
> > Janus/Ada, it won't be calculated at compile-time, either.
>
> Hmmmm, nasty. Is this (the non-staticness of things in generics) something
> that is likely to be addressed in the next revision, Randy?

I hope not, or I'll be out of the compiler business. (Redoing all of the
generic support in Janus/Ada is out of the question.)

> Do you think fixed point types should have a Floor attribute?

The original answer to this showed that for some fixed point types, it
wouldn't be possible to implement it accurately. Thus, it is much better to
show what you are doing via a conversion to an appropriate float type.
Hopefully the compiler can note the easy cases and eliminate the float
operations.

                    Randy.

Re: Why no 'Floor for fixed point types

[Robert I. Eachus]

Randy Brukardt wrote:

 > Read G.2.3 to see what the RM says about the accuracy of fixed point.
 > In particular, read about the 'perfect result set' and the 'close
 > result set'. If you care about accuracy, you need to avoid operations
 > which only require a result in the 'close result set', because those
 > are cases that the compiler is allowed to be inaccurate.

Actually, there are cases that are allowed to use the close result set
that no compiler goes out of their way to get inaccurate results on. 
But whether you limit yourself to the perfect result set, or are willing 
to accept some well-behaved cases in the close result set.  My real 
point is that there are some pathological cases which no one cares 
about, and I doubt that any compiler does a perfect job of documenting.

But that is fine with me.  As I said, if you care, you check and for the 
compiler vendors to try and understand what code the compiler will 
generate in 2**93 cases (assuming only three 31-bit 'Smalls) is not 
something that I would want any compiler vendor to waste time on.

In any case, the wierd/pathological whatever term you want to use cases 
are just not that usual.  In the usual cases 1.0/fixed_type'Small is an 
integer for all three operands and A'Small/(B'Small * C'Small) is an 
integer as well.

Of course, I am one of those nasty people who goes around doing things 
like measuring angles in microradians--and declaring a fixed point type 
with a 'Small to match.  Technically, as declared 'Small is a rational 
number (2*Pi/1_000_000.0) since Ada.Numerics.Pi is only declared to 50 
decimal places...

But since 'Small is static, it is usally easy to see if the compiler did 
a good job of eliminating common factors to simplify the job. 
Incidently back in Ada 83 days Paul Hilfinger and I went round and 
around on when 2*actual precision or 3*actual precision was needed.  I 
have implementation notes somewhere and Paul actually published a couple 
of papers.  These are the calculations that the Ada 95 rules allow to be 
done using the close result set, and I think you can see that there are 
a few (as I said very pathological) cases where getting even close is 
difficult.

I even have a program lying around with painful test cases.  I never 
distributed it, because I was afraid it would end up in the ACVC/ACATS 
test.  Remember the reason I was interested in these cases were entirely 
from a computational perspective.  And if I don't care if compilers do 
them well, I don't see why anyone else should.  (In one case I used two 
different power series expansions for Pi that agree to several thousand 
decimal places.  And yes, they are written as universal integer 
expressions, so the compiler has to expand them exactly at compile time. 
    I always thought it was funny when new computers would be used to 
compute a million digits of Pi or so.  In Ada those programs are so fast 
they start printing the answer immediately. ;-)

-- 
                                         Robert I. Eachus

"Quality is the Buddha. Quality is scientific reality. Quality is the
goal of Art. It remains to work these concepts into a practical,
down-to-earth context, and for this there is nothing more practical or
down-to-earth than what I have been talking about all along...the repair
of an old motorcycle."  -- from Zen and the Art of Motorcycle
Maintenance by Robert Pirsig

Re: Why no 'Floor for fixed point types

[Nick Roberts]

Randy Brukardt wrote:

>>Do you think fixed point types should have a Floor attribute?
> 
> The original answer to this showed that for some fixed point types, it
> wouldn't be possible to implement it accurately. Thus, it is much better to
> show what you are doing via a conversion to an appropriate float type.
> Hopefully the compiler can note the easy cases and eliminate the float
> operations.

To my mind, I would not expect this form of optimisation in any compiler.

Would it not be reasonable to provide 'Floor for fixed-point types which 
fulfil certain conditions?

For example, it might be required that the delta be less than 1.0 (and that 
the range includes at least one integer). Alternatively, it might be 
required that the delta is precisely 1.0 (with conditions on the range).

These conditions might be imposed statically (erroneous) or dynamically 
(raising an exception). I suppose the dynamic option would fit easier with 
the possibility of the fixed point type being a generic formal.

After all, if Float'Floor(Float(X)) is going to produce a silly result 
(without itself raising Constraint_Error), what's wrong with 
Some_Fixed'Floor(X) raising Constraint_Error? Surely that would actually be 
better?

-- 
Nick Roberts

Re: Why no 'Floor for fixed point types

[Randy Brukardt]

"Nick Roberts" <nick.roberts@acm.org> wrote in message
news:bns7j9$15h0a9$1@ID-25716.news.uni-berlin.de...
> Randy Brukardt wrote:
>
> >>Do you think fixed point types should have a Floor attribute?
> >
> > The original answer to this showed that for some fixed point types, it
> > wouldn't be possible to implement it accurately. Thus, it is much better
to
> > show what you are doing via a conversion to an appropriate float type.
> > Hopefully the compiler can note the easy cases and eliminate the float
> > operations.
>
> To my mind, I would not expect this form of optimisation in any compiler.

Why not? If a coding style is common, compiler writers will go out their way
to optimize it. Particularly if there are customers who care. It's the same
reason that we don't need Float => Integer rounding attributes -- compilers
can and should optimize the case of the attribute surrounded by the type
conversion.

> Would it not be reasonable to provide 'Floor for fixed-point types which
> fulfil certain conditions?
>
> For example, it might be required that the delta be less than 1.0 (and
that
> the range includes at least one integer). Alternatively, it might be
> required that the delta is precisely 1.0 (with conditions on the range).

To make sense, the 'Small (the delta is irrelevant) would have to be 1/<some
integer>. The default powers of 2 and 10 would work, but not Eachus's
PI/2000.

> These conditions might be imposed statically (erroneous) or dynamically
> (raising an exception). I suppose the dynamic option would fit easier with
> the possibility of the fixed point type being a generic formal.

Yes, it couldn't be a legality check - that would be a "generic contract
model violation". Typically, that's how otherwise good ideas get shot down -
by someone saying "contract model violation".

And it would be weird for this to be a dynamic check. The problem, after
all, is one of accuracy, not that the operation doesn't make sense
mathematically. If 'floor worked like the mixed multiply, it would OK, but
that seems like overkill for a minor problem.

> After all, if Float'Floor(Float(X)) is going to produce a silly result
> (without itself raising Constraint_Error), what's wrong with
> Some_Fixed'Floor(X) raising Constraint_Error? Surely that would actually
be
> better?

But Float'Floor(Float(X)) *will* produce a reasonable result. The problem is
that it may not be possible to represent that result as a value of
Some_Fixed (if the type doesn't have integer values). Producing one of the
"nearby" model numbers [the normal handling of accuracy issues] wouldn't
make sense for this function (if you ask for an integer value, getting
3.14159 would be surprising).

                 Randy.

Re: Why no 'Floor for fixed point types

[Nick Roberts]

Randy Brukardt wrote:

>>>>Do you think fixed point types should have a Floor attribute?
>>>
>>>The original answer to this showed that for some fixed point types,
 >>>it wouldn't be possible to implement it accurately. Thus, it is much
 >>>better to show what you are doing via a conversion to an appropriate
 >>>float type. Hopefully the compiler can note the easy cases and
 >>>eliminate the float operations.
>>
>>To my mind, I would not expect this form of optimisation in any compiler.
> 
> Why not? If a coding style is common, compiler writers will go out
 > their way to optimize it. Particularly if there are customers who
 > care. It's the same reason that we don't need Float => Integer rounding
 > attributes -- compilers can and should optimize the case of the
 > attribute surrounded by the type conversion.

I've never seen or heard of it. But I don't know how broad my experience is 
of these things. I don't doubt that it /could/ be done.

>>Would it not be reasonable to provide 'Floor for fixed-point types which
>>fulfil certain conditions?
>>
>>For example, it might be required that the delta be less than 1.0 (and
>>that the range includes at least one integer). Alternatively, it might
 >>be required that the delta is precisely 1.0 (with conditions on the
 >>range).
> 
> To make sense, the 'Small (the delta is irrelevant) would have to be
 > 1/<some integer>. The default powers of 2 and 10 would work, but not
 > Eachus's PI/2000.

Actually, I think, to really make sense, both 'Delta and 'Small would have 
to be exactly 1.0, and the range ought to be required to be non-null and of 
two integral values not equal to each other.

>>These conditions might be imposed statically (erroneous) or dynamically
>>(raising an exception). I suppose the dynamic option would fit easier with
>>the possibility of the fixed point type being a generic formal.
> 
> Yes, it couldn't be a legality check - that would be a "generic contract
> model violation". Typically, that's how otherwise good ideas get shot down -
> by someone saying "contract model violation".
> 
> And it would be weird for this to be a dynamic check. The problem, after
> all, is one of accuracy, not that the operation doesn't make sense
> mathematically. If 'floor worked like the mixed multiply, it would OK, but
> that seems like overkill for a minor problem.

I think I agree with you here.

>>After all, if Float'Floor(Float(X)) is going to produce a silly result
>>(without itself raising Constraint_Error), what's wrong with
>>Some_Fixed'Floor(X) raising Constraint_Error? Surely that would actually
>>be better?
> 
> But Float'Floor(Float(X)) *will* produce a reasonable result. The problem
 > is that it may not be possible to represent that result as a value of
> Some_Fixed (if the type doesn't have integer values).

I disagree that the result would be reasonable. If we had:

    type Measured_Weight is delta 0.02 range 0.20 .. 0.80;
    W: Measured_Weight;

then of course Float'Floor(Float(W)) would be certain to produce 0.0 
regardless of the (valid) value of W. In these kinds of case, it just 
doesn't make sense to find the floor of W at all. Trying to do so would 
indicate a programming error, and it would be better for it to produce an 
error (preferably at compile time, but better an error when executed than 
just blithely carrying on).

 > Producing one of the "nearby" model numbers [the normal handling of
 > accuracy issues] wouldn't make sense for this function (if you ask
 > for an integer value, getting 3.14159 would be surprising).

I agree!

Perhaps in the case of the above example the programmer may have meant (or 
would have decided, having thought harder) to have found 
Float'Floor(Float(W)*1000) and displayed the resulting three digits (maybe 
on a 7-segment display). This thought suggests to me that you are 
essentially right, Randy. To my mind, it makes sense to convert to Float if 
one is then going to scale by some orders of magnitude before calculating a 
floor.

I don't think it is likely to be a (sensible) requirement for a compiler to 
optimise an expression such as Integer(Float'Floor(Float(W)*1000)) to 
eliminate the actual conversion to (and from) a floating point 
representation in these kinds of cases, because I doubt that they would be 
at all speed-critical.

I'm not really sure of all the practical uses of calculating the floor of a 
number. Can you think of any realistic situation where the speed of a 
Integer(Float'Floor(Float(...)) expression would be that important?

In fact, could the same be said of Integer(Float'Rounding(...)) expressions?

-- 
Nick Roberts