As we know, the arithmetic operations in programming
languages are limited by precision accuracy. That means you will not get an
exact answer but a rounded-close answer. For example, if you have 10 divided by
3 then you will get answer like 3.33333339555496.
languages are limited by precision accuracy. That means you will not get an
exact answer but a rounded-close answer. For example, if you have 10 divided by
3 then you will get answer like 3.33333339555496.
The following program will describe a quick and efficient method to
compute the division with high precisions. Actually the space requirement is
just O(1) regardless the number of fraction places you want. The algorithm
complexity is just O(n) which is fast enough to retrieve a few thousand places
within seconds. However, the following C++ program will just print each
fraction result to screen without storing it. If you want to further manipulate
the result, then you need an array to store it.
compute the division with high precisions. Actually the space requirement is
just O(1) regardless the number of fraction places you want. The algorithm
complexity is just O(n) which is fast enough to retrieve a few thousand places
within seconds. However, the following C++ program will just print each
fraction result to screen without storing it. If you want to further manipulate
the result, then you need an array to store it.
The algorithm will simulate the human (as we are taught in
the primary school) doing division computation. Get the remainder and subtract
it from the dividend, multiply by ten and go to the next iteration. Of course,
if we can get the whole result, we may not need to continue until the
pre-defined number of iterations are reached.
the primary school) doing division computation. Get the remainder and subtract
it from the dividend, multiply by ten and go to the next iteration. Of course,
if we can get the whole result, we may not need to continue until the
pre-defined number of iterations are reached.
#include <iostream>
using namespace std;
void PrintDiv(int a, int b, int n)
{
cout
<< a << ” / ” << b << ” = ” ;
<< a << ” / ” << b << ” = ” ;
if (b
== 0)
== 0)
{
//
if divide by 0
if divide by 0
cout
<< (a >= 0 ? “+INF”: “-INF”) << endl;
<< (a >= 0 ? “+INF”: “-INF”) << endl;
return;
}
if (a
== 0)
== 0)
{
cout
<< 0 << endl;
<< 0 << endl;
return;
}
if (n
<= 0)
<= 0)
{
//
just the integer part
just the integer part
cout
<< a / b << endl;
<< a / b << endl;
return;
}
if (((a
> 0) && (b < 0)) || ((a < 0) && (b > 0)))
> 0) && (b < 0)) || ((a < 0) && (b > 0)))
{
//
check the sign
check the sign
cout
<< “-“;
<< “-“;
a
= a > 0 ? a: -a;
= a > 0 ? a: -a;
b
= b > 0 ? b: -b;
= b > 0 ? b: -b;
}
int c =
a / b;
a / b;
for
(int i = 0; i < n; i ++) // iterated
(int i = 0; i < n; i ++) // iterated
{
cout
<< c;
<< c;
a
-= b * c;
-= b * c;
if
(a == 0) break; // full division no need to continue
(a == 0) break; // full division no need to continue
a
*= 10;
*= 10;
c
= a / b;
= a / b;
if
(i == 0) cout << “.”;
(i == 0) cout << “.”;
}
cout
<< endl;
<< endl;
}
int main()
{
cout
<< “Please give me three integers: ” << endl;
<< “Please give me three integers: ” << endl;
int a,
b, n;
b, n;
do {
cin
>> a >> b >> n;
>> a >> b >> n;
PrintDiv(a,
b, n);
b, n);
} while
(n >= 0);
(n >= 0);
cin
>> n;
>> n;
}
The C++ program asks you to input three integers and it will
take it from there. The output of the close rational number of PI is 355/113
and the program prints the correct answer.
take it from there. The output of the close rational number of PI is 355/113
and the program prints the correct answer.
Also Read: C++ Tic-Tac-Toe Game
Also Read: Menu Driven C Program to Perform Insert, Display and Delete Operations on a Singly Linked List (SLL)
Be noted that the C++ program also checks for some corner
test cases such as divide by zero and it will take care of the sign as well.
Below illustrates some test cases.
test cases such as divide by zero and it will take care of the sign as well.
Below illustrates some test cases.
Please be noted that when we check the signs of the input
integers (a and b), we can do it two ways. First is to check if a*b is
negative. Or we can just check if it falls into two cases
(a<0)&&(b>0) or (a>0)&&(b<0). The second in my
opinion is better because the first one may actually overflow and give
incorrect judgements if given numbers are too large.
integers (a and b), we can do it two ways. First is to check if a*b is
negative. Or we can just check if it falls into two cases
(a<0)&&(b>0) or (a>0)&&(b<0). The second in my
opinion is better because the first one may actually overflow and give
incorrect judgements if given numbers are too large.
Author’s bio:
Zhihua Lai is now a Marie Curie Experienced Researcher at
University of Sheffield. At his spare time, he writes blogs and programs just
for fun. He is also an ACMer where he is keen on fast and efficient algorithms. His blog can be found at http://codingforspeed.com/
University of Sheffield. At his spare time, he writes blogs and programs just
for fun. He is also an ACMer where he is keen on fast and efficient algorithms. His blog can be found at http://codingforspeed.com/
