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

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