Wikimore

Summary

DescriptionMonotonic dense jumps.pdf	English: Monotonic function with a dense set of jump discontinuities. It is defned as $F(x)=\sum _{i=0,\;\;q_{i}\leq x}^{\infty }0.9999^{i}$ , where $(q_{i})_{i\in \mathbb {N} }$ is the diagonal enumeration (e.g. File:Diagonal argument.svg) of the nonnegative rational numbers, i.e. $({\frac {0}{1}},\;\;{\frac {1}{1}},{\frac {0}{2}},\;\;{\frac {2}{1}},{\frac {1}{2}},{\frac {0}{3}},\;\;{\frac {3}{1}},{\frac {2}{2}},{\frac {1}{3}},{\frac {0}{4}},\;\;{\frac {4}{1}},\ldots )$ , but with reducible fractions omitted. — The picture shows an approximation of this function, viz. $f(x)=\sum _{i=0,\;\;q_{i}\leq x}^{152032}0.9999^{i}$ , which considers all 152032 fractions with a numerator up to 500 and a denominator up to 501. The maximal plotting error $\max _{0\leq x\leq 500}F(x)-f(x)$ can be estimated to be less than $\sum _{i=152032}^{\infty }0.9999^{i}=0.00249462$ . In the plot, the red line shows $f(x)$ , and the grey line shows $f(x)+0.00249462$ , if visible at all; the value of $F(x)$ lies somewhere between red and grey line. Seven views on different sections of the curve are shown, correponding to $x$ ranges of 10.000 , ... , 11.000 (large plot), 0.000 , ... , 500.000 (top left insertion), 450.000 , ... , 500.000 (top mid insertion), 0.000 , ... , 0.003 (center left insertion), 1.990 , ... , 2.010 (center right insertion), 0.490 , ... , 0.510 (bottom mid insertion), and 0.990 , ... , 10.010 (bottom right insertion). The approximated function $f(x)$ is monotonically non-decreasing by definition. The unapproximated function $F(x)$ is even monotonically increasing, since $x<y$ implies $x<q_{i}<y$ for some $q_{i}\in \mathbb {Q}$ , hence $F(x)<F(x)+0.9999^{i}\leq F(q_{i})\leq F(y)$ . Moreover, $F(x)$ has, at every $q_{i}\in \mathbb {Q}$ , a jump disconitnuity of size $0.9999^{i}$ .
Date	7 January 2022
Source	Own work, following the example of 2 Jan 2022 by en:User:Ninjamin at en:Monotonic_function#Some_basic_applications_and_results
Author	Jochen Burghardt
Other versions	File:Monotonic dense jumps.pdf * File:Monotonic dense jumps svg.svg

Gnuplot source code

set term pdf size 22,13
set term pdf font "sans,20"
set output "monotonic_dense_jumps.pdf"
set key off
set multiplot

# large
set title "Around 10.5"
set xrange [9.99:11.01]
set yrange [9087:9166]
set xtics 0.05
set ytics 5
  plot "monotonic_dense_jumps.gpdat" using 1:3 with lines lc 8 title ""
  plot "monotonic_dense_jumps.gpdat" using 1:2 with lines lc 7 title ""

set border linecolor 6
set title textcolor lt 6

# top left
set size 0.3, 0.3
set origin 0.05, 0.65

set title "All"
set grid
set xrange [-2:500]
set yrange [0:10200]
set xtics 100
set ytics 2000
  plot "monotonic_dense_jumps.gpdat" using 1:3 with lines lc 8 title ""
  plot "monotonic_dense_jumps.gpdat" using 1:2 with lines lc 7 title ""

# top mid
set size 0.3, 0.3
set origin 0.35, 0.65

set title "Upper right end"
set xrange [450:500]
set yrange [9999.94:10000]
set xtics 10
set ytics 0.02
  plot "monotonic_dense_jumps.gpdat" using 1:3 with lines lc 8 title ""
  plot "monotonic_dense_jumps.gpdat" using 1:2 with lines lc 7 title ""

# mid left
set size 0.3, 0.3
set origin 0.05, 0.35

set title "Lower left end"
set xrange [-0.00002:0.00302]
set yrange [0:2.5]
set xtics 0.001
set ytics 1
  plot "monotonic_dense_jumps.gpdat" using 1:3 with lines lc 8 title ""
  plot "monotonic_dense_jumps.gpdat" using 1:2 with lines lc 7 title ""

# mid left
set size 0.3, 0.3
set origin 0.65, 0.35

set title "Around 2.0"
set xrange [1.9895:2.0105]
set yrange [6652.7:6656.7]
set xtics 0.005
set ytics 1
  plot "monotonic_dense_jumps.gpdat" using 1:3 with lines lc 8 title ""
  plot "monotonic_dense_jumps.gpdat" using 1:2 with lines lc 7 title ""

# bottom mid
set size 0.3, 0.3
set origin 0.35, 0.05

set title "Around 0.5"
set xrange [0.4895:0.5105]
set yrange [3275:3364]
set xtics 0.005
set ytics 20
  plot "monotonic_dense_jumps.gpdat" using 1:3 with lines lc 8 title ""
  plot "monotonic_dense_jumps.gpdat" using 1:2 with lines lc 7 title ""

# bottom right
set size 0.3, 0.3
set origin 0.65, 0.05

set title "Around 1.0"
#set xrange [0.98:1.02]
#set yrange [4944:5028]
set xrange [0.9895:1.0105]
set yrange [4974:4998.5]
set xtics 0.005
set ytics 5
  plot "monotonic_dense_jumps.gpdat" using 1:3 with lines lc 8 title ""
  plot "monotonic_dense_jumps.gpdat" using 1:2 with lines lc 7 title ""

unset multiplot
pause -1

Gnuplot data file "monotonic_dense_jumps.gpdat"
is too large to be shown here (18 MBytes)

C source code to compute gnuplot data

#include <stdio.h>
#include <string.h>
typedef int bool;
#define true            ((bool)1)
#define false           ((bool)0)



/* ***************************************************************** */
/* ***** fractions **********************************************@@* */
/* ***************************************************************** */



typedef int numT;    /* numerator value */
typedef int denT;    /* denominator value */

struct _frac {
    numT num;
    denT den;
};

#define numMax          ((numT)500)
#define denMax          ((denT)numMax+1)



/* ***************************************************************** */
/* ***** Q enumeration ******************************************@@* */
/* ***************************************************************** */



typedef int eRankT;  /* rank of fraction in Q enumeration */

#define eRankIrr        ((eRankT)-2)    /* irreducible fraction */
#define eRankRed        ((eRankT)-1)    /* reducible fraction */
#define eRankMax        ((eRankT)(numMax*denMax))

static eRankT eRank[numMax][denMax];
static struct _frac eUnrank[eRankMax];

static eRankT eRankTop;



static inline void enterERank(
    numT n,
    denT d)
{
    eRank[n][d] = eRankTop;
    eUnrank[eRankTop].num = n;
    eUnrank[eRankTop].den = d;
    eRankTop += 1;
}



static inline void setupERank(void)
{
    numT n;
    denT d;
    numT p;

    /* init */
    for (d=0; d<denMax; ++d)
        for (n=0; n<numMax; ++n)
            eRank[n][d] = eRankIrr;

    /* sieve out all reducible fractions */
    for (d=1; d<denMax; ++d) {
        for (p=2; p<=(numT)d; ++p) {
            if ((numT)d % p != 0)
                continue;
            for (n=0; n<numMax; n+=p)
                eRank[n][d] = eRankRed;
        }
    }

    /* allocate */
    eRankTop = 0;
#if 0   /* "L" order */
    /* N\D  1  2  3 */
    /*   0  a  d  i */
    /*   1  b  c  h */
    /*   2  e  f  g */
    for (p=0; p<denMax; ++p) {
        n = p - 1;
        for (d=1; d<=p; ++d)
            if (eRank[n][d] == eRankIrr)
                enterERank(n,d);
        d = p;
        for (n=p-1; n>=0; --n)
            if (eRank[n][d] == eRankIrr)
                enterERank(n,d);
    }
#else   /* "/" order */
    /* N\D  1  2  3 */
    /*   0  a  c  f */
    /*   1  b  e  h */
    /*   2  d  g  i */
    for (p=1; p<2*denMax-2; ++p) {
        for (d=1; (numT)d<=p; ++d) {
            n = p - (numT)d;
            if (n >= numMax || d >= denMax)
                continue;
            if (eRank[n][d] == eRankIrr)
                enterERank(n,d);
        }
    }
#endif
}



/* ***************************************************************** */
/* ***** Q size *************************************************@@* */
/* ***************************************************************** */



typedef int sRankT;  /* rank of fraction when ordered by size */

#define sRankRed        ((sRankT)-1)    /* reducible fraction */
#define sRankMax        ((sRankT)(numMax*denMax))

static sRankT sRank[numMax][denMax];
static struct _frac sUnrank[sRankMax];

static sRankT sRankTop;

typedef int cmpT;    /* comparison result */



/* Return   <0, =0, >0   if   p<q, p==q, p>q,   respectively. */
/* All denominators are assumed to be positive. */
static inline cmpT cmpFrac(
    const struct _frac *p,
    const struct _frac *q)
{
    return (cmpT)(p->num * (numT)q->den - (numT)p->den * q->num);
}



static inline cmpT cmpSRank(
    sRankT s,
    sRankT t)
{
    return cmpFrac(&sUnrank[s],&sUnrank[t]);
}



static inline void swapSRank(
    sRankT s,
    sRankT t)
{
    numT const ns = sUnrank[s].num;
    denT const ds = sUnrank[s].den;
    numT const nt = sUnrank[t].num;
    denT const dt = sUnrank[t].den;
    sUnrank[s].num = nt;
    sUnrank[s].den = dt;
    sUnrank[t].num = ns;
    sUnrank[t].den = ds;
    sRank[ns][ds] = t;
    sRank[nt][dt] = s;
}



static void quicksortSRank(
    sRankT from,
    sRankT to)
{
    sRankT f;
    sRankT t;

    while (from < to) {
        sRankT const mid   = (from + to) / 2;
        sRankT const pivot = to;
        f     = from - 1;
        t     = to;
        swapSRank(mid,to);
        while (true) {
            while (++f < t && cmpSRank(f,pivot) < 0)
                ;
            while (f < --t && cmpSRank(pivot,t) < 0)
                ;
            if (f >= t)
                break;
            swapSRank(f,t);
        }
        swapSRank(f,to);
        if (f < mid) {          /* minimize stack usage */
            quicksortSRank(from,f-1);
            from = f + 1;
        } else {
            quicksortSRank(f+1,to);
            to = f - 1;
        }
    }
}



static inline void setupSRank(void)
{
    numT n;
    denT d;

    /* init */
    sRankTop = 0;
    for (n=0; n<numMax; ++n)
        for (d=1; d<denMax; ++d)
            if (eRank[n][d] == eRankRed) {
                sRank[n][d] = sRankRed;
            } else {
                sRank[n][d] = sRankTop;
                sUnrank[sRankTop].num = n;
                sUnrank[sRankTop].den = d;
                sRankTop += 1;
            }
    quicksortSRank(0,sRankTop-1);
}



/* ***************************************************************** */
/* ***** summable sequence **************************************@@* */
/* ***************************************************************** */



typedef long double seqT;    /* sequence member, sum */

#define seqBase         ((seqT)0.9999)



/* raise (base) to the (r).th power */
static inline seqT ipow(
    seqT base,
    eRankT r)
{
    eRankT i;
    seqT res = 1.0;

    for (i=0; i<r; ++i)
        res *= base;
    return res;
}



static inline void calcMonFct(void)
{
    sRankT s;
    seqT curSum;

    seqT const err = ipow(seqBase,eRankTop) / (1.0-seqBase);
    printf("\n");
    printf("# Base %Lf, %d fractions, up to %d/%d, max error %Lg\n",
                                    seqBase,eRankTop,numMax,denMax,err);
    printf("# xrange [0:%d]\n",numMax);
    printf("# yrange [0:%Lf]\n",1.0/(1.0-seqBase));
    printf("\n");
    curSum = 0.0;
    for (s=0; s<sRankTop; ++s) {
        numT const n = sUnrank[s].num;
        denT const d = sUnrank[s].den;
        eRankT const e = eRank[n][d];
        if (e == eRankRed)
            continue;
        if (d == 0) {
            printf("# s=%d n/d=%d/%d e=%d break\n",s,n,d,e);
            break;
        }
        seqT const q = (seqT)n / (seqT)d;
        printf("%19.15Lf\t%19.15Lf\t%19.15Lf\n",q,curSum,curSum+err);
        curSum += ipow(seqBase,e);
        printf("%19.15Lf\t%19.15Lf\t%19.15Lf\n",q,curSum,curSum+err);
    }
}



/* ***************************************************************** */
/* ***** main ***************************************************@@* */
/* ***************************************************************** */



int main(void)
{
    setupERank();
    setupSRank();
    calcMonFct();
    return 0;
}

Licensing

I, the copyright holder of this work, hereby publish it under the following license:

This file is licensed under the Creative Commons Attribution-Share Alike 4.0 International license.

You are free:

to share – to copy, distribute and transmit the work
to remix – to adapt the work

Under the following conditions:

attribution – You must give appropriate credit, provide a link to the license, and indicate if changes were made. You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use.
share alike – If you remix, transform, or build upon the material, you must distribute your contributions under the same or compatible license as the original.

Category:CC-BY-SA-4.0#Monotonic%20dense%20jumps.pdf

Category:Self-published work Category:Monotonicity Category:Fractals Category:Discontinuous functions Category:Images with Gnuplot source code Category:Images with C source code Category:Files by User:Jochen Burghardt

Wikimore

File:Monotonic dense jumps.pdf

Summary

Licensing