Best performance for basic arbitrary-precision arithmetic with arbitrary base [closed]

Question

What is the best way to perform basic arbitrary-precision arithmetic on an arbitrary base, with best performance ?

I was thinking about switching to binary, and then work with some inline assembly, but actually, I need the best-performance way to do it and I am not sure that this is the best way to do it.

EDIT : I do not want to use any library except the standart C++ one.

Answer 1

The problem is, "best" performance attainable with multiprecision numeric algorithms very strongly depends on the data you're working with (such as average order of numbers you may need to calculate). Consider the discussion of algorithm selection used by gnu gmp as an example:

https://gmplib.org/manual/Algorithms.html

Gnu GMP code is also used inside glibc (in particular, in precise floating point conversion code), so in a sense it is part of a "standard c" library.

Speaking of personal experience, it is extremely difficult to beat GMP's performance figures (in fact, it is rather difficult to even get within factor of 2 to GMP's performance in a general case, so if performance is an absolute priority you may want to reconsider your design goals). Performance in multiprecision calculations is not strongly dependent on implementation technique (so you're not going to win anything by using assembly instead of something like Java for this matter, if your numbers are reasonably long) - the algorithmic complexities will necessarily dominate. In fact, it makes sense to start with highest level language available and optimize from there.

And just in case, you should definitely go through chapter 4, volume 2 of Knuth's TAoCP if you haven't done so already.

I know this is probably not the answer you're looking for, but it's longer than a comment.