Provide Minkowski's question mark function and Conway's box function

[slel]

This is to provide Minkowski's question mark function
and Conway's box function.

Requested by Pierre Arnoux.

Wikipedia: https://en.wikipedia.org/wiki/Minkowski's_question-mark_function

Sage-devel discussion: https://groups.google.com/d/topic/sage-devel/uvGKvMQQpws/discussion

Component: number theory

Keywords: continued_fraction

Issue created by migration from https://trac.sagemath.org/ticket/28853

[slel]

comment:1

Tentative implementation for Minkowski's question mark function:

def mqm(x):
    r"""
    Minkowski's question-mark function.

    Reference: :wikipedia:`Minkowski's_question-mark_function`.
    """
    c = list(continued_fraction(x)[:30])
    res = c[0]
    aa = c[1:]
    s = 2.
    for a in aa:
        s = (-s) >> a
        res -= s
    return res

and for Conway's box function:

def box(x):
    r"""
    Conway's box function.

    Reference: :wikipedia:`Minkowski's_question-mark_function`.
    """
    aa = [floor(x)]
    s = (RR(x - aa[0])/2).str(base=2)[2:]
    if 'e-' in s:
        s, e = s.split('e-')
        s = '0' * (int(e)-1) + '1' + s
    y = [int(i) for i in s]
    d = 1
    while y and any(y):
        try:
            a = y.index(d)
        except ValueError:
            a = len(y)
        aa.append(a)
        y = y[a:]
        d = 1 - d
    return RR(continued_fraction(aa))

Plots of these two functions and their compositions:

plots = [
    plot(lambda x: mqm(x), (0, 1), aspect_ratio=1),
    plot(lambda x: box(x), (0, 1), aspect_ratio=1),
    plot(lambda x: mqm(box(x)), (0, 1), aspect_ratio=1),
    plot(lambda x: box(mqm(x)), (0, 1), aspect_ratio=1),
]
graphics_array(plots, ncols=2)

[slel]

comment:2

Sage-devel discussion: https://groups.google.com/d/topic/sage-devel/uvGKvMQQpws/discussion

[embray]

comment:3

Ticket retargeted after milestone closed

[mkoeppe]

comment:4

Batch modifying tickets that will likely not be ready for 9.1, based on a review of the ticket title, branch/review status, and last modification date.