[enhancement] I think I’ve figured out how to do arbitrary-height super-roots.

Currently, break_eternity.js supports super-logarithms of arbitrary base, but only super-square roots. I understand that this is because super-square roots can be calculated with the Lambert W function… but I think I’ve figured out an algorithm that could be used to calculate super-square roots in general. (This will be in pseudocode since I’m not familiar with JavaScript yet).

The basic structure would be a guess-and-check. Start with a lower bound and an upper bound, see whether the average of the bounds is above or below the correct answer (so if the average is 6 and the super-root height is 3, check whether 6^^3 is above or below the input), then set the lower bound to the average if the average turns out to be below the correct value, set the upper bound to the average if the average turns out to be above the correct value, then take the average of the new bounds and change the appropriate bound, and repeat until the average stops changing.

I’d say the lower bound can easily just be 0, but what about the upper bound? Well, if the input is above 10^^(super-root degree), then input.superroot(degree) < input.iteratedlog(10, degree - 1): for example, input.ssqrt() < log10(input) if input > 10^10, and input.superroot(3) < log10(log10(input)) if input > 10^10^10, since 10^10^10...^n < n^n^n…^n if n > 10. This means that if input >= 10^^degree, the upper bound can be input.iteratedlog(10, degree - 1). On the other hand, if input < 10^^degree, then obviously input.superroot(degree) < 10, so the upper bound can be 10.

The trick to make sure this doesn’t take eons for higher numbers is to change what we’re comparing based on the size of the number. We’ll be keeping track of five numbers during this loop, which I’ll call “lower”, “upper”, “layer”, “guess”, and “previous”. Lower starts at 0, layer is whatever the layer of the upper bound is (so if the upper bound is ee100, layer is 2), upper = (upper bound).iteratedlog(10, layer) (so if the upper bound is ee100, upper is 100), previous = upper to start, and average can be set to 0 for now. Once these numbers are set, we begin the loop. If input >= 1, the steps of the loop are as follows:

guess = lower.add(upper).div(2)
To check whether our guess is smaller or larger than the correct value, compare guess.iteratedexp(10, layer).tetr(degree) with input (the iterated exponential is to look at the actual guess rather than the layer-lowered guess, then the tetration is to undo the possible super-root). If guess.iteratedexp(10, layer).tetr(degree) < input, then we set upper = guess, otherwise we set lower = guess.
If guess == previous, then the calculation is finished, and return guess.iteratedexp(10, layer) as the value of the super-root. Otherwise, we set previous = guess, then we return to the beginning of the loop. (You’d think we’d need a test in there to lower the layer if the upper bound gets too small, but in practice I don’t think it’s needed; it seems that as long as the upper bound is greater than 10, the iteratedlog estimate shouldn’t be too far off from the answer).

That algorithm works fine if the input is above 1, but if the input is below 1, there’s a chance that the tetration of that degree isn’t strictly increasing, which means the algorithm could skip over the correct answer. To resolve this, I’ll use a different algorithm if the input is below 1. For whole-degree tetration, there’s a clear distinction between even and odd degrees. An odd-degree tetration is strictly increasing, while an even-degree tetration goes from 1 at x = 0, decreases to some minimum (that occurs at some x between 0 and 1), then increases afterwards A tetration of decimal degree can potentially have three different portions, as shown at https://www.desmos.com/calculator/ayvqks6mxa, which is a graph of x^^2.05:

The portion where the function is increasing, extending from a minimum (which may be at x = 0 or at some x between 0 and 1) up to infinity (I’ll call this the “increasing” range)
The portion where the function is decreasing (I’ll call this the “decreasing” range)
A small, steep increasing portion very close to x = 0 (I’ll call this the “zero” range)

If ceiling(degree) is even, then the tetration will either be strictly increasing, or it will have the increasing and decreasing ranges, but not the zero range (because if ceiling(degree) is even, 0^^degree == 1). If ceiling(degree) is odd, then the tetration will either be strictly increasing, or it will have all three ranges (because if ceiling(degree) is odd, 0^^degree == 0). The existence of these ranges means that a super-root could potentially have two or three valid answers; out of these, we’d prefer the increasing range value if it exists, otherwise we’ll take the zero range value (it can’t have a decreasing range value if it doesn’t have an increasing range value) if the zero range exists. To make sure we search the right range, we’ll need to know where the ranges are, and to do that we’ll need to find the (local, if the zero range exists) minimum at the end of the decreasing range, and, if the zero range exists, the local maximum at the end of the zero range. Luckily, according to my observations, there’s a way to tell what range you’re in by looking at a single point:

If the tetration is decreasing at that point, the point is in the decreasing range
If the tetration is increasing at that point and ceiling(degree) is even, the point is in the increasing range since there is no zero range
If the tetration is increasing at that point and ceiling(degree) is odd, look at the second derivative at that point. If the second derivative is positive, the point is in the increasing range. If the second derivative is negative, the point is the zero range.

With these facts in mind, we can find our minimum and maximum. To do this, we’ll need a bunch of variables: minimum, maximum, stage, lower, upper, difference, prevspan, and nextspan. minimum and maximum start at 0, lower starts at 0, upper starts at 1, difference starts at 1, and stage starts at 1. The “stage” variable indicates what stage of the algorithm we’re in: stage 1 is “finding the minimum”, stage 2 is “set-up to find the maximum”, stage 3 is “finding the maximum”. Lower and upper are the lower and upper bounds for the x-value of whichever part of the tetration we’re finding, and difference is the difference between the two. Also, we obviously need the input and the degree of our super-root, as usual. Here’s how the loop goes:

If stage == 2, then {end the loop if ceiling(degree) is even, otherwise set lower = 0, upper = minimum, and stage = 3); don’t do anything on this step if stage is not 2.}
Set prevspan and nextspan to upper.mul(1.2e-16), a value so close to upper that upper.add(nextspan) can be treated as the next point right after upper and upper.sub(prevspan) can be treated as the previous point right before upper. If upper.sub(prevspan).tetr(degree) == upper.tetr(degree), multiply prevspan by 2, repeating that until those two values are no longer equal. If upper.add(nextspan).tetr(degree) == upper.tetr(degree), multiply nextspan by 2, repeating that until those two values are no longer equal. Now, we use these “closest points” to check which range the upper bound is in:
- If upper.add(nextspan).tetr(degree) < upper.tetr(degree), then upper is in the decreasing range, so set range = -1.
- Otherwise, if ceiling(degree) is even, then upper is in the increasing range, so set range = 1.
- Otherwise, if (upper.add(nextspan).tetr(degree) - upper.tetr(degree)) < (upper.tetr(degree)) - upper.sub(prevspan).tetr(degree)), then the second derivative is negative, so upper is in the zero range, so set range = 0.
- Otherwise, upper is in the increasing range, so set range = 1.
If stage == 1, we’re looking for the minimum, so if range = 1, then upper is too high, so set upper = (lower + upper)/2. However, if range != 1, then upper is too low, and the last time we decreased upper, we should have gone to the other half of the range instead, so set lower = lower.add(difference) and upper = upper.add(difference). On the other hand, if stage == 3, then we’re looking for the maximum at the end of the zero range, so upper is too high if range = 1 or range = -1, so set upper = (lower + upper)/2, but if range = 0, then set lower = lower.add(difference) and upper = upper.add(difference).
Set difference = (lower + upper)/2.
If difference <= 1e-16 (meaning lower and upper are basically equal), do “set prevspan and nextspan to upper.mul(1.2e-16), a value so close to upper that upper.add(nextspan) can be treated as the next point right after upper and upper.sub(prevspan) can be treated as the previous point right before upper. If upper.sub(prevspan).tetr(degree) == upper.tetr(degree), multiply prevspan by 2, repeating that until those two values are no longer equal. If upper.add(nextspan).tetr(degree) == upper.tetr(degree), multiply nextspan by 2, repeating that until those two values are no longer equal” again. If stage == 1, {check if upper.sub(prevspan).tetr(degree) > upper.tetr(degree) and upper.add(nextspan).tetr(degree) > upper.tetr(degree). If those inequalities are both true, then we’ve found the minimum, so set minimum = upper and stage = 2. Otherwise, the minimum doesn’t exist, so end the loop without changing minimum.}. If stage == 3, {check if upper.sub(prevspan).tetr(degree) < upper.tetr(degree) and upper.add(nextspan).tetr(degree) < upper.tetr(degree). If those inequalities are both true, then we’ve found the maximum, so set maximum = upper. After that check, end the loop regardless of the check’s outcome.}.

Now we have the minimum and maximum, so it’s time to calculate the actual super-root: first, check whether it’s in the increasing range: do the normal super-root algorithm (the one used for inputs above 1), with layer = 0, lower starting at minimum, and upper starting at 1. Once guess = previous, then if guess != minimum, return guess as the value of the super-root… but if guess == minimum, that means the actual result isn’t in the increasing range and the algorithm just kept trying to go down. If this does happen, then we need to see if there’s a zero range: if maximum = 0, then there’s no zero range, so return NaN since the super-root has no value; otherwise, there is a zero range, so run the super-root algorithm again with layer = 0, lower = 0 and upper = maximum, with the caveat that if guess gets to be below 1e-16 or so, we should just return NaN since otherwise we’ll spiral infinitely downwards towards zero.

Okay, that was a lot, but I think following the simpler algorithm for input >= 1 and the more complicated algorithm for 0 < input < 1 will give you the super-root in almost all cases. There are, of course, some special cases:

If the layer of the input is greater than the degree of the super root (for example, the 3rd super-root of eee1e16), then don’t even bother doing the calculation, because the iteratedlog estimate is going to be within rounding error of the answer. Just return input.iteratedlog(10, degree - 1).
If degree == 1, then just return input.
If degree == 2, then return input.ssqrt() since it’s faster than doing this calculation.
I’m not sure if my upper bound works when degree < 1, so I think the algorithm only works when degree >= 1… but if we’re still using the linear approximation of tetration, x^^n == x^n if 0<n<1. Therefore, if 0 < degree < 1, return input.root(degree).
According to the Wikipedia article on tetration, if degree == positive infinity, return input.pow(input.recip()) if 1/e < input < e, otherwise return NaN.
Return NaN if -1 < degree <= 0, or degree <= -2. Super-roots can, however, be defined for a degree between -2 and -1: assuming we’re using the linear approximation, if the degree is between -2 and -1, return degree.add(2).pow(input.recip()).
Return NaN if input is 0 or negative and degree > 0. (If -2 < degree < -1, the rule for that case covers negatives)
If degree is even and input < 1/e, return NaN, because the minimum outputs of even-degree tetrations are all higher than 1/e.

Super-roots seem to me to be the biggest thing break_eternity.js is missing right now, but I think the algorithm I’ve described here will work to calculate them. If I got anything wrong here or there’s something you don’t understand about my super-root algorithm, please let me know.

P. S. Why does break_eternity.js use a different formula for fractional-height tetrations when the base is above 10 (linear approximation) than when the height is below 10? It seems to me that this could cause issues, such as 10.00001^^2 being significantly higher than 10^^2. If you’re going to use an approximation (which you have to, since tetration doesn’t have an agreed-upon definition for fractional heights), be consistent with what approximation you’re using!

actually 2^^-1.1=-0.13439101394380359178,10^^-1.1=-0.073413324316674049650,so you can't just return nan for those numbers;(

You’re right, but just barely. Using https://naruyoko.github.io/OmegaNum.js/test.html for testing, it’s clear that if x is between -1 and 0, n^^x = 1 + x, regardless of what n is, so 2^^-0.3 = 0.7 and 100^^-0.3 = 0.7. This means a super-root with a degree between -1 and 0 would return NaN: (0.4).superroot(-0.5) returns NaN because n^^-0.5 never equals 0.4, while (0.4).superroot(-0.6) returns NaN because any base works, so there’s infinite solutions. Meanwhile, tetrating to any tetra-exponent <= -2 returns NaN, so super-roots with degree <= -2 return NaN. Super-roots can, however, be defined for a degree between -2 and -1. My testing has shown that, at least in OmegaNum.js, when the tetra-exponent is between -2 and -1, if we call the base “b”, the tetra-exponent “x”, and the answer “a”, then a = log[b](x + 2), where b is the base of the logarithm and x+2 is the logarithm input. We can rearrange this to solve for the base, which is what we need for a super-root: b = (x + 2)^(1/a), where now a is the input of the super-root, x is the degree of the super-root, and b is the answer of the super-root. Therefore, when the degree is between -2 and -1, we can return degree.add(2).pow(input.recip()). Now, I know that OmegaNum.js isn’t the same as break_eternity.js, but I would assume that the differences between break_eternity’s tetration values and OmegaNum’s (for example, 10^^-1.1 in OmegaNum is -0.04575749056067517) are because OmegaNum consistently uses the linear approximation while break_eternity uses special rules for bases like 2 and 10; if I’m wrong on this, please let me know. If you really want to return the exact value, accounting for these special rules, rather than using a consistent approximation, I suppose we can just use the super-root algorithm I previously described, but with an upper bound of (degree.add(2).pow(input.recip())… but since super-roots of a degree between -1 and 0 and super-roots of a degree less than or equal to -2 are going to be NaN, does it really matter if we implement an exact check for degrees between -2 and -1?

also, the super roots are NOT ALWAYS mono-increasing nor decreasing. so the guess can lead to incorrect calculation.

Okay, yep, you’re right on this one. I thought that all tetrations only switched slope zero or one time, but it turns out some, like x^^3.1, change slope twice. However, it turns out there’s a simpler solution: at a number as small as x = 10^-18, x^x is so close to 1 that its difference from one is smaller than the 53-bit precision of JavaScript integers, which means tetrations effectively oscillate between x and 1 and the answers stop being accurate entirely… so if our upper bound gets to be below 10^-18, I think it’s safe to return NaN, no negative-layer loop required.

EDIT: Okay, I realized what you were really saying there: if the current bounds are, say 0 and 0.1, and the correct answer is 0.085, but 0.05^^degree is greater than the input, then the algorithm will set the bounds to be 0 and 0.05, bypassing the correct answer. However, using Desmos to analyze the super-root functions, I think I’ve found a solution to this. If ceiling(degree) is even, such as x^^3.4, then as you go down in x from 1 to 0, you’ll eventually hit a minimum of x^^degree, then start going back up again, reaching 1 at x = 0. Therefore, if guess < previous but guess.tetr(degree) > previous.tetr(degree) [no need for the iteratedexp’s here since we know this is on layer 0] and ceiling(degree) is even, we can return NaN, since once we hit the point where the tetration is decreasing, it doesn’t go back to increasing as we get closer to 0. On the other hand, if ceiling(degree) is odd, then even if we hit a the local minimum, there will be a local maximum closer to zero, after which the tetration will start decreasing again and go down to 0 once we hit x = 0, so we don’t need to do that decreasing test. In this case, if there’s a valid super-root answer within that interval where the tetration is decreasing, there’s also a valid super-root answer closer to 0; this algorithm will most likely miss the one within the decreasing interval (which is unfortunate, since that’s the one we’d probably consider the principal super-root), but it will hit the one closer to 0, which is still a valid answer. An algorithm could probably be made to find the principal super-root even in this case, but it would involve analyzing the tetration to figure out where the two slope changes are, and would probably be pretty complicated. I’ll update the main issue once I’ve figured out how to account for the nuances here.

EDIT 2: Okay, I think I’ve figured it out. See the main post for the updated algorithm.

Patashu / break_eternity.js

[enhancement] I think I’ve figured out how to do arbitrary-height super-roots. #155