MegaInt – Custom data type for very large numbers

I recently created a new data type for Above the Stars. It was an interesting excursion into many things I’ve never used before so I thought I’d do a write-up regarding it.

The MegaInt is capable of holding very large numbers all in a single integer, as well displaying them in a readable format.
A basic description can be found below as well as the full script (Creative Commons 4.0).

Description

The MegaInt can hold very large numbers by splitting the 32 bits of an integer. It uses the last 24 bits for accuracy (7 significant figures) and the remaining 8 bits for power (10256).

The concept itself is quite straightforward. It takes the input (converted into a String) and reduces it to the 7 digit length, incrementing the power for each excess digit dropped.
I wont go into the various conversions or mathematical methods. (the latter works as normal but accounts for the powers). There may be some odd behaviours at very low numbers (always rounding up) but for the most part it works quite well.

Conclusion

Overall I’m very happy with the result. It is lightweight and accurate enough for my purposes, although there is much that could be improved.
If I were to do it again I would definitely build it to work with below-one numbers (I’d do it now but it would require a large rewrite). Some of the methods should probably be rewritten to look/run cleaner, as well. I might also focus less on saving memory and more on performance, but I’m not too sure.
Anyway, I hope someone finds this useful.

Code

//ArmanDoesStuff 2017
using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public static class ArmanLibrary
{
//Check if string only contains digits
    public static bool IsDigitsOnly(this string str)
    {
        foreach (char c in str)
        {
            if (c < '0' || c > '9')
            {
                return false;
            }
        }
        return true;
    }
}

Above is a snippet from my custom library of common functions. IsDigitsOnly extends the string class and is pretty self-explanatory. It’s used in the MegaInt script (below) when taking a string input from an outside source

//ArmanDoesStuff 2017
//MegaInt 1.0
using System;

public class MegaInt
{
    #region variables
    string[] PowerNames = new string[]
    {
            "", "Thousand", "Million", "Billion", "Trillion", "Quadrillion", "Quintillion", "Sextillion", "Septillion",
            "Octillion", "Nonillion", "Decillion", "Undecillion", "Duodecillion", "Tredecillion", "Quattuordecillion",
            "Quindecillion", "Sexdecillion", "Septendecillion", "Octodecillion", "Novemdecillion", "Vigintillion"
    };

    uint storedValue; //actual data, holds Value and Power
    #endregion

    #region accessors
    //First 8 bits are Power (up to 10^255)
    byte Power
    {
        get
        {
            //return as byte (pushed right to override Val)
            return (byte)(storedValue >> 24);
        }
        set
        {
            //set as left bits, add original Val
            storedValue = (uint)(value << 24) + (storedValue & 16777215);
        }
    }

    //Last 24 are Value(16777216 - accuracy to 7 - 9999999)
    uint Val
    {
        get
        {
            //return with Power masked out
            return (storedValue & 16777215); //16777215 = 0000 0000 1111 1111 1111 1111 1111 1111
        }
        set
        {
            //set unmasked since the Power bits should never be set anyway. Add original Power to left bits
            storedValue = (uint)((value /* & 16777215 */) + (Power << 24));
        }
    }
    #endregion

    #region functions

    //divide by power of 10
    public static MegaInt Pow10Div(MegaInt a, byte p)
    {
        //get power difference
        int outPower = a.Power - p;
        if (outPower < 0)
        {
            string outValString = a.Val.ToString();
            //take off last digets to the amount of power or until only one remains
            return ulong.Parse(outValString.Substring(0, outValString.Length - Math.Min(Math.Abs(outPower), outValString.Length - 1)));
        }
        else
        {
            //if there is power remaining after divide, just output val with new power
            return new MegaInt(a.Val, (byte)outPower);
        }
    }

    public MegaInt Pow10Div(byte p)
    {
        return Pow10Div(this, p);
    }

    //divide by mult of 10
    public static MegaInt Pow10Mult(MegaInt a, byte p)
    {
        //get power difference
        return new MegaInt(a.Val, (byte)(a.Power + p));
    }

    public MegaInt Pow10Mult(byte p)
    {
        return Pow10Mult(this, p);
    }

    //divide by power of 10, round up
    public static uint OverPowerDiff(MegaInt a, byte highPower)
    {
        return (uint)((a.Val - 1) / (Math.Pow(10, highPower - a.Power))) + 1;
    }

    uint[] ConvertToMega(string a)
    {
        return ConvertToMega(a, 0);
    }

    //Power Function
    public static MegaInt PowerMult(MegaInt init, MegaInt mult, int pow)
    {
        for (int i = 0; i < pow; i++)
        {
            init *= mult;
        }
        return init;
    }

    uint[] ConvertToMega(string a, byte p)
    {
        //normalise to 7 digits if there is power
        while (a.Length < 7 && p > 0)
        {
            a += "0";
            p--;
        }

        //accuracy to 7 digits since 24-bits go up to 16777216 - 8 characters
        while (a.Length > 7)
        {
            //remove end number and increase power of 10 by one
            a = a.Remove(a.Length - 1);
            p++;
        }
        //return as values suitable for variables
        return new uint[2] { uint.Parse(a), p };
    }

    #region constuctors
    public MegaInt(ulong a)
    {
        uint[] i = ConvertToMega(a.ToString());
        Val = i[0];
        Power = (byte)i[1];
    }

    public MegaInt(uint a)
    {
        uint[] i = ConvertToMega(a.ToString());
        Val = i[0];
        Power = (byte)i[1];
    }

    public MegaInt(ulong a, byte p)
    {
        uint[] i = ConvertToMega(a.ToString(), p);
        Val = i[0];
        Power = (byte)i[1];
    }

    public MegaInt(string a)
    {
#if UNITY_EDITOR //Deactivate sanitized input check because I'm not using direct user input to MegaInt.
        a = a.TrimStart('0');
        if (!a.IsDigitsOnly() || a == "")
        {
            Val = 0;
            Power = 0;
            return;
        }
#endif
        uint[] i = ConvertToMega(a);
        Val = i[0];
        Power = (byte)i[1];

    }
    #endregion

    #region implicits
    public static implicit operator MegaInt(string a)
    {
        return new MegaInt(a);
    }

    public static implicit operator MegaInt(uint a)
    {
        return new MegaInt(a);
    }

    public static implicit operator MegaInt(ulong a)
    {
        return new MegaInt(a);
    }

    public static implicit operator string(MegaInt a)
    {
        return a.ToString();
    }
    #endregion

    #region overrides
    public override string ToString()
    {
        if (Val < 1000)  //only act on Values above 1 thousand
        {
            return Val.ToString();
        }

        //the higher the power the further the point moves until it resets at 10^3 to x.xxx
        int digits = Power + (Val.ToString().Length); //number of digits
        if (digits > 66) //if above Vigintillion then just show power
        {
            return Val.ToString().Substring(0, 4).Insert(1, ".") + " 10^" + digits;
        }
        int decimalPlace = digits % 3 == 0 ? 3 : digits % 3; 
        // + (Value < 0 ? 1 : 0); if doing negetives
        //get first 4 digits as significant figures
        //Add decimal point at correct place (as described above)
        //add power name (power, plus extra power for length minus the first 3) over 3 for because increments are 10^3
        return Val.ToString().Substring(0, 4).Insert(decimalPlace, ".") + " " + PowerNames[(digits - 1) / 3];
    }

    //I have no idea what I'm doing
    public override bool Equals(object obj)
    {
        var item = obj as MegaInt;

        if (item == null)
        {
            return false;
        }

        return this.storedValue.Equals(item.storedValue);
    }

    //I have no idea what I'm part II
    public override int GetHashCode()
    {
        return this.storedValue.GetHashCode();
    }

    #region equalities
    public static bool operator <(MegaInt leftSide, MegaInt rightSide)
    {
        //check powers, then check values (if powers are equal)
        if (leftSide.Power < rightSide.Power || (leftSide.Power == rightSide.Power && leftSide.Val < rightSide.Val))
        {
            return true;
        }
        return false;
    }

    public static bool operator >(MegaInt leftSide, MegaInt rightSide)
    {
        //same as above (with signs switched)
        if (leftSide.Power > rightSide.Power || (leftSide.Power == rightSide.Power && leftSide.Val > rightSide.Val))
        {
            return true;
        }
        return false;
    }

    public static bool operator ==(MegaInt leftSide, MegaInt rightSide)
    {
        //powers AND values must match
        if (leftSide.storedValue == rightSide.storedValue)
        {
            return true;
        }
        return false;
    }

    public static bool operator !=(MegaInt leftSide, MegaInt rightSide)
    {
        //defined above then inverted
        if (leftSide == rightSide)
        {
            return false;
        }
        return true;
    }
    #endregion

    #region enumeration
    //get higher power of both values and sum based on that
    public static MegaInt operator +(MegaInt leftSide, MegaInt rightSide)
    {
        byte highPower = (byte)Math.Max(leftSide.Power, rightSide.Power);
        ulong totalVal = OverPowerDiff(leftSide, highPower) + OverPowerDiff(rightSide, highPower);
        return new MegaInt(totalVal, highPower);
    }

    //minus based on the power difference
    public static MegaInt operator -(MegaInt leftSide, MegaInt rightSide)
    {
        if (rightSide > leftSide) { return 0; }
        if (leftSide.Power - rightSide.Power > 7) { return leftSide; }
        ulong totalVal = leftSide.Val - (OverPowerDiff(rightSide, leftSide.Power));
        return new MegaInt(totalVal, leftSide.Power);
    }

    //Simple multiplication with powers
    public static MegaInt operator *(MegaInt leftSide, MegaInt rightSide)
    {
        return new MegaInt((ulong)leftSide.Val * (ulong)rightSide.Val, (byte)(leftSide.Power + rightSide.Power));
    }

    //Simple division with powers
    public static MegaInt operator /(MegaInt leftSide, MegaInt rightSide)
    {
        return new MegaInt(((ulong)(leftSide.Val - 1) / (ulong)rightSide.Val) + 1, (byte)(leftSide.Power - rightSide.Power));
    }
    #endregion

    #endregion

    #endregion
}


Thanks for reading and have a great day!

Creative Commons License

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.