My Math Forum  

Go Back   My Math Forum > College Math Forum > Number Theory

Number Theory Number Theory Math Forum


Reply
 
LinkBack Thread Tools Display Modes
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.
Bogauss is offline  
 
February 19th, 2012, 12:05 PM   #2
Global Moderator
 
CRGreathouse's Avatar
 
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.
CRGreathouse is offline  
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
LordofthePenguins is offline  
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.
Bogauss is offline  
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.
Bogauss is offline  
February 20th, 2012, 11:36 AM   #6
Global Moderator
 
CRGreathouse's Avatar
 
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.
CRGreathouse is offline  
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.
Bogauss is offline  
February 24th, 2012, 09:40 AM   #8
Global Moderator
 
CRGreathouse's Avatar
 
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 in the worst case; do you? I'd be curious to know!
CRGreathouse is offline  
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 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.
Bogauss is offline  
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 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 ?
proglote is offline  
Reply

  My Math Forum > College Math Forum > Number Theory

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
196-Algorithm skainstein Number Theory 6 September 15th, 2009 05:39 PM
What algorithm mmx64 Algebra 0 July 2nd, 2008 12:23 AM





Copyright © 2018 My Math Forum. All rights reserved.