Open afabri opened 2 months ago
@afabri : Could you post a reproducer? Sounds like a bug that needs fixed instead of something that needs a workaround.
Indeed, plus is there any particular reason not to just call the .str()
method?
I have put a self contained program here on gist.github.com. Calling .str()
has the same difference in performance.
Under vtune I can see that it is the divide_unsigned_helper()
which is time consuming.
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).
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.
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?
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?
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?
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.
We use
i.convert_to<std::string>
for a multi precision integeri
and observe a factor of 10 difference for thecpp_int
backend compared to thegmp_int
backend. Is there a better way than usingconvert_to()
?