Arbitrary-Precision Arithmetic base

[jxu]

Article: Arbitrary-Precision Arithmetic

Problem:
Is using base 10^9 really better than using a base like 2^30? Seems like modulo and carry flag operations would be much more efficient, at the cost of slower decimal I/O.

[adamant-pwn]

I'm not sure, base conversion is typically quite slow

[jxu]

I guess it depends which is done more - base conversion or arithmetic. I think GMP uses full words as its "base" to speed up operations.

[jxu]

@jakobkogler what do you think?

[jakobkogler]

I personally use the base $10^4$ in my big-integer library.
The intuition was, that multiplications between two digits can be done with 32-bit integers.
But it's probably a stupid idea, as operations like addition are then twice as slow.
And I don't think I've ever benchmarked if multiplications are really that much faster.
However it was fast enough for any big-integer problems that I ever solved.

The obvious algorithm for base conversion is $O(n^2)$ for an n-digit number.
With divide and conquer you can get down to $O(n \log^2 n)$: see here https://codeforces.com/blog/entry/95047
Back then I didn't know about this trick, so the choice for a power of 10 was the only way.

Also, modulo operations are not that bad. For addition/subtraction you don't need to do a modulo operation, you can just compare ala if (result >= mod) result -= mod;.
And for multiplication: if the compiler knows the modulus at compile time, it can optimize modulo operations (e.g. by Strength reduction).

However you are correct, that if you do a lot of operations, then a binary base will be faster.

Anyway, big integer problems in competitive programming don't have super tight limits. So it doesn't matter too much which version we present on the website. (Although the D&C trick might be interesting either way, regardless if it leads to a better way or not).

If you want to know the difference, why not implement two versions yourself and publish the results?