simplifying ratios and fractions

December 17, 2005 3:35 AM

Is there a mathematical technique for simplifying ratios/fractions?

This sounds searchable I know, but I can't find anything. If you've got 4/12, you can see that it simplifies to 1/3, but is there a way you could work out that 168/504 simplifies to 1/3 with pen and paper?

I think finding the lowest prime number they can be divided by would be one way but I don't know a way to work this out.

If anyone has some good links for maths and physics questions involving ratios/fractions that would be cool.

posted by lunkfish to science & nature (21 comments total)

You might be thinking of the lowest common denominator and the greatest common factor.
posted by boo_radley at 3:52 AM on December 17, 2005

What you want is the greatest common factor which is the product of all the prime factors that the numerator and divisor have in common. so you'd factor the numbers into primes, giving (with your second example) 168=(2*2*2*3*7) and 504=(2*2*2*3*7)*3, so they have (2*2*2*3*7) as a common divisor. dividing both numerator and denominator by 168 gives you 1/3. It should be apparent that this is not "workable" with pen and paper (i.e. factoring = hard) when sufficiently large primes are involved.

on preview, beat to the punch by boo_radley.
posted by juv3nal at 3:56 AM on December 17, 2005

Euclid's algorithm for finding the GCD
posted by Leon at 4:06 AM on December 17, 2005

It should be apparent that this is not "workable" with pen and paper (i.e. factoring = hard) when sufficiently large primes are involved.

Ack, poorly phrased. In the case (as in both your examples) where the denominator is divisible by the numerator, obviously it's going to be workable with pen and paper; the not workable comes in when the simplified form is (large prime)/(other large prime).
posted by juv3nal at 4:08 AM on December 17, 2005

Here's a link for you.

What you really want is to find the greatest common divisor of the numerator and denominator. (Then divide both of them by the GCD and voila, your fraction's in least terms.)

Euclid's algorithm is aces at finding the GCD, if the numbers are big enough that you can't spot it just by looking like in your example.

In the first linked example, gcd(2322,654)=6, so you could simply the fraction 654/2322 to 109/387 by dividing top & bottom by 6; now the fraction is in least terms, guaranteed.

It's a kind of peculiar circumstance that it's generally easier to find the common factors of two integers (like you're doing here) than to find all the prime factors of one integer. (One way to reduce a fraction is to completely factor the numerator and denominator into primes, then cross out the common factors. But for big numbers, completely factoring into primes can be hard; the Euclidean algorithm never gets any harder as the numbers get bigger.

A couple more links for you: Simplifying fractions, another Euclidean algorithm example, divisibility rules. I included the last, because for not-too-large numbers you can easily learn to spot a lot of factors just by looking.
posted by Wolfdog at 4:09 AM on December 17, 2005

the euclidean algorithm will give you the greatest common divisor, which you can divide both top and bottom numbers by to reduce the fraction. this is efficient even when large primes are involved (ie euclid's algorithm gives you the gcd without the hard problem of factoring that juv3nal mentioned).
posted by andrew cooke at 4:14 AM on December 17, 2005

oh, sorry.
posted by andrew cooke at 4:14 AM on December 17, 2005

Thanks, that's good stuff.

It would actually be useful to do it by the primes way - I'm working with music and the prime numbers can be significant to the sound.

Do you know if a cheapish calculator can find the prime factors these days, or is it a job for a PC?
posted by lunkfish at 4:23 AM on December 17, 2005

as people keep saying, finding primes is hard for big numbers. this is the basis of some of the crptography behind secure web pages, for example. so if the numbers really are large (like 1000 bits) then even the largest supercomputers in the world won't come close (although quantum computers should, as they work differently).
posted by andrew cooke at 4:32 AM on December 17, 2005

that should read: finding prime factors is hard (finindg primes themselves is actually pretty easy).
posted by andrew cooke at 4:33 AM on December 17, 2005

You can write at least a naive program to factor integers on a modern handheld calculator, but it doesn't come as a built-in feature on any that I'm aware of.

There are, however, things like this [Java applet] that implement high-powered factorization algorithms and will make mincemeat out of any numbers you're likely to encounter "in real life" (that is, assuming you're not a cryptologist (which I think is a safe assumption)).
posted by Wolfdog at 5:05 AM on December 17, 2005

Factoring algorithms. I meant to link that earlier. Not too hard to read and should get you up to speed factoring integers by hand or with a basic calculator.
posted by Wolfdog at 6:23 AM on December 17, 2005

i don't know how fast this has to be (maybe yu're generating musi creal-time from streams of binary data for example), but it would be a bit more elegant if you fisrt used euclid's algorithm to find the gcd and then factored *that*. since the gcd could be quite a lot smaller than either of the numbers, it could save you a fair amount of effort.

in other words, the common prime factors of the two numbers are the prime factors of the gcd.
posted by andrew cooke at 7:12 AM on December 17, 2005

A couple of points: everyone is correct to say that simplifying a fraction is easy by Euclid's algorithm, and that finding the prime factors of a large number is hard. But note that "large" here means hundreds of digits; a number like 504 (or 5000004) can be factored instantaneously by computer. No need to program this yourself; googling "factorization applet" will give you lots of sites that will factor numbers of this size for you. For instance, you can do it here.
posted by escabeche at 7:27 AM on December 17, 2005

Psst. Escabeche.
posted by Wolfdog at 7:30 AM on December 17, 2005

Thanks Wolfdog et al. That links not opening now, but I'll try it later.

I'm not writing code or anything, I'm working with Just Intonation

Most of the basic ratios are simple e.g. 3:2, but some calculations can end up more complicated. I'm not likely to get numbers much bigger than 1000 though.

I've been looking for a way of doing this that let's me see the calculation rather than just giving the answer. It is handy to see the prime factors, as ratios based on different primes can have a different flavour.
posted by lunkfish at 7:58 AM on December 17, 2005

my knowledge of musical theory is limited, but i thought that the "flavour" depended on the reduced fraction, rather than primes.

often the numbers in the reduced fraction are primes, but not always, and there's no argument i know of that says that the timbre of 13/12 is related to 1/2 any more than 13/11, even though 12 includes the prime factor 2.

have i misunderstood? are you saying that the "flavour" of 13/12 is related to 1/2 (say) in a way that 13/11 isn't?

just curious...
posted by andrew cooke at 8:09 AM on December 17, 2005

The TI line of calculators have GCD functions. And they will do just about any other math function you can think of, and program them to do even more. They aren't cheapish, but maybe you could pick up a used one on Ebay.
posted by Roger Dodger at 8:20 AM on December 17, 2005

gleuschk, where are you? We have a chance to get all of MeFi's math profs in one Answer.

As escabeche emphasized, Euclid's algorithm is much faster than factoring numerator and denominator, even when the latter is already computer-approachable. Since this question has now been answered...

Knuth's Art of Computer Programming Vol 1 has an analysis of how fast Euclid's algorithm is. The worst case turns out to be two successive Fibonacci numbers, taking log N steps where N is the larger number and the base of the logarithm is the golden ratio. The average case takes log N steps where the base of the logarithm is "Khinchin's constant", exp(pi^2/12 ln 2).
posted by Aknaton at 9:01 AM on December 17, 2005

Thanks Roger, I'll have a look.

ac, I'm still learning this stuff myself but for example you can make a scale with 7:4, 7:5 and 7:6 in and the pitches share a particular quality (flinty, dark). and seem to fit together as a 'family'. I don't know why this is mathematically, but I'd imagine they share harmonics in common.

Obviously a lot of numbers will have the prime factor 2 and not be especially related, but I think looking at the numbers helps get my subconscious learning rather than just getting the results off a spreadsheet.
posted by lunkfish at 11:44 AM on December 17, 2005

Do you know if a cheapish calculator can find the prime factors these days, or is it a job for a PC?

Prime factorization, not that I know of, but even the cheapies will reduce fractions (as long as the calculator is designed to work with fractions.)

Something like this goes for under 20 bucks.

HP has one for 12 bucks online.

These calculators probably do the job using one of the algorithms discussed above.
posted by Opposite George at 1:42 PM on December 17, 2005