Physics Forums

Physics Forums (http://www.physicsforums.com/index.php)
-   Linear & Abstract Algebra (http://www.physicsforums.com/forumdisplay.php?f=75)
-   -   Common factor : new algo? (http://www.physicsforums.com/showthread.php?t=587238)

Gaussianheart Mar15-12 08:34 AM

Common factor : new algo?
 
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 Mar15-12 09:46 AM

Re: Common factor : new algo?
 
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 Mar15-12 10:41 AM

Re: Common factor : new algo?
 
Quote:

Quote by Dodo (Post 3816626)
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 Mar15-12 10:54 AM

Re: Common factor : new algo?
 
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.

dodo Mar15-12 11:05 AM

Re: Common factor : new algo?
 
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 Mar15-12 11:44 AM

Re: Common factor : new algo?
 
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 Mar16-12 11:55 AM

Re: Common factor : new algo?
 
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 Mar17-12 06:58 PM

Re: Common factor : new algo?
 
So if I understood no one here is an expert on GCD algorithms.
Thank you anyway for your answers.

jreelawg Mar17-12 07:57 PM

Re: Common factor : new algo?
 
The euclidian algorithm

Code:

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:

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 Mar17-12 08:11 PM

Re: Common factor : new algo?
 
Quote:

Quote by jreelawg (Post 3820814)
the euclidian algorithm

Code:

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

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

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

Code:

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 Mar17-12 08:19 PM

Re: Common factor : new algo?
 
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 Mar17-12 08:31 PM

Re: Common factor : new algo?
 
Quote:

Quote by Norwegian (Post 3820843)
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 Mar17-12 08:34 PM

Re: Common factor : new algo?
 
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 Mar17-12 08:53 PM

Re: Common factor : new algo?
 
Quote:

Quote by Gaussianheart (Post 3820828)
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 Mar18-12 12:42 PM

Re: Common factor : new algo?
 
Quote:

Quote by Norwegian (Post 3820843)
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/g...0Algorithm.pdf

Gaussianheart Mar18-12 12:44 PM

Re: Common factor : new algo?
 
Let me add one more thing :

There exists a function f(x) such as :

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

Norwegian Mar18-12 01:19 PM

Re: Common factor : new algo?
 
Quote:

Quote by Gaussianheart (Post 3821729)
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 Mar18-12 01:35 PM

Re: Common factor : new algo?
 
Quote:

Quote by Norwegian (Post 3821768)
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


All times are GMT -5. The time now is 09:30 AM.

Powered by vBulletin Copyright ©2000 - 2014, Jelsoft Enterprises Ltd.
© 2014 Physics Forums