Talk:Greatest common divisor
From Wikipedia, the free encyclopedia
 |
|||||||||||||||||||||||
| Mathematics rating: | Start Class | High Priority | Field: Number theory | ||||||||||||||||||||
| One of the 500 most frequently viewed mathematics articles. | |||||||||||||||||||||||
|
|||||||||||||||||||||||
- I don't know about you, but as far as I know (and forgive my Year 11 barin) in West Australian schools at least, this is known as the 'Highest Common Factor', not 'Greatest Common Divisor' - Mark Ryan
- True... and its not just WA, its NSW (and VIC i think) as well -- in primary and high school they call it a HCF... but get to university, and they call it a GCD... I think GCD is the proper maths term, and HCF is just something the teaching profession in Australia invented, because they thought it would be easier to understand than GCD... -- SJK
- When I was taught this in a British school, it was referred to as highest common factor, so this alternative nomenclature is not exclusive to Australia. It seems odd that nobody calls it greatest common factor or highest common divisor. Furby100 02:58, 31 May 2007 (UTC)
- When analyzing the runtime of Euclid's algorithm, it turns out that the inputs requiring the most steps are two successive Fibonacci numbers, and the worst case runtime is O(n), where n is the number of digits in the input (see Big O).
That's the case in Modified Euclid's Algorithm (with division modulo), not in Original Euclid's Algorithm (with subtraction). --Taw
What's this GCD algorithm called ? --Taw
def bgcd(a,b)
g=0
while(a&1==0 && b&1==0)
g++
a>>=1
b>>=1
end
while b!=0
if a&1 == 0
a>>=1
elsif b&1 == 0
b>>=1
else
if (a>b)
a-=b
a>>=1
else
b-=a
b>>=1
end
end
end
return a<<g
end
I don't know, but it is cool. Runtime is O(lg(n)); I wonder if it is faster than the ordinary division method? (I changed one line to make it a tiny bit simpler.) --AxelBoldt
It's much faster on most hardware because it doesn't use these slow modulo divisions, only ultra-fast shifts and substractions. If we're simplifying, here's an additional simplification. --Taw
Changed a multiplication to a bitshift. Also (I had to stare at it for a second to notice), the above algorithm loops infinitely if a is 0. So implementors beware; either don't pass a=0 in or add a check for it (what is GCD(0,n) and GCD(0,0) defined as anyway?) --JCipriani
- GCD(0,n)=n for n>0 to the extent it is meaningful; GCD(0,0) is undefined or infinite. --Henrygb 11:44, 22 May 2006 (UTC)
Contents |
[edit] Quicker GCD method
There is a possible quicker way to calculate Greatest Common Divisor at least on a computer anyway. This is because division by 2 in a computer is one of the quickest operations. The base ideas behind this algorithm are shown on the following link im not sure what the time complexity is but it should run faster. [1]
- This person is actually talking about the exact same algorithm detailed above. It's the "binary GCD" algorithm, also described at [2] (which gives a link to the cut-the-knot.org) page. --JCipriani
[edit] Examples of no gcd
Would this article be the right place to put an example of an integral domain with two elements that don't have a gcd?
I think of this example:
![R = \mathbb{Z}[\sqrt{-3}], a = 4 = 2\cdot 2 = (1+\sqrt{-3})(1-\sqrt{-3}), b = (1+\sqrt{-3})\cdot 2](../../../../math/5/8/3/58364e1d53d1add0f16ae13404c78483.png)
where 
and 2 are two "maximal common divisors" but they are not associated, so there is no greatest common divisor.
--SirJective 17:40, 25 Nov 2004 (UTC)
- I now inserted the example. --SirJective 22:53, 26 Jan 2005 (UTC)
[edit] greatest common denominator
KneeLess wrote:
- rv, a denominator IS a divisor, just another name.
You are of course right! What you are not right about is saying that a greatest common divisor is a greatest common denominator.
For example, I give you two integers, 6 and 9. Their greatest common divisor if of course 18. How about their greatest common denominator? There is none, because there are no denominators and no fractions around whatsoever.
So, I explained in my edit summary, the greatest common divisor is a more general thing than the greatest common denonminator. They coincide only when we talk about fractions, but the notion of greatest common divisor has meaning way beyond that. As such, these concepts are not equivalent, and are not synonimous. Oleg Alexandrov 16:56, 2 Apr 2005 (UTC)
- Oh, I see. Thanks for actually telling me what the problem is, instead of having a revert war. I did make a redirect from Greatest common denominator to this article, is that a problem? -- KneeLess 18:42, 2 Apr 2005 (UTC)
-
- No revert wars (TM) :) The redirect is all right. Oleg Alexandrov 18:53, 2 Apr 2005 (UTC)
-
-
- Actually we were both wrong. Greatest common divisor of 6 and 9 is 3. We meant the least common multiple, which for 6 and 9 is 18. Oleg Alexandrov 19:29, 2 Apr 2005 (UTC)
-
[edit] Error in property
It is stated in the page that:
If m is any integer, then gcd(m·a, m·b) = m·gcd(a, b) and gcd(a + m·b, b) = gcd(a, b). If m is a nonzero common divisor of a and b, then gcd(a/m, b/m) = gcd(a, b)/m.
However, this is only true if m is a non-negative integer, since gcd is a non-negative integer.
Example: -1 x gcd(a,b) =< 0 , but, gcd(-a,-b) >= 0.
jff 13:46, 26 September 2006 (UTC)
[edit] Can you find it by scientific calculator?
Is there a function for finding the GCD in a calculator? The current way takes too much time, guessing which two/three numbers...etc.--80.227.100.62 09:42, 13 November 2006 (UTC)
- You can use the Euclidean_algorithm. You don't even need a scientific calculator for that. There is no quick and easy formula. In the future, please ask questions at the wikipedia reference desk [3]. Article discussion pages are meant for discussions concerning the article, not the subject. S Sepp 23:23, 13 November 2006 (UTC)
[edit] removing the link to Greatest common divisor of two polynomials
i removed this link because the referenced article talks about some tricks from "vedic mathematics" to calculate the the gcd of some simple polynomials. this "vedic mathematics" cannot be found in the mathematical literature (see http://www.sacw.net/DC/CommunalismCollection/ArticlesArchive/NoVedic.html)
[edit] Lowest common factor
Why does lowest common factor redirect here? As I understand it, the lowest common factor between two natural numbers will always be 1. This is completely different from the highest common factor/greatest common divisor. Furby100 02:59, 31 May 2007 (UTC)
