Is This New Algorithm Effective for Finding Common Factors?

[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.

 

[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!

 

[Gaussianheart]

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!

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.

 

[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 preferred method.

 

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

 

[Gaussianheart]

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
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!)

 

[Gaussianheart]

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

 

[Gaussianheart]

So if I understood no one here is an expert on GCD algorithms.
Thank you anyway for your answers.

 

[jreelawg]

The euclidian algorithm

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;

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.

 

[Gaussianheart]

the euclidian algorithm

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

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

cout << "gcd(1989,867)=" << b;

in steps;

r = b mod a = 225;
b = 867;
a = 225;

r = b mod a = 192
b = 225
a = 192

r = b mod a = 33
b = 192
a = 33

r = b mod a = 32
b = 33
a = 32

r = b mod a = 1
b = 32
a = 1

r = 32 mod 1 = 0
b = 1
a = 0

loop condition met, gcd(1989, 867) = 1

1989=39*51
867=17*51

So GCD(1989, 867)=51 not 1

 

[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.

 

[Gaussianheart]

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.

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.

 

[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.

 

[jreelawg]

1989=39*51
867=17*51

So GCD(1989, 867)=51 not 1

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

 

[Gaussianheart]

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.

Maybe you did not give too much attention to my algorithm.
Here you have a deep analysis of the binary GCD algorithm:

http://www.csie.nuk.edu.tw/~cychen/gcd/An%20Analysis%20of%20the%20Generalized%20Binary%20GCD%20Algorithm.pdf

 

[Gaussianheart]

Let me add one more thing :

There exists a function f(x) such as :

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

 

[Norwegian]

Let me add one more thing :

There exists a function f(x) such as :

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

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

 

[Gaussianheart]

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

If f(a)=0

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

 

[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.

 

[Norwegian]

If f(a)=0

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

I rest my case.
[/endthread]

 

[Gaussianheart]

I rest my case.
[/endthread]

?

a and b have to be different.
If b=a then no need to search the gcd.