Greatest Common Factor Script

J

JFitch

Guest
GM Version: GM Studio 1.4
Target Platform: ALL
Download: N/A
Links: N/A

Summary:
This tutorial gives a script for calculating the Greatest Common Factor of two numbers.

Tutorial:

The simplest way to calculate the greatest common factor of two numbers is to replace the larger number with the remainder when it's divided by the smaller number, and continue to do that until there's no remainder. With this script, you can just use gcf(a,b) to get the greatest common factor of a and b.
Code:
var a=abs(argument[0]);
var b=abs(argument[1]);
var new_a;
var new_b;

while (a!=b && a!=0 && b!=0)
{
new_a=a mod b;
new_b=b mod a;
a=new_a;
b=new_b;
}

return max(a,b);
If you want the greatest common factor of more than two numbers, first find the GCF of the first two numbers, then find the GCF of the result and the third number, then find the GCF of the result and the fourth number, etc. It would look like gcf(gcf(gcf(a,b),c),d).
 
Last edited by a moderator:

chance

predictably random
Forum Staff
Moderator
I haven't tested your algorithm carefully. I'll leave that to other members. But it looks interesting.

I'm interested in prime factorization and number theory. So I'm curious to see what other members have to say about your approach, and this area in general.
 
Last edited:
J

JFitch

Guest
I actually added to it since posting it. The original post works for two numbers. I changed it to work for any amount of numbers.
Code:
var a=argument[0];
var b;
var new_a;
var new_b;
var i;

for (i=1;i<argument_count;i++)
{
b=argument[i];

while (a!=b && a!=0 && b!=0)
{
new_a=a mod b;
new_b=b mod a;
a=new_a;
b=new_b;
}
a=max(a,b);
}
return a;
With this code, instead of using the code gcf(gcf(gcf(a,b),c),d), you can use gcf(a,b,c,d).
 

Appsurd

Member
Interesting script, it's simple and neat. But I once found another script online so I was interested to see whether both scripts were just as quick.

Code:
// gcd(a,b)
// constraint: a>0 and b>0
var a,b;
a = argument0;
b = argument1;
while true {
    a = a mod b;
    if a=0 then return b;
    b = b mod a;
    if b=0 then return a;
}
Nothing special but a little different. I just this testing script.

Code:
N = 100000;

t1 = current_time;

for(i=0; i<N; i+=1)
{
    var res = gcd(7583,59375);
}

t2 = current_time - t1;

for(i=0; i<N; i+=1)
{
    var res = gcf(7583,59375);
}

t3 = current_time - t2;

show_message_async("The gcd script: Time: "+string(t2)+"#The gcf script: Time: "+string(t3));
And it turned out that your script is about two times slower than this old script I found (and no, it's not my script, just took it from the internet)

--------------

Another remark, perhaps you could look into Euclides's algorithm? It yields the gcf/gcd but also the numbers x and y such that
x a + y b = ggd(a,b)
 
Top