How to resolve the algorithm Minkowski question-mark function step by step in the Go programming language

Published on 12 May 2024 09:40 PM
#Go

How to resolve the algorithm Minkowski question-mark function step by step in the Go programming language

Table of Contents

Problem Statement

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.

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

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Minkowski question-mark function step by step in the Go programming language

Minkowski's Question Mark Function

The provided Go code is an implementation of Minkowski's question mark function and its inverse.

Minkowski's Question Mark Function

The function minkowski(x) computes the continued fraction expansion of x and then uses it to calculate the Minkowski question mark function.

The Minkowski question mark function is defined as follows:

?(x) = floor(x) + ?(x - floor(x)) if x > 1 or x < 0
?(1) = 1
?(0) = 0
?(x) = y + d  where:
   y is the continued fraction expansion of x
   d = 1/2^n, where n is the number of times y can be added to itself without changing 
**Minkowski's Inverse Question Mark Function**

The function `minkowskiInv(x)` computes the inverse of Minkowski's question mark function using a continued fraction expansion.

The inverse Minkowski question mark function is defined as follows:

?^-1(x) = floor(x) + ?^-1(x - floor(x)) if x > 1 or x < 0 ?^-1(1) = 1 ?^-1(0) = 0 ?^-1(x) = 1 / (c[n] + 1 / (c[n-1] + ... + 1 / (c[0] + 1 / d))), where: d = 1/2^n, where n is the number of times y can be added to itself without changing c[i] is the ith element of the continued fraction expansion of x Output:

The program prints three pairs of values:

  • minkowski(0.5*(1+math.Sqrt(5))) and 5.0/3.0, which are equal within the specified precision.
  • minkowskiInv(-5.0/9.0) and (math.Sqrt(13)-7)/6, which are equal within the specified precision.
  • minkowski(minkowskiInv(0.718281828)) and minkowskiInv(minkowski(0.1213141516171819)), which are equal within the specified precision.

These results demonstrate that the implementation correctly computes the Minkowski question mark function and its inverse.

Source code in the go programming language

package main

import (
    "fmt"
    "math"
)

const MAXITER = 151

func minkowski(x float64) float64 {
    if x > 1 || x < 0 {
        return math.Floor(x) + minkowski(x-math.Floor(x))
    }
    p := uint64(x)
    q := uint64(1)
    r := p + 1
    s := uint64(1)
    d := 1.0
    y := float64(p)
    for {
        d = d / 2
        if y+d == y {
            break
        }
        m := p + r
        if m < 0 || p < 0 {
            break
        }
        n := q + s
        if n < 0 {
            break
        }
        if x < float64(m)/float64(n) {
            r = m
            s = n
        } else {
            y = y + d
            p = m
            q = n
        }
    }
    return y + d
}

func minkowskiInv(x float64) float64 {
    if x > 1 || x < 0 {
        return math.Floor(x) + minkowskiInv(x-math.Floor(x))
    }
    if x == 1 || x == 0 {
        return x
    }
    contFrac := []uint32{0}
    curr := uint32(0)
    count := uint32(1)
    i := 0
    for {
        x *= 2
        if curr == 0 {
            if x < 1 {
                count++
            } else {
                i++
                t := contFrac
                contFrac = make([]uint32, i+1)
                copy(contFrac, t)
                contFrac[i-1] = count
                count = 1
                curr = 1
                x--
            }
        } else {
            if x > 1 {
                count++
                x--
            } else {
                i++
                t := contFrac
                contFrac = make([]uint32, i+1)
                copy(contFrac, t)
                contFrac[i-1] = count
                count = 1
                curr = 0
            }
        }
        if x == math.Floor(x) {
            contFrac[i] = count
            break
        }
        if i == MAXITER {
            break
        }
    }
    ret := 1.0 / float64(contFrac[i])
    for j := i - 1; j >= 0; j-- {
        ret = float64(contFrac[j]) + 1.0/ret
    }
    return 1.0 / ret
}

func main() {
    fmt.Printf("%19.16f %19.16f\n", minkowski(0.5*(1+math.Sqrt(5))), 5.0/3.0)
    fmt.Printf("%19.16f %19.16f\n", minkowskiInv(-5.0/9.0), (math.Sqrt(13)-7)/6)
    fmt.Printf("%19.16f %19.16f\n", minkowski(minkowskiInv(0.718281828)),
        minkowskiInv(minkowski(0.1213141516171819)))
}

You may also check:How to resolve the algorithm Knuth shuffle step by step in the Elixir programming language
You may also check:How to resolve the algorithm Mutex step by step in the Racket programming language
You may also check:How to resolve the algorithm Reverse a string step by step in the PL/I programming language
You may also check:How to resolve the algorithm Weird numbers step by step in the Phix programming language
You may also check:How to resolve the algorithm Literals/Integer step by step in the REBOL programming language