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.
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.
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.
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. :)
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!)
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
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 Sorry, I made the corrections.
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.
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.
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 Analysis of the Generalized Binary GCD Algorithm.pdf
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.