The Minkowski question-mark function converts the continued fraction representation [a0; a1, a2, a3, ...] of a number into a binary decimal representation in which the integer part a0 is unchanged and the a1, a2, ... become alternating runs of binary zeroes and ones of those lengths. The decimal point takes the place of the first zero.

Thus, ?(31/7) = 71/16 because 31/7 has the continued fraction representation [4;2,3] giving the binary expansion 4 + 0.01112.

Among its interesting properties is that it maps roots of quadratic equations, which have repeating continued fractions, to rational numbers, which have repeating binary digits.

The question-mark function is continuous and monotonically increasing, so it has an inverse.

 Produce a function for ?(x).   Be careful: rational numbers have two possible continued fraction representations:
   [a0;a1,... an−1,an]     and 
   [a0;a1,... an−1,an−1,1] 
 Choose one of the above that will give a binary expansion ending with a   1.
 Produce the inverse function ?-1(x)
 Verify that ?(φ) = 5/3, where φ is the Greek golden ratio.
 Verify that ?-1(-5/9) = (√13 - 7)/6
 Verify that the two functions are inverses of each other by showing that ?-1(?(x))=x and ?(?-1(y))=y for x, y of your choice 


Don't worry about precision error in the last few digits.



See also

 Wikipedia entry: Minkowski's question-mark function


with javascript_semantics
constant MAXITER = 151
 
function minkowski(atom x)
    atom p = floor(x)
    if x>1 or x<0 then return p+minkowski(x-p) end if
    atom q = 1, r = p + 1, s = 1, m, n, d = 1, y = p
    while true do
        d = d/2
        if y + d = y then exit end if
        m = p + r
        if m < 0 or p < 0 then exit end if
        n = q + s
        if n < 0 then exit end if
        if x < m/n then
            r = m
            s = n
        else
            y = y + d
            p = m
            q = n
        end if
    end while
    return y + d
end function
 
function minkowski_inv(atom x)
    if x>1 or x<0 then return floor(x)+minkowski_inv(x-floor(x)) end if
    if x=1 or x=0 then return x end if
    sequence contfrac = {}
    integer curr = 0, count = 1
    while true do
        x *= 2
        if curr = 0 then
            if x<1 then
                count += 1
            else
                contfrac &= count
                count = 1
                curr = 1
                x -= 1
            end if
        else
            if x>1 then
                count += 1
                x -= 1
            else
                contfrac &= count
                count = 1
                curr = 0
            end if
        end if
        if x = floor(x) then
            contfrac &= count
            exit
        end if
        if length(contfrac)=MAXITER then exit end if
    end while
    atom ret = 1/contfrac[$]
    for i = length(contfrac)-1 to 1 by -1 do
        ret = contfrac[i] + 1.0/ret
    end for
    return 1/ret
end function
 
printf(1,"%20.16f %20.16f\n",{minkowski(0.5*(1+sqrt(5))), 5/3})
printf(1,"%20.16f %20.16f\n",{minkowski_inv(-5/9), (sqrt(13)-7)/6})
printf(1,"%20.16f %20.16f\n",{minkowski(minkowski_inv(0.718281828)), 
                              minkowski_inv(minkowski(0.1213141516171819))})
