Truncating a fixed-point value

Truncating a fixed-point value

[Adam Beneschan]

I must be suffering from an embarrassing mental block, because I'm
sure there's a simple solution, but I can't see what it is.

I have a value X of a fixed-point type, X >= 0.0, and I need to
compute Floor(X) as an Integer.  'Truncation and 'Floor aren't defined
for fixed-point types; the type conversion Integer(X) rounds; and
Integer(X-0.5) fails if X=0.0.

How do others do this?  Or do I have to resort to an IF statement (or
conditional expression in Ada 2012) to handle the different cases?

               -- Adam

Re: Truncating a fixed-point value

[Simon Wright]

Adam Beneschan <adam@irvine.com> writes:

> I must be suffering from an embarrassing mental block, because I'm
> sure there's a simple solution, but I can't see what it is.
>
> I have a value X of a fixed-point type, X >= 0.0, and I need to
> compute Floor(X) as an Integer.  'Truncation and 'Floor aren't defined
> for fixed-point types; the type conversion Integer(X) rounds; and
> Integer(X-0.5) fails if X=0.0.
>
> How do others do this?  Or do I have to resort to an IF statement (or
> conditional expression in Ada 2012) to handle the different cases?

Looks as though Integer(X+0.5)-1 might do the trick ..

Re: Truncating a fixed-point value

[Adam Beneschan]

On Jul 9, 1:34 pm, Simon Wright <si...@pushface.org> wrote:
> Adam Beneschan <a...@irvine.com> writes:
> > I must be suffering from an embarrassing mental block, because I'm
> > sure there's a simple solution, but I can't see what it is.
>
> > I have a value X of a fixed-point type, X >= 0.0, and I need to
> > compute Floor(X) as an Integer.  'Truncation and 'Floor aren't defined
> > for fixed-point types; the type conversion Integer(X) rounds; and
> > Integer(X-0.5) fails if X=0.0.
>
> > How do others do this?  Or do I have to resort to an IF statement (or
> > conditional expression in Ada 2012) to handle the different cases?
>
> Looks as though Integer(X+0.5)-1 might do the trick ..

Yes, it looks like it, as long as X >= 0.0 and 0.5 is a model number
of the fixed-point type (I think I'm using the right term).  Those
conditions do hold for the code I need it for.  It isn't useful for
negative numbers---it yields -2 if X=-1.0, which is not useful whether
you want a truncation or a floor operation---but I did stipulate
nonnegative X in my original question.

                         -- Adam

Re: Truncating a fixed-point value

[Gene]

On Jul 9, 7:21 pm, Adam Beneschan <a...@irvine.com> wrote:
> On Jul 9, 1:34 pm, Simon Wright <si...@pushface.org> wrote:
>
> > Adam Beneschan <a...@irvine.com> writes:
> > > I must be suffering from an embarrassing mental block, because I'm
> > > sure there's a simple solution, but I can't see what it is.
>
> > > I have a value X of a fixed-point type, X >= 0.0, and I need to
> > > compute Floor(X) as an Integer.  'Truncation and 'Floor aren't defined
> > > for fixed-point types; the type conversion Integer(X) rounds; and
> > > Integer(X-0.5) fails if X=0.0.
>
> > > How do others do this?  Or do I have to resort to an IF statement (or
> > > conditional expression in Ada 2012) to handle the different cases?
>
> > Looks as though Integer(X+0.5)-1 might do the trick ..
>
> Yes, it looks like it, as long as X >= 0.0 and 0.5 is a model number
> of the fixed-point type (I think I'm using the right term).  Those
> conditions do hold for the code I need it for.  It isn't useful for
> negative numbers---it yields -2 if X=-1.0, which is not useful whether
> you want a truncation or a floor operation---but I did stipulate
> nonnegative X in my original question.
>
>                          -- Adam

Shouldn't there be a way to convert a fixed point type to a
corresponding modular or integer type with one integer value per
floating point value, use rem to compute a floor, and convert back?

Re: Truncating a fixed-point value

[Gene]

On Jul 9, 11:13 pm, Gene <gene.ress...@gmail.com> wrote:
> On Jul 9, 7:21 pm, Adam Beneschan <a...@irvine.com> wrote:
>
>
>
>
>
> > On Jul 9, 1:34 pm, Simon Wright <si...@pushface.org> wrote:
>
> > > Adam Beneschan <a...@irvine.com> writes:
> > > > I must be suffering from an embarrassing mental block, because I'm
> > > > sure there's a simple solution, but I can't see what it is.
>
> > > > I have a value X of a fixed-point type, X >= 0.0, and I need to
> > > > compute Floor(X) as an Integer.  'Truncation and 'Floor aren't defined
> > > > for fixed-point types; the type conversion Integer(X) rounds; and
> > > > Integer(X-0.5) fails if X=0.0.
>
> > > > How do others do this?  Or do I have to resort to an IF statement (or
> > > > conditional expression in Ada 2012) to handle the different cases?
>
> > > Looks as though Integer(X+0.5)-1 might do the trick ..
>
> > Yes, it looks like it, as long as X >= 0.0 and 0.5 is a model number
> > of the fixed-point type (I think I'm using the right term).  Those
> > conditions do hold for the code I need it for.  It isn't useful for
> > negative numbers---it yields -2 if X=-1.0, which is not useful whether
> > you want a truncation or a floor operation---but I did stipulate
> > nonnegative X in my original question.
>
> >                          -- Adam
>
> Shouldn't there be a way to convert a fixed point type to a
> corresponding modular or integer type with one integer value per
> floating point value, use rem to compute a floor, and convert back?- Hide quoted text -

I'll try to answer my own question.  Here is an attempt that works for
a variety of fixed point types.  I'm no expert on fixed point. Perhaps
I've embedded some non-portable assumptions. With optimizations turned
up and range checks off, the Floor function inlines as the 3 (x86)
instructions you'd expect (subtract, "and" with mask, add) using GPL
2007.

with Ada.Text_IO; use Ada.Text_IO;

procedure FPF is

  type FP is delta 0.125 range -10.0 .. 50.0;

  function Floor(X : FP) return FP is
    Delta_Inv : constant := 1.0 / FP'Delta;
    type Bits is mod 2 ** 32;
    type FP_Bits is delta 1.0 range 0.0 .. (FP'Last - FP'First) *
Delta_Inv;
    Ordinal : constant Bits := Bits((X - FP'First) * Delta_Inv) and
not(Bits(Delta_Inv) - 1);
  begin
    return FP'Base(FP_Bits(Ordinal) * FP'Delta) + FP'First;
  end;

  X : FP := FP'First;
begin
  loop
    Put_Line(FP'Image(X) & " -> " & FP'Image(Floor(X)));
    exit when X = FP'Last;
    X := X + FP'Delta;
  end loop;
end;

Re: Truncating a fixed-point value

[Simon Wright]

Adam Beneschan <adam@irvine.com> writes:

> On Jul 9, 1:34 pm, Simon Wright <si...@pushface.org> wrote:
>> Adam Beneschan <a...@irvine.com> writes:
>> > I must be suffering from an embarrassing mental block, because I'm
>> > sure there's a simple solution, but I can't see what it is.
>>
>> > I have a value X of a fixed-point type, X >= 0.0, and I need to
>> > compute Floor(X) as an Integer.  'Truncation and 'Floor aren't defined
>> > for fixed-point types; the type conversion Integer(X) rounds; and
>> > Integer(X-0.5) fails if X=0.0.
>>
>> > How do others do this?  Or do I have to resort to an IF statement (or
>> > conditional expression in Ada 2012) to handle the different cases?
>>
>> Looks as though Integer(X+0.5)-1 might do the trick ..
>
> Yes, it looks like it, as long as X >= 0.0 and 0.5 is a model number
> of the fixed-point type (I think I'm using the right term).  Those
> conditions do hold for the code I need it for.  It isn't useful for
> negative numbers---it yields -2 if X=-1.0, which is not useful whether
> you want a truncation or a floor operation---but I did stipulate
> nonnegative X in my original question.

I hadn't considered the model number aspect, but nonnegative X is
indeed necessary for this solution!

Re: Truncating a fixed-point value

[Gene]

On Jul 9, 3:06 pm, Adam Beneschan <a...@irvine.com> wrote:
> I must be suffering from an embarrassing mental block, because I'm
> sure there's a simple solution, but I can't see what it is.
>
> I have a value X of a fixed-point type, X >= 0.0, and I need to
> compute Floor(X) as an Integer.  'Truncation and 'Floor aren't defined
> for fixed-point types; the type conversion Integer(X) rounds; and
> Integer(X-0.5) fails if X=0.0.
>
> How do others do this?  Or do I have to resort to an IF statement (or
> conditional expression in Ada 2012) to handle the different cases?
>
>                -- Adam

There is a prior discussion of this question:

http://coding.derkeiler.com/Archive/Ada/comp.lang.ada/2003-10/0729.html

The problem is that fixed point types don't have to include all the
integers.

An ugly approach is to convert to e.g. a long float, take the floor,
and convert back.  No doubt others will have something more elegant.

Re: Truncating a fixed-point value

[Jeffrey R. Carter]

On 07/09/2010 01:39 PM, Gene wrote:
>
> An ugly approach is to convert to e.g. a long float, take the floor,
> and convert back.  No doubt others will have something more elegant.

That's the approach I use, though, in the interest of portability, I declare my 
own floating-point type for the purpose:

function Floor (Value : in Fixed) return Integer is
    type Big is digits System.Max_Digits;
begin -- Floor
    return Integer (Big'Floor (Big (Value) ) );
end Floor;

-- 
Jeff Carter
"It's symbolic of his struggle against reality."
Monty Python's Life of Brian
78

Re: Truncating a fixed-point value

[Adam Beneschan]

On Jul 9, 1:39 pm, Gene <gene.ress...@gmail.com> wrote:
> On Jul 9, 3:06 pm, Adam Beneschan <a...@irvine.com> wrote:
>
> > I must be suffering from an embarrassing mental block, because I'm
> > sure there's a simple solution, but I can't see what it is.
>
> > I have a value X of a fixed-point type, X >= 0.0, and I need to
> > compute Floor(X) as an Integer.  'Truncation and 'Floor aren't defined
> > for fixed-point types; the type conversion Integer(X) rounds; and
> > Integer(X-0.5) fails if X=0.0.
>
> > How do others do this?  Or do I have to resort to an IF statement (or
> > conditional expression in Ada 2012) to handle the different cases?
>
> >                -- Adam
>
> There is a prior discussion of this question:
>
> http://coding.derkeiler.com/Archive/Ada/comp.lang.ada/2003-10/0729.html

Thanks for the link.  I was aware of AI95-60 but I hadn't been aware
that the problem had been brought up again.


> The problem is that fixed point types don't have to include all the
> integers.

Ah, I see.  This is a problem because 'Truncation and 'Floor are
defined to return the same fixed-point type.  It seems to me that the
language could use a way to do the truncation (or floor) and return an
integer, without having to worry about an intermediate result of the
same fixed-point type (which might not be a possible value of the
type).  I think someone mentioned that in the thread, but mentioned
that it would probably have to be generic.


> An ugly approach is to convert to e.g. a long float, take the floor,
> and convert back.  No doubt others will have something more elegant.

That will probably work for my purpose; but in general, it's easy to
define a fixed-point number with a 'Small of 2**(-N) that has more
bits to the right of the binary point than are available in the
mantissa part of the floating-point.  If that's the case, this
approach will fail on certain values (probably M - (K * T'Small) for
integer M and suitably small integer K).  Since this situation lends
itself to really efficient code (basically just a bit shift), it's
kind of a shame that the language doesn't give you a good way to do
this.

                           -- Adam

Re: Truncating a fixed-point value

[Jacob Sparre Andersen]

Adam Beneschan wrote:

> That will probably work for my purpose; but in general, it's easy to
> define a fixed-point number with a 'Small of 2**(-N) that has more
> bits to the right of the binary point than are available in the
> mantissa part of the floating-point.  If that's the case, this
> approach will fail on certain values (probably M - (K * T'Small) for
> integer M and suitably small integer K).  Since this situation lends
> itself to really efficient code (basically just a bit shift), it's
> kind of a shame that the language doesn't give you a good way to do
> this.

Isn't it possible to write a truncation function, which uses bit shift
when it is appropriate?  If the 'Small is statically known, there is a
fair chance that the compiler will remove the unused branch at
compile-time.

Jacob
-- 
"If we weren't at least occasionally surprised by the results,
 we might as well save ourselves the trouble of measuring :)"

Re: Truncating a fixed-point value

[Shark8]

On Jul 9, 1:06 pm, Adam Beneschan <a...@irvine.com> wrote:
> I must be suffering from an embarrassing mental block, because I'm
> sure there's a simple solution, but I can't see what it is.
>
> I have a value X of a fixed-point type, X >= 0.0, and I need to
> compute Floor(X) as an Integer.  'Truncation and 'Floor aren't defined
> for fixed-point types; the type conversion Integer(X) rounds; and
> Integer(X-0.5) fails if X=0.0.
>
> How do others do this?  Or do I have to resort to an IF statement (or
> conditional expression in Ada 2012) to handle the different cases?
>
>                -- Adam

I'd think that 1-Integer(X+0.5) would work... wouldn't it?