Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Multiple/Division dilemma in equation

Tags:

c++

c

I need to compute this equation in C/C++:

x=(a*b-1)/c;

with a,b,c,x of type __int64 (a,b,c,x<10^13). In all cases, a,b,c is select to make x fit in __int64.
However, a*b is very big that cause overflow and x is wrong.
I try to seperate a*b by typecasting:

x=(__int64)(((double)a/c)*(double)b - 1.0/c);  

This way, a/c is computed first and overflow error not occur.
However, the problem is ((double)a/c)*(double)b sometimes have great value (about billions) and precision is reduced, so 1.0/c (very small) don't take any effect and cause an error within +-1.

For example: (__int64)(((double)a/c)*(double)b=123456789.01 is more likely to become 123456789.0 and 1.0/c=0.02. In this case, there is an error of +1.

Is there any way to compute x precise without external library such as Boost or Bignum? Even with error +-1 can screw up my code.
Thanks in advance.
By the way, I use Visual Studio 10.

like image 286
user1704182 Avatar asked Oct 20 '12 02:10

user1704182


People also ask

What is a division equation with multiple variables?

Division equations with two or more variables have the usual division operator and multiple unknown variables. Learn how to solve these problems with the right number of equations using detailed examples.

What is an example of multiplication and Division in math?

Division (÷) Multiplication and division, both are inverse operations of each other. If we say, a multiplied by b is equal to c, then c divided by b results in a. Mathematically, it can be represented as: a × b = c. c ÷ b = a. For example, 4 x 5 = 20. 20 ÷ 5 = 4. Let us learn more about multiplication and division along with rules and examples.

What are the division and multiplication properties of equality of equations?

This characteristic of equations is generalized in the Multiplication Property of Equality. Let’s review the Division and Multiplication Properties of Equality as we prepare to use them to solve single-step equations. For all real numbers a,b,c a, b, c, and c ≠0 c ≠ 0, if a =b a = b, then a c = b c a c = b c.

What are division problems with two or more variables?

Division problems with two or more variables are math problems that include the division operator and that have more than one unknown value. To solve these problems requires you to have one equation for each variable. You then use the most appropriate solution method to solve your equations to find your unknown values, your variables.


1 Answers

You could implement the long arithmetic by hand, work with 32-bit blocks:

Long multiplication:

  (ax + b) * (cx + d)
= ac x^2 + (ad+bc) x + bd

  [ab]*[cd]=[efg]:

   //long long e,f,g
   g = (long long)b*d;
   f = (long long)a*d+b*c;
   e = (long long)a*c;
   //perform carry
   f += g>>32; g &= 0xFFFFFFFF
   e += f>>32; f &= 0xFFFFFFFF

School division, assuming unsigned arithmetic:

   [efg]/[hi]=[jkl]:

    [jk] = [ef]/[hi];
    r = [ef]-j*[hi];
    l = [rg]/[hi];
    if j > 0, result doesn't fit
    x = [kl];

If a and b are signed, fix the sign first and compute with absolute values, as suggestd by @Serge: if a or b is zero, x=(-1)/c otherwise, sign(x)=sign(a)*sign(b)*sign(c)

like image 123
John Dvorak Avatar answered Sep 20 '22 16:09

John Dvorak