Real literals with fixed point multiplication 870210 AI00262/01 1
 !standard 04.05.05 (10) 870210 AI00262/01
!class study 840713 (provisional classification)
!status received 840713
!topic Real literals with fixed point multiplication and division
!summary 840713
!question 840713
Should real literals be allowed as operands in fixed point multiplication and
division?
!recommendation 840713
!wording 840713
!discussion 840713
 !appendix 870210

 *****************************************************************************
!section 04.05.05 (10) P.Kruchten 830631 8300128
!version 1983
!topic can a real literal be an operand of a fixed point multiply ?
Query:
Can a universal_real be an operand of a fixed point multiplying
operator ? Is 'universal_real' a case of 'any fixed point type' ?
or else:
Is there an implicit conversion of the real literal to one of the
fixed point types visible at that point ? ( LRM 4.6(15) )
and then:
If there are several fixed point types visible at that point,
shall the choice of the type be made on criteria such as the range
or accuracy ?
Example:
procedure MAIN is
type FX1 is delta 0.1 range 100.0 .. 100.0;
type FX2 is delta 0.001 range 1.0 .. 1.0;
A : FX1 := 5.0 ;
begin
A := FX2( A * 0.001 ) ;  type violation ?
 ambiguous ?
 equiv. to: FX2( A * FX2(0.001) ) ?
end MAIN;
Real literals with fixed point multiplication 870210 AI00262/01 2
 *****************************************************************************
!section 04.05.05 (10) P. N. Hilfinger 830531 8300129
!version 1983
!topic can a real literal be an operand of a fixed point multiply ? (8300128)
It was the intent of the LDT (not clearly expressed in 4.10 and 4.5.5)
that universal_real be a fixed point type for the purposes of 4.5.5.
 *****************************************************************************
!section 04.05.05 (10) Ron Brender 831031 8300201
!version 1983
!topic Can a real literal be an operand of a fixed point multiply?
!reference AI00020
I concur with comment 8300129 that it was intended that a real
literal be allowed as an operand of a fixed point multiply (and
division) operator. However, there is a subtle point that bears
further consideration.
RM 4.5.5(11) states that
"Multiplication of operands of the same or of different fixed
point types is exact and delivers a result of the anonymous
predefined fixed point type universal_fixed whose delta is
arbitrarily small. The result of any such multiplication must
always be explicitly converted to some numeric type".
Pragmaticly, it was always understood that fixed point multiplication
(at least where the deltas are powers of two) is essentially an
"integer" multiplication producing a doublelength product which is
then appropriately scaled to the target type of the conversion
(typically also a fixed point type). That is, for the unconverted
result of the multiplication, a delta equal to the product of the
deltas of the two operands was always sufficiently small. However, a
real literal (or other real universal operand) has no defined delta as
such; indeed, real literals and static universal operands generally
are required to be exact according to 4.10(4). This leads to the
conclusion that universal arithmetic (involving both unbounded
accuracy and/or unbounded range) may be required at RUNTIME.
The following examples will help make this concrete.
Example 1:
type T is delta 0.125 range 100.0 .. 100.0;
X , Y : T;
N : constant := 13#7.0#E1;  7/13th
...
X := 13.0;  a model number of T
...  anything to stop constant propagation
Real literals with fixed point multiplication 870210 AI00262/01 3
Y := T(X*N);  Exactly 7.0
Because the value of X (13.0) is a model number of T, N (7/13th) is a
static universal operand, and the exact result (1.0) is also a model
number of T, Y must have the exact result 7.0. In general,
arbitrarily accurate computation at RUNTIME will be required to
assure this result on most reasonable machines.
In the following, assume that FLOAT is the most accurate floating
point type supported by an implementation.
Example 2:
type T is delta 2.0**(20) range 1000.0 .. 1000.0;
N := constant := FLOAT'SMALL*(2.0**(20));
X : T := 2.0**(20);  a model number of T
...
Y := FLOAT(X * N);  exactly FLOAT'SMALL
Here again, the value of X (1.0/(2.0**20))is a model number of T, N is
a universal operand and the exact result (FLOAT'SMALL) is a model
number of FLOAT, so that Y must have this exact result as its value.
In general, unbounded range will be required at RUNTIME to assure
this result.
I do not believe that it was ever contemplated or intended by either
the LDT or DRs that universal arithmetic would/should be required at
runtime. If true, then further work is required to specify just what
is required of an implementation in such examples as the above.
 *****************************************************************************
!section 04.05.05(10) Paul N. Hilfinger 831031
!version 1983
!topic Can a real literal be an operand of a fixed point multiply?
!reference AI00020
Well over a year ago, I had an exchange of messages with Brian Wichmann on
precisely the issue that Brender has raised, but I suspect that we neglected
to post the results.
Assume the following declarations
N: constant := ...;  Where N is universal_real
type Source is delta d1 ...;  Assume that d1 is the actual delta.
type Target is delta d2 ...;  Assume that d2 is the actual delta.
X: Source := ...;
and consider the evaluation of the expression
Target(N*X)
Real literals with fixed point multiplication 870210 AI00262/01 4
In the case where X and N*X are model numbers, this must yield an exact
result. The question is whether this requires "infinite"precision
arithmetic at runtime. I claim it does not.
Assume that X is internally represented by MX, where
X = MX * d1
Then the problem is to find MR such that
MR*d2 = N * X = N * MX * d1
in such a way that when MR is integral, it is computed exactly. We have
MR = MX * (N * d1/d2).
The quantities N, d1, and d2 are all static. Hence, we can compute in
advance integers P and Q such that
P/Q = N * d1/d2
and P/Q is in lowest terms. If MR is integral, then
MR = (P*MX) div Q
and no runtime infinite precision is required.
Of course this blithe formulation hides a host of pitfalls for the user, one
of which is that an innocentlooking multiplication causes a division as
well (since Q is not likely to be a power of 2 unless the programmer was
more careful than he should have to be.) Another problem is that it is
quite easy to get into situations where P and Q are too large, even though N
may look innocent enough.
We may relieve this situation a bit with a little work. Define
I(x) = { ceil(x), floor(x) }
When computing N*X, the rules for fixed point always require only that we
compute an MR that is in the set I(MX * N * d1/d2) (of course, this set has
only one element when N*X is a model number.) Suppose that from range
information, we know that
 MX  <= U
and suppose that
P/Q = N * d1/d2 + epsilon
Then
P*MX div Q = trunc(P*MX/Q) = trunc(MX * N * d1/d2 + MX*epsilon)
Real literals with fixed point multiplication 870210 AI00262/01 5
and a sufficient condition that this quantity be in I(MX * N * d1/d2) is
that
 epsilon  < 1/U, and epsilon has the same sign as N*d1/d2.
This puts much smaller demands on the sizes of P and Q. If we choose
Q to be a power of two, we can use arithmetic shifting, if we are careful
to remember that arithmetic right shifting computes the floor of the
quotient, not the trunc:
P * MX shiftright (log2 Q) = floor(P * MX / Q) =
floor(MX*N*d1/d2 + MX * epsilon)
A sufficient condition that this quantity be in I(MX * N * d1/d2) is
0 <= epsilon < 1/U.
 *****************************************************************************
!section 04.05.05(10) Paul N. Hilfinger 831031
!version 1983
!topic Can a real literal be an operand of a fixed point multiply?
!reference AI00020
Correction on last message: floor doesn't behave quite as nicely as I
initially thought. This is what comes of doing high school algebra at
1AM.
To use right shifting (which computes the floor function), use the same
conditions on epsilon as for div:
 epsilon  < 1/U, and epsilon has the same sign as N*d1/d2
and use the fact that for integers x and y, y>0,
x div y = if x>=0 then floor(x/y) else floor((x+y1)/y) fi.
(This is an example of why Guy Steele once published a note entitled
something to the effect ``Arithmetic right shift considered harmful.'')
 *****************************************************************************
!section 04.05.05(10) Peter Belmont 831102
!version 1983
!topic Can a real literal be an operand of a fixed point multiply?
!reference AI00020 and PNF(831031) (both messages)
!reference Brender(831031)
Good lord.
I did not interpret these messages to mean
Real literals with fixed point multiplication 870210 AI00262/01 6
"Yes, a real literal CAN be an operand..."
and must, on the contrary, interpret them to mean
"Yes, we have no bananas."
and "The gobeluns'll gitche eff ..."
Ada is not supposed to be a writable language, but a readable one (for
people who like longwindedness). If the programmer cannot write
... Target(X*1.734) ...
then he will jolly well have to write
... Target( X * SomeType(1.734) ) ...
and thereby specify what he means. We do NOT want to require
exact arithmetic of arbitrary precision at runtime. Accordingly,
I recommend that the fixedpoint multiply not be overloaded
on universalreal. Compilers can give very useful error messages:
... Target( X * 1.734 ) ...
^
*** Error: This expression must be explicitly converted to some
*** fixed point type (LRM 4.5.5(?))
just as they would do if the 'Target()' had been omitted.
 By the way,
what would we like to happen if the user has defined
a function "*"(x:fixedtype; y:float)
and writes X * 1.734
or Target( X * 1.734 ) ?
If real literals cannot be implicvitly converted to universal
fixed, then there is some hope that his intent will be realized.
 *****************************************************************************
!section 04.05.05 (10) Ron Brender 831118 8300207
!version 1983
!topic Can a real literal be an operand of a fixed point multiply?
!reference AI00020, 8300128
Regarding Hilfinger's analysis of 31 Oct 83, the following is of
interest. In short, it appears the approach suggested can work when
the target type is itself a fixed point type, but it appears to break
down when the target type is a floating point type. The argument is
presented in the following:

From: BRETT 8NOV1983 08:48
To: BRENDER,MITCHELL,STOCKS,GROVE
Real literals with fixed point multiplication 870210 AI00262/01 7
Subj: Sigh
Paul Hilfinger's response is correct as far as it goes...
(1) Using the technique he gives is going to require 2Nbit integer arithmetic
to implement Nbit fixed point multiplication that yields another fixed point
number. This is true for other reasons as well, so isn't too much of a worry
(although annoying).
(2) His midnight highschool math did not address the issue of fixed point
division yielding a fixed point result (of the form N/X, the other way round of
course can be replaced by X/N <=> X*(1/N)).
In this case, and assuming D1/D2 = 1,...
0 <= P/X  N/X < 1, where P is an approximation for N
=>
0 <= P  N < X
=>
N <= P < X + N
Fortunately, the largest N for which N/X will not overflow is only X*X, which
still only requires 2*F'mantissa bits, so his technique is still adequate.
(3) His midnight highschool math did not address the issue of conversions to
FLOATING POINT types.
Consider the equality A = B * (A/B)
Let
F be the floating point type used
N = A/B
P = an approximation for N
E = PN
X = 1.0  greatest number for F that is less than 1.0
Y = least number for F that is greater than 1.0  1.0
(notice that this means X = Y/2 on most machines)
Then
A * (1.0  X/2) < B * P < A * (1.0 + Y/2)
to guarantee that after rounding the answer is A
=>
A * (1.0  X/2) < B * (N+E) < A * (1.0 + X)
A * (1.0  X/2) < A + BE < A * (1.0 + X)
 A * X/2 < BE < A * X
 A/B * X/2 < E < A/B * X
Now, when 1/2 < A/B < 2/3, the range covered by
Real literals with fixed point multiplication 870210 AI00262/01 8
A/B  A/B*X/2 .. A/B + A/B*X
is less than X in width, and thus MAY HAVE NO MODEL NUMBERS in it.
Furthermore if N is done via a divide and multiply, more precision/range than is
provided by F is going to be required, which will be difficult if F is the most
precise/greatest range type available in the implementation.
For instance, on the VAX11 architecture using Hprecision arithmetic, there
is no Hprecision number adequate to express 7.0/12.0, sigh.

(As a sidenote, Goodenough has also pointed out to me that the
approach can't be used in the case of certain attributes that yeild
"runtime universal" values... I leave to him to present the
details.)
 *****************************************************************************
!section 04.05.05 (10) J. Goodenough 831118 8300208
!version 1983
!topic real literals for fixed point multiply and divide
!reference AI00020 8300128
My feeling is that we should stick to the wording of the RM here. Paul
Hilfinger's analysis assumes that all universal real values are static, and
this is not the case. There are several ways to get arbitrary nonstatic
universal real values, e.g., 2.0**N/3.0**M or 1.0*A'LENGTH or 1.0*T'POS(M).
Since we can't interpret the RM to allow just static universal real values,
the runtime consequences of using nonstatic universal real operands for fixed
point multiplication and division are just too unpleasant to contemplate.
Even if there were not nonstatic universal real values, I would still argue
now that static universal real operands should not be allowed. Although the
technique Paul sketches is probably feasible (I haven't really analyzed it
closely), it is a technique that an implementation must, in general, only
support when it allows nonpowers of 2 for 'SMALL. If an implementation has
chosen to restrict representation clauses for 'SMALL, it should not have to do
the extra work required by Paul's technique.
The current wrding of the RM certainly disallows real literals as operands in
fixed point multiplication or division because there are always two fixed
point types in scope (DURATION and the anonymous fixed point type required by
3.5.9(7)). Therefore, there is never a unique fixed point type that can serve
as the target of an implicit conversion, and so C(1.1*F) is always ambiguous,
and hence, illegal. I think we should stick with this reading of the RM.
Real literals with fixed point multiplication 870210 AI00262/01 9
 *****************************************************************************
!section 04.05.05 (10) P. N. Hilfinger 831119 8300217
!version 1983
!topic real literals for fixed point multiply and divide
!reference 8300207, 8300208, 8300128, AI00020
I had only intended to recapitulate what I thought was the original intent
of the LDT (or at least of Brian Wichmann) on this subject. If this was not
the intent, then I concur that we may as well get rid (or stay rid) of the
capability multiplying universal_real*fixed_type (I would just as soon get
rid of builtin fixed point types altogether anyway.) In case Brian should
come up with a strong argument for wanting to provide the capability, here
are a few comments.
1) ``Paul Hilfinger's analysis assumes that all universal real values are
static, and this is not the case. There are several ways to get arbitrary
nonstatic universal real values, e.g., 2.0**N/3.0**M or 1.0*A'LENGTH or
1.0*T'POS(M). Since we can't interpret the RM to allow just static
universal real values, the runtime consequences of using nonstatic
universal real operands for fixed point multiplication and division are just
too unpleasant to contemplate.'' [Goodenough]
Comment: True. In an expression such as
F((2.7**N) * X)  N an INTEGER, X of some fixed type,
 F a fixed point type.
we would not know in advance what the proper delta is to ascribe to the left
operand. The only thing that keeps us from having a simple implementation,
however, is 4.5(7), which says that we are not allowed to raise
NUMERIC_ERROR if the mathematical result of an operation is in a safe
interval (i.e., 4.5(7) disallows hidden intermediate computations that could
overflow.) Without this requirement, the computation above can be performed
as follows for a delta that is a power of 2 and a machine that represents a
fixedpoint number, X, as a simple integer REP(X):
if abs REP(X) > MAX_FLOAT_MANTISSA then raise NUMERIC_ERROR;
else
TEMP := (2.7**N) * BIG_FLOAT(X);
if abs TEMP > MAX_ACCURATE_FLOAT_FOR_F then
raise NUMERIC_ERROR;
else RESULT := F(TEMP);
end if;
end if;
Here, BIG_FLOAT is the highest precision floating type on the machine
(mentioned in 4.10(4)); MAX_FLOAT_MANTISSA is the largest integer that can
be exactly represented as a BIG_FLOAT; and MAX_ACCURATE_FLOAT_FOR_F is the
maximum floating point number that can be converted accurately to an F. It
may seem strange to be using floating point for this computation, but note
that runtime floating point (or better) is required in any case for
Real literals with fixed point multiplication 870210 AI00262/01 10
computations of nonstatic universal_real quantities (see 4.10(4)). I do
not believe, in other words, that these runtime consequences are ``too
unpleasant to comtemplate.''
2) ``It is a technique that an implementation must, in general, only
support when it allows nonpowers of 2 for 'SMALL. If an implementation has
chosen to restrict representation clauses for 'SMALL, it should not have to do
the extra work required by Paul's technique.'' [Goodenough]
Comment: This is true if you disallow universal*fixed computations. When
they are allowed, Brender's original objection seems to apply regardless of
the legal values of 'SMALL. Namely, the result of a fixed point
multiplication has infinite accuracy, and when the mathematically exact
answer is a model number of the target type, it must be produced exactly.
By the way, support for 'SMALLs other than a power of 2 causes some
interesting headaches. For example, again because of 4.5(7), a computation
such as f(p*q) or f(p/q) (f a fixed type, p and q fixed variables) must not
overflow if the mathematical result is in a safe interval of f. However,
for general 'SMALLs, these computations will actually be translated,
respectively as something like (REP(p)*REP(q)*K1)/K2, and
Rep(p)*K1/(K2*Rep(q)) (or possibly Rep(p)*K1/K2/Rep(q)). What's interesting
here is that if K1 is allowed not to be a power of 2, then the first
computation will involve multiplication of doublelength result by a single
length result (rather than the usual single times single yielding double).
Furthermore, if K2 is allowed not to be a power of two then the second
computation will involve either division of a double length quantity by a
double length quantity or division of a double length quantity by a single
length quantity yielding a double length result (rather than the usual
double by single yielding single).
One wants to conclude that support for 'SMALLs other than powers of two will
be rare. However, this puts a slight burden on the implementor of DURATION,
since machines that yield clock or timer values in units of 10E6 seconds or
1/60 second sort of cry out for wierd 'SMALL values.
3) ``His midnight highschool math did not address the issue of conversions to
FLOATING POINT types.'' [Brett]
Comment: True, and this is a problem. As for point (1) above, what prevents
an easy solution are the stringent requirements on NUMERIC_ERROR.
Specifically, in a computation such as
F(G * X)
where G is a universal_real quantity and X a fixed point variable, there are
constants MAX1 and MAX2 such that we can compute
if abs X > MAX1 then raise NUMERIC_ERROR;
else
TEMP := BIG_FLOAT(G) * BIG_FLOAT(X);
if abs TEMP > MAX2 then raise NUMERIC_ERROR;
Real literals with fixed point multiplication 870210 AI00262/01 11
else RESULT := F(TEMP);
end if;
end if;
(The constants MAX1 and MAX2 can be improved if conversion to F rounds.)
SUMMARY
In short, it is very difficult to generate code that computes the correct
answers for the cases above if we have to produce answers in all cases
required by the LRM. Should it be deemed desirable to allow multiplications
of universal_real by fixed quantites, it seems that a slight relaxation of
4.5(7), together with the analyses presented before (which are not
particularly burdensome on an compiler implementation that has rational
arithmetic.)
On the other hand, it is merely a sense of intellectual fair play that
prompts me to defend a feature such as fixed point, which might just as well
be deepsixed and replaced with a specialized generic package for all I care.
 *****************************************************************************
!section 04.05.05 (10) R P Wehrum, Siemens A.G., Muenchen 830602 8300248
!version 1983
!topic Ambiguous Expressions Involving Universal Real Values
Let
... V1 : SOME_FIXED_POINT_TYPE := ...;
V1 := SOME_FIXED_POINT_TYPE(V1 * 3.14);
...
The rhs of the assignment should be legal (at least the programmer will
expect that). However, according to the RM it is not. The type of the
literal is universal_real. Thus an implicit conversion of the literal to
some fixed_point type is needed (or another predefined operator for "*");
but the context does not suffice to determine the target type of the
conversion; the expression is ambiguous; some semantic rule is missing.
(Cf. Section 4.5.5(10), 4.6(15).)
Is this an oversight of the language designers?
 *****************************************************************************

 !section 04.05.05 (10) Terry Froggatt 861210 8300889
 !version 1983
 !topic Fixed Multiplication & Division with Real Literals

 In Ada, a floating point number can be multiplied or divided by a real
 literal constant (or any universal real named number) whereas a fixedpoint
 number cannot be: the programmer has to give the literal a type.
Real literals with fixed point multiplication 870210 AI00262/01 12
 This is AI20. In fact this restriction is unnecessary.

 To perform A := A_TYPE(C*B) or A := A_TYPE(B*C) or A := A_TYPE(B/C), where
 C is a constant, we simply multiply or divide the scaling factor associated
 with the conversion of A to B, by the value of C, in the compiler; then
 generate exactly the same code that we would have used for A := A_TYPE(B)
 but using the revised scaling factor (which can now be negative).
 (But note that A := A_TYPE(C/B) is a different problem).

 This is implemented using a multiplication by one constant then a
 division by another constant: the ratio of the constants being a
 continued fraction approximation to the scaling factor. Of all the
 operations on fixed point numbers which involve the use of scaling
 factors, this one (fixedtofixed conversion) is the only one which
 can be implemented easily.

 So it is strange that the reason given for the lack of the literal
 operations is the uncertainty over the accuracy to which the constant
 has to be held at runtime, (see Ada Letters IV2.68 & VI.677).
 There are considerably worse problems over the representation of
 scale factors for fixedtointeger, fixedto/fromfloat, and
 universalfixedtoanynumerictype.

 Note that it is already possible in Ada to multiply or divide fixed
 values by named numbers, without having to specify any reduction in
 the named number's accuracy:
 PI: constant := 3.14..........................................;
 type PI_TYPE is delta PI range 0..2*PI;
 for PI_TYPE'SMALL use PI;
 TYPED_PI: constant PI_TYPE := PI;  Still as exact as the named number.
 ....
 FIXED_VALUE := FIXED_TYPE ( FIXED_VALUE * TYPED_PI );