C# format arbitrarily large BigInteger for endless

问题:

I am trying to create an endless game such as Tap Titans, Clicker Heroes, etc. I have a BigInteger class that is capable of representing arbitrarily large integers as long as they fit into memory.

Now I have a class that formats a BigInteger into a specific format. It uses K (thousand), M (million), B (billion), T (trillion), Q (quadrillion) for the 'smaller' numbers, but after that the short hand notations become ambiguous and unintuitive. Q is already ambiguous due to Quintillion, but I can live with that.

After Q, I want to start from the letter a. So 1000Q = 1.000a, then 1000a = 1.000b etc. When 1000z is reached, it should be formatted to 1.000aa. Then 1000aa = 1.000 ab, 1000 az = 1.000 ba, 1000 bz = 1.000 ca, etc.

So far I have achieved the above, however my class is unable to format a number after 1000zz. I have not been able to come up with a generic algorithm that automatically determines how many characters are needed (could be aaaz for extremely large numbers).

My class looks as follows:

public class NumericalFormatter : BigIntegerFormatter
{
    public string Format(BigInteger number)
    {
        return FormatNumberString(number.ToString());
    }

    private string FormatNumberString(string number)
    {
        if (number.Length < 5)
        {
            return number;
        }

        if (number.Length < 7)
        {
            return FormatThousands(number);
        }

        return FormatGeneral(number);
    }

    private string FormatThousands(string number)
    {
        string leadingNumbers = number.Substring(0, number.Length - 3);
        string decimals = number.Substring(number.Length - 3);

        return CreateNumericalFormat(leadingNumbers, decimals, "K");
    }

    private string CreateNumericalFormat(string leadingNumbers, string decimals, string suffix)
    {
        return String.Format("{0}.{1}{2}", leadingNumbers, decimals, suffix);
    }

    private string FormatGeneral(string number)
    {
        int amountOfLeadingNumbers = (number.Length - 7) % 3 + 1;
        string leadingNumbers = number.Substring(0, amountOfLeadingNumbers);
        string decimals = number.Substring(amountOfLeadingNumbers, 3);

        return CreateNumericalFormat(leadingNumbers, decimals, GetSuffixForNumber(number));
    }

    private string GetSuffixForNumber(string number)
    {
        int numberOfThousands = (number.Length - 1) / 3;

        switch (numberOfThousands)
        {
            case 1:
                return "K";
            case 2:
                return "M";
            case 3:
                return "B";
            case 4:
                return "T";
            case 5:
                return "Q";
            default:
                return GetProceduralSuffix(numberOfThousands - 5);
        }
    }

    private string GetProceduralSuffix(int numberOfThousandsAfterQ)
    {
        if (numberOfThousandsAfterQ < 27)
        {
            return ((char)(numberOfThousandsAfterQ + 96)).ToString();
        }

        int rightChar = (numberOfThousandsAfterQ % 26);
        string right = rightChar == 0 ? "z" : ((char)(rightChar + 96)).ToString();
        string left = ((char)(((numberOfThousandsAfterQ - 1) / 26) + 96)).ToString();

        return left + right;
    }
}

As you can see the getProceduralSuffix() method cannot handle BigIntegers that would result in more than two character suffixes.

I also have a unit test that verifies the functionality of this class (prepare for some side scrolling):

namespace UnitTestProject.BigIntegerTest
{
    [TestClass]
    public class NumericalformatterTest
    {
        [TestMethod]
        public void TestFormatReturnsNumericalFormat()
        {
            BigIntegerFormatter numericalFormatter = new NumericalFormatter();

            foreach (string[] data in DpNumbersAndNumericalFormat())
            {
                BigInteger number = new BigInteger(data[0]);
                string expectedNumericalFormat = data[1];

                Assert.AreEqual(expectedNumericalFormat, numericalFormatter.Format(number));
            }
        }

        private string[][] DpNumbersAndNumericalFormat()
        {
            return new string[][]
            {
                new string[] { "0", "0" },
                new string[] { "1", "1" },
                new string[] { "15", "15" },
                new string[] { "123", "123" },
                new string[] { "999", "999" },
                new string[] { "1000", "1000" },
                new string[] { "9999", "9999" },
                new string[] { "10000", "10.000K" },
                new string[] { "78456", "78.456K" },
                new string[] { "134777", "134.777K" },
                new string[] { "999999", "999.999K" },
                new string[] { "1000000", "1.000M" },
                new string[] { "12345000", "12.345M" },
                new string[] { "999999000", "999.999M" },
                new string[] { "1000000000", "1.000B" },
                new string[] { "12345678900", "12.345B" },
                new string[] { "123345678900", "123.345B" },
                new string[] { "1233000000000", "1.233T" },
                new string[] { "9999000000000", "9.999T" },
                new string[] { "12233000000000", "12.233T" },
                new string[] { "99999000000000", "99.999T" },
                new string[] { "100000000000000", "100.000T" },
                new string[] { "456789000000000", "456.789T" },
                new string[] { "999999000000000", "999.999T" },
                new string[] { "1000000000000000", "1.000Q" },
                new string[] { "10000000000000000", "10.000Q" },
                new string[] { "100000000000000000", "100.000Q" },
                new string[] { "999999000000000000", "999.999Q" },
                new string[] { "1000000000000000000", "1.000a" },
                new string[] { "10000000000000000000", "10.000a" },
                new string[] { "100000000000000000000", "100.000a" },
                new string[] { "1000000000000000000000", "1.000b" },
                new string[] { "1000000000000000000000000", "1.000c" },
                new string[] { "1000000000000000000000000000", "1.000d" },
                new string[] { "1000000000000000000000000000000", "1.000e" },
                new string[] { "1000000000000000000000000000000000", "1.000f" },
                new string[] { "1000000000000000000000000000000000000", "1.000g" },
                new string[] { "1000000000000000000000000000000000000000", "1.000h" },
                new string[] { "1000000000000000000000000000000000000000000", "1.000i" },
                new string[] { "1000000000000000000000000000000000000000000000", "1.000j" },
                new string[] { "1000000000000000000000000000000000000000000000000", "1.000k" },
                new string[] { "1000000000000000000000000000000000000000000000000000", "1.000l" },
                new string[] { "1000000000000000000000000000000000000000000000000000000", "1.000m" },
                new string[] { "1000000000000000000000000000000000000000000000000000000000", "1.000n" },
                new string[] { "1000000000000000000000000000000000000000000000000000000000000", "1.000o" },
                new string[] { "1000000000000000000000000000000000000000000000000000000000000000", "1.000p" },
                new string[] { "1000000000000000000000000000000000000000000000000000000000000000000", "1.000q" },
                new string[] { "1000000000000000000000000000000000000000000000000000000000000000000000", "1.000r" },
                new string[] { "1000000000000000000000000000000000000000000000000000000000000000000000000", "1.000s" },
                new string[] { "1000000000000000000000000000000000000000000000000000000000000000000000000000", "1.000t" },
                new string[] { "1000000000000000000000000000000000000000000000000000000000000000000000000000000", "1.000u" },
                new string[] { "1000000000000000000000000000000000000000000000000000000000000000000000000000000000", "1.000v" },
                new string[] { "1000000000000000000000000000000000000000000000000000000000000000000000000000000000000", "1.000w" },
                new string[] { "1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000", "1.000x" },
                new string[] { "1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000", "1.000y" },
                new string[] { "1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000", "1.000z" },
                new string[] { "1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000", "1.000aa" },
                new string[] { "1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000", "1.000ab" },
                new string[] { "1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000", "1.000ac" },
                new string[] { "1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000", "1.000ad" },
                new string[] { "1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000", "1.000ae" },
                new string[] { "1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000", "1.000af" },
                new string[] { "1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000", "1.000ag" },
                new string[] { "1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000", "1.000ah" },
                new string[] { "1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000", "1.000ai" },
                new string[] { "1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000", "1.000aj" },
                new string[] { "1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000", "1.000ak" },
                new string[] { "1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000", "1.000al" },
                new string[] { "1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000", "1.000am" },
                new string[] { "1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000", "1.000an" },
                new string[] { "1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000", "1.000ao" },
                new string[] { "1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000", "1.000ap" },
                new string[] { "1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000", "1.000aq" },
                new string[] { "1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000", "1.000ar" },
                new string[] { "1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000", "1.000as" },
                new string[] { "1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000", "1.000at" },
                new string[] { "1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000", "1.000au" },
                new string[] { "1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000", "1.000av" },
                new string[] { "1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000", "1.000aw" },
                new string[] { "1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000", "1.000ax" },
                new string[] { "1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000", "1.000ay" },
                new string[] { "1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000", "1.000az" },
                new string[] { "1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000", "1.000ba" },
                new string[] { "1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000", "1.000bb" },
                new string[] { "1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000", "1.000bc" },
                new string[] { "1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000", "1.000bd" },
                new string[] { "1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000", "1.000be" },
                new string[] { "1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000", "1.000bf" },
                new string[] { "1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000", "1.000bg" },
                new string[] { "1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000", "1.000bh" },
                new string[] { "1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000", "1.000bi" },
                new string[] { "1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000", "1.000bj" },
                new string[] { "1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000", "1.000bt" },
                new string[] { "1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000", "1.000by" },
                new string[] { "1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000", "1.000bz" },
                new string[] { "1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000", "1.000ca" },
                new string[] { "1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000", "1.000cb" },
                new string[] { "1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000", "1.000cc" },
                new string[] { "1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000", "1.000cd" },
                new string[] { "1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000", "1.000ce" },
                new string[] { "1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000", "1.000ct" },
                new string[] { "1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000", "1.000cy" },
                new string[] { "1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000", "1.000cz" },
                new string[] { "1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000", "1.000da" },
                new string[] { "1234000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000", "1.234da" },
                new string[] { "123456000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000", "123.456da" },
                new string[] { "1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000", "1.000db" },
                new string[] { "1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000", "1.000dr" },
                new string[] { "1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000", "1.000dz" },
            };
        }
    }
}

All the tests above pass at the moment. The tests that are missing is one that checks if 1000 ^ (26 ^ 3 + 5) (the +5 is because the a formatting starts after Q) can be formatted into "1.000aaa".

How do I go about formatting procedurally large integers in the way I have described above.

回答1:

In the world of numerical notation, this is actually a solved problem. That is, you could instead use scientific notation to represent these especially large numbers. Scientific notation is compact, allows arbitrary precision for the mantissa, and readily understandable. Personally, that's the approach I'd take.

For the sake of discussion, let's look at what other alternatives you have…

On the face of it, your request boils down to a straight numeric base value to text conversion. Just as we can convert a numeric value to its textual representation in, for example, base 2, base 10, base 16, etc. we can convert a numeric value to a textual representation using base 26, using just the letters a through z as the digits.

Then your GetProceduralSuffix() method would look something like this:

static string GetProceduralSuffix(int value)
{
    StringBuilder sb = new StringBuilder();

    while (value > 0)
    {
        int digit = value % 26;

        sb.Append((char)('a'+ digit));
        value /= 26;
    }

    if (sb.Length == 0)
    {
        sb.Append('a');
    }

    sb.Reverse();
    return sb.ToString();
}

where the Reverse() extension method is this:

public static void Reverse(this StringBuilder sb)
{
    for (int i = 0, j = sb.Length - 1; i < sb.Length / 2; i++, j--)
    {
        char chT = sb[i];

        sb[i] = sb[j];
        sb[j] = chT;
    }
}

However, there's a slight problem with the above. In base 26 represented this way, the digit a corresponds to 0, and so your suffixes will never start with the letter a, at least not after the first one (that's a special case, just like when using decimal notation we use the digit 0 by itself to represent the value of zero). Instead, for example, you'll get ba after z and baa after zz.

Personally, I think that's fine. It would preclude suffixes like aaaz, but only because the suffix notation system would be logical, predictable, and easily reversed (i.e. given a suffix, it's trivial to figure out what that means numerically).

However, if you insist on a sequence like a…z, aa…zz, aaa…zzz, aaaa… and so on, you can use base 27 instead of 26, with a character other than a…z for the 0 digit, and precompute the suffixes skipping values that would have a 0 digit as you go, and then index the result. For example:

List<string> _hackedValues = new List<string>();

static void PrecomputeValues()
{
    // 531441 = 27 ^ 4, i.e. the first 5-digit base 27 number.
    // That's a large enough number to ensure that the output
    // include "aaaz", and indeed almost all of the 4-digit
    // base 27 numbers
    for (int i = 0; i < 531441; i++)
    {
        string text = ToBase27AlphaString(i);

        if (!text.Contains('`'))
        {
            _hackedValues.Add(text);
        }
    }
}

static string GetProceduralSuffix(int value)
{
    if (hackedValues.Count == 0)
    {
        PrecomputeValues();
    }

    return _hackedValues[value];
}

static string ToBase27AlphaString(int value)
{
    StringBuilder sb = new StringBuilder();

    while (value > 0)
    {
        int digit = value % 27;

        sb.Append((char)('`'+ digit));
        value /= 27;
    }

    if (sb.Length == 0)
    {
        sb.Append('`');
    }

    sb.Reverse();
    return sb.ToString();
}

Here is a complete program that illustrates both techniques, showing the text for "interesting" input (i.e. where the number of characters in the output changes):

class Program
{
    static void Main(string[] args)
    {
        int[] values = { 0, 25, 26, 675, 676 };

        foreach (int value in values)
        {
            Console.WriteLine("{0}: {1}", value, ToBase26AlphaString(value));
        }

        Console.WriteLine();

        List<Tuple<int, string>> hackedValues = new List<Tuple<int, string>>();

        for (int i = 0; i < 531441; i++)
        {
            string text = ToBase27AlphaString(i);

            if (!text.Contains('`'))
            {
                hackedValues.Add(Tuple.Create(i, text));
            }
        }

        Tuple<int, string> prev = null;

        for (int i = 0; i < hackedValues.Count; i++)
        {
            Tuple<int, string> current = hackedValues[i];

            if (prev == null || prev.Item2.Length != current.Item2.Length)
            {
                if (prev != null)
                {
                    DumpHackedValue(prev, i - 1);
                }
                DumpHackedValue(current, i);
            }

            prev = current;
        }
    }

    private static void DumpHackedValue(Tuple<int, string> hackedValue, int i)
    {
        Console.WriteLine("{0}: {1} (actual value: {2})", i, hackedValue.Item2, hackedValue.Item1);
    }

    static string ToBase26AlphaString(int value)
    {
        return ToBaseNAlphaString(value, 'a', 26);
    }

    static string ToBase27AlphaString(int value)
    {
        return ToBaseNAlphaString(value, '`', 27);
    }

    static string ToBaseNAlphaString(int value, char baseChar, int numericBase)
    {
        StringBuilder sb = new StringBuilder();

        while (value > 0)
        {
            int digit = value % numericBase;

            sb.Append((char)(baseChar + digit));
            value /= numericBase;
        }

        if (sb.Length == 0)
        {
            sb.Append(baseChar);
        }

        sb.Reverse();
        return sb.ToString();
    }
}

static class Extensions
{
    public static void Reverse(this StringBuilder sb)
    {
        for (int i = 0, j = sb.Length - 1; i < sb.Length / 2; i++, j--)
        {
            char chT = sb[i];

            sb[i] = sb[j];
            sb[j] = chT;
        }
    }
}