I played with bits and Calc.exe. That is, I experimented loosely like I
do when I’m lost (everyone has his own way to deal with problems).

Looking for a way to simplify the **>> 1**, then **/ 5** thing, I
noticed a bizarre property.

(I call it ‘property’ now that I see it is not the coincidence I
thought in the beginning).

Suppose you want to divide a 16 bits number by 10.

Example:**59561** (binary: **1110**.**1000** | **1010**.**1001**)

Goal is: 59561 / 10 = **5956** (binary: **1**.**0111** |
**0100**.**0100**)

If we take 16 bits all ON, we obtain this value: 65535 (such a
discovery :p )

Divide this number by 5, and obtain 13107. A magic number.

Now, if we multiply 59561 by 13107, we obtain:

780666027 (binary: **10**.**1110** | **1000**.**1000** |
**0000**.**0100** | **1010**.**1011**).

We can almost recognize in this thing the bits for the 5956 we are
after…

In fact if we add 1, and then divide by 2 (or shift right by 1), we
obtain:

390333014 (binary: **1**.**0111** | **0100**.**0100** |
**0000**.**0010** | **0101**.**0110**)

Divide this by 65535 (or shift it right by 16 bits), and what remain
will spell: 5956.1000etc, the integer part of which is 5956 : )

And the division by 10 is done without using division.

Honestly I don’t understand why it is so. But I see it is so every time.

What I described works for any 16 bit number to divide by 10.

If I want to use it for 8 bits numbers, the magic number is: ((1 << 8)
- 1) / 5

And then take the higher 8 bits of the final 16 bits value.

Similarly for a 32 bits number to divide by 10, the magic number is: ((1
<< 32) - 1) / 5

And then take the higher 32 bits of the final 64 bits value.

So… for a 64 bits number to divide by 10 (what I’m after), I have to
take the higher 64 bits of the final 128 bits value.

Switching to 128 bits integers is too much, I think.

I’m lost again. Help?

Ciao ciao : )

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:

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.

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.

Any suggestions?

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 :p

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…

Please, anyone?

Ciao ciao : )

[/EDIT]