-
Notifications
You must be signed in to change notification settings - Fork 0
/
BigNum.vb
163 lines (141 loc) · 3.92 KB
/
BigNum.vb
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
Public Class BigNumber
Private number As Byte()
Private size As Integer
Private maxDigits As Integer
Public Sub New(ByVal maxDigits As Integer)
Me.maxDigits = maxDigits
Me.size = CInt(Math.Ceiling(CSng(maxDigits) * 0.104)) + 2
number = New Byte(size - 1) {}
End Sub
Public Sub New(ByVal maxDigits As Integer, ByVal intPart As Byte)
Me.New(maxDigits)
number(0) = intPart
For i As Integer = 1 To size - 1
number(i) = 0
Next
End Sub
Private Sub VerifySameSize(ByVal value As BigNumber)
If [Object].ReferenceEquals(Me, value) Then
Throw New Exception("BigNumbers cannot operate on themselves")
End If
If value.size <> Me.size Then
Throw New Exception("BigNumbers must have the same size")
End If
End Sub
Public Sub Add(ByVal value As BigNumber)
VerifySameSize(value)
Dim index As Integer = size - 1
While index >= 0 AndAlso value.number(index) = 0
index -= 1
End While
Dim carry As UInt32 = 0
While index >= 0
Dim result As UInt64 = CType(number(index), UInt64) + value.number(index) + carry
number(index) = CByte(result Mod (Byte.MaxValue + 1))
If result >= &H100000000UL Then
carry = 1
Else
carry = 0
End If
index -= 1
End While
End Sub
Public Sub Subtract(ByVal value As BigNumber)
VerifySameSize(value)
Dim index As Integer = size - 1
While index >= 0 AndAlso value.number(index) = 0
index -= 1
End While
Dim borrow As UInt32 = 0
While index >= 0
Dim result As UInt64 = &H100000000UL + CType(number(index), UInt64) - value.number(index) - borrow
number(index) = CByte(result Mod (Byte.MaxValue + 1))
If result >= &H100000000UL Then
borrow = 0
Else
borrow = 1
End If
index -= 1
End While
End Sub
Public Sub Multiply(ByVal value As UInt32)
Dim index As Integer = size - 1
While index >= 0 AndAlso number(index) = 0
index -= 1
End While
Dim carry As UInt32 = 0
While index >= 0
Dim result As UInt64 = CType(number(index), UInt64) * value + carry
number(index) = CByte(result Mod (Byte.MaxValue + 1))
carry = CType(result >> 32, UInt32)
index -= 1
End While
End Sub
Public Sub Divide(ByVal value As UInt32)
Dim index As Integer = 0
While index < size AndAlso number(index) = 0
index += 1
End While
Dim carry As UInt32 = 0
While index < size
Dim result As UInt64 = CULng((number(index) + (CType(carry, UInt64) << 32)) / CType(value, UInt64))
number(index) = CByte(result Mod (Byte.MaxValue + 1))
carry = CType(result Mod CType(value, UInt64), UInt32)
index += 1
End While
End Sub
Public Sub Assign(ByVal value As BigNumber)
VerifySameSize(value)
For i As Integer = 0 To size - 1
number(i) = value.number(i)
Next
End Sub
Public Function IsZero() As Boolean
For Each item As UInt32 In number
If item <> 0 Then
Return False
End If
Next
Return True
End Function
Public Sub ArcTan(ByVal multiplicand As Byte, ByVal reciprocal As UInt32)
Dim X As New BigNumber(maxDigits, multiplicand)
X.Divide(reciprocal)
reciprocal *= reciprocal
Me.Assign(X)
Dim term As New BigNumber(maxDigits)
Dim divisor As UInt32 = 1
Dim subtractTerm As Boolean = True
While True
X.Divide(reciprocal)
term.Assign(X)
divisor = CUInt(divisor + 1)
term.Divide(divisor)
If term.IsZero() Then
Exit While
End If
If subtractTerm Then
Me.Subtract(term)
Else
Me.Add(term)
End If
subtractTerm = Not subtractTerm
End While
End Sub
' limit the size
Public Sub Truncate(ByVal newsize As Integer)
If size <= newsize Then Return
size = newsize
End Sub
' stupid property macro hacks
Default ReadOnly Property Item(ByVal i As Integer) As UInteger
Get
Return number(i)
End Get
End Property
Public ReadOnly Property Length As Integer
Get
Return size
End Get
End Property
End Class