Reducing the accuracy of Fractions

Discussion in 'Mac Programming' started by MorphingDragon, Jun 20, 2011.

  1. macrumors 603

    MorphingDragon

    Joined:
    Mar 27, 2009
    Location:
    The World Inbetween
    #1
    This is more of a mathematics question than programming.

    Say I have fractions a/b and c/d.

    If say a * c > UINT_MAX or b * d > UINT_MAX, how could I reduce the accuracy of one or both the fractions without knowing the decimal value to fit inside UINT_MAX? This is assuming the fractions are already in their simplest form.
     
  2. Moderator

    balamw

    Staff Member

    Joined:
    Aug 16, 2005
    Location:
    New England
    #2
    Spitballing.

    Look for max(a,b,c,d) >sqrt(MAX_UINT) and divide both the numerator and denominator by the factor you need to reduce it to less than MAX_UINT.

    ?

    B
     
  3. macrumors 603

    Joined:
    Aug 9, 2009
    #3
    I think you should just throw more bits at it.

    Carry out the calculation using the next longer type, and then reduce. I think the C99 typedef is uint64_t.
     
  4. thread starter macrumors 603

    MorphingDragon

    Joined:
    Mar 27, 2009
    Location:
    The World Inbetween
    #4
    Thats not always a solution though. If a reduced component is still greater than UINT_MAX, you still have to deal with reducing the accuracy.


    That might work... Certainly a lot faster than my original idea.
     
  5. macrumors 6502

    Joined:
    Apr 24, 2008
    #5
    You want to do this because you are going to multiply those fractions?
     
  6. chown33, Jun 21, 2011
    Last edited: Jun 21, 2011

    macrumors 603

    Joined:
    Aug 9, 2009
    #6
    If by "reducing the accuracy" you mean "reducing the fraction", then the GCD algorithm works no matter what.
    http://en.wikipedia.org/wiki/Binary_GCD_algorithm

    Reducing a fraction does not reduce its accuracy. 3/9 is exactly as accurate as 1/3, but only the latter is a reduced fraction.
    http://en.wikipedia.org/wiki/Irreducible_fraction
     
  7. MorphingDragon, Jun 22, 2011
    Last edited: Jun 22, 2011

    thread starter macrumors 603

    MorphingDragon

    Joined:
    Mar 27, 2009
    Location:
    The World Inbetween
    #7
    Reduce the actual accuracy of the numbers the fractions represent, not just simplify the fraction.

    (1359 / 2750) 0.5463 -> (11 / 20) 0.55

    I already have a method of doing it, but it takes a long time to compute and I was wondering if there was a known way that's most likely a lot quicker.


    Yes, I'm working on a Uni project where there's lots of lovely numbers like 1/3 is involved and there's no other way than fractions if you want maximum accuracy. Working in a minimum unit isn't really appropriate for the purpose of the project.

    It would be bad programming practice to not account for the limitation of the CPU and allow an overflow exception to occur during operations on the fractions. You could flag the fraction and abort the operation. A much more desirable action would be to reduce the accuracy of the fraction so you stay within the limits of the CPU during the operation.
     
  8. macrumors 6502

    Joined:
    Apr 24, 2008
    #8
    Would you still flag the fraction as having "reduced accuracy"? I'm asking because when you print out your final result as a fraction, a user might rightfully assume that this is an exact answer. If you're reducing accuracy anyway, you could consider simply switching to floating point arithmetic at that point.
     
  9. Moderator

    balamw

    Staff Member

    Joined:
    Aug 16, 2005
    Location:
    New England
    #9
    Question: So, how is this different than just switching to floating point if there is an overflow? That would typically be more accurate than your "(1359 / 2750) 0.5463 -> (11 / 20) 0.55" example. As Sander says, you would still somehow have to indicate that precision was lost.

    Also, have you considered using gmp http://gmplib.org/ or some other bignum/"arbitrary precision" library to maintain your precision... http://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic

    Finally, you say you have an approach. What is it? Can you describe it or post code. Maybe someone else has the same problem or idea, but will never know...

    B
     
  10. thread starter macrumors 603

    MorphingDragon

    Joined:
    Mar 27, 2009
    Location:
    The World Inbetween
    #10
    That fraction was just an example of what I wanted to achieve, the library would theoretically have to be doing it on fractions like 3/2^31.

    Floating point was our first idea, but the application does a lot of calculations involving Radians and tricks with fractions let us be accurate calculating the angles without actually knowing PI.

    Now why the hell don't they tell you about these things at Uni? :D There's no point changing it now anyway, its due in on Friday and I already have it working. I just want to try improve it.

    In reality, the application doesn't approach the limits. This is just to help satisfy "Good Software Engineering Practice" portion of the marking schedule, by making sure limits are accounted for in the design and testing of the fraction library.

    I don't have the actual Code with me but I wouldn't mind posting it when I get back to Hamilton.
     
  11. macrumors 603

    Joined:
    Aug 9, 2009
    #11
    There's an old trick for embedded systems where angles are measured in pirads, i.e. the fraction of a semicircle. So a semicircle (180 degress, pi radians) is exactly 1.0 pirads, a quarter circle is exactly 0.5 pirads (90 degrees, pi/2 radians), etc. The range of fixed-point or floating-point values is usually chosen to be 0.n (pure fraction) or 1.n bits, where n is the desired precision. Both formats are pretty easy to work with on puny processors, and angles like 180, 90, 45 etc. are represented exactly.
     
  12. Moderator

    balamw

    Staff Member

    Joined:
    Aug 16, 2005
    Location:
    New England
    #12
    At least somewhere along the road you learned about overflows and that they should be dealt with. :p

    As chown33 points out many of these problems have solutions in the embedded/fixed point world.

    Another Wiki link for you to read: http://en.wikipedia.org/wiki/Fixed-point_arithmetic

    B
     

Share This Page