fractions

This is a discussion on fractions within the C Programming forums, part of the General Programming Boards category; i decided to write a little program which took a numerator and a denominator and gave the decimal. I then ...

1. fractions

i decided to write a little program which took a numerator and a denominator and gave the decimal. I then decided that showing repeating decimals was important so i decided to use the format 1/3 = .(3). My only problem is i don't know a way to tell if the decimal is repeating. Here is what i have so far:

<code>

#include <stdio.h>

float n, d;
float decimal;

int main()
{

printf("N will be the numerator and D will be the denominator");
scanf("%f %f", &n, &d);

decimal = n / d;

printf("The fraction %f/%f = %f", n, d, decimal);
system("Pause");
return 0;

}

</code>

2. 1) VBulletin tags begin and end with [] not <>
2) Why are you using global variables?
3) On paper how would you determine if the number was rational or not? Figure that out and then translate it into code.

3. I don't think there is a simple way to find out if a number is periodic. But then again, I didn't study mathematics. This might be a start (maybe not the best though):

Using 1/3 as an example, devide 1 by 3 (in integers, always rounded down [floor]). The result is 0. So you know you have a "0 point something" number.
Now get the mod, 1%3 which is 1. Multiplying this with 3 again gives you your second digit: 3. To get the next one you would have to devide the mods result by 3 again. You know you already did this and that it left you with a mod of 1, so you know you're stuck in an endless loop. 0.33333333333333....

To find a pattern like 0.545854585458 would require you to keep track of multiple results though. After each run you compare your buffers first n/2 elements with the remaining ones. If they match, you found a sequence and can stop there.
Of course, you could just do the ugly thing and convert the float result into a string and search for a pattern as described above, but that limits you to FP precision. Which is bad.

I hope this helps somewhat.

(btw grats thantos for removing your post so quickly )

4. Originally Posted by joeshmoe1337
i decided to write a little program which took a numerator and a denominator and gave the decimal. I then decided that showing repeating decimals was important so i decided to use the format 1/3 = .(3). My only problem is i don't know a way to tell if the decimal is repeating. Here is what i have so far:

Code:
```#include <stdio.h>

float n, d;
float decimal;

int main()
{

printf("N will be the numerator and D will be the denominator");
scanf("%f %f", &n, &d);

decimal = n / d;

printf("The fraction %f/%f = %f", n, d, decimal);
system("Pause");
return 0;

}```
(note: I changed your <code> tags)

I see this as two problems:

1. extract the decimal digits of a fraction

2. recognize a repeating pattern.

Now the first part is "easy" using C-type built-in data types and arithmetic. Here's an example inserted into your program:

Code:
```#include <stdio.h>

int main()
{
double n, d;
double decimal;
int digit;
int i;

printf("N will be the numerator and D will be the denominator");
scanf("%lf %lf", &n, &d);

decimal = n / d;

printf("The fraction %lf/%lf = %.16lf\n", n, d, decimal);

printf("I will now extract the decimal digits from the floating point representation: \n");
for (i = 0; i < 16; i++) {
digit = (int)(decimal * 10);
decimal = decimal * 10.0 - digit;
printf("%d", digit);
}
printf("\n");

return 0;

}```
What are the limitations? Well, the binary representation of doubles in C (in my compilers, which use 32-bit doubles) has a precision of about 16 or 17 decimal digits. So you can only extract a maximum of 16 or 17 correct digits by this method.

Some fractions have much longer periods.

The fraction 1/17 has the following decimal representation:

0.058823529411764705882352941176470588235294117647 ...

You can't get enough digits from the printout of the machine representation to see the pattern (repeats every 16 digits, I think: count for yourself).

Now, for a certain subset of all possible fractions, the pattern may be obvious from the 16 decimal digits that we can depend on: The question is how to spot the pattern (and how to make sure it's really a pattern that is repeated infinitely, not just some local sequence that appears to be repeating, but is not a full period).

Have fun with it. I thinks it's an interesting challenging program exercise.

If you want to really get into it, look for some decimal arithmetic packages/libraries, and get back to us with your results.

I love this stuff.

Regards,

Dave

5. Originally Posted by Nyda
I don't think there is a simple way to find out if a number is periodic. But then again, I didn't study mathematics. This might be a start (maybe not the best though):

Using 1/3 as an example, devide 1 by 3 (in integers, always rounded down [floor]). The result is 0. So you know you have a "0 point something" number.
Now get the mod, 1%3 which is 1. Multiplying this with 3 again gives you your second digit: 3. To get the next one you would have to devide the mods result by 3 again. You know you already did this and that it left you with a mod of 1, so you know you're stuck in an endless loop. 0.33333333333333....

To find a pattern like 0.545854585458 would require you to keep track of multiple results though. After each run you compare your buffers first n/2 elements with the remaining ones. If they match, you found a sequence and can stop there.
Of course, you could just do the ugly thing and convert the float result into a string and search for a pattern as described above, but that limits you to FP precision. Which is bad.

I hope this helps somewhat.

(btw grats thantos for removing your post so quickly )

Gives the right answer for 1/3. How about 1/17? Does it work? Maybe I'm missing something ???

Regards,
Dave

6. I'm just guessing Dave but I think he's only looking for numbers that are periodic over one digit:
0.3333333333333
0.6666666666666
0.2222222222222
etc
maybe even ones like
0.2322222222222 but they really didn't specify

7. You could try to form a fraction from the decimal. Then simplify the fraction.

If you have .45445, you could form the fraction r = 45445/10000. To simplify the fraction you would calculate g = gcd(45445, 10000), from which you could simplify to r = (45445/g)/(10000/g) like so.

To calculate the gcd you would use Euclid's algorithm. You could then have some sort of criteria for when to express a fraction in decimal form and when not to. Nonperiodic numbers will always have the denominator 1, so you should be able to do this.

The problem though, is that you might have rounding errors 1/3 is typically .3333333 some number of 3's which are not fully expressed in the machine. You will get a fraction but it will not be the right fraction. But if the fraction is off a very simplified fraction by some very small epsilon, you could effectively add the epsilon to the fraction without changing the result by too much. For instance, suppose you're fraction is 10001/30000. Because this fraction is 1/30000 away from 1/3, you should be able to subtract 1/30000 without changing the result too much.

8. I made a mistake: not all non-repeating decimals will have a denominator of 1.

9. I think you could do this to find out if the fraction is repeating or not. Supposing a, b relatively prime, you can find out if a fraction q = a/b is repeating or not by seeing if it can be expressed a/b = n / 10^k for some integer n and k > 1. Hence a(5^k * 2^k)/b = n, and because b and a are relatively prime, b must divide 5^k*2^k.

10. given a fraction n/d you can effectively do long division like this:
Code:
```  value in before decimal = n/d (integer arithmetic)
remainder before decimal = n % d;
1st value after decimal = (10 * remainder before decimal) / d
1st remainder after decimal = (10 * remainder before decimal) % d
2nd value after decimal = (10 * 1st remainder after decimal) / d
2nd remainder after decimal = (10 * 1st remainder after decimal) % d
... and so on until either:
the remainder is 0 - no repeating necessary
or:
you repeat a previous remainder - decimal notation has a repetition```
The code to do this is actually not as complex as I at first thought
- its an interesting problem )

11. Originally Posted by DavT
given a fraction n/d you can effectively do long division like this:
Code:
```  value in before decimal = n/d (integer arithmetic)
remainder before decimal = n % d;
1st value after decimal = (10 * remainder before decimal) / d
1st remainder after decimal = (10 * remainder before decimal) % d
2nd value after decimal = (10 * 1st remainder after decimal) / d
2nd remainder after decimal = (10 * 1st remainder after decimal) % d
... and so on until either:
the remainder is 0 - no repeating necessary
or:
you repeat a previous remainder - decimal notation has a repetition```
The code to do this is actually not as complex as I at first thought
- its an interesting problem )
That's the ticket! Use custom decimal arithmetic routines for dividing decimal numbers with an arbitrarily large number of digits.

My thoughts were that if you put the digits as '0' and '1' into an ascii string, then you could use strstr() or some such thing to test for periodicity.

(Maybe a good exercise for you recursion geeks.)

After you have identified a candidate, then use some method like the one in the first post by okinrus to recreate the original fraction (assuming that common factors have been removed so that the numerator and denominator are relatively prime). You could do this arithmetic in decimal also, using a custom multiplication and subtraction routines.

My only problem is knowing how to stop (not how to stop the program, but how to stop thinking of ways to do it, given the good ideas presented by the good people here).

Regards,

Dave

12. Actually, wouldnt the number always be rational?

n and d are floating point, and so can each be expressed in the form p/q, p and q being integers.
so n/d=(p/q)/(r/s)=ps/qr
Since p, q, r and s are integers, ps and qr are integers, hence n/d must be rational.
Therefore, there will always be repeating digits.

13. Originally Posted by laserlight
Actually, wouldnt the number always be rational?

n and d are floating point, and so can each be expressed in the form p/q, p and q being integers.
so n/d=(p/q)/(r/s)=ps/qr
Since p, q, r and s are integers, ps and qr are integers, hence n/d must be rational.
Therefore, there will always be repeating digits.
Yes, if you consider, for example,

1/2 = 0.5000000000000...

Where 0 is the repeating digit.

(Some people say that in cases like this the decimal is terminated, since you don't usually write 000000... Then they say that all rational numbers can be represented either by a terminated decimal number or a decimal with repeating digiits.)

By the way, what if someone claimed that you could also say

1/2 = 0.4999999999999...

Is this valid?

Dave

14. Where 0 is the repeating digit.
Yep.

1/2 = 0.4999999999999...

Is this valid?
It might be, considering that 0.999... is equal to 1.
I never got a chance to study limits properly in school though, so I'm not sure how to construct a proof or otherwise.

15. Originally Posted by laserlight
Yep.

It might be, considering that 0.999... is equal to 1.
I never got a chance to study limits properly in school though, so I'm not sure how to construct a proof or otherwise.
This points out that computer arithmetic always stops somewhere (finite number of digits), whereas in math, lots of times we use "=" to indicate something about "converges to". This problem (repeating decimals) is in the category of things that can't be perfectly emulated with finite computer arithmetic. (But we may be able to draw valuable conclusions if we understand this.)

That is, the infinite series:

.4 + .09 + .009 + .0009 + ...

Converges to 0.5

Regards,

Dave

"When I use a word," Humpty Dumpty said, in rather a scornful tone, "it means just what I choose it to mean—neither more nor less."

---Lewis Carrol
"Through the Looking Glass"

Page 1 of 2 12 Last