Minkowski question-mark function

Minkowski question-mark function is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

The Minkowski question-mark function converts the continued fraction representation [a₀; a₁, a₂, a₃, ...] of a number into a binary decimal representation in which the integer part a₀ is unchanged and the a₁, a₂, ... 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/17 has the continued fraction representation [4;2,3] giving the binary expansion 4 + 0.0111₂.

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- choose the one 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.

FreeBASIC

<lang freebasic>#define MAXITER 151

function minkowski( x as double ) as double

   if x>1 or x<0 then return int(x)+minkowski(x-int(x))
   dim as ulongint p = int(x)
   dim as ulongint q = 1, r = p + 1, s = 1, m, n
   dim as double d = 1, y = p
   while true 
       d = d / 2.0
       if y + d = y then exit while
       m = p + r
       if m < 0 or p < 0 then exit while
       n = q + s
       if n < 0 then exit while
       if x < cast(double,m) / n then
           r = m
           s = n
       else
           y = y + d
           p = m
           q = n
       end if
   wend
   return y + d

end function

function minkowski_inv( byval x as double ) as double

   if x>1 or x<0 then return int(x)+minkowski_inv(x-int(x))
   if x=1 or x=0 then return x
   redim as uinteger contfrac(0 to 0)
   dim as uinteger curr=0, count=1, i = 0
   do
       x *= 2
       if curr = 0 then
           if x<1 then
               count += 1
           else
               i += 1
               redim preserve contfrac(0 to i)
               contfrac(i-1)=count
               count = 1
               curr = 1
               x=x-1
           endif
       else
           if x>1 then
               count += 1
               x=x-1
           else
               i += 1
               redim preserve contfrac(0 to i)
               contfrac(i-1)=count
               count = 1
               curr = 0
           endif
       end if
       if x = int(x) then
           contfrac(i)=count
           exit do
       end if
   loop until i = MAXITER
   dim as double ret = 1.0/contfrac(i)
   for j as integer = i-1 to 0 step -1
       ret = contfrac(j) + 1.0/ret
   next j
   return 1./ret

end function

print minkowski( 0.5*(1+sqr(5)) ), 5./3 print minkowski_inv( -5./9 ), (sqr(13)-7)/6 print minkowski(minkowski_inv(0.718281828)), minkowski_inv(minkowski(0.1213141516171819)) </lang>

Output:

 1.666666666669698           1.666666666666667
-0.5657414540893351         -0.5657414540893352
 0.7182818280000092          0.1213141516171819