Combinatorical Function - VB.NET style.

Iceplug
12-21-2003, 02:47 PM
See this thread for MathImagics' details on the Combinational Formula.
http://www.visualbasicforum.com/t129902.html

It is quite fast. ;)
Public Class Combinational_FormulaOpt
'...
Public Shared Function ChooseFromTwo(ByVal N As Long, ByVal K As Long) As Decimal
'The decimal can hold up to 79 octillion
Dim FactorCount As Long = System.Math.Min(K, N - K)
'This is the number of entries to factor[ (5 2) = 2; (5 3) = 2; (5 4) = 1; ]
K = N - FactorCount 'The lowest distance that K is from N and 0.
Dim UpperSet(FactorCount), LowerSet(FactorCount) As Long
'The lowerset will hold the numbers from 1 to FactorCount, which is N-K
'The upperset will hold the numbers from K+1 to K+N-K = N.
Dim LV, IV, GCD As Integer, Verified As Boolean = True
'LV and IV are loop values,
'GCD will hold our greatest common divisor
'Verified makes sure that our values in the denominator are eliminated

'Set up our factor array.
UpperSet(1) = K + 1
For LV = 2 To FactorCount
LowerSet(LV) = LV
UpperSet(LV) = K + LV
Next

For LV = FactorCount To 2 Step -1 'No need to check 1.
If LowerSet(LV) > 1 Then
For IV = 1 To FactorCount
GCD = GreatestCommonDivisor(LowerSet(LV), UpperSet(IV))
If GCD > 1 Then
UpperSet(IV) /= GCD
LowerSet(LV) /= GCD
End If
Next
End If
Verified = Verified AndAlso (LowerSet(LV) <= 1)
Next

If Not Verified Then
MessageBox.Show("Failed reduction of factors.", "Choosing Failed", MessageBoxButtons.OK, MessageBoxIcon.Exclamation)
Else
Try
ChooseFromTwo = Convert.ToDecimal(UpperSet(1))
For LV = 2 To FactorCount
If UpperSet(LV) > 1 Then
ChooseFromTwo *= Convert.ToDecimal(UpperSet(LV))
End If
Next
Catch ex As System.OverflowException
If Verified Then
MessageBox.Show("Answer overflows!", "Choose Failed", MessageBoxButtons.OK, MessageBoxIcon.Exclamation)
Else
MessageBox.Show("Answer unobtainable! ", "Choose Failed", MessageBoxButtons.OK, MessageBoxIcon.Exclamation)
End If
End Try
End If
End Function

Public Shared Function GreatestCommonDivisor(ByVal Num1 As Decimal, ByVal Num2 As Decimal) As Decimal
Dim X As Decimal = System.Math.Max(Num1, Num2) 'X is the maximum of the two numbers.
Dim Y As Decimal = System.Math.Min(Num1, Num2) 'Y is the minimum of the two numbers.
Dim Remainder As Decimal = X Mod Y 'Remainder always holds the remainder.
'Method:
'Ra Rb Rc
'X = Q0 * Y + R0; Q# is quotient of X/Y, R# = remainder of X/Y
'Y = Q1 * R0 + R1; Since we have Mod, there's no need to calculate Q#
'R0 =Q2 * R1 + R2

'etc...

'Ra =Qc * Rb + Rc; a + 2 = b + 1 = c
'where Rc = 0, Rb is the GCD
Do Until Remainder = 0
X = Y 'Pass Rb into Ra
'Y is smaller than X at the beginning
Y = Remainder 'Pass Rc into Rb
'Remainder cannot be larger than the dividend or the divisor (than X or Y)
Remainder = X Mod Y
Loop
'Extract our GCD
Return Y
End Function

End Class

EZ Archive Ads Plugin for vBulletin Copyright 2006 Computer Help Forum