Square Root of a Function.


1. Introduction.

    In math it's common to study when a function has inverse, denoting it with
    f^-1, since f^-1 ∘ f = id.  Following the same syntax it makes sense to
    define f^n = f ∘ ... ∘ f {n times}.

        We then introduce √f = g iff g∘g = f, and in this work we try to derive
    the square root of a functions for a few simple cases, for which we use
    PostScript as it's a concatenative language.

        Also we should note that there's as well multiple possible values for
    the square root of a given function, some cases being more useful than
    others.  Such an example of a trivial useless solution could be checking if
    a special private singleton is located at the top of the stack, if it's not
    then we push it, otherwise we pop it and apply f.  Here we will strive for
    meaningful solutions instead.


2. Basic examples for Real arithmetic.

    Single operations:

    * √{n add} -> {m add} where m = n/2,
      as: x m add m add  ->  x <2m> add  ->  x n add

    * √{n sub} -> {m sub} where m = n/2.

    * √{n mul} -> {m mul} where m = √n.
      being careful with negative values of n, as PostScript doesn't provide
      complex math support by default (though they could be represented as
      arrays of two numbers).

    * √{n sub} -> {m sub} where m = n/2.
    * √{n div} -> {m div} where m = √n.

    In the following case we observe how √(f∘g) = √f∘√g does always not hold.

    * √{a mul b add} -> {c mul d add} where c=√a, d=b/(1+√a).
      as: x c mul d add c mul d add  ->  <c(cx+d)+d = c²x+cd+d = ax+b>
      a=c²  ->  c=√a,
      b=cd+d  ->  b=(c+1)d  ->  d = b/(c+1) = b/(1+√a)

    * √{a mul b add} -> {d add c mul} where c=√a, d=b/(a+√a)
      as x d add c mul d add c mul  ->  <c(c(x+d)+d) = c(cx+cd+d) = c²x+c²d+cd>
      b = c²d+cd = (c²+c)d  ->  d = b/(a+√a).

    * √{b add a mul} -> {c mul d add} where c=√a, d=ab/(1+√a)
    * √{b add a mul} -> {d add c mul} where c=√a, d=ab/(a+√a)
      since √{b add a mul} -> √{a mul b' add} with b'=ab, as a(x+b)=ax+ab.

3. Integer arithmetic.

    There are two cases to consider here: idiv and mod.  For √{n idiv} we know
    that if n is the square of an integer we can apply the same derivation as
    in real algebra.  The case where n=2 is trickier as {2 idiv} is in essence
    the same as {-1 bitshift} or in other words dropping the least significant
    bit, then √{2 idiv} would mean shifting right half a bit.


TODO:
* Think about the half-bit case.

                                                                              π

                        Square Root of a Function.


1. Introduction.

    In math it's common to study when a function has inverse, denoting it with
    f^-1, since f^-1 ∘ f = id.  Following the same syntax it makes sense to
    define f^n = f ∘ ... ∘ f {n times}.

        We then introduce √f = g iff g∘g = f, and in this work we try to derive
    the square root of a functions for a few simple cases, for which we use
    PostScript as it's a concatenative language.

        Also we should note that there's as well multiple possible values for
    the square root of a given function, some cases being more useful than
    others.  Such an example of a trivial useless solution could be checking if
    a special private singleton is located at the top of the stack, if it's not
    then we push it, otherwise we pop it and apply f.  Here we will strive for
    meaningful solutions instead.


2. Basic examples for Real arithmetic.

    Single operations:

    * √{n add} -> {m add} where m = n/2,
      as: x m add m add  ->  x <2m> add  ->  x n add

    * √{n sub} -> {m sub} where m = n/2.

    * √{n mul} -> {m mul} where m = √n.
      being careful with negative values of n, as PostScript doesn't provide
      complex math support by default (though they could be represented as
      arrays of two numbers).

    * √{n sub} -> {m sub} where m = n/2.
    * √{n div} -> {m div} where m = √n.

    In the following case we observe how √(f∘g) = √f∘√g does always not hold.

    * √{a mul b add} -> {c mul d add} where c=√a, d=b/(1+√a).
      as: x c mul d add c mul d add  ->  <c(cx+d)+d = c²x+cd+d = ax+b>
      a=c²  ->  c=√a,
      b=cd+d  ->  b=(c+1)d  ->  d = b/(c+1) = b/(1+√a)

    * √{a mul b add} -> {d add c mul} where c=√a, d=b/(a+√a)
      as x d add c mul d add c mul  ->  <c(c(x+d)+d) = c(cx+cd+d) = c²x+c²d+cd>
      b = c²d+cd = (c²+c)d  ->  d = b/(a+√a).

    * √{b add a mul} -> {c mul d add} where c=√a, d=ab/(1+√a)
    * √{b add a mul} -> {d add c mul} where c=√a, d=ab/(a+√a)
      since √{b add a mul} -> √{a mul b' add} with b'=ab, as a(x+b)=ax+ab.

3. Integer arithmetic.

    There are two cases to consider here: idiv and mod.  For √{n idiv} we know
    that if n is the square of an integer we can apply the same derivation as
    in real algebra.  The case where n=2 is trickier as {2 idiv} is in essence
    the same as {-1 bitshift} or in other words dropping the least significant
    bit, then √{2 idiv} would mean shifting right half a bit.


TODO:
* Think about the half-bit case.
[cancel] password:  [private]