Single-exp series computation code - Printable Version +- Tetration Forum ( https://math.eretrandre.org/tetrationforum)+-- Forum: Tetration and Related Topics ( https://math.eretrandre.org/tetrationforum/forumdisplay.php?fid=1)+--- Forum: Computation ( https://math.eretrandre.org/tetrationforum/forumdisplay.php?fid=8)+--- Thread: Single-exp series computation code ( /showthread.php?tid=439) |

Single-exp series computation code - mike3 - 04/20/2010
tommy1729 wanted the details of the method using the single-exp series. I'd post it anyway, but here you go. Periodic interpolation The idea is this. If we denote by , a finite sequence of points () to be interpolated, then we can find a periodic interpolation by taking their discrete Fourier transform (DFT): We can find the points interpolated by taking the inverse discrete Fourier transform: If is odd, then the interpolation is constructed by . where for outside is obtained by periodic repetition, i.e. . The values of will equals when for integers . If we want period , . In any case, will be . If we want our nodes to represent values on either side of 0, with the middle node being 0, then we just rotate them by the appropriate factor () before interpolating. The discrete Fourier transform can be done much faster using the Fast Fourier Transform (FFT) algorithm. The current program uses only the "brute force" method, since it was just an initial test to see if this route was any good. Periodizing functions The next thing we need is a "periodizing function". The tetration is not periodic, so we must approximate it with a periodic function of long period. A "periodizing function" is a function such that 1. has period . 2. . The idea is that given some non-periodic function , is a periodic function approximately equal to for near 0. Increasing the period makes the approximation better. For example, is one possibility. For the program, we use the slightly better . The algorithm We can put these two together to get the following algorithm: 1. Create a Fourier series array with some odd number of nodes and an initial guess. 2. Compute the continuum sum of the array. Store the linear term separately from the new exp/Fourier series. 3. Compute the exponential to the base by converting to function space (via IDFT), exponentiating each node, and converting back to Fourier space (via DFT). This may not be the most precise way, and is not very precise for very small numbers of nodes. However it can be done using the FFT if that is available. (Question: Are there any better methods, perhaps with more precision?). Exponentiate the linear term separately (implicit, just interpret its separetly-value from before not as but and as a multiplier instead of an addend). 4. Multiply by . This is just "implicit" (just treat the array after this point as if it has a multiplier). 5. Integrate with lower bound -1. The integral of the Fourier terms is . 6. Periodize the result by substituting the periodizing function into the newly-constructed interpolation, evaluating the result at the interpolation nodes' absicssas, and converting it back to Fourier space. (This can also be done using the FFT algorithm, but we should use the DIT/Cooley-Tukey method.) 7. Normalize. Divide the result by its evaluation at 0. 8. Repeat steps 2-7 until convergence is attained. The program The implementation of the algorithm is given below, in PARI/GP. Code: `/* Perform discrete Fourier transform (DFT). */` To use, create an initial guess with Code: `tv = ConvToFourier(vector(N, i, 1))` where N should be odd, say N = 129. Decide on some period. I use pure imaginary periods. Assign it to P, say P = 48*I. Then just iterate away with Code: `tv = NormTetIter(P, base, tv)` where base is the desired base, like 2, or exp(1). When you want to use the approximation to evaluate tetration, use TetApprox(P, tv, base, x) with x being the height. For complex bases, a flat initial guess does not seem to yield convergence. However, starting with a real base's tetration, and then using that as the initial guess for a base somewhat away from it in the imaginary direction, and then using that as the guess for another, and so on, seems to work better. I haven't yet been able to push this into the left halfplane, not sure why. |