Common factor : new algo?

  • Thread starter Gaussianheart
  • Start date
In summary: If you want to be really safe, you can use the modular inverse of a and b (which you could have computed in step 1 if you knew a and b were coprime), but this is not necessary.In summary, at step 6 of the euclidean algorithm, if a and b are not coprime to 10, you remove the 5 factors and continue with a and e.
  • #1
Gaussianheart
31
0
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.
 
Physics news on Phys.org
  • #2
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
Dodo said:
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.
 
  • #4
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.
 
  • #5
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
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!)
 
  • #7
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
 
  • #8
So if I understood no one here is an expert on GCD algorithms.
Thank you anyway for your answers.
 
  • #9
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.
 
Last edited:
  • #10
jreelawg said:
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
 
  • #11
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
Norwegian said:
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.
 
  • #13
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
Gaussianheart said:
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.
 
  • #15
Norwegian said:
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
 
  • #16
Let me add one more thing :

There exists a function f(x) such as :

Gcd(a,b)=f(b)-f(a)
 
  • #17
Gaussianheart said:
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?
 
  • #18
Norwegian said:
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
 
  • #19
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
Gaussianheart said:
If f(a)=0

f(a)-f(a) ----> 0-0=0
I rest my case.
[/endthread]
 
  • #21
Norwegian said:
I rest my case.
[/endthread]

?

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

1. What is a common factor?

A common factor is a number that divides evenly into two or more other numbers, leaving no remainder.

2. Why is finding common factors important?

Finding common factors is important in mathematics because it allows us to simplify fractions, factorize polynomials, and solve equations.

3. What is a new algorithm for finding common factors?

The new algorithm for finding common factors is a more efficient and systematic method compared to traditional techniques. It involves breaking down the numbers into their prime factors and identifying the common factors.

4. How does the new algorithm improve upon traditional methods?

The new algorithm is more efficient because it reduces the number of steps needed to find common factors. It also works for larger numbers and can handle multiple numbers at once, making it more versatile.

5. How can the new algorithm be applied in real-life situations?

The new algorithm can be applied in various real-life situations, such as simplifying recipes, calculating discounts, and finding the greatest common factor for a group of numbers. It is also used in computer science for data compression and cryptography.

Similar threads

  • Engineering and Comp Sci Homework Help
Replies
7
Views
1K
Replies
3
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
5
Views
4K
  • Advanced Physics Homework Help
Replies
4
Views
2K
  • Math Proof Training and Practice
2
Replies
60
Views
8K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
962
Replies
72
Views
5K
  • Linear and Abstract Algebra
2
Replies
44
Views
4K
Replies
7
Views
794
  • Math Proof Training and Practice
3
Replies
93
Views
10K
Back
Top