1. Hey! Guest! The 35th GMC Jam will take place between November 28th, 12:00 UTC - December 2nd, 12:00 UTC. Why not join in! Click here to find out more!
    Dismiss Notice

Greatest Common Factor Script

Discussion in 'Tutorials' started by JFitch, Apr 23, 2017.

  1. JFitch

    JFitch Member

    Joined:
    Sep 28, 2016
    Posts:
    428
    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: Apr 23, 2017
  2. chance

    chance predictably random Forum Staff Moderator

    Joined:
    Apr 22, 2016
    Posts:
    798
    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: Apr 23, 2017
  3. JFitch

    JFitch Member

    Joined:
    Sep 28, 2016
    Posts:
    428
    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).
     
  4. Appsurd

    Appsurd Member

    Joined:
    Jun 20, 2016
    Posts:
    238
    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)
     

Share This Page

  1. This site uses cookies to help personalise content, tailor your experience and to keep you logged in if you register.
    By continuing to use this site, you are consenting to our use of cookies.
    Dismiss Notice