On 2/13/07, Stefan Heinzmann
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