My Math Forum GCD algorithm

 Number Theory Number Theory Math Forum

 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:
 Originally Posted by Bogauss So the question GCD(a,b) equal to 1 or not ?
Well, you could do this faster on average by searching for small primes in common between the two. I don't know of a way to do this faster than $O(n\log^{2+\varepsilon}n)$ in the worst case; do you? I'd be curious to know!

February 24th, 2012, 10:09 AM   #9
Senior Member

Joined: Jan 2011

Posts: 560
Thanks: 1

Re: GCD algorithm

Quote:
Originally Posted by CRGreathouse
Quote:
 Originally Posted by Bogauss So the question GCD(a,b) equal to 1 or not ?
Well, you could do this faster on average by searching for small primes in common between the two. I don't know of a way to do this faster than $O(n\log^{2+\varepsilon}n)$ in the worst case; do you? I'd be curious to know!
GCD(A,B) = 1 or not that is the question not find the common factor.

February 24th, 2012, 10:23 AM   #10
Senior Member

Joined: Apr 2011
From: Recife, BR

Posts: 352
Thanks: 0

Re: GCD algorithm

Quote:
 Originally Posted by CRGreathouse Well, you could do this faster on average by searching for small primes in common between the two. I don't know of a way to do this faster than $O(n\log^{2+\varepsilon}n)$ in the worst case; do you? I'd be curious to know!
I think the Euclidean algorithm is fast enough.. On a sidenote, I wonder how do you calculate "time", with big-O notation given some algorithm.. For an easier example, how long does it take to calculate $n!$?

 Tags algorithm, gcd

 Thread Tools Display Modes Linear Mode

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

 Contact - Home - Forums - Cryptocurrency Forum - Top