User:Thebigh/mysandbox

The Minkowski question-mark function converts the continued fraction representation of a number into

header|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.718281828)) </lang>