language support for fixed-point arithmetic

language support for fixed-point arithmetic

[Kurt Baudendistel]

I'd like to find out about language support for fixed-point arithmetic.

I am aware of only two types of support for such a data type:

  Ada supports an intrinsic fixed-point type that allows the user 
      to specify the range (maximum absolute value supported) and 
      scale (maximum required step-size). It is intended to be
      implemented via an integer arithmetic unit to provide (1) fixed-
      accuracy computations and (2) efficient execution in embedded
      systems without floating-point hardware support.

      The ideas for Ada's fixed-point type came from some other
      embedded systems lanaguages, but it is the only ``modern''
      language that supports a fixed-point type.

  C++ and other object-oriented languages (such as Ada) that support
      data type synthesis (constructors/destructors, infix operators,
      etc.) can be used to build fixed-point data types.  
      
      If we are interested in efficient execution and fixed-accuracy
      computations, as the Ada fixed-point intrinsic type is, we
      must note that, as with any other user-defined type, such fixed-
      point data types can be constructed only of existing language 
      components.  This means that we can construct such types only in 
      the manner that Ada does---integer arithmetic is the implementation 
      method and a fixed-point type has a specified range and scale.
      Such data types will not be as efficient as the built-in Ada type,
      since they have to carry around a lot of baggage that can't be
      integrated in to the code, but that's life in the fast lane.

      If we are interested in the fixed-point data type only for the
      purposes of simulation, however, we can construct fixed-point
      data types that do many more things---saturation overflow, 
      delayed multiplication, automatic scale adjustment, etc.

Why am I intereted in such fixed-point data types? Well, Programmable
DSP (Digital Signal Processing) chips have become commonplace, but a
programming medium (in the form of a fixed-point data type) and a
programming methodology (that would help the programmer pick range
and scale parameters) have not materialized. 

I would like to proceed with some ideas to (hopefully) produce thesis 
quality material on this topic, but I have discovered a disconcerting
fact---there doesn't appear to be any literature on this topic!  A
better statement might be that I can't find any literature on this 
topic, and this makes me very uncomfortable since I'm sure that there
must be some out there!

I know of only a few articles dealing with this topic from a language 
design standpoint:

  Froggatt, Fixed-point conversion, multiplication, and division in Ada,
    Ada Letters, Vol. 7, No. 1, Jan-Feb 1987, pp. 71-81
    (A rationale for the Ada fixed-point data type)

  Nelson, Pascal-F, IEEE ElectroTechnology Review, 1986
    (I haven't read this one yet)

  Pepe and Rogers, Simulation of fixed-point operations with high-level
    languages, IEEE Trans. on ASSP, Vol. ASSP-35, No. 1, p. 116-18,
    Jan 1987 
    (Fortran subroutines)

  Johnson, [I can't find the reference right now]
    (C++ classes for fixed-point simulation)
    
I have tried on-line library searches, scoured the ACM Computing
Guide for the last ~5 years, and asked local CS profs, and come up
dry! Can anyone out there in netland put me on the trail of some
research/articles on language design for fixed-point arithmetic?
Any help at all (including references and personal contacts) will
be greatly appreciated.

Please respond, and please respond by e-mail! If you are interested
in the results of my search, e-mail a result-request as well.

Thanks.
kurt
-- 
Kurt Baudendistel --- GRA
Georgia Tech, School of Electrical Engineering, Atlanta, GA  30332
internet: baud@eedsp.gatech.edu         uucp: gatech!gt-eedsp!baud

Re: language support for fixed-point arithmetic

[Bob Robison]

In article <787@eedsp.eedsp.gatech.edu> baud@eedsp.eedsp.gatech.edu (Kurt Baudendistel) writes:
>I'd like to find out about language support for fixed-point arithmetic.
[bunch of stuff deleted]
>
>  Johnson, [I can't find the reference right now]
>    (C++ classes for fixed-point simulation)

The one I have on this is Robert E. Vaughan and Don H. Johnson,
	A Fixed Point Arithemtic Type for Signal Processing Systems Simulation
	Rice University Technical Report #8510, May 1985

>Thanks.
>kurt

Good Luck.

bob

-- 
Bob Robison	- Southwest Research Institute, Electromagnetics Div.
robison@dfsun1.electro.swri.edu
{sun!texsun, gatech!petro, uunet!cs.utexas.edu}!swrinde!dfsun1!robison

Re: language support for fixed-point arithmetic

[Terry J. Westley]

In article <787@eedsp.eedsp.gatech.edu> baud@eedsp.eedsp.gatech.edu (Kurt Baudendistel) writes:
>  Ada supports an intrinsic fixed-point type that allows the user 
>      to specify the range (maximum absolute value supported) and 
>      scale (maximum required step-size). It is intended to be
>      implemented via an integer arithmetic unit to provide (1) fixed-
>      accuracy computations and (2) efficient execution in embedded
>      systems without floating-point hardware support.
>
>Please respond, and please respond by e-mail! If you are interested
>in the results of my search, e-mail a result-request as well.
>

First, thanks to Mr. Baudendistel for posting technical questions and
comments, not language war stuff.

I find Watt, Wichmann, and Findlay's _ADA_Language_and_Methodology_
(Prentice-Hall) useful in teaching advanced Ada students about fixed
point types.  It includes a section on analyzing how the error bound
grows when performing many fixed point type calculations.  However, it
is not a formal or exhaustive treatement of the subject.

Please e-mail me or post the results. 

Fixed point types are potentially very useful, but I have run into a
number of interesting educational challenges, all originating from
users' expectations.  (This is in a real-time system running on a
distributed network of M68030 and Sun workstation environment.)

1. Designers and programmers understand why 'small must be a power of
   two, but they wish they could have it be any arbitrary size.  In
   principle, this seems very possible, but I can see the performance
   problems that would crop up because people use a powerful feature
   without realizing what is really happening in the machine.

2. Users see the potential of fixed point types to give them the best of
   both worlds of real and integer types, and they want more of each.
   For example, they see a number as a real and expect to use the math
   co-processor.  Naturally, converting back and forth to a floating point
   type destroys much the integer representation advantages.

I am slowly beginning to get across the responsibility of the designer
in choosing data types and the flexibility there is to add operations as
needed.

You give them an inch and they'll take a mile.  Then, they complain that
the compiler doesn't support the mile.  Then, they realize they can
bridge the mile themselves with not too much effort.  Great stuff!!

Terry J. Westley
Arvin/Calspan Advanced Technology Center
P.O. Box 400, Buffalo, NY 14225
acsu.buffalo.edu!planck!hercules!westley

Re: language support for fixed-point arithmetic

[Robert I. Eachus]

In article <1990Mar19.175559.17109@planck.uucp> westley@corsair.uucp (Terry J. Westley) writes:

>  Fixed point types are potentially very useful, but I have run into a
>  number of interesting educational challenges, all originating from
>  users' expectations.  (This is in a real-time system running on a
>  distributed network of M68030 and Sun workstation environment.)

>   1. Designers and programmers understand why 'small must be a power of
>     two, but they wish they could have it be any arbitrary size.  In
>     principle, this seems very possible, but I can see the performance
>     problems that would crop up because people use a powerful feature
>     without realizing what is really happening in the machine.

      Huh? Why must 'SMALL be a power of two?  By default 'SMALL is a
power of two, but this is an arbitrary choice which can be overridden
by a "for foo'SMALL use ..." declaration.  Compilers are not required
to support ARBITRARY values for 'SMALL, because there would be an ACVC
test with something like "for foo'SMALL use 7#0.0000005#
- 5#0.000000000000000004# / 3#0.22222222#;" or some other dubious
expression.  However, the good compilers support most reasonable
specifications, and the ARG is working on a definition of what a
"reasonable" value is.  (At which point there probably will be an ACVC
test...)

>   2. Users see the potential of fixed point types to give them the best of
>     both worlds of real and integer types, and they want more of each.
>     For example, they see a number as a real and expect to use the math
>     co-processor.  Naturally, converting back and forth to a floating point
>     type destroys much the integer representation advantages.

     When you find an Ada compiler generating floating point code for
fixed point operations, bitch.  This is not a feature--it is almost
always a bug.  For example, the expresion A := foo(B*C) should never
generate floating point code if A, B and C are of the same (fixed
point) type.  (Speak carefully here, you are being watched. :-) This
does not mean that operations involving fixed point may not use mixed
mode instructions, or scaling functions in a floating point chip, just
that in the general case, using a floating point multiply or divide
will result in loss of accuracy.  Please, no flames from implementers
saying we use lots of guard bits...many fixed point multiplication
results must be exact, and RTFM, exact may mean many more bits than
are required to represent either of the operand types.

>   I am slowly beginning to get across the responsibility of the designer
>  in choosing data types and the flexibility there is to add operations as
>  needed.

>   You give them an inch and they'll take a mile.  Then, they complain that
>  the compiler doesn't support the mile.  Then, they realize they can
>  bridge the mile themselves with not too much effort.  Great stuff!!

     Agreed.  If the implementer gets fixed point right, and the user
does a little bit of thinking, operations in fixed point are both much
faster and much more accurate than floating point arithmetic.  My
favorite example is:

     type Meters is delta 0.000_001 range
		-2.0**31/0.000_001..2.0**31/0.000_001-0.000_001; 
     for Meters'SMALL use 0.000_001;

     type Nautical_Miles is delta Meters'SMALL / 1852.0 range
		Meters'FIRST / 1852.0 .. Meters'LAST / 1852.0; 
     for Nautical_Miles'SMALL use Meters'SMALL / 1852.0;

     function To_Meters (X: in Nautical_Miles) return Meters is
     begin return Meters (X*1852); end To_Meters;

     function To_Nautical_Miles (X: in Meters) return Nautical_Miles is
     begin return Nautical_Miles (X/1852); end To_Nautical_Miles;

     pragma INLINE (To_Meters, To_Nautical_Miles);

     If your compiler is really good it will not generate any code for
the conversions.  Of course, if it has trouble you can write the
conversion functions as instantiations of UNCHECKED_CONVERSION...
--

					Robert I. Eachus

with STANDARD_DISCLAIMER;
use  STANDARD_DISCLAIMER;
function MESSAGE (TEXT: in CLEVER_IDEAS) return BETTER_IDEAS is...

'small not power of 2 (Was: language support for fixed-point arithmetic)

[Terry J. Westley]

In article <EACHUS.90Mar21171727@aries.aries.mitre.org> eachus@aries.mitre.org (Robert I. Eachus) writes:
>      Huh? Why must 'SMALL be a power of two?  By default 'SMALL is a
>power of two, but this is an arbitrary choice which can be overridden
>by a "for foo'SMALL use ..." declaration.

Since confession is supposed to be good, I confess that this capability
had never penetrated the fog in my brain.  I know that I have read it
in Booch (_Software_Engineering_with_Ada_) and in the RM, but it never
clicked.  Thanks.

I tried your types METERS and NAUTICAL_MILES example from the referenced
article.  The compiler I used (Verdix 6.0 on Sun 4) generated code for
the conversion functions.  The compiler crashed when I used higher
levels of optimization.  (Note to anyone from Verdix who might be
reading this: I sent a report in today with the details.)
Unchecked_Conversion, of course, works.

Do you know of any compilers that are "smart" enough to detect this
situation?

Terry J. Westley
Arvin/Calspan Advanced Technology Center
P.O. Box 400, Buffalo, NY 14225
acsu.buffalo.edu!planck!hercules!westley

Re: language support for fixed-point arithmetic

[C. D. Covington]

    I have been involved in this field for some time and authored the GOSPL
system (Graphic Oriented Signal Processing Language) which appeared at the
same time as the BDC (Block Diagram Compiler) of Lincoln Labs and has now been
eclipsed by the Gabriel system of Berkeley.  In summary, my impression is that
exact mapping of algorithms into fixed point implementations has been relegated
to technicians in real companies and that academia consistently uses floating
point to bury this problem during algorithm development.

    I think you have an interesting problem.  Go for it.


C. David Covington (WA5TGF)                       INTERNET cdc@uafhcx.uark.edu
Assistant Professor, Electrical Engineering  (501)575-6583 campus office
University of Arkansas                            575-5379 research office
Fayetteville, AR 72701                            575-3041 research lab