[Haskell-cafe] Implementation of scaled integers

[Sebastian Sylvan]

On 2/13/07, Stefan Heinzmann <stefan_heinzmann at yahoo.com> wrote:
> Hi all,
>
> is there a library for Haskell that implements scaled integers, i.e.
> integers with a fixed scale factor so that the scale factor does not
> need to be stored, but is part of the type?
>
> In particular it would be useful (i.e. for signal processing) to have
> numbers based on Int scaled such that they fall into the range [-1.0 ..
> 1.0). Or other scale factors which are powers of 2. Addition and
> subtraction would then map to the ordinary operations for Int, while
> Multiplication and Division would have to apply the scale factor to
> correct the result of normal Int operations (which would be a shift
> operation).
>
> If it doesn't exist yet, have you got ideas how to implement that for
> maximum efficiency?
>

What you're looking for is usually referred to as "fixed point
arithmetic", sadly the term "fixed point" when talking about
functional languages means something entirely different so it's a bit
tricky to google for it! :-)

As for implementation tips, I would recommend that you take a look at
Data.Bits for shifting (assuming that the scaling factor is a power of
two). The only caveat is that when you perform the "(a<< s)/b" and
"(a*b)>>s" operations that you need for multiplication and division,
the inner multiplication/shift needs to have enough precision in its
result value to avoid overflow (i.e. for Int32, you'll need to use a
multiplication which has a 64 bit result type -- probably easiest to
just convert both operands to Int64 before multiplying).

-- 
Sebastian Sylvan
+46(0)736-818655
UIN: 44640862