mulitplication in embedded(integer) system

[joegao1]

can anyone help here?

I am working on an embedded system with a C-like programming language,
therefore floating point operation is not allowed (because it is time consuming),
and floating point variable has to be represented by integer variable, with F stands for the length of bits representing the fractional part.

e.g. value 4.5 with F=5 is represent by 10010000 (where the higher 3 bits representing integer value, and the lower 5 bits representing fractional value)

now I need to write a function for the multiplication operation of two variables A and B (note they can have different F values: Fa and Fb ), and the result C with the F value Fc.

my code is given as followed and it works. But the problem is that this code still takes too long time to run on an embedded system (multiplication operations dominate the activitives ). Can any one provide a better algorithm ?

------------------------------------------

int16_t multiInt(int16_t a, uint8_t Fa, int16_t b, uint8_t Fb, uint8_t Fr)
{
// assume the maximum amount of available digits for integer variable is 16
//
// Fa --- lenght of fractional bit of value "a"
// Fb --- lenght of fractional bit of value "b"
// Fr --- lenght of fractional bit of result/output "res"

uint8_t isNeg=0, stepB;
int16_t res; // result/output
uint8_t Ha, La, Hb, Lb; // higher (and lower) significant bits for a and b
uint16_t HaHb, LaLb,LH; // temporal value
uint16_t Hr, Lr; // higher (and lower) significant bits for the result/output

if (a<0)
{
a=-a;
isNeg ++;
}
if (b<0)
{
b=-b;
isNeg ++;
}
stepB=Fa+Fb - Fr


Ha = a>>8;
La = a-(Ha<<8);
Hb = b>>8;
Lb = b-(Hb<<8);

HaHb = Ha*Hb;
LH = La*Hb + Lb*Ha;
LaLb = La*Lb;

Hr = HaHb + (LH>>8);
Lr = LaLb + (LH<<8);

if ((Hr>>stepB)>0) //if overflow
res = 0x7fff;
else
res = (Hr<<(16-stepB)) + (Lr>>stepB)

return res*(1-2*(isNeg%2));
}

[newb16]

How long is 'long" ( machine cycles) ? Does the system have hardware multiplication? (16*16->16, or 8*8->16 that is mostly like can't be utilized by compiler )? Did you examine generated assembly output for this code? What is uint16>>8 ( <<8) operation like - does it fetch higher byte or really shift 8 times by 1 bit?

And this one
if ((Hr>>stepB)>0)

is better to be substituted with something like
if((Hr & mask) != 0 )
where mask is from array of 16 pre-calculated values of 'all N highest bits set to 1' for different N.

Regarding 2*(isNeg%2)) --
Check that compiler is smart enough to optimize 2*x and x%2 to shift and
x&1 , if not, rewrite.

If MCU has 16*16->32 HW multiply, it may be better to rewrite it utilizing this feature.

[joegao1]

Many thanks for the answer !!!

How long is 'long" ( machine cycles) ? Does the system have hardware multiplication? (16*16->16, or 8*8->16 that is mostly like can't be utilized by compiler )?

"long" is my objective meaning, what I am looking for is a fast (as fast as possible)
algorithm/code to do the multiplication. The system i am working on is the TelosB sensor mote, which so far as i know only has very limited computation power and ability. it can only handle up to 16-bit operations.

Did you examine generated assembly output for this code? What is uint16>>8 ( <<8) operation like - does it fetch higher byte or really shift 8 times by 1 bit?

"uint16_t" stands for unsign integer with 16 bits;

>> and << basically do the "shift" job:

by "uint16>>8 " , it results in a 16-bit integer with the lower 8 bits equal to the previous higher 8 bits, and the new higher 8 bits are filled with zero.
by "uint16<<8 " , it results in a 16-bit integer with the higher 8 bits equal to the previous lower 8 bits, and the new lower 8 bits are filled with zero.

And this one
if ((Hr>>stepB)>0)
is better to be substituted with something like
if((Hr & mask) != 0 )
where mask is from array of 16 pre-calculated values of 'all N highest bits set to 1' for different N.

great !!! I will try this out. (i am new to this integer-operation programming)

Regarding 2*(isNeg%2)) --
Check that compiler is smart enough to optimize 2*x and x%2 to shift and
x&1 , if not, rewrite.

I will check it. thanks ...

If MCU has 16*16->32 HW multiply, it may be better to rewrite it utilizing this feature.

unfortunately, the processor only support 16-bit operations .

[donbock]

I am working on an embedded system with a C-like programming language, therefore floating point operation is not allowed (because it is time consuming), and floating point variable has to be represented by integer variable, with F stands for the length of bits representing the fractional part.

e.g. value 4.5 with F=5 is represent by 10010000 (where the higher 3 bits representing integer value, and the lower 5 bits representing fractional value)

now I need to write a function for the multiplication operation of two variables A and B (note they can have different F values: Fa and Fb ), and the result C with the F value Fc.

What you're doing is called "fixed-point" arithmetic. You might want to google "fixed-point" or "fixed-point multiplication" to get an overview of the subject. Your example is a little more complicated because the fixed point isn't really fixed (that is, F varies).

Another approach you might look into [if you were willing to consider a complete rewrite] is "rational" arithmetic. In this case, all numbers are expressed by two values, a numerator and a denominator. Again, you google the term for an overview. You could model your fixed-point arithmetic as rational arithmetic, where the denominator is 2^F.

I don't know that any of this will help; I'm just making some suggestions for where you can look for background information.

Cheers,
donbock

[newb16]

"uint16_t" stands for unsign integer with 16 bits;

>> and << basically do the "shift" job:

I am... uhm... aware. What I was asking is whether MCU in question (+compiler used ) generate fast code for such shift operation - is there constant-time operation for shift-by-8-bits, or direct move from higher byte to lower byte? Or machine code generated is dumb and shifts it 8 times by 1 bit?

if ((Hr>>stepB)>0)
is better to be substituted with something like ...

Edit - this is valid if there is no constant-time multibit shift operation.

unfortunately, the processor only support 16-bit operations .

That's strange. Only 16*16 -> 16 multiply?

[donbock]

Did you examine generated assembly output for this code?

For example, the -S command line switch tells gcc to stop after compilation and leave the assembly source file present so you can examine it. Whatever compiler you're using, there should be something equivalent.
Cheers,
donbock

[joegao1]

Thank you all for the tips given above.

I have checked the specification of the hardware of the embedded system.
The MCU does be able to handle multiplication between two 16-bit variables, even though the processor is a 16bit processor.

Now it is much faster than before by utilizing this feature.
And I am satisfied with the result, so is my boss !!!

Thank you all for the inspirations, this is a very nice forum .