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=(ca)/10=(60691989)/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. 
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! 
Re: Common factor : new algo?
Quote:
a=761 b=269 So 9b mod 10=a mod 10 (9*269761)/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 (761581)/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. 
Re: Common factor : new algo?
Hi, what do you do when a'=5? Maybe you also have to throw away all 5factors? 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. 
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 ca or cb, 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 (cb or ca, 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 15, you just take e=ab. (Or ba, 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 7417=57, then 5717=40, then 4017=23, 2717=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. :) 
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*3867)/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!) 
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 
Re: Common factor : new algo?
So if I understood no one here is an expert on GCD algorithms.
Thank you anyway for your answers. 
Re: Common factor : new algo?
The euclidian algorithm
Code:
int a=867; Code:
In steps; 
Re: Common factor : new algo?
Quote:
867=17*51 So GCD(1989, 867)=51 not 1 
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.

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

Re: Common factor : new algo?
Quote:
Here you have a deep analysis of the binary GCD algorithm: http://www.csie.nuk.edu.tw/~cychen/g...0Algorithm.pdf 
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) 
Re: Common factor : new algo?
Quote:

Re: Common factor : new algo?
Quote:
f(a)f(a) > 00=0 
All times are GMT 5. The time now is 10:59 AM. 
Powered by vBulletin Copyright ©2000  2014, Jelsoft Enterprises Ltd.
© 2014 Physics Forums