baud@eedsp.eedsp.gatech.edu (Kurt Baudendistel) (03/16/90)
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!baudrobison@dfsun1.electro.swri.edu (Bob Robison) (03/16/90)
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
westley@corsair.uucp (Terry J. Westley) (03/20/90)
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
eachus@aries.mitre.org (Robert I. Eachus) (03/22/90)
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...
cdc@uafhcx.uucp (C. D. Covington) (03/27/90)
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