Big numbers
When I first started learning about numbers I remember marveling at what infinity means. How many integers are there? Are there more real numbers than integers?
How many numbers are there between zero and 1?
Then I remember thinking about how these numbers get to be so big… so many digits.
Then I started playing around with computers and calculators and tried to see these big numbers. They always represented these big numbers in scientific notation: a mantissa times ten raised to an exponent, like 3.1415926535 * 10 ^ (0)
The large numbers were all represented in just a few characters.
It’s sort of like in those days, when you spend money, you typically count out the bills: the 1’s, the 10’s the twenties, the nickels and quarters. It really felt like you’re spending money and you feel a little less rich after the purchase. Nowadays, everything costs the same: hand over a plastic card and sign a piece of paper.
Large numbers didn’t really feel large: just some mantissa and some exponent.
For example, 12345678901234567890123456789012345678901234567890 seems much bigger than 1.23456789E50. It really feels like a big number.
Some sequences grow bigger pretty quickly. The Fibonacci numbers, for example: 1,1,2,3,5,8,13,21 (each number is the sum of the prior 2) grow pretty quickly.
The Factorial of a number (written n!) grows even faster. A recursive definition: n! = n * (n-1)!)
Suppose I want to see the factorial of 50. Rather than seeing 3.0414E64, I’d see:
30414093201713378043612608166064768844377641568960512000000000000
Now I can easily notice a trend: large factorial numbers always have a string of zeros at the end. Not immediately obvious, but I’m sure you can figure out why.
Below is a program that calculates these big numbers. It uses a class called BigNum that represents a positive integer as an array of digits. It uses operator overloading to define the operations of addition and multiplication ( BigNum + BigNum, or BigNum * BigNum)
Note that the base can easily be changed. (want to see the factorials in base 2?)
Because the numbers that the BigNum class represents are so big, the ToString override includes the number of digits (or the exponent in the current base).
The display shows that 5! = 120 (which has an exponent of 2 (log10(5!) = 2)
1 0 1
2 0 2
3 0 6
4 1 24
5 2 120
The numbers get very big very fast. try increasing the list to > 1000 items. Try scrolling the listview to the right and down. Try the Stirling numbers. (pi, e, and factorials are related!)
After spending a few minutes writing the code (and of course tests that exercise the code: Test Driven Development!) I found that there already is a class that does this, called System.Numerics.BigInteger
Start Visual Studio
File->New->c# WPF application.
Replace MainWindow.Xaml.cs with the below code.
<sample code>
using System;
using System.Collections.Generic;
using System.Text;
using System.Windows;
using System.Windows.Controls;
namespace WpfApplication1
{
/// <summary>
/// Interaction logic for MainWindow.xaml
/// </summary>
public partial class MainWindow : Window
{
BigNum factorial(BigNum n)
{
if (n != 1)
{
return factorial(n + (-1)) * n;
}
return new BigNum(1);
}
public MainWindow()
{
InitializeComponent();
this.Loaded += (o, e) =>
{
try
{
this.WindowState = WindowState.Maximized;
var lst = new List<Tuple<double, BigNum>>();
var n1 = new BigNum(1);
var n2 = new BigNum(1);
var n3 = n1 + n2;
for (int i = 1; i <= 10000; i++)
{
// try stirling!
//var stirling = Math.Sqrt(2 * i * Math.PI) * Math.Pow(i / Math.E, i);
//lst.Add(Tuple.Create<double, BigNum>(stirling, n1));
lst.Add(Tuple.Create<double, BigNum>(i, n1));
System.Diagnostics.Debug.WriteLine($"{i} {n1}");
//* Fibonacci
var newn = n1 + n2;
n1 = n2;
n2 = newn;
/*/
// Factorial
n1 = n1 * (new BigNum(i + 1));
//*/
}
var lv = new ListView()
{
ItemsSource = lst
};
this.Content = lv;
}
catch (Exception ex)
{
this.Content = ex.ToString();
}
};
}
}
// https://referencesource.microsoft.com/#System.Numerics/System/Numerics/BigNumber.cs
public class BigNum
{
internal const int MaxDigits = 10000;
internal static byte Base = 10;
internal byte[] _digits;
internal int _numDigits;
public BigNum(int initVal)
{
SetVal(initVal);
}
BigNum(byte[] digits, int numdigits)
{
_digits = digits;
Array.Resize(ref _digits, numdigits);
_numDigits = numdigits;
}
public static BigNum CreateMax(int size = MaxDigits)
{
var x = new BigNum(0);
x._numDigits = 0;
x._digits = new byte[size];
return x;
}
private void SetVal(int initVal)
{
var val = initVal;
var digits = new byte[MaxDigits];
while (val > 0)
{
byte digit = (byte)(val % Base);
digits[_numDigits] = digit;
val = val / Base;
_numDigits++;
}
_digits = new byte[_numDigits];
Array.Copy(digits, _digits, _numDigits);
}
public static BigNum operator +(BigNum num1, BigNum num2)
{
var max = Math.Max(num1._numDigits, num2._numDigits);
var temp = BigNum.CreateMax(size: max + 1);
byte carry = 0;
for (int i = 0; i < max; i++)
{
byte new1 = 0;
byte new2 = 0;
if (i < num1._numDigits)
{
new1 = num1._digits[i];
}
if (i < num2._numDigits)
{
new2 = num2._digits[i];
}
byte newdig = (byte)(new1 + new2 + carry);
carry = 0;
while (newdig >= Base)
{
carry++;
newdig -= Base;
}
temp._digits[temp._numDigits++] = newdig;
}
while (carry > 0)
{
temp._digits[temp._numDigits++] = (byte)(carry % Base);
carry = (byte)(carry / Base);
}
var result = new BigNum(temp._digits, temp._numDigits);
return result;
}
public static BigNum operator *(BigNum num1, BigNum num2)
{
var numDigits = 1 + num1._numDigits * num2._numDigits;
var temp = new BigNum(0);
if (numDigits > 1)
{
var partSums = new BigNum[num1._numDigits];
for (int i = 0; i < num1._numDigits; i++)
{
var curSum = BigNum.CreateMax();
var multiplier = num1._digits[i];
if (multiplier != 0)
{
var carry = 0;
for (int j = 0; j < num2._numDigits; j++)
{
var partres = carry + num2._digits[j] * multiplier;
var newdig = partres % Base;
carry = (partres - newdig) / Base;
curSum._numDigits = Math.Max(1 + i + j, curSum._numDigits);
curSum._digits[i + j] += (byte)newdig;
}
if (carry > 0)
{
curSum._digits[curSum._numDigits] += (byte)carry;
curSum._numDigits++;//= Math.Max(curSum._numDigits, 1 + num2._numDigits);
}
}
partSums[i] = curSum;
}
foreach (var b in partSums)
{
temp += b;
}
}
var result = new BigNum(temp._digits, temp._numDigits);
return result;
}
public static BigNum operator +(BigNum num1, int int2)
{
var b2 = new BigNum(int2);
return num1 + b2;
}
public static bool operator ==(BigNum n1, object n2)
{
return n1.Equals(n2);
}
public static bool operator !=(BigNum n1, object n2)
{
return !(n1 == n2);
}
public override bool Equals(object obj)
{
if (obj is BigNum)
{
return this.Equals((BigNum)obj);
}
if (obj is int)
{
var b = new BigNum((int)obj);
return this.Equals(b);
}
return base.Equals(obj);
}
public override int GetHashCode()
{
// todo
return base.GetHashCode();
}
public bool Equals(BigNum obj)
{
var areEqual = false;
var bobj = (BigNum)obj;
if (this._numDigits == bobj._numDigits)
{
areEqual = true;
for (int i = 0; i < this._numDigits; i++)
{
if (this._digits[i] != bobj._digits[i])
{
areEqual = false;
break;
}
}
}
return areEqual;
}
public string GetValue()
{
StringBuilder sb = new StringBuilder();
if (_numDigits == 0)
{
sb.Append(0.ToString());
}
else
{
for (int i = _numDigits - 1; i >= 0; i--)
{
sb.Append(_digits[i].ToString());
}
}
return sb.ToString();
}
public double GetDouble()
{
double val = 0;
for (int i = _numDigits - 1; i >= 0; i--)
{
val = val * Base + _digits[i];
}
return val;
}
public override string ToString()
{
return string.Format($"{_numDigits - 1 } {GetValue()}");
}
}
}
<sample code/>