I wrote this VB implementation of BigInt, and I like it, so thought it might be helpful. It can't handle truly gigantic numbers like graham's number, but it can calculate the volume of the universe in planck-lengths (+/- 1) in about 3 milliseconds, and thus seems suitable for most practical big-number applications. It's accurate for addition, subtraction, multiplication, integral division, Log2, and Shifting. Examples are at the top, feel free to reuse this code in any way you please. If you like it, and you work for Googol, hire me :)
Public Structure BigInt
Public Shared Function U() As BigInt 'Volume of the universe in planck-lengths
Dim lRet As BigInt = New BigInt(10) ^ 35 'Planck-lengths per meter
lRet = (lRet * 30000000) * 13700000 * (60 * 60 * 24 * 365) ' Diameter of Observable Universe in planck-lengths
lRet = BigInt.TimesPi((lRet ^ 3) * 4) \ 3 ' Volume of the universe in Plank-lengths
Return lRet
End Function
Public Shared Function TimesPi(pBigInt As BigInt) As BigInt
Dim lOp As BigInt
'Just a handy rational approximation of Pi, in hex for performance
Dim lSignificantDigits = (pBigInt.Log2 \ 4) + 3
'lOp = BigInt.FromBase10("1901870728566923076090143944714770339621590768313546337192526115562704339680963564320007808107929370299752345187688835741387003036853361285671158059867702399073227994426905220194699766118756059055619036488502928002591")
'Debug.Print("Multiple=" & BigInt.ToBase16(lOp))
lOp = BigInt.FromBase16(Left("5845B0A4C43FF041EE3CB64FE4AC283EC160121098D69A6E811E20511E3AE9B57DF4090D8855B3DC8BD649FA3756935283A0022779248D97ADD33C6B0BEAC74973DC124A3E1F0DBD6937F0E9E6975FF3C1C556B02A38ED94CE1F", lSignificantDigits))
Dim lRet As BigInt = pBigInt * lOp
'lOp = BigInt.FromBase10("605384255146420326102361023215940531716391478150345020739231253172134740688232476946000058713774549796561447468267746412874022717544100946587144148739626803435133473281606663121381125761746030151344353855924025288111")
'Debug.Print("Multiple=" & BigInt.ToBase16(lOp))
lOp = BigInt.FromBase16(Left("1C1911716363228A62BB598F0ACD9C1565D39E10D84CE34459AF8E7B7C871CF668B48356882A8239FC1FD6523E3B273E5232C420D9CB5564A5A2D1E571BD2D4ED25995EB9B7B06A9721C4929034443808B4F399D6714F9F1E5AF", lSignificantDigits))
'Debug.Print("Dividend=" & BigInt.ToBase16(lOp))
lRet = lRet \ lOp
Return lRet
End Function
Public Shared Function TestTimesPi(pReps As Integer) As Double
Dim lOp As BigInt
Dim lBigInt As BigInt = U()
Dim lEnd As Double
Dim lRet As BigInt
Dim lStart As Double = Microsoft.VisualBasic.Timer
For i As Integer = 1 To pReps
lRet = TimesPi(lBigInt)
Next i
lEnd = Microsoft.VisualBasic.Timer
Debug.Print(lEnd - lStart & " seconds for " & pReps & " pi calculations")
Return lEnd - lStart
End Function
Private mBytes As List(Of Byte)
Private mIsNegative As Boolean
Public Function IsEven() As Boolean
Return Not IsOdd()
End Function
Public Function IsOdd() As Boolean
If IsZero() Then Return False Else Return mBytes(0) And 1
End Function
Public Function Abs() As BigInt
Dim lRet As New BigInt
lRet.mBytes = New List(Of Byte)
lRet.mBytes.AddRange(mBytes)
lRet.Normalize()
Return lRet
End Function
Public Sub Normalize()
If mBytes Is Nothing Then
mIsNegative = False
Exit Sub
End If
If mBytes.Count > 0 Then
While mBytes(mBytes.Count - 1) = 0
mBytes.RemoveAt(mBytes.Count - 1)
End While
End If
If (mBytes.Count = 0) Then
mIsNegative = False
End If
End Sub
Public Sub New(pVal As Long)
If pVal < 0 Then
mIsNegative = True
pVal = -pVal
End If
mBytes = New List(Of Byte)
While pVal > 0
Dim lByte As Byte = pVal And 255
mBytes.Add(lByte)
pVal = pVal >> 8
End While
'No need to normalize this
End Sub
Public Sub New(pBigInt As BigInt)
mBytes = New List(Of Byte)
mBytes.AddRange(pBigInt.mBytes.ToArray)
mIsNegative = pBigInt.mIsNegative
Normalize()
End Sub
Public Shared Operator -(ByVal class1 As BigInt) As BigInt
Dim lRet As New BigInt(class1)
lRet.mIsNegative = Not lRet.mIsNegative
lRet.Normalize()
Return lRet
End Operator
Public Shared Function Compare(ByVal class1 As BigInt, ByVal class2 As BigInt) As Integer
class1.Normalize()
class2.Normalize()
If class1.IsZero Then
If class2.IsZero Then
Return 0
ElseIf class2.mIsNegative Then
Return 1
Else
Return -1
End If
ElseIf class2.IsZero Then
If class1.mIsNegative Then
Return -1
Else
Return 1
End If
ElseIf class1.mIsNegative Then
If class2.mIsNegative Then
Return -Compare(-class1, -class2)
Else
Return -1
End If
ElseIf class2.mIsNegative Then
Return 1
End If
'Handle positive-positive comparison here
Dim iLeft As Integer = class1.mBytes.Count - 1
Dim iRight As Integer = class2.mBytes.Count - 1
While iLeft > iRight
If class1.mBytes(iLeft) <> 0 Then
Return 1
End If
iLeft -= 1
End While
While iRight > iLeft
If class2.mBytes(iRight) <> 0 Then
Return -1
End If
iRight -= 1
End While
While iLeft >= 0
If class1.mBytes(iLeft) < class2.mBytes(iLeft) Then
Return -1
ElseIf class1.mBytes(iLeft) > class2.mBytes(iLeft) Then
Return 1
End If
iLeft -= 1
End While
Return 0
End Function
Public Shared Operator <(ByVal class1 As BigInt, ByVal class2 As BigInt) As Boolean
Select Case Compare(class1, class2)
Case -1
Return True
Case Else
Return False
End Select
End Operator
Public Shared Operator >(ByVal class1 As BigInt, ByVal class2 As BigInt) As Boolean
Select Case Compare(class1, class2)
Case 1
Return True
Case Else
Return False
End Select
End Operator
Public Shared Operator <=(ByVal class1 As BigInt, ByVal class2 As BigInt) As Boolean
Select Case Compare(class1, class2)
Case 0, -1
Return True
Case Else
Return False
End Select
End Operator
Public Shared Operator >=(ByVal class1 As BigInt, ByVal class2 As BigInt) As Boolean
Select Case Compare(class1, class2)
Case 0, 1
Return True
Case Else
Return False
End Select
End Operator
Public Shared Operator =(ByVal class1 As BigInt, ByVal class2 As BigInt) As Boolean
Select Case Compare(class1, class2)
Case 0
Return True
Case Else
Return False
End Select
End Operator
Public Shared Operator <>(ByVal class1 As BigInt, ByVal class2 As BigInt) As Boolean
Select Case Compare(class1, class2)
Case 0
Return False
Case Else
Return True
End Select
End Operator
Public Function IsZero() As Boolean
If mBytes Is Nothing Then Return True
If mBytes.Count = 0 Then Return True
For Each lByte In mBytes
If lByte <> 0 Then Return False
Next
Return True
End Function
Public Shared Operator +(ByVal class1 As BigInt, ByVal class2 As Long) As BigInt
Return class1 + New BigInt(class2)
End Operator
Public Shared Operator +(ByVal class1 As BigInt, ByVal class2 As BigInt) As BigInt
If class1.mBytes Is Nothing Then Return class2
If class2.mBytes Is Nothing Then Return class1
Dim lBytes1 As Integer = class1.mBytes.Count
Dim lBytes2 As Integer = class2.mBytes.Count
Dim lBytes As New List(Of Byte)
Dim lRemainder As Byte = 0
Dim i As Integer = 0
Dim lZeros As Integer = 0
While (i < lBytes1) Or (i < lBytes2) Or (lRemainder <> 0)
Dim lByte1 As Integer = 0
Dim lByte2 As Integer = 0
Dim lTemp As Integer = 0
If i < lBytes1 Then lByte1 = class1.mBytes(i)
If i < lBytes2 Then lByte2 = class2.mBytes(i)
lTemp = lByte1 + lByte2 + lRemainder
lRemainder = 0
If lTemp > 255 Then
lRemainder = lTemp \ 256
lTemp -= 256 * lRemainder
End If
lBytes.Add(lTemp)
If lTemp = 0 Then lZeros += 1 Else lZeros = 0
i += 1
End While
While lZeros > 0
lBytes.RemoveAt(lBytes.Count - 1)
lZeros -= 1
End While
Dim lRet As New BigInt
lRet.mBytes = lBytes
Return lRet
End Operator
Public Shared Operator -(ByVal class1 As BigInt, ByVal class2 As Long) As BigInt
Return class1 - New BigInt(class2)
End Operator
Public Shared Operator -(ByVal class1 As BigInt, ByVal class2 As BigInt) As BigInt
Dim lResultIsNegative As Boolean
Dim lLeft As BigInt
Dim lRight As BigInt
class1.Normalize()
class2.Normalize()
If class1.mIsNegative Then
If class2.mIsNegative Then
Return -(class1.Abs + class2.Abs)
Else
Return class1.Abs + class2
End If
ElseIf class2.mIsNegative Then
Return class1 + class2.Abs
End If
Select Case Compare(class1, class2)
Case 0
Return New BigInt(0)
Case -1
lResultIsNegative = True
lLeft = class2
lRight = class1
Case 1
lResultIsNegative = False
lLeft = class1
lRight = class2
Case Else
Throw New InvalidOperationException("BigInt.vb encountered an invalid result when comparing numbers.")
End Select
'Left is bigger than right, switch sign at the end if indicated
Dim lBorrow As Integer = 0
Dim lRet As New BigInt(0)
For i As Integer = 0 To lLeft.mBytes.Count - 1
Dim iLeft As Integer
Dim iRight As Byte
iLeft = lLeft.mBytes(i) - lBorrow
If i >= lRight.mBytes.Count Then
iRight = 0
Else
iRight = lRight.mBytes(i)
End If
lBorrow = 0
While iLeft < iRight
lBorrow += 1
iLeft += 256
End While
lRet.mBytes.Add(iLeft - iRight)
Next
lRet.mIsNegative = lResultIsNegative
lRet.Normalize()
Return lRet
End Operator
Public Shared Function GrahamNotation(pBase As Integer, pArrows As Integer, pHeight As Integer) As BigInt
Return GrahamNotation(New BigInt(pBase), pArrows, New BigInt(pHeight))
End Function
Public Shared Function GrahamNotation(pBase As BigInt, pArrows As Integer, pHeight As BigInt) As BigInt
If pArrows > 1 Then
Return GrahamNotation(pBase, pArrows - 1, GrahamNotation(pBase, 1, pHeight))
End If
Dim lRet As BigInt = pBase
lRet = pBase ^ pHeight
'lRet = lRet ^ (pHeight - 1)
Return lRet
End Function
Public Shared Operator *(ByVal class1 As BigInt, pByte As Byte) As BigInt
Dim lBytes1 As Integer = class1.mBytes.Count
Dim lOutBytes As New List(Of Byte)
Dim lCarry As Long = 0
For i = 0 To lBytes1 - 1
Dim lTemp As Long = (CLng(class1.mBytes(i)) * pByte) + lCarry
lCarry = 0
If lTemp > 255 Then
lCarry = lTemp \ 256
lTemp = lTemp Mod 256
End If
lOutBytes.Add(CByte(lTemp))
Next
'While lCarry > 255
If lCarry > 255 Then
lOutBytes.Add(CByte(lCarry Mod 256))
lCarry = lCarry \ 256
End If
'End While
If lCarry > 0 Then lOutBytes.Add(CByte(lCarry))
Dim lRet As New BigInt
lRet.mBytes = lOutBytes
lRet.mIsNegative = class1.mIsNegative
Return lRet
End Operator
Public Shared Operator ^(ByVal class1 As BigInt, class2 As BigInt) As BigInt
class2.Normalize()
If class2.IsZero Then Return New BigInt(1)
If class2 = New BigInt(1) Then Return class1
Dim lIsNegative As Boolean = False
If class1.mIsNegative AndAlso (class2.mBytes(0) And 1) Then lIsNegative = True
Dim lPow As New BigInt(class2)
Dim lBase As New BigInt(class1)
Dim l1 As New BigInt(1)
Dim lSuperpow As New BigInt(l1)
Dim lMultiplier As New BigInt(l1)
Dim l2 As New BigInt(2)
While lPow > l2
If lPow.IsOdd Then
lPow -= l1
lMultiplier = lMultiplier * (lBase ^ lSuperpow)
Else
lPow = lPow >> 1
lSuperpow = lSuperpow << 1
End If
End While
lBase = lBase ^ lSuperpow
If lPow = l2 Then lMultiplier = lMultiplier * lBase
lBase = lBase * lMultiplier
'If lSuperpow > l1 Then lBase = lBase ^ lSuperpow
Return lBase
End Operator
Public Shared Operator ^(ByVal class1 As BigInt, class2 As Integer) As BigInt
Return class1 ^ New BigInt(class2)
End Operator
Public Shared Operator *(ByVal class1 As BigInt, class2 As Long) As BigInt
Return class1 * New BigInt(class2)
End Operator
Public Shared Operator *(ByVal class1 As BigInt, class2 As BigInt) As BigInt
Dim lTop As BigInt
Dim lBottom As BigInt
class1.Normalize()
class2.Normalize()
If class1.IsZero Or class2.IsZero Then Return New BigInt(0)
Dim lResultIsNegative As Boolean = class1.mIsNegative Xor class2.mIsNegative
If class1.mBytes.Count < class2.mBytes.Count Then
lTop = class2
lBottom = class1
Else
lTop = class1
lBottom = class2
End If
Dim lRunningTotal As New BigInt
For i = 0 To lBottom.mBytes.Count - 1
Dim lAdditive As BigInt = lTop * CByte(lBottom.mBytes(i))
For j = 1 To i
lAdditive.mBytes.Insert(0, CByte(0))
Next
lRunningTotal += lAdditive
Next
lRunningTotal.mIsNegative = lResultIsNegative
lRunningTotal.Normalize()
Return lRunningTotal
End Operator
Public Shared Function PowerOf2(pPower As Integer) As BigInt
Dim lRet As BigInt = New BigInt(1) << (pPower - 1)
Return lRet
End Function
Private Shared mPowersOf10 As Dictionary(Of Integer, BigInt)
Public Shared Function ClearCachedPowers()
If mPowersOf10 IsNot Nothing Then
mPowersOf10.Clear()
End If
End Function
Public Shared Function PowerOf10(pPower As Integer) As BigInt
If pPower = 0 Then
Return New BigInt(1)
ElseIf pPower = 1 Then
Return New BigInt(10)
ElseIf mPowersOf10.ContainsKey(pPower) Then
Return New BigInt(mPowersOf10(pPower))
Else
mPowersOf10(pPower) = New BigInt(10) ^ pPower
Return New BigInt(mPowersOf10(pPower))
End If
End Function
Public Shared Operator \(ByVal class1 As BigInt, class2 As BigInt) As BigInt
Dim lResult As BigInt = New BigInt(0)
Divide(class1, class2, lResult, New BigInt(0))
Return lResult
End Operator
Public Shared Operator /(ByVal class1 As BigInt, class2 As Long) As BigDecimal1
'Dim lResult As BigDecimal = New BigInt(0)
'Divide(class1, New BigInt(class2), lResult, New BigInt(0))
'Return lResult
End Operator
Public Shared Operator /(ByVal class1 As BigInt, class2 As BigInt) As BigDecimal1
'Dim lResult As BigInt = New BigInt(0)
'Divide(class1, New BigInt(class2), lResult, New BigInt(0))
'Return lResult
End Operator
Public Shared Operator \(ByVal class1 As BigInt, class2 As Long) As BigInt
Dim lResult As BigInt = New BigInt(0)
Divide(class1, New BigInt(class2), lResult, New BigInt(0))
Return lResult
End Operator
Public Shared Operator Mod(ByVal class1 As BigInt, class2 As BigInt) As BigInt
Dim lResult As BigInt = New BigInt(0)
Divide(class1, class2, New BigInt(0), lResult)
Return lResult
End Operator
Public Shared Operator Mod(ByVal class1 As BigInt, class2 As Long) As BigInt
Dim lResult As BigInt = New BigInt(0)
Divide(class1, New BigInt(class2), New BigInt(0), lResult)
Return lResult
End Operator
Public Function ToByte() As Byte
Normalize()
If IsZero() Then Return 0
Return mBytes(0)
End Function
Public Shared Sub SquareTest(pPower As Integer)
Dim lRet As BigInt = (New BigInt(1) << pPower) - New BigInt(1)
Debug.Print(lRet.ToString)
End Sub
Public Shared Sub SpeedTest2()
Dim lBigNum As BigInt = New BigInt(10)
Dim lTime1 As Double = Microsoft.VisualBasic.Timer
lBigNum = lBigNum ^ 1000
Dim lTime2 As Double = Microsoft.VisualBasic.Timer
Debug.Print((lTime2 - lTime1) & " seconds to calculate Googol^10")
lTime1 = Microsoft.VisualBasic.Timer
lBigNum = lBigNum ^ 50
lTime2 = Microsoft.VisualBasic.Timer
Debug.Print((lTime2 - lTime1) & " seconds to raise that to the 50th power")
Debug.Print("The result is " & lBigNum.Log2 & " bits long.")
Debug.Print("Converting to decimal...")
lTime1 = Microsoft.VisualBasic.Timer
Debug.Print(lBigNum.ToString)
lTime2 = Microsoft.VisualBasic.Timer
Debug.Print("Converting to decimal took " & (lTime2 - lTime1) & " seconds.")
End Sub
Public Shared Sub SpeedTest3()
Debug.Print("Generating 3 (arrow) 3")
Dim lTime1 As Double = Microsoft.VisualBasic.Timer
Dim lBigInt = BigInt.GrahamNotation(3, 1, 3)
Dim lTime2 As Double = Microsoft.VisualBasic.Timer
Debug.Print("Time elapsed: " & (lTime2 - lTime1))
Debug.Print(lBigInt.ToString)
Debug.Print("Generating 3 (double-arrow) 3")
lTime1 = Microsoft.VisualBasic.Timer
lBigInt = BigInt.GrahamNotation(3, 2, 3)
lTime2 = Microsoft.VisualBasic.Timer
Debug.Print("Time elapsed: " & (lTime2 - lTime1))
Debug.Print(lBigInt.ToString)
Exit Sub
Debug.Print(lBigInt.mBytes.Count & " bytes")
Debug.Print("Generating 3 (triple-arrow) 2")
lTime1 = Microsoft.VisualBasic.Timer
lBigInt = BigInt.GrahamNotation(3, 3, 2)
lTime2 = Microsoft.VisualBasic.Timer
Debug.Print("Time elapsed: " & (lTime2 - lTime1))
Debug.Print(lBigInt.ToString)
Debug.Print(lBigInt.mBytes.Count & " bytes")
Debug.Print("Generating 3 (triple-arrow) 3")
lTime1 = Microsoft.VisualBasic.Timer
lBigInt = BigInt.GrahamNotation(3, 3, 3)
lTime2 = Microsoft.VisualBasic.Timer
Debug.Print("Time elapsed: " & (lTime2 - lTime1))
Debug.Print(lBigInt.ToString)
Debug.Print(lBigInt.mBytes.Count & " bytes")
End Sub
Public Shared Sub SpeedTest4()
Dim lBigInt As BigInt = GrahamNotation(2, 4, 2)
Debug.Print(lBigInt.ToString)
End Sub
Public Shared Sub SpeedTest()
Dim lTime1 As Double = Microsoft.VisualBasic.Timer
Dim j As Integer
For i = 1 To 1000000
j = j + 1
Next
Dim lTime2 As Double = Microsoft.VisualBasic.Timer
Debug.Print("Integer: " & (lTime2 - lTime1))
Dim k As New BigInt(0)
Dim l1 As New BigInt(1)
For i = 1 To 10000
k = k + l1
Next
lTime1 = Microsoft.VisualBasic.Timer
Debug.Print("BigInt: " & (lTime1 - lTime2))
End Sub
Public Function ToInt16() As Int16
Dim lRet As Int16
If IsZero() Then Return 0
If mBytes.Count > 1 Then lRet = lRet + (CLng(mBytes(1) And 127) << 8)
If mBytes.Count > 0 Then lRet = lRet + mBytes(0)
If mIsNegative Then Return -lRet Else Return lRet
End Function
Public Function ToInt32() As Int32
Dim lRet As Int32
If IsZero() Then Return 0
If mBytes.Count > 3 Then lRet = lRet + (CLng(mBytes(3) And 127) << 24)
If mBytes.Count > 2 Then lRet = lRet + (CLng(mBytes(2)) << 16)
If mBytes.Count > 1 Then lRet = lRet + (CLng(mBytes(1)) << 8)
If mBytes.Count > 0 Then lRet = lRet + mBytes(0)
If mIsNegative Then Return -lRet Else Return lRet
End Function
Private Shared Sub Divide(pDividend As BigInt, pDivisor As BigInt, ByRef pResult As BigInt, ByRef pModulus As BigInt)
pDivisor.Normalize()
If pDivisor.IsZero Then Throw New DivideByZeroException
pDividend.Normalize()
If pDividend.IsZero Then
pResult = New BigInt(0)
pModulus = New BigInt(0)
Exit Sub
End If
Dim lResultIsNegative As Boolean = pDividend.mIsNegative Xor pDivisor.mIsNegative
Dim lDividend As BigInt = pDividend.Abs
Dim lDivisor As BigInt = pDivisor.Abs
Select Case Compare(lDividend, lDivisor)
Case -1
pResult = New BigInt(0)
pModulus = New BigInt(lDividend)
Exit Sub
Case 0
pResult = New BigInt(1)
pModulus = New BigInt(0)
Exit Sub
End Select
' Dividend is greater than divisor
' Multiply the dividend by 256 while
Dim lShift As Integer
Dim lRunningTotal As New BigInt(0)
While Not lDividend.IsZero
If lDividend < lDivisor Then
pModulus = lDividend
pResult = lRunningTotal
Exit Sub
End If
lShift = Math.Truncate(lDividend.Log2_Dbl - lDivisor.Log2_Dbl)
'lShift = Math.Truncate(lDividend.Log2 - lDivisor.Log2)
Dim lTestDivisor As BigInt = lDivisor << lShift
If lTestDivisor > lDividend Then
lTestDivisor = lTestDivisor >> 1
lShift -= 1
End If
lRunningTotal += (New BigInt(1) << lShift)
lDividend -= lTestDivisor
End While
pResult = lRunningTotal
pModulus = New BigInt(0)
Exit Sub
End Sub
Public Shared Operator <<(pBigInt As BigInt, pBits As Integer) As BigInt
Dim lRet As New BigInt(pBigInt)
Dim lBits As Integer = pBits
pBigInt.Normalize()
If lBits >= 8 Then
Dim lInsertBytes((pBits \ 8) - 1) As Byte
lRet.mBytes.InsertRange(0, lInsertBytes)
lBits = lBits Mod 8
End If
If lBits = 0 Then
lRet.Normalize()
Return lRet
End If
Dim lMostSignificantBit As Byte = Log2(lRet.mBytes(lRet.mBytes.Count - 1))
Dim lAvailableBits As Byte = 8 - lMostSignificantBit
If lAvailableBits < lBits Then lRet.mBytes.Add(0)
Dim lMaskLeft As Byte = (1 << (lBits + 1)) - 1
Dim lMaskRight As Byte = Not lMaskLeft
For i = lRet.mBytes.Count - 1 To 1 Step -1
lRet.mBytes(i) = ((lRet.mBytes(i) << lBits) Or (lRet.mBytes(i - 1) >> (8 - lBits))) And 255
Next
lRet.mBytes(0) = (lRet.mBytes(0) << lBits) And 255
Return lRet
End Operator
Public Shared Operator >>(pBigInt As BigInt, pBits As Integer) As BigInt
Dim lRet As New BigInt(pBigInt)
Dim lBits As Integer = pBits
pBigInt.Normalize()
If lBits >= 8 Then
lRet.mBytes.RemoveRange(0, pBits = 8)
lBits = lBits Mod 8
End If
If lBits = 0 Then
lRet.Normalize()
Return lRet
End If
Dim lMostSignificantBit As Byte = Log2(lRet.mBytes(lRet.mBytes.Count - 1))
Dim lAvailableBits As Byte = 8 - lMostSignificantBit
If lAvailableBits < lBits Then lRet.mBytes.Add(0)
Dim lMaskLeft As Byte = (1 << (lBits + 1)) - 1
Dim lMaskRight As Byte = Not lMaskLeft
For i = 0 To lRet.mBytes.Count - 2
lRet.mBytes(i) = ((lRet.mBytes(i) >> lBits) Or (lRet.mBytes(i + 1) << (8 - lBits))) And 255
Next
lRet.mBytes(lRet.mBytes.Count - 1) = (lRet.mBytes(lRet.mBytes.Count - 1) >> lBits) And 255
Return lRet
End Operator
Public Function Log2() As Long
Normalize()
If IsZero() Then Return 0
Return ((mBytes.Count - 1) * 8) + Log2(mBytes(mBytes.Count - 1))
End Function
Public Function Log2_Dbl() As Double
Normalize()
If IsZero() Then Return 0
Dim lBits As Integer = (mBytes.Count - 1) * 8
Dim lDivisor As Double = 1
Dim lRunningTotal As Double = lBits + Log2_Dbl(mBytes(mBytes.Count - 1))
For i = mBytes.Count - 2 To Math.Max(mBytes.Count - 8, 0) Step -1
lDivisor = lDivisor * 256
lRunningTotal += (CDbl(Log2_Dbl(mBytes(i))) / lDivisor)
Next
Return lRunningTotal
End Function
Public Overrides Function ToString() As String
Return BigInt.ToBase10(Me)
End Function
Public Shared Function ToBaseX(pBigInt As BigInt, pBase As Byte) As String
If pBase < 2 Then Throw New ArgumentException("Cannot display as base less than 2")
If pBase > 2 Then Throw New ArgumentException("Cannot display as base greater than 16")
pBigInt.Normalize()
If pBigInt.IsZero Then Return "0"
Dim aChars() As Char = {"0", "1", "2", "3", "4", "5", "6", "7", "8", "9", "A", "B", "C", "D", "E", "F"}
Dim lRet As New System.Text.StringBuilder()
If pBigInt.mIsNegative Then lRet.Append("-")
lRet.Append("&(" & pBase & ")")
Dim lByte As Byte = (pBigInt Mod pBase).ToByte
If lByte And &HF0 Then
lRet.Append(aChars(lByte))
End If
If lByte And &HF Then
lRet.Append(aChars(lByte And &HF))
End If
For i = pBigInt.mBytes.Count - 2 To 0 Step -1
lByte = pBigInt.mBytes(i)
lRet.Append(aChars(lByte >> 4) & aChars(lByte And 15))
Next
Return lRet.ToString
End Function
Public Shared Function ToBase16(pBigInt As BigInt) As String
pBigInt.Normalize()
If pBigInt.IsZero Then Return "0"
Dim aChars() As Char = {"0", "1", "2", "3", "4", "5", "6", "7", "8", "9", "A", "B", "C", "D", "E", "F"}
Dim lRet As New System.Text.StringBuilder()
If pBigInt.mIsNegative Then lRet.Append("-")
lRet.Append("&H")
Dim lByte As Byte = pBigInt.mBytes(pBigInt.mBytes.Count - 1)
If lByte And &HF0 Then
lRet.Append(aChars(lByte >> 4))
End If
If lByte And &HF Then
lRet.Append(aChars(lByte And &HF))
End If
For i = pBigInt.mBytes.Count - 2 To 0 Step -1
lByte = pBigInt.mBytes(i)
lRet.Append(aChars(lByte >> 4) & aChars(lByte And 15))
Next
Return lRet.ToString
End Function
Public Function ToBase16() As String
Return BigInt.ToBase16(Me)
End Function
Public Shared Function FromBase10(pSource As String) As BigInt
Dim lMode As Byte = 1
Dim lIsNegative As Boolean
Dim lNB As New System.Text.StringBuilder
Dim lDec As Integer = -1
Dim lShiftDirection As Char
Dim lShiftAmt As String
For Each lChar In pSource
Select Case lMode
Case 1
Select Case lChar
Case " ", "+"
Case "-"
lIsNegative = True
lMode = 2
Case "0" 'ignore leading zeros
Case "1" To "9"
lNB.Append(lChar)
lMode = 2
Case "."
lDec = lNB.Length
lMode = 3
Case Else
Throw New InvalidCastException
End Select
Case 2
Select Case lChar
Case ","
Case "0" To "9"
lNB.Append(lChar)
Case "."
lDec = lNB.Length
lMode = 3
Case "E"
lMode = 4
Case Else
Throw New InvalidCastException
End Select
Case 3
Select Case lChar
Case ","
Case "0" To "9"
lNB.Append(lChar)
Case "E"
lMode = 4
lShiftDirection = "+"
Case Else
Throw New InvalidCastException
End Select
Case 4
Select Case lChar
Case "+", "-"
lShiftDirection = lChar
lMode = 5
Case "0"
Case "1" To "9"
lShiftAmt = lShiftAmt & lChar
lMode = 6
Case Else
Throw New InvalidCastException
End Select
Case 5
Select Case lChar
Case "0"
Case "1" To "9"
lShiftAmt = lShiftAmt & lChar
lMode = 6
Case Else
Throw New InvalidCastException
End Select
Case 6
Select Case lChar
Case "0" To "9"
lShiftAmt = lShiftAmt & lChar
lMode = 6
Case Else
Throw New InvalidCastException
End Select
End Select
Next
If lDec = -1 Then lDec = lNB.Length + 1
Dim lAsDecimal As String
If lShiftAmt = "" Then
lAsDecimal = lNB.ToString
ElseIf lShiftDirection = "+" Then
lDec = lDec + Val(lShiftAmt)
If lDec > (lNB.Length + 1) Then
lAsDecimal = lNB.ToString & New String("0", (lDec - lNB.Length) - 1)
Else
lAsDecimal = lNB.ToString.Substring(0, lDec - 1)
End If
ElseIf lShiftDirection = "-" Then
lDec = lDec - Val(lShiftAmt)
If lDec < 1 Then
Return New BigInt(0)
Else
lAsDecimal = lNB.ToString.Substring(0, lDec - 1)
End If
End If
'lAsDecimal is now a clean, unsigned decimal with scientific notation expanded
Dim l10 As BigInt = New BigInt(10)
Dim lTens As BigInt = New BigInt(1)
Dim lRet As BigInt = New BigInt(0)
For i = lAsDecimal.Length - 1 To 0 Step -1
Dim lAdditive As BigInt = lTens * New BigInt(Asc(lAsDecimal.Substring(i, 1)) - 48)
lRet += lAdditive
lTens = lTens * l10
Next
lRet.mIsNegative = lIsNegative
lRet.Normalize()
Return lRet
End Function
Public Shared Function FromBase16(pSource As String) As BigInt
Dim lProc As New Stack(Of Byte)
Dim lTemp As String = ""
Dim lRet As New BigInt(0)
For i = 0 To pSource.Length - 1
Dim lChar As Char = pSource.Substring(i, 1)
Dim lAsc As Integer = Asc(lChar)
Select Case lAsc
Case 48 To 57
lTemp = lTemp & lChar
Case 65 To 70
lTemp = lTemp & lChar
End Select
If Len(lTemp) = 2 Then
Dim lByte As Byte = 0
lAsc = Asc(lTemp.Substring(0, 1))
Select Case lAsc
Case 48 To 57
lByte = (lAsc - 48) << 4
Case 65 To 70
lByte = (lAsc - 55) << 4
End Select
lAsc = Asc(lTemp.Substring(1, 1))
Select Case lAsc
Case 48 To 57
lByte = lByte + (lAsc - 48)
Case 65 To 70
lByte = lByte + (lAsc - 55)
End Select
lTemp = ""
lRet.mBytes.Insert(0, lByte)
End If
Next
If lTemp <> "" Then
Select Case Asc(lTemp)
Case 48 To 57
lRet = lRet << 4
lRet += New BigInt(Asc(lTemp) - 48)
Case 65 To 70
lRet = lRet << 4
lRet += New BigInt(Asc(lTemp) - 55)
End Select
End If
lRet.Normalize()
Return lRet
End Function
Public Shared Function ToBase10(pBigInt As BigInt) As String
Dim lRemaining As BigInt = pBigInt
Dim lStack As New Stack(Of Char)
Dim lMod As BigInt = Nothing
Dim lDigit As Byte
Dim l10 As New BigInt(10)
Dim l10K As New BigInt(10000)
Dim l1B As New BigInt(1000000000)
Dim l1Googol As BigInt = New BigInt(0)
If pBigInt.Log2 >= 332 Then l1Googol = New BigInt(10000) ^ 25
Dim l1GoogolE10 As BigInt = New BigInt(0)
If pBigInt.Log2 >= 3321 Then l1GoogolE10 = l1Googol ^ 10
pBigInt.Normalize()
If pBigInt.IsZero Then Return "0"
Dim lLastUpdate As Double = Microsoft.VisualBasic.Timer
Dim lStartTime As DateTime = Now
Dim lStartDigits As Integer = lRemaining.Log2
Dim lStackSize As Long = 0
Do
If (Not l1GoogolE10.IsZero) AndAlso (lRemaining > l1GoogolE10) Then
Divide(lRemaining, l1GoogolE10, lRemaining, lMod)
Dim lText As String = lMod.ToString.PadLeft(1000, "0")
For i = lText.Length - 1 To 0 Step -1
lStack.Push(lText.Substring(i, 1))
Next
lStackSize += lText.Length
ElseIf (Not l1Googol.IsZero) AndAlso (lRemaining > l1Googol) Then
Divide(lRemaining, l1Googol, lRemaining, lMod)
Dim lText As String = lMod.ToString.PadLeft(100, "0")
For i = lText.Length - 1 To 0 Step -1
lStack.Push(lText.Substring(i, 1))
Next
lStackSize += lText.Length
ElseIf lRemaining > l1B Then
Divide(lRemaining, l1B, lRemaining, lMod)
Dim lText As String = Format(lMod.ToInt32, "000000000")
For i = lText.Length - 1 To 0 Step -1
lStack.Push(lText.Substring(i, 1))
Next
lStackSize += lText.Length
ElseIf lRemaining > l10K Then
Divide(lRemaining, l10K, lRemaining, lMod)
Dim lText As String = Format(lMod.ToInt16, "0000")
For i = lText.Length - 1 To 0 Step -1
lStack.Push(lText.Substring(i, 1))
Next
lStackSize += lText.Length
Else
Divide(lRemaining, l10, lRemaining, lMod)
lStack.Push(CStr(lMod.ToByte))
lStackSize += 1
End If
If (Microsoft.VisualBasic.Timer - lLastUpdate) > 10 Then
Dim lLog2 As Integer = lRemaining.Log2
If lLog2 < lStartDigits Then
Debug.Print(lLog2 & " significant digits remaining.")
Dim lTimeSpent As TimeSpan = Now.Subtract(lStartTime)
Dim lUnitTime As Double = lTimeSpent.TotalSeconds / (lStartDigits - lLog2)
Dim lCompletion As DateTime = Now.AddSeconds(lUnitTime * lLog2 * (lLog2 / lStartDigits) / 3)
Debug.Print("Estimated Completion: " & Format(lCompletion, "M/d/yyyy HH:mm:ss"))
Dim lDigitRatio As Double = lStackSize / (lStartDigits - lLog2)
Debug.Print("Estimated Output Digits: " & (lStackSize + CInt(lDigitRatio * lLog2)))
lLastUpdate = Microsoft.VisualBasic.Timer
End If
End If
Loop Until lRemaining.IsZero
If pBigInt.mIsNegative Then lStack.Push("-")
Dim lRet As New System.Text.StringBuilder
While lStack.Count
lRet.Append(lStack.Pop)
End While
If Now - lStartTime > New TimeSpan(0, 1, 0) Then
Using lwriter As New IO.StreamWriter("c:\temp\Calculation.txt", False)
lwriter.WriteLine(lRet.ToString)
lwriter.Close()
lwriter.Dispose()
End Using
End If
Return lRet.ToString
End Function
Public Shared Function Log2(pByte As Byte) As Byte
Dim lRet As Byte
While pByte <> 0
lRet += 1
pByte = pByte >> 1
End While
Return lRet
End Function
Public Shared Function Log2(pInteger As Integer) As Byte
Dim lRet As Byte
If pInteger < 0 Then Throw New InvalidOperationException("BigInt cannot take the logarithm of a negative number.")
While pInteger <> 0
lRet += 1
pInteger = pInteger >> 1
End While
Return lRet
End Function
Public Shared Function Log2_Dbl(pByte As Byte) As Double
Dim lRet As Double = 8
If pByte = 0 Then Return 0
While (pByte And &H80) = 0
lRet -= 1
pByte = pByte << 1
End While
pByte = pByte << 1
Dim lDivisor As Integer = 2
While pByte <> 0
If pByte And &H80 Then
lRet = lRet + 1 / lDivisor
End If
lDivisor *= 2
pByte = pByte << 1
End While
Return lRet
End Function
Public Shared Function Log2_Dbl(pInteger As Integer) As Double
Dim lRet As Double = 8
If pInteger = 0 Then Return 0
While (pInteger And &H8000) = 0
lRet -= 1
pInteger = pInteger << 1
End While
pInteger = pInteger << 1
Dim lDivisor As Integer = 2
While pInteger <> 0
If pInteger And &H8000 Then
lRet = lRet + 1 / lDivisor
End If
lDivisor *= 2
pInteger = pInteger << 1
End While
Return lRet
End Function
End Structure
Submit an article or tip