Algorithmically Finding the LCD (or decimal to fractions)

[k_squared]

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?

 

[CRGreathouse]

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 let's you simplify 0.00000000000001048576 in twenty steps instead of a million.

 

[k_squared]

Awesome.
Neat how it works like that - I wish I had a knack for seeing that kinda thing off the top of my head.

 

[uart]

Awesome.
Neat how it works like that - I wish I had a knack for seeing that kinda thing off the top of my head.

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.

 

[DoctorBinary]

This let's you simplify 0.00000000000001048576 in twenty steps instead of a million.

The Euclidean algorithm will find this is ONE step, since 1048576 divides 10^20. The reduced fraction is 1/95367431640625.