Author: | Wojciech Muła |
---|---|

Added on: | 2015-12-29 |

The conversion of floating-point numbers to a string representation is not an easy task. Such procedure must deal with different special FP values, perform proper rounding and so on. The paper Printing Floating-Point Numbers Quickly and Accurately [PDF] by Robert G. Burger & R. Kent Dybvig describes a procedure which solves the problem correctly.

However, in some applications (mostly logging, debugging) rounding and accuracy are not as important as the speed. Sometimes we simply want to know if a number was 1000.5 or 0.5 and even if we read "0.499999" nothing wrong would happen.

A floating-point number could be represented as a fixed-point number of size
64:64 and then fast conversion routines could be used. This approach is several
times faster than standard `sprintf`, moreover the method is also suitable
for embedded systems.

The biggest drawback is that the method is able to convert only a sub-range of possible floating-point values. However, the sub-range covers reasonable interval of numbers and in the practice it should be acceptable.

The conversion from floating-point to integer require a few simple bit-instructions: bit-ands, bit-ors and shifts. The full procedure is described in article Convert float to int without FPU/SSE. Of course not all values could be converted, and some testing is needed before doing conversion.

When an integer is ready we can use any procedure to convert it to the text. Even the simplest, naive method would be good; I've described some other, faster methods in the article SSE: conversion integers to decimal representation.

The fraction part is obtained in the same way as the integer part: by shifting floating-point binary representation. The layout of fraction part:

+----+--------------+ |0000|xxxxxxx...xxxx| +----+--------------+ | | | | | +- fraction bits | | | +- decimal dot | +- integer part (4 highest bits)

Such number is then treated as an integer number and the naive method of conversion fraction numbers is used. In each step fraction value is multiplied by 10, then the integer part is extracted from the result:

uint64_t fraction = ... while (fraction != 0) { fraction *= 10; const uint64 intpart = fraction >> (64-4); // save intpart as ASCII fraction &= 0x0ffffffffffffffflu; }

In a single iteration following operations are performed:

- 1 multiplication by constant (on x86 this may be single
`lea`); - 1 right shift by constant;
- 1 bit-and.

Sample code is available at github. The program `speed` does conversion
of wide range of `float` values using `sprintf` and the described method.

Following times were printed on my Core i5 (gcc 4.9.2 with `-O3` flag):

`sprintf`: 8.842 s- custom: 0.594 s.

The speedup is **around 15 times**. However, `sprintf` does rounding,
parsing a format string, allocates memory etc. I guess the real speedup
would be **4 to 8 times**, but still it's really impressive improvement.