Home | Blog | Software | Reviews and Features | Forum | Help | Donate | About us
topbanner_forum
  *

avatar image

Welcome, Guest. Please login or register.
Did you miss your activation email?

Login with username, password and session length
  • December 05, 2016, 09:08:47 PM
  • Proudly celebrating 10 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.
  • donate

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

Hirudin

  • Charter Member
  • Joined in 2005
  • ***
  • Posts: 543
    • View Profile
    • Donate to Member
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
    • View Profile
    • Donate to Member
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.

* GCD 1.1.rar (22.95 kB - downloaded 122 times.)
« Last Edit: July 13, 2007, 10:50:30 AM by Hirudin »

Eóin

  • Charter Member
  • Joined in 2006
  • ***
  • Posts: 1,401
    • View Profile
    • Donate to Member
The Euclidean algorithm is considered to be quite efficient :)

Hirudin

  • Charter Member
  • Joined in 2005
  • ***
  • Posts: 543
    • View Profile
    • Donate to Member
The Euclidean algorithm is considered to be quite efficient :)
Whoa! Looks pretty efficient to me. Thanks Eóin!