CODEWITHSUNDEEP
c#biginteger
nicomp
nicomp

Reputation: 4647

How to load a huuuuuge string into a BigInteger in C# and not lose the ASCII encoding

I am using BigInteger.Parse(some string) but it takes forever and I'm not even sure if it finishes.

However, I can convert the huge string to a byte array and jam the byte array into a BigInteger constructor in very little time but it munges the original number stored in the string because of the endian issue with BigInteger and byte arrays.

Is there a way to convert the string to a byte array and put the byte array into the BigInteger object while preserving the original number stored in ASCII in the string?

String s = "12345";  // Some huge string, millions of digits.

BigInteger bi = new BigInteger(Encoding.ASCII.GetBytes(s);  // very fast but the 12345 is lost 

// OR...
BigInteger bi = BigInteger.Parse(s);  // Takes forever therefore unuseable.

Upvotes: 2

Views: 345

Answers (1)

Titian Cernicova-Dragomir
Titian Cernicova-Dragomir

Reputation: 250036

The byte[] representation of BigInteger has little to do with the ASCII characters. Much like the byte representation of an int has little to do with the ASCII representation of it.

To parse the number, each character must be converted to the digit value, and added to the previously parsed value multiplied by 10. That is probably why it's taking so long, and any version you write will probably not perform better. It has to do something like:

    var nr=0;
    foreach(var c in "123") nr=nr*10+(c-'0');

Edit

While it is not possible to perform the conversion by just converting to a byte array, the library implementation is slower then it has to be (at least for simple scenarios that do not need internationalization for example). Using the trick suggested by Rudy Velthuis in the comments and not taking into account hex formats or internationalization, I was able to produce a version which for 303104 characters runs ~5 times faster (from 18.2s to 3.75s. For 1 milion digits the fast method takes 47s, long, but it is a huge number):

public static class Helper
{
    static BigInteger[] factors = Enumerable.Range(0, 19).Select(i=> BigInteger.Pow(10, i)).ToArray();
    public static BigInteger ParseFast(string str)
    {
        var result = new BigInteger(0);
        var n = str.Length;
        var hasSgn = str[0] == '-';
        int j;
        for (var i = hasSgn ? 1 : 0; i < n; i += j - i)
        {
            long gr = 0;
            for (j = i; j < i + 18 && j < n; j++)
            {
                gr = gr * 10 + (str[j] - '0');
            }
            result = result * factors[j-i]+ gr;

        }
        if (hasSgn)
        {
            result = BigInteger.MinusOne * result;
        }
        return result;
    }
}

Upvotes: 5

Related Questions