Check if 1/n has infinite number of digits after decimal point

user_12645782 0
Viewed 660

If a user enters a number "n" (integer) not equal to 0, my program should check if the the fraction 1/n has infinite or finite number of digits after the decimal sign. For example: for n=2 we have 1/2=0.5, therefore we have 1 digit after the decimal point. My first solution to this problem was this:

int n=1;
cin>>n;
if((1.0/n)*n==1)
{
    cout<<"fixed number of digits after decimal point";
}
else cout<<"infinite number of digits after decimal point";

Since the computer can't store infinite numbers like 1/3, I expected that (1/3)*3 wouldn't be equal to 1. The first time I ran the program, the result was what I expected, but when I ran the program today, for n=3 I got the output (1/3)*3=1. I was surprised by this result and tried

double fraction = 1.0/n;
cout<< fraction*n;

which also returned 1. Why is the behaviour different and can I make my algorithm work? If I can't make it to work, I will have to check if n's divisors are only 1, 2 and 5, which, I think, would be harder to program and compute. My IDE is Visual Studio, therefore my C++ compiler is VC.

arithmetic-expressions math c++
2 Answers

Your code tries to make use of the fact that 1.0/n is not done with perfect precision, which is true. Multiplying the result by n theoretically should get you something not equal to 1, true.
Sadly the multiplication with n in your code is ALSO not done with perfect precision.
The fact which trips your concept up is that the two imperfections can cancel each other out and you get a seemingly perfect 1 in the end.

So, yes. Go with the divisor check.

user_77334180

Binary vs. decimal

Your assignment asks you whether the fraction 1/n can be represented with a finite number of digits in decimal representation. Floating-point numbers in python are represented using binary, which has some similarities and some differences with decimal:

  • if a rational number can be represented in binary with a finite number of bits, then it can also be represented in decimal with a finite number of digits;
  • some numbers can be represented in decimal with a finite number of digits, but require an infinite number of bits in decimal.

This is because 10 = 2 * 5; for any integer p, p / 2**k == (p * 5**k) / 10**k. So 1/2==5/10 and 1/4 == 25/100 and 1/8 == 125/1000 can be represented with finitely many digits or bits. But 1/5 can be represented with finitely many digits in decimal, yet requires infinitely many bits in binary.

Floating-point arithmetic and test for equality

See also: Is floating-point math broken? and What every programmer should know about floating-point arithmetic (pdf paper).

The computation (1.0 / n) * n results in an approximation; there is mostly no way to know whether checking for equality with 1.0 will return true or false. In language C, which uses the same floating-point arithmetic as python, compilers will raise a warning if you try to test for equality of two floating-point numbers (this warning can be abled or disabled with option -Wfloat-equal).

A different logic for your algorithm

You can't rely on floating-point arithmetic to decide your problem. But it's not needed. A number can be represented with finitely many digits if and only if it can be written under the form p / 10**k with p and k integers. So your program should examine n to find out whether there exists j and k such that 1 / n == 1 / (2**j * 5**k), without using floating-point arithmetic.

user_30807230
Related