conversion of big int to string

[afabri]

We use i.convert_to<std::string> for a multi precision integer i and observe a factor of 10 difference for the cpp_int backend compared to the gmp_int backend. Is there a better way than using convert_to() ?

[NAThompson]

@afabri : Could you post a reproducer? Sounds like a bug that needs fixed instead of something that needs a workaround.

[jzmaddock]

Indeed, plus is there any particular reason not to just call the .str() method?

[afabri]

I have put a self contained program here on gist.github.com. Calling .str() has the same difference in performance.

[afabri]

Under vtune I can see that it is the divide_unsigned_helper() which is time consuming.

[jzmaddock]

Ah performance, not value of result, I misunderstood, apologies.

Yes we know that cpp_int division is terribly slow compared to GMP, but GMP is a tour-de-force of optimisation and we're not really trying to compete on that front (which is not to say we couldn't do better).

[afabri]

In our use case (a multiprecision float with mantissa and exponent being arbitrary precision ints) we are only interested in the leading N characters of the string representing the number.

[ckormanyos]

In our use case (a multiprecision float with mantissa and exponent being arbitrary precision ints) we are only interested in the leading N characters of the string representing the number.

Cound you do something a bit non-elegant like get the MSB (for $2^n$), then get the highest order limb and subsequently perform a table-based addition for the leading bits? It does not really sound like a lot of fun, but might work?

[afabri]

Ah performance, not value of result, I misunderstood, apologies.

Yes we know that cpp_int division is terribly slow compared to GMP, but GMP is a tour-de-force of optimisation and we're not really trying to compete on that front (which is not to say we couldn't do better).

@jzmaddock Can you give me a pointer to a publication that tells what has to be implemented to catch up?

[ckormanyos]

to a publication that tells what has to be implemented to catch up?

I'll put out a few details. cpp_int division is known to be slow. What could be done?

• Investigate Knuth long-division. I have an implementation of it (but with limbs ordered the other way around). Knuth long-division is quite difficult to program but it is rather quick for low limb counts.
• One of the things that can be done, but we are probably a long way away from, would be to visualize integer division as floating-point multiplication via numerator scaling-up and subsequent Newton-Raphson iteration and re-rationalization. If you convert cpp_int to cpp_bin_float this would be a very roundabout way to start seeing if this could help. Why? Besauce at least we go up to Karatsuba in multiplication. So although using Newton iteration to perform division is about as slow as 3 multiplications, you'd ultimately get sub-Order-N-squared in division.

@jzmaddock might add more.

P.S. I like the algorithm descriptions in:

[1] R. Brent and P. Zimmermann, "Modern Computer Arithmetic", Cambridge University Press, 2011.
[2] J. Arndt, "Matters Computational", Springer Verlag, 2011.
[3] and of course the Knuth's volume 2.