Fixed-point multiply.

[Pallav]

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)
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

 

[SM Ryan]

(e-mail address removed) (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;

 

[Peter Nilsson]

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)

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.