Fixed-point multiply.

Discussion in 'C Programming' started by Pallav, Jun 24, 2004.

  1. Pallav

    Pallav Guest

    I'm trying to convert some source code containing floating point into
    fixed-point arithmetic.

    I am having some trouble understanding fixed point signed multiply. I
    have a 18.14 base integer with 18 bits integer and 14 bits for
    fraction. Now what I understand is that if I multiply two 18.14
    values, I will get

    18.14 * 18.14 = 36.28 for a result

    But need to fit in 32-bits. So in the fraction part we must drop the
    lower 14 bits and then in the integer part we drop the upper 18 bits.
    Correct?

    If so, then here is my pseudocode.

    typedef long fp14;

    fp14 FPMUL(fp14 a1, fp14 a2)
    {
    fp14 frac = 0, result = 0;
    char sign = 0;

    if (a1 < 0) { sign = 1; a1 = -a1; }
    if (a1 < 0) { sign ^= 1; a2 = -a2; }

    frac = (a1 * a2) >> 14;
    // Is this correct? Or do I need to say ((a1 & 0x3FF) * (a2 & 0x3FF)
    >> 14)


    result = (a1 >> 14) * (a2 >> 18); // 18 bits * 14 bits = 32 bits
    result = result + (a1 >> 14) * ((a2 >> 14) & 0xF); // 18 bits * 4
    lower bits of a2

    result = (result << 18) | (frac & 0x3FF); // concatante lower 18
    bits of result with lower 14 bits of frac to get 32 bit result

    return result * -sign;
    }

    Does this code look correct or am I missing something? Also is there a
    more efficient way to implement this? Any help is appreciated.

    Thanks
    Pallav, Jun 24, 2004
    #1
    1. Advertising

  2. Pallav

    SM Ryan Guest

    (Pallav) wrote:
    # I'm trying to convert some source code containing floating point into
    # fixed-point arithmetic.
    #
    # I am having some trouble understanding fixed point signed multiply. I
    # have a 18.14 base integer with 18 bits integer and 14 bits for
    # fraction. Now what I understand is that if I multiply two 18.14
    # values, I will get
    #
    # 18.14 * 18.14 = 36.28 for a result
    #
    # But need to fit in 32-bits. So in the fraction part we must drop the
    # lower 14 bits and then in the integer part we drop the upper 18 bits.
    # Correct?

    Do you have 64-bit integers availables? If so

    int64 product = ((int64)a) * ((int64)b);

    (Some implementations provide a 32bit*32bit -> 64bit, so you don't have
    to widen the factors to get a wide product. Otherwise you have to widen
    first so you don't get a truncated 32bit product.)

    int32 scaledproduct = product>>14;

    --
    SM Ryan http://www.rawbw.com/~wyrmwif/
    JUSTICE!
    Justice is dead.
    SM Ryan, Jun 25, 2004
    #2
    1. Advertising

  3. "Pallav" <> wrote in message
    news:...
    > I'm trying to convert some source code containing floating point into
    > fixed-point arithmetic.
    >
    > I am having some trouble understanding fixed point signed multiply. I
    > have a 18.14 base integer with 18 bits integer and 14 bits for
    > fraction. Now what I understand is that if I multiply two 18.14
    > values, I will get
    >
    > 18.14 * 18.14 = 36.28 for a result
    >
    > But need to fit in 32-bits. So in the fraction part we must drop the
    > lower 14 bits and then in the integer part we drop the upper 18 bits.
    > Correct?


    It's your call how you deal with precision and overflow.

    > If so, then here is my pseudocode.
    >
    > typedef long fp14;


    Better to use an unsigned type as it's behaviour more like the two's complement that you
    might wish to rely on.

    > fp14 FPMUL(fp14 a1, fp14 a2)
    > {
    > fp14 frac = 0, result = 0;
    > char sign = 0;
    >
    > if (a1 < 0) { sign = 1; a1 = -a1; }
    > if (a1 < 0) { sign ^= 1; a2 = -a2; }

    ^
    ITYM (a2 < 0)

    >
    > frac = (a1 * a2) >> 14;


    This will work (to a point) if fp14 happens to be 64 bits. If you have access to C99's
    long long you could try...

    frac = ( ((unsigned long long) a1)
    * ((unsigned long long) a1)) >> 14;

    > // Is this correct? Or do I need to say ((a1 & 0x3FF) * (a2 & 0x3FF)
    > >> 14)


    Your question is really an algorithm one, not a C one. There are methods for multiplying
    large integer numbers and keeping full precision, but this isn't the group to discus them.

    > ...Also is there a more efficient way to implement this?


    If you want practical efficiency, then ISO C and comp.lang.c may not be what you're
    looking for. For starters you would have to define the nature of what you percieve as
    efficient, because ISO C doesn't.

    --
    Peter
    Peter Nilsson, Jun 26, 2004
    #3
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. H aka N
    Replies:
    15
    Views:
    15,617
    Ben Jones
    Mar 2, 2006
  2. Motaz Saad
    Replies:
    7
    Views:
    6,461
  3. johnp
    Replies:
    4
    Views:
    3,655
    Toby Inkster
    May 23, 2005
  4. Replies:
    4
    Views:
    1,274
    Default User
    Feb 22, 2006
  5. Saraswati lakki
    Replies:
    0
    Views:
    1,290
    Saraswati lakki
    Jan 6, 2012
Loading...

Share This Page