search

cp-algorithms / cp-algorithms

Algorithm and data structure articles for https://cp-algorithms.com (based on http://e-maxx.ru)
https://cp-algorithms.com/
Creative Commons Attribution Share Alike 4.0 International
7.29k stars 1.53k forks source link

Arbitrary-Precision Arithmetic base #1034

Open jxu opened 1 year ago

jxu commented 1 year ago

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 commented 1 year ago

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

jxu commented 1 year ago

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 commented 1 year ago

@jakobkogler what do you think?

jakobkogler commented 1 year ago

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?