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. #1
    Registered User
    Join Date
    Aug 2004
    Posts
    5

    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");
    printf("\nPlease enter N D: ");
    scanf("%f %f", &n, &d);

    decimal = n / d;

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

    }

    </code>

  2. #2
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    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. #3
    not-a-geek
    Join Date
    Apr 2004
    Posts
    210
    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 )
    Last edited by Nyda; 09-07-2004 at 05:13 PM.

  4. #4
    Registered User
    Join Date
    Mar 2004
    Posts
    536
    Quote 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");
        printf("\nPlease enter N D: ");
        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");
      printf("\nPlease enter N D: ");
      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. #5
    Registered User
    Join Date
    Mar 2004
    Posts
    536
    Quote 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. #6
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    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. #7
    Registered User
    Join Date
    Aug 2003
    Posts
    470
    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.
    Last edited by okinrus; 09-08-2004 at 12:27 AM.

  8. #8
    Registered User
    Join Date
    Aug 2003
    Posts
    470
    I made a mistake: not all non-repeating decimals will have a denominator of 1.

  9. #9
    Registered User
    Join Date
    Aug 2003
    Posts
    470
    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.
    Last edited by okinrus; 09-08-2004 at 01:18 AM.

  10. #10
    Registered User
    Join Date
    Mar 2003
    Posts
    143
    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 )
    DavT
    -----------------------------------------------

  11. #11
    Registered User
    Join Date
    Mar 2004
    Posts
    536
    Quote 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
    Last edited by Dave Evans; 09-08-2004 at 08:33 AM.

  12. #12
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,939
    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.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  13. #13
    Registered User
    Join Date
    Mar 2004
    Posts
    536
    Quote 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. #14
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,939
    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.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  15. #15
    Registered User
    Join Date
    Mar 2004
    Posts
    536
    Quote 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"
    Last edited by Dave Evans; 09-08-2004 at 06:02 PM.

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. fractions
    By zdream8 in forum C Programming
    Replies: 2
    Last Post: 05-21-2008, 09:54 PM
  2. Algebraic Fractions
    By treenef in forum C++ Programming
    Replies: 8
    Last Post: 12-20-2005, 04:10 AM
  3. Greatest Common Factors of Fractions
    By sonict in forum C++ Programming
    Replies: 1
    Last Post: 01-15-2003, 03:33 AM
  4. Fractions
    By Unregistered in forum C++ Programming
    Replies: 2
    Last Post: 04-01-2002, 06:51 AM
  5. Decimals to Fractions
    By ToasterPas in forum C++ Programming
    Replies: 4
    Last Post: 12-28-2001, 11:58 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21