Minkowski question mark function

minkowski_question_mark.cc

// All rights reserved,
// Derrick Pallas
// License: zlib

#include <cmath>
#include <cstdlib>

template <typename fp_type>
fp_type minkowski_question_mark(const fp_type fp) {
    float a0 = floor(fp);

    int sum_a = 1;
    bool add_term = true;
    float sum_terms = 0.0;

    for (float a, t = fp - a0 ; ; ) {
        t = std::modf(1.0/t, &a);
        sum_a -= int(a);
        float term = exp2(sum_a);

        if (!std::isnormal(term))
            break;

        sum_terms += add_term ? term : -term;
        add_term = !add_term;
    }

    return a0 + sum_terms;
}

//

The loop generates the fractional terms of the continued fraction and sums them. The sign of this sum is kept negative for simplicity, since we divide by 2**(sum-1) to generate the next term in the overall, alternating sum of terms. Once this term is non-normal, we stop.