Fastest/most efficient way to add two fractions

[lightfighter]

Hello,

I have to write a function

struct rNumber add(rNumber a ,rNumber b);

which adds two rational numbers in following representation :
rNumber := s*(n/d)* 2^e

struct rNumber{
 _byte_t s; // sign (do not consider for this question)
 uint n; //numerator
 uint d;// denominator
 short e;//exponent
}

If the exponents of both numbers are not equal, then they have to be made equal in order to add them. This can be made in 4 ways : increase or decrease the n or d of both numbers.

But if we decrease the denominator of a number (a.d =1) by shifting it for example 1 bit to the right, we get 0 which leads to INFINITY for the fraction. In another case decreasing the numerator would lead the n to be 0 which meanse the whole fraction is then 0.


According to this, in worst case, all 4 cases has to be checked for the right result.

So far the UNDERFLOW of n or d is considered. If we try to increase the value of n or d, then OVERFLOW may also occur.

The very first, intuitive solution would be iteratively increase/decrease one of the terms and to check if the change leads to ZERO or INFINITY.

Is there any faster or more efficient way ?

[weaknessforcats]

You are definitely going the hard way. Each struct has a numerator denominator and exponent.

So the first thing to do is write a function that converts the struct into an int. Then in your add function you just call the convert function for each struct which will give you two int values. So you add the structs by adding the ints.

Finally, you write a function that converts an int back to a struct and you call that function to get the struct you need to return from the add function.

This is the same process you use in adding and subtracting dates.

[donbock]

I gather rNumber is 4-tuple (s,n,d,e) that represents the real number s*(n/d)*2^e; where s is +1 or -1, and where n and d are always nonnegative.

Add two rNumbers together:
s1*(n1/d1)*2^e1 + s2*(n2/d2)*2^e2
  = (s1*n1*2^e1)/d1 + (s2*n2*2^e2)/d2
  = (s1*n1*d2*2^e1 + s2*n2*d1*2^e2)/(d1*d2)

As you mentioned, care is needed to avoid arithmetic overflow.

Finally, you have to convert the real number result into a new rNumber:
s3*(n3/d3)*2^e3.

[lightfighter]

@weaknessforcat s

thank you for your answer!
Your solution ist very smart.

But I forgot to mention about the aim of desired function or defined it not completely.

In fact I must write a function collection which shall substitute the floating point operations. These functions should be used in tiny devices which are either not capable of operating with floating numbers or need to much processor time to calculate. For this reason these new functions shall run faster so that processor time respectively energy can be saved.

On the other hand they should run on different platforms so that the size of available variable type can be restricted to 8bits/1byte.
To convert the struct into an integer could exceed (because of multiplication by 2^e) this limit easily.

[lightfighter]

@donbock

thank you for your answer.

I made the definition of the problem more clear in my previous reply to weaknessforcats .

Also your solution leads to exceeding of variable size. And if I did not misunderstand my supervisor, intermediate floating point results must be avoided. The perfect solution would be staying in the integer domain while calculating.

[donbock]

Do you truly need the flexibility of variable denominator and/or variable exponent? Consider fixed-point arithmetic or Q number format to significantly simplify the software.

@lightfighter -- I did not mean to suggest that you should implement the intermediate floating point calculations. I meant for you to use them with pencil and paper in order to derive the necessary formulas.