Efficiently convert large BigInteger to string, ToString() takes too long

Question

I was working on a factorial function, and factorial with big integers can get REALLY long.

For example, 200000! = 973350 digits long and if i just use ToString(), things take a very long time.

200000! takes longer to convert to string then actually compute it!

I've tried to set the factorial function to a Process, and then use ProcessorAffinity to pin the Thread to a specific core so that that core ONLY converts to string, but that just took exactly the same time.

Also, the reason I want to convert it to string is because I want to write the output (FactFile) to a text file.

String Conversion code:

using (Process proc = Process.GetCurrentProcess())
{
     proc.ProcessorAffinity = (IntPtr)0x0003;
     FactFile = Res.ToString(); //FactFile is Going to be the final string, Res is the Factorial.
}

here's my code for Factorial:

for (BigInteger i = 1; i < k; i++)
{
    Res *= i; // Res is the number to Calculate the factorial of
}

200000! takes 15 seconds to compute, and then another 18 seconds to convert it to string (this can differ from cpu to cpu, I have an i7).

Reminder: What's the most efficient way to convert to string?

output:

Total Computation Time: 00:00:16.2007276
String Conversion Time: 00:00:19.4049292

Why do you need to output it as a decimal string? Are you going to write it down? — John Wu, May 11 '19 at 08:06
I think 19 seconds is a pretty fair time tbh. Why do you think it is possible to go faster? — Sweeper, May 11 '19 at 08:06
https://stackoverflow.com/questions/18911262/parallel-calculation-of-biginteger-factorial — Inside Man, May 11 '19 at 08:12
If it were a hex string, it could probably be done in parallel, but I am not sure about a decimal string. — Sweeper, May 11 '19 at 08:13
@OP I mean a number expressed as a string in base 10, a decimal string, as opposed to binary or hexadecimal. Why do you want a human-readable, millilon-digit long number? You could just store it in binary or hex, since whatever is going to read it is going to be another program, and would probably have the same difficulty converting it back. — John Wu, May 11 '19 at 08:15

score 2 · Accepted Answer · answered May 11 '19 at 22:14

Here is a 40% faster stringifier. It divides the big integer repeatedly with the number 10^10000, stringifies the remainder, and finally joins all the strings together. It can handle negative numbers also.

public static string ToDecimalString(this BigInteger value)
{
    if (value == 0) return "0";
    var digits = 10000;
    var divider = BigInteger.Pow(10, digits);
    var parts = new Stack<string>();
    while (true)
    {
        BigInteger remainder;
        value = BigInteger.DivRem(value, divider, out remainder);
        if (value != 0)
        {
            parts.Push(BigInteger.Abs(remainder).ToString().PadLeft(digits, '0'));
        }
        else
        {
            parts.Push(remainder.ToString());
            break;
        }
    }
    return String.Join("", parts);
}

It can become slightly faster by offloading the stringifying of the remainders to a background thread. Unfortunately the slowest part of the algorithm (the call to BigInteger.DivRem) is not parallelizable.

public static string ToDecimalStringParallel(this BigInteger value)
{
    if (value == 0) return "0";
    var digits = 10000;
    var divider = BigInteger.Pow(10, digits);
    var remainders = new BlockingCollection<BigInteger>();
    var parts = new ConcurrentStack<string>();
    var task = Task.Run(() =>
    {
        foreach (var remainder in remainders.GetConsumingEnumerable())
        {
            parts.Push(BigInteger.Abs(remainder).ToString().PadLeft(digits, '0'));
        }
    });
    while (true)
    {
        BigInteger remainder;
        value = BigInteger.DivRem(value, divider, out remainder);
        if (value != 0)
        {
            remainders.Add(remainder);
        }
        else
        {
            remainders.CompleteAdding();
            task.Wait();
            parts.Push(remainder.ToString());
            break;
        }
    }
    return String.Join("", parts);
}

I tested this with a number having 222.000 decimal digits: `BigInteger.Pow(13, 200000)`, and it is around 40% faster compared to the direct `ToString()`. I have not enough patience to test it with `200000!`. It is possible that the performance could deteriorate with larger numbers, in which case the variable `digits` would need some tweaking. — Theodor Zoulias, May 12 '19 at 08:19
@TheodorZoulias do i input the number i want to "facotialize" or the output? so do i input 50, or 50 factorial? But thanks! — Omer Enes, May 13 '19 at 14:36
@OmerEnes the input is the large number you want to convert to string. In your example it's the 50 factorial. — Theodor Zoulias, May 13 '19 at 16:48

score 1 · Answer 2 · answered May 11 '19 at 13:45

For n! above n = 24, the result will have more digits than the value of input n.

That explosion of digits causes ToString to have to do more work than the factorial (n-1 multiplies vs more than n divides).

However because BigInteger operations take longer based on the magnitude of the numbers they work on, you can divide by a factor first, e.g. for your 200000! example:

var asString = Res.ToString()

Versus:

BigInteger[] bits = new BigInteger[2];
bits[0] = BigInteger.DivRem(Res,  BigInteger.Pow(new BigInteger(10), 486675), out var remainder);
bits[1] = remainder;
var strs = new string[2];
System.Threading.Tasks.Parallel.For(0, 2, (i) => 
{
    strs[i] = bits[i].ToString();
});
var asString = strs[0] + strs[1];

I found this to be 5 seconds faster but:

I had to choose a factor of 10^486675 to divide the digits equally - not sure how you'd do that in general
The initial DivRem takes 8 seconds

See also some existing attempts to speed up both factorial calculation and bigint to base 10 by breaking up the work.

The conclusion of the second one seemed to be.. don't convert large BigIntegers to base 10!

Efficiently convert large BigInteger to string, ToString() takes too long

2 Answers2

Linked