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.