Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
fixed point formula
(09/28/2014, 09:22 PM)jaydfox Wrote: Now, I haven't put much thought yet into how to analytically extend the function. However, just to get something to work with, we could calculate a bunch of fixed points for a list of bases, and then use that information to come up with an approximate Taylor series. This would boil down to either polynomial interpolation or least squares regression. You can do both at the same time if you use a discrete fourier transform, or DFT (use a list of equally spaces points on the circumference of a circle). I believe this is what Sheldon refers to as a Cauchy integral. It has the benefit of being a polynomial interpolation and a least squares fit, which is why it's so useful.

Another benefit of a DFT (compared to, say, Lagrange or Newton interpolation), is that it uses considerably less memory, and it's quite a bit faster if you use an FFT (Fast Fourier Transform). I'll see what I can put together over the next few days.

Okay, here's a somewhat stable version of my DFT/FFT library, a slightly updated version of the fixed point finder, and a piece of code that calculates the fixed point Taylor series using a DFT (i.e., a "Cauchy integral").

I was able to calculate 512 terms to 96 digits of precision, in just a couple seconds. It took my other code (closed-form calculation of terms, using reversion of a power series) over 2 minutes to get the same result. I then calculated 1600 terms, again in only a few seconds. It took nearly two days using my other code.

Needless to say, in this specific scenario, the DFT method is extremely fast. And just as accurate.

So, the files. First, the fixed point iterative solver:
.gp (Size: 6.3 KB / Downloads: 551)
It also has code for finding the inverse Schroeder function at the fixed point of an arbitrary Taylor series. This is used to find the inverse Schroeder function for the exponential function, but I assume it can be used for arbitrary functions. Edit: I forgot to mention, in this version of the library, I decided to go with Sheldon's convention of applying a factor of sqrt(-1) to the "z" term: z = I*sqrt(ln(ln(base))+1). The benefit of this is that the Taylor series takes on real coefficients only, which makes it a little easier to study. I haven't double checked all my other code yet to make sure I didn't break something in the process, so if you get an unexpected result, check with the previous version of the code. End Edit

The second file is the DFT library:
.gp (Size: 16.45 KB / Downloads: 538)
It has a few comments here and there, but it needs more. I was originally writing it to speed up the "Cauchy integrals" in Sheldon's kneser/tetcomplex code, by converting them from simple DFT's to Fast Fourier Transforms. But FFT's turned out to be so much fun, that I got carried away and built a library, useful for other applications as well.

Finally, here's the code that uses these two libraries to calculate the fixed point formula:
.gp (Size: 6.76 KB / Downloads: 547)
There's a lot of experimental code in here, so I apologize in advance for any bugs, or for any code that's hard to reverse engineer.

Note the performance of the FFT. I can use thousands of samples and still get a result in a few seconds. Heck, I can do tens of thousands of samples and still get a result in a reasonable timeframe. I did 8! (40320) samples in 11 seconds at 67 digits of precision, or 30 seconds at 144 digits.

Update: I suppose I should post a screenshot. The following three lines of code were typed at the prompt. It's hard to tell because of the long help text that displays when you load the file):
DFT_FPFunc(-30, 2.0, 67)

~ Jay Daniel Fox

Messages In This Thread
fixed point formula - by sheldonison - 02/25/2012, 06:35 AM
RE: fixed point formula - by jaydfox - 09/23/2014, 11:01 PM
RE: fixed point formula - by jaydfox - 09/28/2014, 09:22 PM
RE: fixed point formula - by jaydfox - 10/01/2014, 04:43 AM
RE: fixed point formula - by sheldonison - 03/11/2015, 01:24 PM
RE: fixed point formula - by sheldonison - 03/30/2015, 05:25 AM
RE: fixed point formula - by mike3 - 05/23/2015, 04:32 AM

Possibly Related Threads...
Thread Author Replies Views Last Post
  Attempt to find a limit point but each step needs doubling the precision... Gottfried 15 29,451 11/09/2014, 10:25 PM
Last Post: tommy1729
  Find all fixed points of exp[b] MorgothV8 10 23,738 10/07/2014, 11:00 AM
Last Post: Gottfried
  Road testing Ansus' continuum product formula mike3 33 48,307 09/23/2009, 08:26 PM
Last Post: mike3
  sexp(strip) is winding around the fixed points Kouznetsov 8 18,517 06/29/2009, 10:05 AM
Last Post: bo198214
  An error estimate for fixed point computation of b^x bo198214 0 3,643 05/31/2008, 04:11 PM
Last Post: bo198214

Users browsing this thread: 1 Guest(s)