[Enhancement] Adding the Super Square-Root (ssrt(z)), The 2nd Tetration of x (exp_x(2), x^x), Infinite Power-Tower (exp_z(oo)), and Infinite Super-Root (srt_oo(z)).

[Hyrumveneno]

I think some—at least primitive—support for these functions are due. They do have simple enough closed solutions.
Allow me to give so definitions (For the guy browsing in 3045 ;)):

Tetration:

Super Square-Root, the inverse of Tetration with respect to the base (Note: There are two real branches for this function. Here

Infinite Power-Tower:

Infinite Super-Root:

(Note: x^x has been fairly studied compared to tetration as a whole)

Reasons to implement:

• Marks the start of an implementation of a "big number" handler.
• Marks the start of the implementation of tetration.
  • If you need reasons for tetration: http://tetration.itgo.com/up/eng-tetration-paper.pdf.
• Finally they are functions found by climbing the hyper-operators tree.

Questions:

• Now that you can see that these functions (Super Square-Root, Infinite Power-Tower, Infinite Super-Root, and x^x) can be implemented in at least a primitive way, are there any issues that would stop these from being implemented (The Super Square-Root I could see so issues with)?
• Do you think I—only an armature python programmer (4ish years as a hobby & some formal Comp. Sci.)—write this pull request?
• If this is "agreed to" what other identities, rules, etc. do/would/should I need to give?
• Am I missing anything (or did I do something incorrectly)?
• Is this a issue that should be lodged with mpmath and when they implement it come back and add it?

-H.V.

[oscarbenjamin]

It seems reasonable to add these. There should be some control over when they evaluate to avoid generating extremely large numbers.

Presumably mpmath can be used to compute these functions if they are expressed in terms of W etc.

Take a look in sympy/functions to get some idea of how a function is implemented if you are wondering whether you can do this.

[ThePauliPrinciple]

Do you think I—only an armature python programmer (4ish years as a hobby & some formal Comp. Sci.)—write this pull request?

Absolutely. This will be helpful: https://github.com/sympy/sympy/wiki/Development-workflow

[Hyrumveneno]

There should be some control over when they evaluate to avoid generating extremely large numbers.

Agreed. Do you have a number in mind?

Absolutely. This will be helpful: https://github.com/sympy/sympy/wiki/Development-workflow

Thanks, I was looking for this.

Presumably mpmath can be used to compute these functions if they are expressed in terms of W etc.

Yes. Mpmaths's W or sympy's LambertW will work.

[oscarbenjamin]

Do you have a number in mind?

No but maybe these functions should not evaluate by default i.e. you need to call doit or something to make them evaluate.

[Hyrumveneno]

I don't know; I think the tet2 & IPTower are the only ones that would need a .doit() because of their growth rate. Most of the time they (except tet2 & IPTower) would evaluate to small irrational numbers (like 1/10<x<5) so they wouldn't evaluate until the end (right?).

[Hyrumveneno]

https://www.desmos.com/calculator/eyi06eoi6k

[oscarbenjamin]

Extremely small numbers are problematic as well.

Make sure you save all of your work etc before running this code because you might not be able to interrupt before it consumes all the memory in your system forcing a hard reboot:

In [12]: S(0.1)**S(10.0)**S(10.0)**S(10.0)
^C^C^C^C^C^C^C
KeyboardInterrupt

[asmeurer]

Even doit shouldn't evaluate when it comes to numbers that cannot possibly fit in memory. There can be a separate function that tries to evaluate it for users who really want to try.

[Hyrumveneno]

Infinite Super-Root approaches 1 so it'll be fine. Ssrt grows slower then (I think log and) LambertW. In short the only ones you would need to worry about at all are tet2 & inf P-Tower. These I can do as @asmeurer states and evaluate a piecewise (if x>1000 -> NaN) or something.

[Hyrumveneno]

Also, I've decided I'll make the (at least primitive) pull request.

[asmeurer]

This is closely related to #6835. Any sort of power tower object, whether it's an explicit object for tetration or just nested Pow, should estimate its size and refuse to evaluate if it is too large. The same also applies to evalf if the exponent would be too large (mpmath/Float do not have a limit in exponent size, so this would need to be done manually). It also means that we need to be able to evaluate anything on a tetration object which would normally be done using numerical evaluation via smarter means (e.g., computing a < b would need to be done via a smarter algorithm). By default, anything that isn't known to be computed without explicitly evaluating the number should remain symbolic/unevaluated.

[oscarbenjamin]

I think we need two functions for something like tetration:

1. A Python function e.g. tet2 that actually computes the result but (by default) has some checks to prevent generating an absurdly large result.
2. A symbolic SymPy Function subclass Tet2 that represents tetration symbolically. It could have a doit method that calls tet2 or otherwise a rewrite method for rewriting to different form.

Then symbolic tetration functions will never evaluate by default and there should be routines for handling in that form.

I'm wondering also whether tetration should just be implemented as a special case of a hyperoperation though: https://en.wikipedia.org/wiki/Hyperoperation
There could be a H(n, a, b) routine that is equivalent to tetration when n=4.

[asmeurer]

Apparently there's not a single common notation used for hyperoperation https://en.wikipedia.org/wiki/Hyperoperation#Notations. I would suggest using Knuth arrow notation as that's the notation I've seen used most often. Although I would also suggest only implementing such generalizations if there are actual symbolic things that could be computed on them, like some simplifications or some such, or if they can be the result of some other operation. Otherwise we would just have a way of representing such functions but nothing else that we could really do with them.

[Hyrumveneno]

Tetration help PDF: https://math.osu.edu/sites/math.osu.edu/files/chun_tetration.pdf
Ok first things first I was planning on posting 5 separate issues to implement to what I wanted but, I guess, because of the turn of conversation, I will list them here (I probably still will post them individually):

• Issue 1
  • Adding Basic infinite/2(/3) base Tetration and its root- inverses.
    • h(z, k, l) -> (k, l) optional (they are the branches of the LambertW and ln) ->
    • isr(z) ->
    • ssqrt(z, k, l) -> (k, l) optional ->
    • Tet2(z) -> z^z
    • Tet3(z) -> z^(zz)
      • If you are super worried about growth rate look: (Tet3(z) > Tet2(z) > Gamma(z+2) and Gamma(z+2)^6 ~ Tet3(z) and Gamma(z+2)^(4/3) ~ Tet2(z)) as z --> oo. Also, they would be warned with that every time they are used. (Nobody should be computing 72! in sympy. Thus, no one should be computing tet3(5).)
      • 
• Issue 2
  • BigInt primitive implementation.
    • BigInts will come in degrees Only the 0th degree will be implemented here
    • BigInt -> [[x, y, z, w], [a, b, ...]] -> [[signed float or int, int, int, int], [metadata]] -> x * (10**y) * ((1 googol)**z)
    • BigInts will not solve in any sympy solver except the BigInt reducer.
    • BigInt functions can be wrapped so they can evaluate in sympy solvers.
    • Built-in rounding.
  • Superfactorial, Hyperfactorial, and other big-number function support added.
    • Via the K(z) and BarnesG(z) (This one is partially implemented via the multigamma.)
• Issue 3
  • Tetration to integer heights fully added ((Tet(E, n) when no z is given) Tet(z, n) = z^^n (Knuth).)
  • Super Logarithm added (If Tet(b, z) = w -> slog(w, b) = z)
  • Iterated Exponents added
  • Super-Roots added
    • These last four have a normal unevaluated version that requires a .doit() to return anything.
  • N-ary towers added (Denoted by a large capital Tau. They're products for exponents)
• Issue 4
  • Tetration, Slog, and Super-Root estimates and extensions added
• Issue 5
  • Knuth/HyperOperator added
  • Ackermann added
    • Our (For our implementation not over all) Knuth is for real N⁺ only and not ever for exponentiation or tetration. HyperOp is used everywhere else.
  • N-ary Knuth towers added.
  • N-ary composition added

[oscarbenjamin]

That looks broadly like a good plan but I'm unclear on some things. Everything there looks like something that should be added but there are always details to be worked out.

I suggest starting with the part that is smallest and most useful and then opening a PR for that first. Then we can discuss the details of that and once that is merged we will all have a clearer idea how to implement the rest.

[Hyrumveneno]

That looks broadly like a good plan but I'm unclear on some things. Everything there looks like something that should be added but there are always details to be worked out.

Ok, I am sorry about this post—it was rushed. The later issues in the post are going to be confusing really no matter what until the previous ones are solved.
Also, thanks!

I suggest starting with the part that is smallest and most useful and then opening a PR for that first. Then we can discuss the details of that and once that is merged we will all have a clearer idea how to implement the rest.

I whole heartedly agree. This is slightly different from my plan but after this I will modify it.

UPDATE: I'm slowly working on that first issue's PR. It is going to be a little while but I have good progress so far. I have hit a small wall though where I have to conduct my own research to give a good definition of the function to SymPy. (This may be an something to be ignored until more research comes out—we are one of the few projects that are dipping into this pool.)

[oscarbenjamin]

This may be an something to be ignored until more research comes out

There's no rush. We can also discuss the issue around definitions here.

[Hyrumveneno]

Ok great! I'll compile and insert a list after I'm done roughing them all out.