Dragon4 Algorithm for printing floating point numbers

IEEE 754 — Floating Points

The representation of floating point numbers is fascinating. Each number is represented in three parts: sign bit, the exponenet and the mantessa or the fraction. Where the value of the floating point number is \(value = sign \times 1.mantissa \times 2^{exposant}\).

For example, 0b 0 01111100 01000000000000000000000: the sign is positif and the exponent is \(124 − 127 = −3\). The mantessa is 0b1.01000000000000000000000 is \(1.25\) in decimal \((1 \times 2^0 + 0 \times 2^{−1} + 1 \times 2^{−2}\)) thus the floating point number is \(+1.25 \times 2^{−3} = +0,15625\).

Dragon4

This article was a great resource to understand and implement this advanced algorithm. I shall describe briefly what is the idea of the algorithm.

We first compute the values of the numerator and denominator based on the sign of the exponent.

t_bigint numerator;
t_bigint denominator;
if (exponent > 0) {
	numerator = bigint_bls(mantissa, exponent);
    denominator = 1;
} else {
	numerator = mantissa;
    denominator = bigint_bls(1, -exponent);
}

Then we need to scale the numerator and denominator so that the value has a single digit in the real part.

if (sci_exponent > 0) {
    denominator = bigint_mul(denominator, bigint_pow(10,sci_exponent));
} else if (sci_exponent < 0) {
    numerator = bigint_mul(numerator, bigint_pow(10, sci_exponent));
}

At last, while there is something to be parsed, we parse it by doing the division between the numerator and denominator and getting the digit that we isolated previously. Then, subtract the value from the fraction and proceed.

int num_digits = 0;
while (numerator > 0.0) {
	int digit = bigint_div(numerator, denominator);
    digits[num_digits++] = '0' + digit;
    numerator = bigint_sub(bigint_mul(digit, denominator));
    numerator = bigint_mul(numerator, 10);
}

The original implementation can be found here, that was an adaptation to my own implementation.

Implementation

I have implemented this algorithm as a part of a printf(3) clone I made for study purposes. It is fairly fast and responsive, and also there are the usual flavours like snprintf and dprintf.

Additional resources

This paper explains another manner to achieve the same thing, printing floats.