3

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.

Kotaka Danski
  • 451
  • 1
  • 4
  • 14
  • Just because a computer can't store infinite precision doesn't mean that it can't get mathematically correct results with finite precision (but of course it's not guaranteed to). Plus you seem to be assuming that floating point numbers are stored as decimals, which they aren't (in general). You're going to have to check the divisors. It's the natural solution to the problem. – john Oct 30 '20 at 11:44
  • The multiplication ` n * (1/n)` is not performed with infinite precision. The simplest way is to check if there are other divisors than 2 and 5, as you suggested – Damien Oct 30 '20 at 11:48
  • It's so close to a duplicate but not exact. However if you read this you will lean a lot you need to know - https://stackoverflow.com/questions/588004/is-floating-point-math-broken Basically you can't answer this question by using floating point maths. – Richard Critten Oct 30 '20 at 11:49
  • @Yunnosch I understood that OP assumes a finite precision for the division `1/n`, and then something perfect for the multiplication. This is why I insisted on the multiplication. I was maybe not clear, or wrong in OP's interpretation. – Damien Oct 30 '20 at 11:56
  • @RichardCritten Thank you for sharing this article. – Kotaka Danski Oct 30 '20 at 11:56
  • @Yunnosch Yes, excactly. I assumed that the division won't be accurrate and that the multiplication would be accurate and therefore I didn't expect the cancellation of errors . – Kotaka Danski Oct 30 '20 at 11:58
  • Checking if `n`s divisors are `1`, `2`, and `5` is the better approach. If `n > 1` and can be expressed in the form `2^a * 5^b` where `a` and `b` are non-negative integral values (and using `^` here to represent "to the power of", not bitwise operation) then the number of decimal places is finite. Otherwise, the number of decimal digits is infinite (typically recurring). Doing things using floating point division, as you are, *inherently* loses precision. – Peter Oct 30 '20 at 12:02

2 Answers2

2

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.

Yunnosch
  • 26,130
  • 9
  • 42
  • 54
  • You understood my question correctly, Thank you for your answer. I won't be wasting my time on trying to fix this code. :-) – Kotaka Danski Oct 30 '20 at 12:01
1

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.

Stef
  • 13,242
  • 2
  • 17
  • 28