2

I'm writing a Fixedpoint class, but have ran into bit of a snag... The multiplication, division portions, I am not sure how to emulate. I took a very rough stab at the division operator but I am sure it's wrong. Here's what it looks like so far:

class Fixed
{
    Fixed(short int _value, short int _part) : 
        value(long(_value + (_part >> 8))), part(long(_part & 0x0000FFFF)) {};

    ...

    inline Fixed operator -() const  // example of some of the bitwise it's doing
    {
        return Fixed(-value - 1, (~part)&0x0000FFFF);
    };

    ...

    inline Fixed operator / (const Fixed & arg) const // example of how I'm probably doing it wrong
    {
        long int tempInt = value<<8 | part;
        long int tempPart = tempInt;
        tempInt  /= arg.value<<8 | arg.part;
        tempPart %= arg.value<<8 | arg.part;
        return Fixed(tempInt, tempPart);
    };

    long int value, part; // members
};

I... am not a very good programmer, haha!

The class's part is 16 bits wide (but expressed as a 32-bit long since I imagine it'd need the room for possible overflows before they're fixed) and the same goes for value which is the integer part. When the 'part' goes over 0xFFFF in one of it's operations, the highest 16 bits are added to 'value', and then the part is masked so only it's lowest 16 bits remain. That's done in the init list.

I hate to ask, but if anyone would know where I could find documentation for something like this, or even just the 'trick' or how to do those two operators, I would be very happy for it! I am a dimwit when it comes to math, and I know someone has had to do/ask this before, but searching google has for once not taken me to the promised land...

phuclv
  • 37,963
  • 15
  • 156
  • 475
Anne Quinn
  • 12,609
  • 8
  • 54
  • 101
  • Is this homework? You're essentially trying to mimic floating point math, but without using the floating-point byte notation? Have you looked at how IEEE handles this? – Zac Howland Feb 17 '11 at 12:43
  • @Zac Sadly no, never gone to programming school or nothing as you can tell! This is for a very poor attempt of avoiding floating point arithmatic in a 2d physics engine I'm doing. But I'm googling IEEE right now, so I'll see! – Anne Quinn Feb 17 '11 at 12:48
  • @Zac: OP is talking about 'fixed' point mul&division, not 'floating' point, there is a difference. http://en.wikipedia.org/wiki/Fixed-point_arithmetic – Tony The Lion Feb 17 '11 at 12:50
  • @Tony: The basic principles behind the two are the same. Though, unless this is being used on a system that doesn't have an FPU, it will likely be less efficient than just using floating point numbers. – Zac Howland Feb 17 '11 at 14:20
  • @ZacHowland not actually. On systems with FPU, simple integer arithmetics may still be faster than floating-point ones. Moreover one might need more precision rather than wider range. For example when 24 bits of single precision significand is a little less than enough but operations on double is longer than 32-bit int – phuclv Mar 11 '15 at 06:41

3 Answers3

3

As Jan says, use a single integer. Since it looks like you're specifying 16 bit integer and fractional parts, you could do this with a plain 32 bit integer.

The "trick" is to realise what happens to the "format" of the number when you do operations on it. Your format would be described as 16.16. When you add or subtract, the format stays the same. When you multiply, you get 32.32 -- So you need a 64 bit temporary value for the result. Then you do a >>16 shift to get down to 48.16 format, then take the bottom 32 bits to get your answer in 16.16.

I'm a little rusty on the division -- In DSP, where I learned this stuff, we avoided (expensive) division wherever possible!

Martin Stone
  • 12,682
  • 2
  • 39
  • 53
  • That sounds about right actually! Okay, using only one 32 bit integer then, not sure why I didn't go with that in the first place. And ... aha, you made the multiplication part look so effortless. I was thinking it would be a whole ordeal. I guess it's just a matter of finding the division portion for me now. Thank you! – Anne Quinn Feb 17 '11 at 13:58
  • @Clairvoire: The [article that Zac linked to](http://en.wikipedia.org/wiki/Fixed-point_arithmetic#Operations) gives the details for the division operation in a more general case, where the multiplication factor isn't 2^16 for both operands. That should give you enough to go on. – Martin Stone Feb 17 '11 at 16:07
1

I'd recommend using one integer value instead of separate whole and fractional part. Than addition and subtraction are the integeral counterparts directly and you can simply use 64-bit support, which all common compilers have these days:

  • Multiplication:

    operator*(const Fixed &other) const {
    return Fixed((int64_t)value * (int64_t)other.value);
}

  • Division:

    operator/(const Fixed &other) const {
    return Fixed(((int64_t)value << 16) / (int64_t)other.value);
}

64-bit integers are

  • On gcc, stdint.h (or cstdint, which places them in std:: namespace) should be available, so you can use the types I mentioned above. Otherwise it's long long on 32-bit targets and long on 64-bit targets.
  • On Windows, it's always long long or __int64.
Jan Hudec
  • 73,652
  • 13
  • 125
  • 172
  • 3
    This messes up the fixed point, you're going to need a bit shift following multiplication to get it back. – Ben Voigt Feb 17 '11 at 13:24
  • I should of specified, but I would want division to behave similar to how normal division works, without discarding the remainder portion, but that does give me an idea! – Anne Quinn Feb 17 '11 at 13:56
0

To get things up and running, first implement the (unary) inverse(x) = 1/x, and then implement a/b as a*inverse(b). You'll probably want to represent the intermediates as a 32.32 format.

MSalters
  • 173,980
  • 10
  • 155
  • 350
  • Never thought of that operation... Trying to wrap my head around how one would do that, but it would need done either way to make division! Thanks for the heads up! – Anne Quinn Feb 17 '11 at 15:13
  • Easiest solution is via `(1<<31)/(x*65536) << 1`. The first part is a constant anyway, and `(x*65536)` is just a reinterpretation of your 16.16 fp number as an 32 bits integer. The result will be a 32 bits integer `(1/x) * 65536`, which you can trivially reintrepret as the 16.16 inverse. Downside: the `<<31` / `<<1` means the LSB is lost. – MSalters Feb 17 '11 at 16:11