February 19th, 2012, 11:34 AM  #1 
Senior Member Joined: Jan 2011 Posts: 560 Thanks: 1  GCD algorithm
Hi, Is there any other way than GCD algorithm to find a factor shared (or not) by 2 numbers ? Thank you. 
February 19th, 2012, 12:05 PM  #2 
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  Re: GCD algorithm
Sure, try factors until one works.

February 19th, 2012, 01:15 PM  #3 
Newbie Joined: Feb 2012 From: A deep,dark hole in the ground Posts: 16 Thanks: 0  Re: GCD algorithm
Euclid's algorithm is used to find the GCD of two numbers. http://mathworld.wolfram.com/EuclideanAlgorithm.html 
February 19th, 2012, 01:37 PM  #4 
Senior Member Joined: Jan 2011 Posts: 560 Thanks: 1  Re: GCD algorithm
Thank you for your answers. Very useful indeed. 
February 20th, 2012, 07:34 AM  #5 
Senior Member Joined: Jan 2011 Posts: 560 Thanks: 1  Re: GCD algorithm
I'm not talking about trivial way. I'm not talking about an algorithm with the same efficiency. I'm talking about something new. New means very efficient. New means a new approach. New mean revolutionary. Thank you anyway. 
February 20th, 2012, 11:36 AM  #6 
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  Re: GCD algorithm
Presumably, anything we'd tell you would be considered standard. (The latest I know of is the HGCD algorithm originally developed by [I think] Moenck and improved by many others.) If you have a new idea, feel free to present it. 
February 24th, 2012, 08:57 AM  #7 
Senior Member Joined: Jan 2011 Posts: 560 Thanks: 1  Re: GCD algorithm
Here is the idea. The goal of the test is not to find the common factor to a and b but to simply respond to one question :a and b share a factor or not? So the question GCD(a,b) equal to 1 or not ? That's it. The GCD algorithm under all it forms (Euclid, Recursive Binary, Half GCD and so on Google can list them all) can give you the common factor if it exist. 
February 24th, 2012, 09:40 AM  #8  
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  Re: GCD algorithm Quote:
 
February 24th, 2012, 10:09 AM  #9  
Senior Member Joined: Jan 2011 Posts: 560 Thanks: 1  Re: GCD algorithm Quote:
 
February 24th, 2012, 10:23 AM  #10  
Senior Member Joined: Apr 2011 From: Recife, BR Posts: 352 Thanks: 0  Re: GCD algorithm Quote:
 

Tags 
algorithm, gcd 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Algorithm for PI  Learner  Applied Math  22  July 31st, 2013 07:05 AM 
GCD new algorithm?  Bogauss  Number Theory  15  March 19th, 2012 09:54 AM 
is there an algorithm?  scoracle  Computer Science  7  June 27th, 2011 06:05 AM 
196Algorithm  skainstein  Number Theory  6  September 15th, 2009 05:39 PM 
What algorithm  mmx64  Algebra  0  July 2nd, 2008 12:23 AM 