User:Thebigh/mysandbox: Difference between revisions
(expand) |
(more) |
||
Line 1: | Line 1: | ||
The '''Minkowski question-mark function''' converts the continued fraction representation of a number into |
The '''Minkowski question-mark function''' converts the continued fraction representation {{math|[a<sub>0</sub>; a<sub>1</sub>, a<sub>2</sub>, a<sub>3</sub>, ...]}} of a number into a binary decimal representation in which the integer part {{math|a<sub>0</sub>}} is unchanged and the {{math|a<sub>1</sub>, a<sub>2</sub>, ...}} become alternating runs of binary zeroes and ones of those lengths. The decimal point takes the place of the first zero. |
||
Thus, {{math|?}}(31/7) = 71/16 because 31/17 has the continued fraction representation {{math|[4;2,3]}} giving the binary expansion {{math|4 + 0.0111<sub>2</sub>}}. |
|||
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 {{math|?(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 {{math|?<sup>-1</sup>(x)}} |
|||
* Verify that {{math|?(φ)}} = 5/3, where {{math|φ}} is the Greek golden ratio. |
|||
* Verify that {{math|?<sup>-1</sup>(-5/9)}} = (√13 - 7)/6 |
|||
* Verify that the two functions are inverses of each other by showing that {{math|?<sup>-1</sup>(?(x))}}={{math|x}} and {{math|?(?<sup>-1</sup>(y))}}={{math|y}} for {{math|x, y}} of your choice |
|||
Don't worry about precision error in the last few digits. |
|||
==header|FreeBASIC== |
==header|FreeBASIC== |
||
<lang freebasic>#define MAXITER 151 |
<lang freebasic>#define MAXITER 151 |
||
#define MAXITER 151 |
|||
function minkowski( x as double ) as double |
function minkowski( x as double ) as double |
||
Line 73: | Line 89: | ||
print minkowski( 0.5*(1+sqr(5)) ), 5./3 |
print minkowski( 0.5*(1+sqr(5)) ), 5./3 |
||
print minkowski_inv( -5./9 ), (sqr(13)-7)/6 |
print minkowski_inv( -5./9 ), (sqr(13)-7)/6 |
||
print minkowski(minkowski_inv(0.718281828)), minkowski_inv(minkowski(0. |
print minkowski(minkowski_inv(0.718281828)), minkowski_inv(minkowski(0.1213141516171819)) |
||
</lang> |
</lang> |
Revision as of 13:41, 12 November 2020
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/17 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- 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.
header|FreeBASIC
<lang freebasic>#define MAXITER 151
- 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>