# Algorithmically Finding the LCD (or decimal to fractions)

1. Oct 7, 2009

### 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?

2. Oct 7, 2009

### 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 lets you simplify 0.00000000000001048576 in twenty steps instead of a million.

3. Oct 7, 2009

### 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.

4. Oct 8, 2009

### uart

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.

5. Oct 8, 2009

### DoctorBinary

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