# Common factor : new algo?

1. Mar 15, 2012

### Gaussianheart

Here is an algorithm very simple to find a common factor to a and b.

An example :
a=867
b=1989

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. Mar 15, 2012

### dodo

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!

3. Mar 15, 2012

### Gaussianheart

First question :

a=761 b=269

So 9b mod 10=a mod 10
(9*269-761)/10=166
We divide 166 by 2 until odd
166/2=83
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
x=7

83*7=581
b=761
(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.

4. Mar 15, 2012

### Norwegian

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.

5. Mar 15, 2012

### dodo

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. :)

6. Mar 15, 2012

### Gaussianheart

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
x=3
(1989*3-867)/100=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!)

7. Mar 16, 2012

### Gaussianheart

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 ?

8. Mar 17, 2012

### Gaussianheart

So if I understood no one here is an expert on GCD algorithms.

9. Mar 17, 2012

### jreelawg

The euclidian algorithm

Code (Text):

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

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

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

Last edited: Mar 17, 2012
10. Mar 17, 2012

### Gaussianheart

1989=39*51
867=17*51

So GCD(1989, 867)=51 not 1

11. Mar 17, 2012

### Norwegian

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.

12. Mar 17, 2012

### Gaussianheart

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.

13. Mar 17, 2012

### Gaussianheart

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.

14. Mar 17, 2012

### jreelawg

I screwed up writing 225 instead of 255. I made the correction.

15. Mar 18, 2012

### Gaussianheart

16. Mar 18, 2012

### Gaussianheart

Let me add one more thing :

There exists a function f(x) such as :

Gcd(a,b)=f(b)-f(a)

17. Mar 18, 2012

### Norwegian

OK, nice try, but did you try to compute gcd(a,a) using this function?

18. Mar 18, 2012

### Gaussianheart

If f(a)=0

f(a)-f(a) ----> 0-0=0

19. Mar 18, 2012

### Gaussianheart

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.

20. Mar 18, 2012

### Norwegian

I rest my case.