-
Notifications
You must be signed in to change notification settings - Fork 0
/
HugeNumber.cs
390 lines (366 loc) · 10.9 KB
/
HugeNumber.cs
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
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace HugeNumbers
{
/// <summary>
/// This class uses a base(-2) encoding to represent integers of arbitrary size.
/// The use of a negative base allows for encodings that do not need a "sign bit"
/// and therefor don't roll over at an upper or lower limit.
/// The numbers are encoded in powers of -2 starting with the low order bit.
/// Max/min value is limited by the number of bits that can be stored in a int indexed
/// List<bool>, or 2^int.MaxValue+2^(int.MaxValue-2)+... which is pretty huge.
/// .NET uses actual bools in its list but C++ has a vector<bool> specialization
/// that uses actual bits. So the .NET implementation is not actually practical.
/// Large number math can be done similarly with lists based on other bases, but
/// base -2 gives some algorithmic simplifications that make it easier to code
/// and understand.
/// </summary>
public class HugeNumber:List<bool>, IComparable<long>, IComparable<HugeNumber>
{
#region Construction and initialization
/// <summary>
/// Conversion constructor. Turns an array of int into an HugeNumber.
/// </summary>
/// <param name="Value">An array of 1s and 0s representing bits.</param>
public HugeNumber(int[] Value)
{
foreach(int b in Value)
Add(b != 0);
}
/// <summary>
/// Default constructor. Necessary because we need the other constructors.
/// </summary>
public HugeNumber()
{ }
/// <summary>
/// Conversion constructor. Turns a long into an HugeNumber.
/// </summary>
/// <param name="Value">The value to encode in base(-2).</param>
public HugeNumber(long Value)
{
FromLong(Value);
}
/// <summary>
/// Copy constructor makes a copy of the source number to give value like behaviour.
/// </summary>
/// <param name="Source">Another number to copy.</param>
public HugeNumber(HugeNumber Source)
{
foreach(bool b in Source)
Add(b);
}
/// <summary>
/// Converts an HugeNumber to a conventional long.
/// </summary>
/// <returns>A long int with the equivalent value, if it will fit.</returns>
public long ToLong()
{
if(Count > 65 && this.Skip(sizeof(long)).Any(b => b)) // long.MaxValue takes 65 bits.
throw new ArgumentOutOfRangeException();
long result = 0;
long bit_value = 1L;
for(int b = 0;b < Count;++b)
{
result += this[b] ? bit_value : 0;
bit_value *=-2;
}
return result;
}
/// <summary>
/// Initialize from a conventional long integer.
/// </summary>
/// <param name="Value">The value to encode.</param>
public void FromLong(long Value)
{
Clear();
while(Value != 0)
{
long rem = 0; // get the remainder as and out parameter.
Value = Math.DivRem(Value, -2 , out rem); // do divide and modulo at the same time for efficiency.
if(rem < 0)
++Value;
Add(rem != 0);
}
}
/// <summary>
/// A way to remove superfluous leading zeros that just take up space.
/// </summary>
/// <returns>A representation with the minimum number of terms.</returns>
public HugeNumber Trim()
{
int len = Count-1;
while(len >= 0 && !this[len])
RemoveAt(len--); // remove high order 0's
return this;
}
#endregion Construction and initialization
/// <summary>
/// Create a human readable representation.
/// </summary>
/// <returns>A string of 1s and 0s representing the base(-2) encoding, with low order first.</returns>
public override string ToString()
{
StringBuilder text = new StringBuilder();
ForEach(b => text.Append(b ? "1" : "0"));
return text.ToString();
}
#region Mathematical operations
/// <summary>
/// Change the sign of the number.
/// </summary>
/// <returns>A new HugeNumber with the opposite sign.</returns>
public HugeNumber Negate()
{
HugeNumber negated = new HugeNumber();
for(int b = 0;b < Count;++b)
{
if(this[b])
{
negated.Add(true);
if(Count <= ++b)
negated.Add(true); // insert a bit
else
negated.Add(!this[b]); // compliment the next highest bit
}
else
negated.Add(false); // 0 stays 0
}
return negated.Trim();
}
/// <summary>
/// Adds a bit at bit position B. Note that this is and iterative approach to
/// avoid the deep recursion that might occur in long carry scenarios.
/// It should also be faster by avoiding function calls for simple operations.
/// </summary>
/// <param name="B">The bit position at which to increment.</param>
/// <returns>true if a carry is required. Caries happen 2 bit positions up.</returns>
protected bool AddBit(int B)
{
int pad = B - Count + 1;
while(pad-- > 0)
Add(false);
if(!this[B])
{
this[B] = true; // increment this bit
return false; // no carry.
}
else
{
if(Count == B + 1)
Add(false);
this[B] = false; // remove +bit_value
if(this[B + 1])
{
this[B + 1] = false; // also remove -2*bit_value
return false; // no carry
}
else
{
this[B + 1] = true; // add -2*bit_value
if(Count == B + 2)
{
Add(true); // make room for carry
return false; // no need to carry
}
return true; // need to carry on B+2 position to add +4*bit_value
}
}
}
/// <summary>
/// Adds this HugeNumber another to produce a third which is the mathematical sum
/// of this and the other.
/// </summary>
/// <param name="Other">The number to add to our value.</param>
/// <returns>A new HugeNumber with the value of us plus the other.</returns>
public HugeNumber Add(HugeNumber Other)
{
HugeNumber result = new HugeNumber(this);
for(int b = 0;b < Other.Count;++b)
{
if(Other[b])
{
int bit = b;
while(result.AddBit(bit))
bit += 2; // carry required.
}
}
return result.Trim();
}
public static HugeNumber operator +(HugeNumber Left, HugeNumber Right)
{
return Left.Add(Right);
}
/// <summary>
/// Subtracts a bit at bit position B. Note that this is and iterative approach to
/// avoid the deep recursion that might occur in long borrow scenarios.
/// It should also be faster by avoiding function calls for simple operations.
/// </summary>
/// <param name="B">The bit position at which to decrement.</param>
/// <returns>true if a borrow is required. Borrows happen 2 bit positions up.</returns>
protected bool SubractBit(int B)
{
int pad = B - Count + 1;
while(pad-- > 0)
Add(false);
if(this[B])
{
this[B] = false; // decrement this bit
return false; // no carry.
}
else
{
if(Count == B + 1)
Add(false);
if(!this[B + 1])
{
this[B] = true; // add this bit and
this[B + 1] = true; // also add next higher bit_value
return false; // no carry
}
else
{
this[B] = true; // add this bit
this[B + 1] = false; // add -2*bit_value
if(Count == B + 2)
{
return false; // no need to no need to borrow
}
return true; // need to borrow on B+2 position to add +4*bit_value
}
}
}
/// <summary>
/// Subtracts another HugeNumber from this.
/// This could be done as a negate and add, but direct subtract is more efficient in time and space.
/// </summary>
/// <param name="Other">The number to subtract from me.</param>
/// <returns>A new HugeNumber representing the difference between me and the Other.</returns>
public HugeNumber Subtract(HugeNumber Other)
{
HugeNumber result = new HugeNumber(this);
for(int b = 0;b < Other.Count;++b)
{
if(Other[b])
{
int bit = b;
while(result.SubractBit(bit))
bit += 2; // borrow required.
}
}
return result.Trim();
}
public static HugeNumber operator -(HugeNumber Left, HugeNumber Right)
{
return Left.Subtract(Right);
}
#endregion Mathematical operaitons
#region Comparisons
public int CompareTo(long other)
{
return CompareTo(new HugeNumber(other)); // up converting avoids OoR exceptions.
}
/// <summary>
/// Compare two HugeNumbers. Starts with high order bits and quits as soon as a difference is found.
/// </summary>
/// <param name="other">THe HugeNumber to compare ourselves to.</param>
/// <returns>-1 if we are less than other, 0 if we are equal, 1 if we are greater.</returns>
public int CompareTo(HugeNumber other)
{
int compare = 0;
if(other.Count > Count)
{
int b = other.Count-1;
while(b >= Count)
if(other[b])
{
compare = (b & 1) == 1 ? 1 : -1;
return compare;
}
}
else
{
int b = Count - 1;
while(b >= other.Count)
if(this[b])
{
compare = (b & 1) == 1 ? -1 : 1;
return compare;
}
}
for(int b = Count-1;b >= 0 && compare == 0;--b)
{
if(this[b] == other[b])
continue; // matching bits don't affect comparison.
if((b&1) == 0)
compare = this[b] ? 1 : -1;
else
compare = this[b] ? -1 : 1;
}
return compare;
}
/// <summary>
/// Value Comparison for "is less than".
/// </summary>
/// <param name="Left">LHS</param>
/// <param name="Right">RHS</param>
/// <returns>true if LHS is less than RHS.</returns>
public static bool operator <(HugeNumber Left, HugeNumber Right)
{
return Left.CompareTo(Right) < 0;
}
/// <summary>
/// Value Comparison for "is greater than".
/// </summary>
/// <param name="Left">LHS</param>
/// <param name="Right">RHS</param>
/// <returns>true if LHS is greater than RHS.</returns>
public static bool operator >(HugeNumber Left, HugeNumber Right)
{
return Left.CompareTo(Right) > 0;
}
/// <summary>
/// Value Comparison for "is equal to".
/// </summary>
/// <param name="Left">LHS</param>
/// <param name="Right">RHS</param>
/// <returns>true if LHS is equal to RHS.</returns>
public static bool operator ==(HugeNumber Left, HugeNumber Right)
{
return Left.CompareTo(Right) == 0;
}
/// <summary>
/// Value Comparison for "is NOT equal to".
/// </summary>
/// <param name="Left">LHS</param>
/// <param name="Right">RHS</param>
/// <returns>true if LHS is NOT equal to RHS.</returns>
public static bool operator !=(HugeNumber Left, HugeNumber Right)
{
return Left.CompareTo(Right) != 0;
}
/// <summary>
/// Value Comparison for "is less than or equal to".
/// </summary>
/// <param name="Left">LHS</param>
/// <param name="Right">RHS</param>
/// <returns>true if LHS is less than or equal to RHS.</returns>
public static bool operator <=(HugeNumber Left, HugeNumber Right)
{
return Left.CompareTo(Right) <= 0;
}
/// <summary>
/// Value Comparison for "is greater than or equal to".
/// </summary>
/// <param name="Left">LHS</param>
/// <param name="Right">RHS</param>
/// <returns>true if LHS is greater than or equal to RHS.</returns>
public static bool operator >=(HugeNumber Left, HugeNumber Right)
{
return Left.CompareTo(Right) >= 0;
}
#endregion Comparisons
}
}