Greetings. Long time no post. Long post.
I'm writing a routine to convert a float number from float to string format.
I'm aware there's sprintf() to do the job already, no worry.
My goal is to make conversion from float to string without calling sprintf(), AND without using any float datatype nor the pow() function.
My function is actually ready and working.
Now I would like to make it faster, because there's lot of room for improvement.
Full code is very long to show, so I won't, unless you ask.
My first issue was to calculate a power of 2, or an inverse power of 2 where required, by using only integer math.
Given the limited amount of significant digits to show, for the final rapresentation of a float, I concluded that using unsigned __int64 to calculate these powers was enough.
Power of 2 are calculated in a simple manner: keep multipling by 2 so long you are not about to cause an overflow. If overflow is about to happen, discard the last digits of the current power ( Pow2 /= 10; ), take note that you lost a digit, perform rounding if needed, and resume the multiplications by 2.
The inverse of a power of 2 is identical in mechanics, with the differece that I calculate powers of 5 and then adjust the exponent by dividing for the corresponding power of 10.
In other words:
// -n n n
// 2 = 5 / 10
Of course I adopt basic optimizations to cut the calculation times of the first powers.
For example the first 27 powers of 5 are pre-generated and held in a lookup array of DWORD64.
Past that limit, I adopt the multiply/discard method described earlier.
The first place to optimize is where I discard the last digit of a power, then perform the rounding.
// If current power is any greater than this, the next power will overflow.
#define kThreshold ((DWORD64 (1) << 63) - 1)
DWORD Lost = 0;
// Are we about to overflow?
if (Pow2 > kThreshold)
// Yes, discard the last digit.
// Reduce current power to 1/10th.
DWORD64 _10th = Pow2 / 10;
// Retrieve the lost digit.
const DWORD Digit = DWORD (Pow2 - (_10th * 10));
// Perform rounding (if necessary).
if (Digit > 4) ++_10th;
++Lost; // Keep note we lost another digit.
Pow2 = _10th;
// Calculate next power.
Pow2 *= 2;
Very basic, as you see.
I know "Pow2 / 10;" can be rewritten as "(Pow2 >> 1) / 5;", which should (in theory) speed up the division, but it also creates 1 extra temporary value from "(Pow2 >> 1)".
Profiling showed no sensible performance gain =/
The same goes for the "(_10th * 10)" which may become "((_10th * 5) \<\< 1)".
What bothers me most, here, is the approach I follow to get the value of Digit.
I could obtain it by doing "Pow2 % 10", but that would be a(nother) division.
And I need to perform "Pow2 / 10" anyway, so I prefer the multiplication method.
I was wondering if there's a clever trick to isolate the last digit of a number in base 10.
Can't think of any...
Another candidate for optimization is where I actually sum the calculated powers to reconstruct the Integer and Fractional parts of the float.
Using DWORD64 to store the powers, give me only 19 digits of precision.
So I thought to convert those powers to string form, and sum them, digit by digit.
The sum process itself is not as slow as one might imagine.
The real problem is the conversion from integers to string form.
The idea to use strings was born to finish the routine quickly.
Now I need to make things better.
Ciao ciao : )
[EDIT] Oops... after writing this I went back to the program and 'noticed' I was doing a big stupid thing.
There's no need to sum the individual powers one by one. I get the same result by offsetting the bits for the integer or fractional part.
I got carried away with the calculation of powers and lost sight of the whole
Now the times required for converting to string format have decreased (roughly) from 1/3rd to 1/7th.
The problem of extracting the least significant digit from a number in base 10 remains, though.
Can't stop thinking there must be a faster way than what I do now...
Ciao ciao : )