[C++] DecimalRealConversion could multiply by 5 instead of 10

[bkietz]

Describe the enhancement requested

To construct the decimal corresponding to a floating point value, we need to perform the multiplication and division mant * 2^k * 10^scale (k < 0). When performing those operations directly would result in overflow, they are broken into smaller steps of interleaved multiplication and division.

Multiplication by 10 then division by 2 can be losslessly simplified to multiplication by 5. Taking advantage of this should increase perfomance by reducing the number of interleaved steps as well as widening the range across which we can use the faster single step approach. Rewriting the above expression as mant * 5^scale * 2^(k + scale), we can use two cases:

• if k + scale >= 0 then we directly multiply by 5^scale then by 2^(k + scale)
• else if we can prove that 5^scale * mant cannot overflow, multiply by 5^scale and use RoundedRightShift to divide by `1/2^(k+scale)
• else let the greatest safe power of 5 for multiplication be 5^N; interleave multiplication by 5^N and division by 4^N since that will keep the range of active bits consistent and easy to debug

Component(s)

C++

[bkietz]

@pitrou what do you think?

[pitrou]

That's a rather interesting idea. You'll have to make sure there are enough tests to exercise all three cases thoroughly.