GCD & LCM: ANALYSIS TOOLPAK

[matt dunbar]

Hi

the analysis Toolpak provides GCD and LCM and are great but some
colleagues in other schools when using my educational XL files cant
install the Toolpak due to network restrictions

is there a way of doing away with the need for the Toolpak to do GCD and
LCM and writing some formualae within a few Excel cells (not a VBA
macro) to find the GCD and LCM dynamically as my data set of 2, 3 and 4
numbers is randomly changing

a challenging math problem!!

TIA

matt

 

[Matt Dunbar]

BTW

i know that for 2 numbers the following works which is great

=MAX(A1:A2)*LEFT(TEXT(MIN(A1:A2)/MAX(A1:A2),"000000000000000/000000000000000"),15)

but i have to cope with 2 or 3 or 4 numbers also

mat

 

[Erich Neuwirth]

Put the 2 numbers on top of each other.
In the cell below put
=MOD(number above, number 2 rows above), and copy the formula
down a few cells.
In the end, you will get division by zero.
The last nonzero number in this column is the GCD.
The product of the 2 numbers divided by the GCD is the LCM.
For 3 numbers, the GCD is the GCD of the gcd of the first two
with the third number, and so on.
Likewise, the LCM of 3 numbers is the LCM of the LCM of the first two
with the third number.


If you are interested in math with spreadsheets,
you migth want to have a look at out book:

The Active Modeler - Mathematical Modeling with Microsoft Excel
Erich Neuwirth - University of Vienna (Austria)
Deane Arganbright - University of Tennessee, Martin
ISBN 0534420850
http://www.amazon.com/exec/obidos/t...002-2501675-2964003?v=glance&s=books&n=507846

 

[Michael Bednarek]

the analysis Toolpak provides GCD and LCM and are great but some
colleagues in other schools when using my educational XL files cant
install the Toolpak due to network restrictions

is there a way of doing away with the need for the Toolpak to do GCD and
LCM and writing some formualae within a few Excel cells (not a VBA
macro) to find the GCD and LCM dynamically as my data set of 2, 3 and 4
numbers is randomly changing

a challenging math problem!!

You've got me intrigued. After a bit of googling, one of the first
links <http://www.geocities.com/SiliconValley/Garage/3323/aat/a_eucl.html>
provided the following insights. Let me know if the code works.

Apparently, good old Euclid came up with this theorem:
GCD(A,B)=GCD(B,A Mod B)
which in VBA looks like:

===== Start: EuclidGCD =====
Function EuclidGCD(a As Variant, b As Variant) As Long

' Source: Knuth D. E., Seminumerical Algorithms, vol. 2 of The Art of Computer Programming
' Addison-Wesley, 1973
' as found at <http://www.geocities.com/SiliconValley/Garage/3323/aat/a_eucl.html>

If b = 0 Then
EuclidGCD = a
Else
EuclidGCD = EuclidGCD(b, a Mod b)
End If
End Function
===== End: EuclidGCD =====

As we have to deal with more than just a pair of values, I wrote
this wrapper:

===== Start: myGCD =====
Function myGCD(a As Variant) As Long

' Wrapper to pass elements of an array to EuclidGCD [[email protected]]

Dim i As Long
Dim x As Long

x = EuclidGCD(a(LBound(a)), a(LBound(a) + 1))
For i = LBound(a) + 1 To UBound(a)
x = EuclidGCD(a(i), x)
Next i
myGCD = x
End Function
===== End: myGCD =====

Tho test it, I used this:

===== Start: testmyGCD =====
Sub testmyGCD() ' Test the function myGCD()
Dim a() As Variant
a = Array(n1, n2, ...) ' You populate it
Debug.Print myGCD(a)
End Sub
===== Start: testmyGCD =====

As for LCM, Euclid observed that:
LCM(A,B)=A * B / GCD(A, B)
which in VBA looks like:

===== Start: EuclidLCM =====
Function EuclidLCM(a As Variant, b As Variant) As Long

' Source: Knuth D. E., Seminumerical Algorithms, vol. 2 of The Art of Computer Programming
' Addison-Wesley, 1973
' as found at <http://www.geocities.com/SiliconValley/Garage/3323/aat/a_eucl.html>

EuclidLCM = a * b / EuclidGCD(a, b)
End Function
===== End: EuclidLCM =====

Again, to accommodate more than a single pair, I wrote this wrapper:

===== Start: myLCM =====
Function myLCM(a As Variant) As Long

' Wrapper to pass elements of an array to EuclidGCD() [[email protected]]

Dim i As Long
Dim x As Long

x = EuclidLCM(a(LBound(a)), a(LBound(a) + 1))
For i = LBound(a) + 1 To UBound(a)
x = EuclidLCM(a(i), x)
Next i
myLCM = x
End Function
===== End: myLCM =====

To test this, I had:

===== Start: testmyLCM =====
Sub testmyLCM() ' Test the function myLCM()
Dim a() As Variant
a = Array(n1, n2, ...) ' You populate it
Debug.Print myLCM(a)
End Sub
===== End: testmyLCM =====

The code is only superficially tested. I know it's prone to
overflows. It does no parameter checking. Good luck.

 

[Dana DeLouis]

You've got me intrigued. After a bit of googling, ...

Hi Michael. Just to add to your excellent GCD program. I though you might
be interested in seeing just another version. This version uses a loop
instead of recursive calls. Here I like to use what I call a "poor-man's"
version of parallel assignments.

Function GCD(a, b)
' = = = = = = = = = =
'// Greatest Common Divisor
'// By: Dana DeLouis
' = = = = = = = = = =
Dim v As Variant
v = Array(a, b)
Do While v(1) <> 0
v = Array(v(1), v(0) Mod v(1))
Loop
GCD = v(0)
End Function

Stolen from someone long ago...
"To understand recursion, you must first understand recursion."

HTH
Dana DeLouis

You've got me intrigued. After a bit of googling, one of the first
links <http://www.geocities.com/SiliconValley/Garage/3323/aat/a_eucl.html>
provided the following insights. Let me know if the code works.

Apparently, good old Euclid came up with this theorem:
GCD(A,B)=GCD(B,A Mod B)
which in VBA looks like:

===== Start: EuclidGCD =====
Function EuclidGCD(a As Variant, b As Variant) As Long

' Source: Knuth D. E., Seminumerical Algorithms, vol. 2 of The Art of Computer Programming
' Addison-Wesley, 1973
' as found at

If b = 0 Then
EuclidGCD = a
Else
EuclidGCD = EuclidGCD(b, a Mod b)
End If
End Function
===== End: EuclidGCD =====

As we have to deal with more than just a pair of values, I wrote
this wrapper:

===== Start: myGCD =====
Function myGCD(a As Variant) As Long

' Wrapper to pass elements of an array to EuclidGCD [[email protected]]

Dim i As Long
Dim x As Long

x = EuclidGCD(a(LBound(a)), a(LBound(a) + 1))
For i = LBound(a) + 1 To UBound(a)
x = EuclidGCD(a(i), x)
Next i
myGCD = x
End Function
===== End: myGCD =====

Tho test it, I used this:

===== Start: testmyGCD =====
Sub testmyGCD() ' Test the function myGCD()
Dim a() As Variant
a = Array(n1, n2, ...) ' You populate it
Debug.Print myGCD(a)
End Sub
===== Start: testmyGCD =====

As for LCM, Euclid observed that:
LCM(A,B)=A * B / GCD(A, B)
which in VBA looks like:

===== Start: EuclidLCM =====
Function EuclidLCM(a As Variant, b As Variant) As Long

' Source: Knuth D. E., Seminumerical Algorithms, vol. 2 of The Art of Computer Programming
' Addison-Wesley, 1973
' as found at

EuclidLCM = a * b / EuclidGCD(a, b)
End Function
===== End: EuclidLCM =====

Again, to accommodate more than a single pair, I wrote this wrapper:

===== Start: myLCM =====
Function myLCM(a As Variant) As Long

' Wrapper to pass elements of an array to EuclidGCD() [[email protected]]

Dim i As Long
Dim x As Long

x = EuclidLCM(a(LBound(a)), a(LBound(a) + 1))
For i = LBound(a) + 1 To UBound(a)
x = EuclidLCM(a(i), x)
Next i
myLCM = x
End Function
===== End: myLCM =====

To test this, I had:

===== Start: testmyLCM =====
Sub testmyLCM() ' Test the function myLCM()
Dim a() As Variant
a = Array(n1, n2, ...) ' You populate it
Debug.Print myLCM(a)
End Sub
===== End: testmyLCM =====

The code is only superficially tested. I know it's prone to
overflows. It does no parameter checking. Good luck.