1

I want to multiply two fixed-point numbers with different fractional length. Fixed point part and fractional one are stored separately:

123    . 4
fix    . frac
sint32 . sint32

I use two variables, one for the fixed part and one for the fractional one.

I tried to use the Karatsuba algorithm. But this one is working only with fixed length of fractional. The fractional part of the two numbers is varying. They could be the same, but there is any guarantee for this. Of course, the max possible value is (2^32) - 1.

What is the best way to multiply 123.4 with 56.789?

// a = 123.4
signed int a_fxd = 123;
signed int a_frx = 4;
// b = 56.789
signed int b_fxd = 56
signed int b_frc = 789;
Vili
  • 29
  • 8
  • Side remark: in your first code block you say uint32 but in the second one you use signed!? – Hagadol Oct 30 '19 at 09:31
  • @Hagadol I have corrected. – Vili Oct 30 '19 at 09:36
  • 2
    How do you represent 123.04? – kakkoko Oct 30 '19 at 09:39
  • @kakkoko 1 min ago signed int a_fxd = 123; signed int a_frx = 4; – Vili Oct 30 '19 at 09:41
  • Possible duplicate: https://stackoverflow.com/questions/14008330/how-do-you-multiply-two-fixed-point-numbers – Martin Wickman Oct 30 '19 at 09:56
  • 1
    But a_fxd = 123; a_frx = 4 can can also represent 123.4, 123.004, 123.0004, ... – dash-o Oct 30 '19 at 09:58
  • @dash-o Input data length is 16 bit. I shall multiply two 16 bit numbers. In worst case i need 32 bit for the result. Since I shall also multiply with some sin(x)value, I have also fractional part. So, i shall separate the fixed part and fractional part into two 32 bit variable. – Vili Oct 30 '19 at 11:53

1 Answers1

2

You need to decide what the actual scaling factor for your fractional part is. For your particular example, it looks like an appropriate factor might be 1/1000, or 0.001. What this means is that 56.789 is represented as 56 + 789 × 0.001. But it means that 123.4 will be represented as 12 + 400 × 0.001. That is, you had a mistake in your question: a_frx will be 400, not 4.

I don't know Karatsuba's algorithm, and I suspect it's not really applicable to this problem anyway. I only know what I earned in elementary school.

Let's represent the scaling factor by sc. So our multiplication is actually

( a_fxd + a_frx * sc ) * ( b_fxd + b_frx * sc )

Multiplying this out, we get

a_fxd * b_fxd + a_fxd * b_frx * sc + a_frx * b_fxd * sc + a_frx * b_frx * sc * sc

Collecting terms, we have

a_fxd * b_fxd + (a_fxd * b_frx + a_frx * b_fxd + a_frx * b_frx * sc) * sc

So if we represent the product as p_fxd and p_frx, it looks like we'll have

p_fxd = a_fxd * b_fxd
p_frx = a_fxd * b_frx + a_frx * b_fxd + a_frx * b_frx * sc

Let's plug in the actual values:

p_fxd = 123 * 56 = 6888
p_frx = 123 * 789 + 400 * 56 + 400 * 789 * 0.001 = 119762.600

But there's an additional wrinkle, because p_frx is really supposed to be an integer in the range 0..999. So we need to discard the .600, and carry the 119. So our final result is

p_fxd = 6888 + 119 = 7007
p_frx = 762

And this corresponds to the correct result, 123.4 × 56.789 = 7007.762.

...Well, actually, the correct correct result is 7007.7626, or rounded to three digits, 7007.763. So strictly speaking we shouldn't have thrown away that .600 we ended up with in p_frx, we should have rounded.

There may also be some extra wrinkles to take care of when we consider the possibility of negative numbers.

Finally, there's the choice of scaling factor. In practice, the 0.001 I've used here isn't really a realistic value. For a general-purpose algorithm you'd probably use something more like 1/10000, or 1/1000000000, or 1/32768, or 1/65536, or something like that. (Using powers of two makes for larger ranges and typically more efficient calculations, but less-obvious fractional parts and less-efficient conversions to and from decimal representations. For example, if you used a scaling factor of 1/32768, a_frx would be 13107, and b_frx would be 25853 or 25854.)

Steve Summit
  • 45,437
  • 7
  • 70
  • 103