Skip to content

Instantly share code, notes, and snippets.

@pallas
Last active December 17, 2015 06:28
Show Gist options
  • Save pallas/5565556 to your computer and use it in GitHub Desktop.
Save pallas/5565556 to your computer and use it in GitHub Desktop.
Minkowski question mark function
// 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;
}
//
@pallas
Copy link
Author

pallas commented May 16, 2013

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment