Did you miss your activation email?

• Wednesday May 25, 2022, 5:10 am
• Proudly celebrating 15+ years online.
• Donate now to become a lifetime supporting member of the site and get a non-expiring license key for all of our programs.

### Author Topic: Efficient way to find highest common denominator? (For reducing fractions.)  (Read 4865 times)

#### Hirudin

• Charter Member
• Joined in 2005
• Posts: 543
##### Efficient way to find highest common denominator? (For reducing fractions.)
« on: July 13, 2007, 09:13 AM »
I'm making some AutoHotkey scripts and need to reduce a fraction.

Can anyone help me find the most efficient way to find the highest common denominator between 2 numbers?

I figure I can do a brute force type thing where I make each number "numerator1" and "numerator2".
Take each numerator and divide it by a counter.
- If the results for each division are integers then I'd make the results the new numerators.
- If one of the results is not an integer then increase the counter over and over until the counter = the smaller of the numerators
But I figure there's probably a better way...

#### Hirudin

• Charter Member
• Joined in 2005
• Posts: 543
##### Re: Efficient way to find highest common denominator? (For reducing fractions.)
« Reply #1 on: July 13, 2007, 10:42 AM »
Welp, I made a function that will do it. It uses a list of prime numbers (primes.txt) that must be in the same directory as the "Func_GreatestCommonDenominator.ahk" script.

Also included is an example ahk script that uses the function to reduce a fraction and report by how much the original was reduced.

« Last Edit: July 13, 2007, 10:50 AM by Hirudin »

#### Eóin

• Charter Member
• Joined in 2006
• Posts: 1,401
##### Re: Efficient way to find highest common denominator? (For reducing fractions.)
« Reply #2 on: July 15, 2007, 04:29 AM »
The Euclidean algorithm is considered to be quite efficient

#### Hirudin

• Charter Member
• Joined in 2005
• Posts: 543
##### Re: Efficient way to find highest common denominator? (For reducing fractions.)
« Reply #3 on: July 16, 2007, 09:15 AM »
The Euclidean algorithm is considered to be quite efficient
-Eóin
Whoa! Looks pretty efficient to me. Thanks Eóin!