Designing a Tetration Library

[andydude]

I aim to address many things in these posts (I have 3 more planned):

1. Definitions of accuracy and precision
   
2. Keeping track of accuracy and precision
   
3. Algorithms for natural super-logarithms
   
4. Algorithms for regular tetration
   
5. General algorithms for tetration
   
6. General algorithms for hyper-operations
   

To do this, I am going to bring together several of Jay Fox's posts on accuracy and precision, since I think I understand them enough to shed some light on the issue.

Jay Fox has posted several threads about improving natural tetration (as we call it), which investigate acceleration (overview (slog/sexp), details (slog)) and accuracy & precision of the natural super-logarithm. I'm currently building a library based on these techniques, which will allow one to ask: "What is e^^pi to 14 significant figures?" (which Jay has already found to 25 sig.fig.) and since Jay Fox has found an upper bound for the possible error, we will know for sure that the result will be accurate to that many decimal places.

How do we do this? First of all, we need a general algorithm for computing tetrate(b, h), superroot(h, z), and the superlog(b, z). The natural method applies to superlog() first, and tetrate() second (you must invert the function somehow), and the regular method applies to tetrate() first, then superlog() second (again, because you must invert it). I will focus on the general algorithms first, in other words, where this inversion takes place, rather than focusing on the method and saying "then invert it". This will be the context in which all other functions will fit in.

Some of the algorithms involve accuracy_of() and precision_of(), which imply a language with arbitrary-precision. These can be, or are, implemented in Sage, Maple, Mathematica, and GMP. But first, I should define these terms a little before continuing. When I say "precision" I mean the number of significant digits. When I say "accuracy" I mean the negative of the least significant digit (base 10). So a number like 3.14 will have "accuracy" 2 and "precision" 3. I will define these in more depth in the next post.

Here is the pseudo-code which is meant to be read, but not executed:

First, a basic framework for tetrate()

Code:

tetrate(base, h) :=
  # try to match the accuracy of 'h'
  # accuracy could also be d=15 by default
  tetrate(base, h, accuracy_of(h))

tetrate(base, h, d) :=

  if h is integer
  
  then: if base is in {-infinity, -1, 0, 1}
        then:
          # use "Limit" method (mainly for b=0)
          limit_tetrate(base, h)
        else:
          # use "Naive" method
          naive_tetrate(base, h)
        
  else: case base == -1: (undefined) or -1 ??
             base == 0: (undefined)
             base == 1: if h > -1
                     then: return 1
                     else: (undefined)
  
             base == infinity:
                case h < -2: (undefined)
                     -2<h<0: return 0
                     h > 0: return infinity

             # prefer "Regular" method for tetrate()
             # this could be Re(base) <= 1 if desired
             # but the series may not converge
             |log(H(base))| <= 1:
                # use "Regular" method
                n = regular_tetrate_size(d)
                regular_tetrate(base, h, n)
  
             Re(base) > 1:
                # use "Natural" method
                [n_sol, n_est] := natural_superlog_size(d)
                natural_tetrate(base, h, n_sol, n_est)
                
             otherwise: (undefined)
end

That was easy! but how are all the sub-functions like natural_tetrate() defined? I will cover these in a future post. Also, the reason why the domains of regular and natural tetration are limited above can be explained in this post.

Second, a basic framework for superlog()

Code:

superlog(base, z) :=
  # try to match the accuracy of 'z'
  # accuracy could also be d=15 by default
  superlog(base, z, accuracy_of(z))

superlog(base, z, d) :=

  [h, t] := ceiling_superlog(base, z)
  
  if t == 0
  
  then: return h

  else: case base == -1: (undefined)
             base == 0: (undefined)
             base == 1: case z > 1:  return infinity
                             z == 1: return 0
                             z < 1:  return -1
  
             base == -infinity: (undefined)
             base == infinity: case z > 0:  return 0
                                    z == 0: return -1
                                    z < 0:  return -2
  
             # prefer "Natural" method for superlog
             Re(base) > 1:
                  # use "Natural" method
                  [n_sol, n_est] := natural_superlog_size(d)
                  natural_superlog(base, z, n_sol, n_est)

             # this could be Re(base) <= 1 if desired
             # but the series may not converge
             |log(H(base))| <= 1:
                  # use "Regular" method
                  n := regular_superlog_size(d)
                  regular_superlog(base, z, n)
  
             otherwise: (undefined)
end

What are all these functions? like ceiling_superlog()?
These will be explained in a future post.

Third, a basic framework for superroot()

Code:

superroot(z, h) :=

  if h is integer

  then: case h == 0: (undefined)
             h == 1: z
             h == 2: ssqrt(z)
             h == infinity: z^(1/z)
             otherwise:
                # use a power series method
                Lagrange_inverse_series(
                  tetrate(base, h) == z, base )

  else:
    # use a numerical method
    Newton_method( tetrate(base, h) - z == 0, base )

Unfortunately I have noticed very little progress in the calculation of superroots.

Andrew Robbins