1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Algorithmically Finding the LCD (or decimal to fractions)

  1. Oct 7, 2009 #1
    I wrote a program to convert decimals into fractions. It basically puts the decimal over the proper power of ten, and simplifies (at least, for nonreapeating fractions.) However, it uses a brute force method to find the LCD, and as a matter of aesthetics, I never like brute force. Does anyone know of some more efficient ways do do that?
  2. jcsd
  3. Oct 7, 2009 #2


    User Avatar
    Science Advisor
    Homework Helper

    Just divide by two until it won't go in any longer, then divide by 5 until it won't go in any longer.

    0.88 -> 88/100 = 44/50 = 22/25. Two won't go into the denominator anymore, and 5 won't go into the numerator, so you're done.

    This lets you simplify 0.00000000000001048576 in twenty steps instead of a million.
  4. Oct 7, 2009 #3
    Neat how it works like that - I wish I had a knack for seeing that kinda thing off the top of my head.
  5. Oct 8, 2009 #4


    User Avatar
    Science Advisor

    It's just the fundamental theorem of arithmetic (aka "uniqueness of prime factorization") at work. The only prime factors of any positive power of ten (eg 10 100 1000 etc) are 2 and 5.
  6. Oct 8, 2009 #5
    The Euclidean algorithm will find this is ONE step, since 1048576 divides 10^20. The reduced fraction is 1/95367431640625.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook