Re: rules of fixed-point arithmetic

On Tue, 09 Sep 2008 13:47:59 +0000, Nick Maclaren wrote:
Sigh. Yes. And I also know that fixed-point arithmetic covers a wide
range of computer models - which, from the inaccuracies you have posted
on the matter, you don't.

Well, it's true that I'd forgotten about the bizzaro-land of PL/I and ADA
"fixed point", where the scale factors not only aren't constant for the
arithmetic, but which don't even have to be powers of two.

I'm certain that every so often that becomes important, but glancing at
the web, it's mostly so that people can write papers about neat ways to
make it perform a little better.

In particular, it makes a HELL of a difference whether you are assuming
two things, either or both of which may be false:

1) All fixed-point numbers have the same precision.

2) Division of two fixed-point numbers is not something that you
have to worry about - either you don't need it, or its exact result
isn't critical.

I assumed those things because both are true in the vast bulk of the
places where fixed point is actually *used*, as opposed to being worried
about.

If you throw away 1, you're almost back to dealing with rational numbers,
which is still integer work, but a lot less fun. At least if you can
keep your scale factors to powers of two, which is IMO not unreasonable,
you can reduce the scale normalization operations to shifts, rather than
multiplications by arbitrary rational numbers. If you keep 1, then you
don't have to re-scale at all, except for when you reduce an accumulator
or product back to one of your standard data types.

Yes, division of fixed point numbers is a pain, since, as you point out,
you have to deal with results that may not fit neatly into the range of
your data. Whenever possible, the answer is to just not divide. When
division is essential, you have to deal with it. One of the more
convenient ways to do that is to define a division operator as x/(y*M),
where M is a power-of-two scale factor that you select to ensure that
your result is a fraction in the appropriate range: trading precision and
range. I think that the only fixed point arithmetic where division isn't
much of a pain is one where the number of bits devoted to integer values
is the same as the number devoted to fractions, such as the 16.16 format
that Knuth used in TeX.


|> > |> Fixed point arithmetic is just integer arithmetic.
Interpretation |> |> > usually involves a scale factor of a power of
two, but that often |> > doesn't |> show up as actual manipulation
(although some chips do have a |> > shift-left |> by one after a
multiply, so that the usual binary points |> > of source |> operands and
accumulators line up.) |> >
|> > That is not true. It is just about true for addition and
subtraction |> > with a fixed precision, but stops being true
thereafter. |>
|> Bull***.
|>
|> Make your disagreement more explicit. Are you worried about
varieties |> and occurrence of rounding? Certainly important, but not
consequential |> for basic arithmetic operations with a sufficiently
wide accumulator. |> That's all pure integer.

I suggest that you should try to be either more polite or less ignorant.
I shall not continue unless you do attempt one or the other.

Seemed like a reasonable response to a post that was little more than
"you're wrong", and offered no more concrete advice for the original
poster than that. In the calm light of morning, I realize that your
response is close to correct, and so I apologise for my abruptness. Done
properly, though, addition, subtraction *and* multiplication are just
integer operations, which covers most of what one needs from an
arithmetic, to a first order approximation.

Consider, for example, the result of dividing one fixed-point number by
another, when the second one is less than 1.0 - you have to worry about
overflow, which cannot occur with integer division (except for the twos'
complement aberration).

Yep. Division is a problem. You might be surprised at how much useful
work can be achieved without it, though. And when it's necessary, it's
possible: you just have to think about it a good deal more than you do in
a floating point environment.

And, unlike with integers, there is no generally accepted result of
imprecise division. Some uses of fixed-point traditionally favour a
quotient and remainder result, and others a nearest approximation.
Neither are trivial.

Yup. This turns out to be very rarely a problem in practice though, for
the reason that I mentioned above.

Cheers,

--
Andrew
.