Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Common factor : new algo?

  1. Mar 15, 2012 #1
    Here is an algorithm very simple to find a common factor to a and b.

    An example :

    1. We compute a'=a mod 10 and b'=b mod 10 so a'=7 b'=9
    2. We solve a'x mod 10 = b' (we can use a table)
    x=7 7*a'=49=9 mod 10=b'

    3. We compute c=x*a=7*867=6069
    4. c>b we compute d=(c-a)/10=(6069-1989)/10=4080/10=408
    5. If d is even we divide by 2 (because a and b are odd the divisor ins consequently an odd

    number) e=d/2=408/2=204 we continue 204/2=102 102/2=51. e=51
    6. We try a/e=867/51=17 and b/e=1989/51=39 so 51 divide a and b
    7. We continue with new values a and b : a=17 b=39 by apllying the same algo looping from 1.

    I gave an example but we have to apply some rules before starting the use of the algo :

    If a is even and b odd (or b odd a even or a and b both even) we have to divide a (or b or and b)

    by 2 until we reach a and b both odds.

    a=1522 b=538

    The values a and b will be a=761 b=269 so then we can start applying the algo above.

    Each time we reach step 7 we have try dividing a and b by e.

    I'm very aware that there is a need to fix some problems to make it working quickly.
    So the core of the algo was presented above.

    Thank you for any improvement.
  2. jcsd
  3. Mar 15, 2012 #2
    Hi, Gaussianheart,
    I didn't understand two things:

    1) What do you do at step 6, when d do not divide a or b? You could show the full workings for your second example, a=761 and b=269, to illustrate what do you do in this case.

    2) Why do you return to step 1, if you already have a common factor? When do you stop looping?

    I could offer a few hints, but I would need the answer to these questions first. Thanks!
  4. Mar 15, 2012 #3
    First question :

    a=761 b=269

    So 9b mod 10=a mod 10
    We divide 166 by 2 until odd
    We try 761/83 and 269/83 so 83 divide none of them

    The new value of a=83 and b=761 (or b=269)
    Same algo

    (761-581)/10=18 ----> e=9

    Try 83/9 and or 761/9 so 9 does not divide 83 nor 761
    If 9 does not divide 761 (knowing that int(sqrt(761)) is > 9) so gcd(761,269)=1

    2. Second question :
    Because sometimes there is another possibility that the "new" a and b could share another factor.

    I know that there are some problems to fix.
    I can not focus now because I'm sick.
  5. Mar 15, 2012 #4
    Hi, what do you do when a'=5? Maybe you also have to throw away all 5-factors? At step 6, the general plan is perhaps to continue with a and e, and start from the top?

    This whole idea differs from the euclidean algorithm in that you first designate an integer, preferably prime p (although u used 10), that you are happy to check out manually as you go along. Then, while the euclidean algorithm subtracts a multiple of the smaller
    number from the bigger, in order to simplify, your strategy is to make numbers divisble by p, and simplify that way. Nice idea, if I have undrstood it right, wonder if there is any setup where this will be a prefered method.
  6. Mar 15, 2012 #5
    Sorry to hear that you're sick, I hope you get better soon.

    While I still have questions (such as: do you subtract c-a or c-b, before dividing by 10?) I think I can contribute something for you to think later.

    One thing is that some of your problems may get solved if you remove the 5 factors, just like you're removing the 2's. The reason is that the equation modulo 10 that you solve for x may not have a solution if a or b are not coprime to 10.

    I believe that it is the difference (c-b or c-a, I'm still not sure of which one you do) the key element at work here. You may want to try what happens to your algorithm if, instead of steps 1-5, you just take e=a-b. (Or b-a, if b is larger.) If you try this, to avoid multiple, unnecessary loops in this case, you may want to take e=the remainder after dividing a by b (or b by a, if b is larger). (Using the remainder is a way of keeping only the last part after subtracting everything subtractable; for example, repeating the subtraction 74-17=57, then 57-17=40, then 40-17=23, 27-17=6 would be unnecessary if you can remove *all* 17's at once, by taking the remainder after the division of 74 by 17, which is 6.)

    Hope this helps, and get better!

    P.S.: Norwegian just owned me on the 5's. It serves me for writing that much. :)
  7. Mar 15, 2012 #6
    Thank you for all your comments.
    When numbers are larger we can work mod 100

    Example :
    a=867 b=1989
    when applying the same algo mod 100 we got directly 51

    The same idea used for my algo is very useful solving linear congruence. Very quick.
    I will post it later.
    Now I will go to the bed (damned flu!)
  8. Mar 16, 2012 #7
    Unanswered questions :
    1. Is the algorithm new one?
    2. Have you ever seen such algo in mathematic literature?
    3. If implemented correctly (I'm not a programmer) do you think that it will be the fastest one ?

    Thank you for any comments
  9. Mar 17, 2012 #8
    So if I understood no one here is an expert on GCD algorithms.
    Thank you anyway for your answers.
  10. Mar 17, 2012 #9
    The euclidian algorithm

    Code (Text):

    int a=867;
    int b=1989;
    int r;

    while ( a != 0 ) {
        r = b % a;             //b mod a

    cout << "GCD(1989,867)=" << b;
    Code (Text):
    In steps;

    r = 1989 mod 867 = 255;
    b = 867;
    a = 255;

    r = 867 mod 255 = 102
    b = 255
    a = 102

    r = 255 mod 102 = 51
    b = 102
    a = 51

    r = 102 mod 51 = 0
    b = 51
    a = 0

    loop condition met, GCD(1989, 867) = 51
    Sorry, I made the corrections.
    Last edited: Mar 17, 2012
  11. Mar 17, 2012 #10

    So GCD(1989, 867)=51 not 1
  12. Mar 17, 2012 #11
    Hi, I have looked a little more into this, and there is case where your algorithm is more efficient than the standard euclidean. It is with p=2 (instead of your 10), it is called the binary GCD algorithm, and you can read more about it here.
  13. Mar 17, 2012 #12
    Someone gave me the same answer in another forum.
    I'm still convinced that my algo if correctly implemented can be fastest maybe the fastest one.
    Working with 10^k will give better results in the case of large numbers.
    Thank you for your comment.
  14. Mar 17, 2012 #13
    I'm working on a formula which give directly the gcd(a,b).
    I have built the formula but I do not know how to prove it.
    I need time to do it. I feel very tired physically.
    I will do it later.
  15. Mar 17, 2012 #14
    I screwed up writing 225 instead of 255. I made the correction.
  16. Mar 18, 2012 #15
  17. Mar 18, 2012 #16
    Let me add one more thing :

    There exists a function f(x) such as :

  18. Mar 18, 2012 #17
    OK, nice try, but did you try to compute gcd(a,a) using this function?
  19. Mar 18, 2012 #18
    If f(a)=0

    f(a)-f(a) ----> 0-0=0
  20. Mar 18, 2012 #19
    In fact you start from a and b
    then you make a transformation to reach new values of a and b
    then you can apply your function.
    I did not finished yet.
  21. Mar 18, 2012 #20
    I rest my case.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook