You can tell I’ve been bored, :lol:. Here are three AppleScript renditions of the calculation of the greatest common divisor of a pair of numbers that are not mutually prime (i.e. have a GCD that isn’t 1).
Euclid’s Algorithm:
(*
Given two numbers not prime to one another, what is their greatest common divisor (GCD)? Euclid's Algorithm involves only repeated subtractions. It is based on the notion that the GCD of two numbers does not change if the smaller of the two is subtracted from the larger. By repeating this subtraction of the smaller from the larger until smaller goes to zero leaves the other as the GCD. If the smaller of the two goes to 1 then the numbers are mutually prime.
*)
set a to 40902
set b to 24140
Euclid_GCD(a, b) --> 34
to Euclid_GCD(a, b)
if a = 0 then return b
repeat while b ≠0
if a > b then
set a to a - b
else
set b to b - a
end if
end repeat
return a
end Euclid_GCD
This can be done by division as well (using modulo arithmetic)
(*
As an alternative to multiple subtractions, the GCD of a pair of numbers can also be found using the remainders of a sequence of divisions. Depending on the language, this may actually be faster than many more iterations of subtraction even though subtraction is a simpler assembly language process than modulo division. Which is faster might also depend on the numbers given. The result is 1 if the numbers chosen are mutually prime. The algorithm is not sensitive to which is the larger of the given numbers.
*)
set m to 40902
set n to 24140
modulo_GCD(m, n) --> 34
to modulo_GCD(m, n)
repeat while n ≠0
set r to m mod n
set m to n
set n to r
end repeat
return m
end modulo_GCD
And finally, a recursive version:
(*
Recursion works in this instance because for the modulo version of the algorithm embedded in the recursion, there are not very many iterations so the stack doesn't explode.
*)
set x to 40902
set y to 24140
recurse_GCD(x, y) --> 34
to recurse_GCD(x, y)
if y = 0 then
return x
else
return recurse_GCD(y, x mod y)
end if
end recurse_GCD
Here’s a adaptation which takes any number of numbers (well, one or more!) and also copes with negatives. Over here, the Greatest Common Divisor (GCD) is called the Highest Common Factor (HCF), so I’ve named my version in that manner:
set m to -40902
set n to 24140
set o to 8.5
HCF({m, n, o}) --> 8.5
-- Adapted from a handler by Adam Bell.
to HCF(l)
set m to beginning of l
repeat with i from 2 to (count l)
set n to item i of l
repeat until (n is 0)
set r to m mod n
set m to n
set n to r
end repeat
end repeat
if (m < 0) then return -m
return m
end HCF
Edit: Shorter handler name and the check for negatives left till the end.
You have a very good timer for handlers, an extension of “lotsa” as I recall. Which is actually the fastest handler for finding GCD/HCF, subtraction or modular division?
A related idea is the Lowest Common Multiple (LCM) ” that is, the lowest (positive) integer value which is exactly divisible by all the given numbers. The Highest Common Factor(s) can be used to calculate this:
-- Adapted from a handler by Adam Bell.
to HCF(l)
set m to beginning of l
repeat with i from 2 to (count l)
set n to item i of l
repeat until (n is 0)
set r to m mod n
set m to n
set n to r
end repeat
end repeat
if (m < 0) then return -m
return m
end HCF
(* The LCM of two numbers can be found by multiplying them together and dividing the result by their HCF. (Dividing one number by the HCF first instead and then multiplying by the other produces a smaller intermediate result, which is allegedly more efficient, but probably doesn't make any difference in AppleScript.) For more than two numbers, we have to get the LCM of the each successive number and the preceding result. *)
on LCM(l)
set m to beginning of l
repeat with i from 2 to (count l)
set n to item i of l
set m to m div (HCF({m, n})) * n
end repeat
if (m < 0) then return -m
return m
end LCM
LCM({8, 10, 59, -118, 20, 0.5}) --> 2360.0
Modular division ” according to the minimal testing I’ve done so far. But there’s not much in it. I suspect that it’s much faster than subtraction when there’s a lot of subtracting to be done, but pretty much the same where there isn’t.
