an interesting subject. has anyone tried the examples in Paul's link?
I just wondered how long they would take to run for big numbers? I expected you would have to find prime factors, but the examples seem to be doing something else.
Yes ! That is what the Greatest Common Divisor is about right?
Wikipedia said:
In mathematics, the greatest common divisor, also known as the greatest common factor, highest common factor, or greatest common measure, of two or more integers, is the largest positive integer that divides the numbers without a remainder. Wikipedia
offhand, I expected to see each number being turned into prime factors, and then the common prime factors being multiplied together to find the GCD.
as extracting prime factors from very large numbers is non-trivial (I would have thought), I expected this to be very difficult for large numbers - but the recursive examples make it seem deceptively simple.
If there is a usable function in Excel, then I believe you can use it in Access. But... seeing as you need to examine a range, I'm not so sure you could use this particular function in MS Access.
Please post your Excel spreadsheet that does this.
Public Function gcd(a() As Long) As Long
Dim i as integer
i = 0
gcd = 0
Do Until i > UBound(a())
x = gcd
y = a(i)
Do
If x > y Then z = x: x = y: y = z 'swap the values so avoid tediously repeating code
If x = 0 Then
gcd = y
Else
y = y Mod x
End If
Loop Until x = 0
i = i + 1
Loop
End Function
Example test...
Code:
Public Sub test()
Dim a(4) As Long
a(0) = 2077
a(1) = 4557
a(2) = 806
a(3) = 23529
Debug.Print gcd(a())
End Sub
I realize that this is an old post and all, but this is still one of the first results when you search Google on how to do this and I came to an answer that satisfied me through this thread.
I used the function in that link from rosettacode.org that pr2-eugin posted and tested it; seems to work, but I tried to use it with numbers such as 2147474627 and 2147474843 (primes), then 2147474626 and 214747484 (composites), then 2147474627 and 214747484 (a prime and a composite). I made a simple test assigning the result to a long variable; I looped only 10 times and it took around 5 seconds to complete (I didn't measure it exactly).
But then I had another idea: why not try to adapt one of the other functions? So I adapted the VBScript function (the syntax is almost the same after all), with a minimum change (since I don't like to break loops with an exit).
The code worked perfectly, and in the same tests it took around 6 seconds (once again, not exactly measured) to complete... 10 MILLION RUNS! Yes, the difference between one way and the other is abysmal.
Here's how I did it:
Code:
Public Function fGCD(ByVal lngFirstNumber As Long, ByVal lngSecondNumber As Long) As Long
Dim lngMod As Long
fGCD = 0
While fGCD = 0
lngMod = lngFirstNumber Mod lngSecondNumber
If lngMod > 0 Then
lngFirstNumber = lngSecondNumber
lngSecondNumber = lngMod
Else
fGCD = lngSecondNumber
End If
Wend
End Function
**********************************************
Edit: Now that I realized it, this function works more or less the same as what stopher wrote, but not exactly. To do it with many numbers, the thing with the GCD is that it works recursively. That is:
GCD(a, b, c, d) = GCD(a, GCD(b, GCD(c, d)))
Stopher's answer combines the code I wrote above with that fact. So I tried four different things, once again, 10 million runs, this time with the 4 numbers provided by stopher: 2077, 4557, 806 and 23529
1) Stopher's function; it took 25 seconds
2) Stopher's function with a little correction: the example sub should be "Dim a(3) as Long" instead of "Dim a(4) as Long"; it took 23 seconds
3) This function:
Code:
Public Function fGCDMulti(ByRef lngValues() As Long) As Long
Dim intCounter As Integer
For intCounter = LBound(lngValues) To UBound(lngValues) - 1
fGCDMulti = fGCD(lngValues(intCounter), lngValues(intCounter + 1))
Next
End Function
It's simply a function that takes a long array as input to call the other function as many times as needed. It's the best option if you don't know which numbers you'll use, since you'll retrieve them and store them in variables. Also, it allows you to separate between a function that will take many numbers from an array (fGCDMulti) and a function that you can call when you have only 2 numbers to compare (fGCD). You can call it (only once, of course) like this:
Code:
Public Sub test()
Dim a(3) As Long
a(0) = 2077
a(1) = 4557
a(2) = 806
a(3) = 23529
Debug.Print fGCDMulti(a())
End Sub
It took 14 seconds when called 10 million times.
4) The fastest way was to simply call "fGCD(2077, fGCD(4557, fGCD(806, 23529)))"; it took 7 seconds to run 10 million times in my test. Of course, the disadvantage is that it requires you to know exactly which numbers you'll be using.
In short, stopher's way works, although mine might be a little bit faster.
Public Function gcd(lngA As Long, lngB As Long) As Long
' Greatest Common Divider
' Euclides algorithme
If lngB = 0 Then
gcd = lngA
Else
gcd = gcd(lngB, lngA Mod lngB)
End If
End Function
