This is an archived, read-only copy of the United-TI subforum , including posts and topic from May 2003 to April 2012. If you would like to discuss any of the topics in this forum, you can visit Cemetech's TI-BASIC subforum. Some of these topics may also be directly-linked to active Cemetech topics. If you are a Cemetech member with a linked United-TI account, you can link United-TI topics here with your current Cemetech topics.

TI-Basic => TI-BASIC
Author Message
thornahawk
μολών λαβέ

Active Member

Joined: 27 Mar 2005
Posts: 569

 Posted: 04 Oct 2007 10:38:00 pm    Post subject: Here, now, is a fast Fourier transform program that works on lists of any length that will fit into calculator memory, not just powers of two. The algorithm, unfortunately, is not "in place", and thus has to use a scratch array to do its work. It also needs a list of prime numbers (with the list dimensions depending on your applications) stored in ∟PRIME, which can be generated by hand or through a sieving program. This is based on a formulation of the FFT by C. de Boor. Code: ```PROGRAM:FFT :L₁→L₂ :dim(L₁)→L :1→F:L→P:1→D :Repeat P=1 :∟PRIME(D)→Q :1→T :If gcd(P,Q)≠1 :Then:Q→Z:P/Z→P :Else:D+1→D :D>dim(∟PRIME)→T :If T:Then :P→Z:1→P :End:End :If T:Then :℮^(2πiB/Z/F)→W :1→S :For(M,1,Z) :For(K,1,F) :For(J,1,P) :0→Y :For(I,1,Z) :YS+L₁(K+F(J–1+P(Z–I)))→Y :End :Y→L₂(K+F(M–1+Z(J–1))) :End :SW→S :End:End :For(J,1,L) :L₂(J)→Y :L₁(J)→L₂(J) :Y→L₁(J) :End :FZ→F :End:End :DelVar L₂ :L₁/√(L/L^A)→L₁``` There is a slight wrinkle in the usage: I wanted the program to act like Mathematica's [font="Courier"]Fourier[] command with its [font="Courier"]FourierParameters option, so one must specify the values of A and B before running the program. The list to be FFT'd is stored in L1, and is replaced by the transformed list after the program has finished running. The usual settings for A and B in most applications are A=1 and B=-1. If the inverse transform is desired, the values of A and B must be negated. (edit 06/09/2010: I have attached the de Boor paper: [attachment=3189:fftmul.pdf]) thornahawkLast edited by Guest on 09 Jun 2010 09:43:16 am; edited 1 time in total
Pseudoprogrammer

Member

Joined: 12 Dec 2006
Posts: 121

 Posted: 04 Oct 2007 10:52:34 pm    Post subject: I see some optimizations, after your delvar, don't skip to a new line, and I'm assuming you used 0->Y instead of delvar for speed reasons.
thornahawk
μολών λαβέ

Active Member

Joined: 27 Mar 2005
Posts: 569

 Posted: 04 Oct 2007 11:09:48 pm    Post subject: Ah, yes, the program can of course be optimized by lobbing off ending parentheses and the others you have mentioned. I only elected not to in the interest of neatness. ;) In other words, optimizing is entirely up to you when you copy it to the calculator. :) thornahawkLast edited by Guest on 09 Jun 2010 09:37:25 am; edited 1 time in total
Weregoose
Authentic INTJ

Super Elite (Last Title)

Joined: 25 Nov 2004
Posts: 3976

 Posted: 04 Oct 2007 11:13:06 pm    Post subject: Well, there are those who are crazy about optimizing, and then some people recognize code that has dropped parentheses, etc. as having sloppy form that makes it less official. The point here is more of what the code does, and anyone is welcome to adjust it as it's being written into the calculator. [EDIT] – Crosspost with thornahawk.Last edited by Guest on 04 Oct 2007 11:15:17 pm; edited 1 time in total
thornahawk
μολών λαβέ

Active Member

Joined: 27 Mar 2005
Posts: 569

 Posted: 08 Jan 2008 08:46:08 pm    Post subject: For reference, here is a TI-Basic implementation of the usual power-of-two in-place Cooley-Tukey FFT. Usage is the same as the program previously posted (including the setting of A and B to appropriate values). Code: ```PROGRAM:FFTCT dim(L₁)→L 1→J For(I,1,L−1) \\ bit-reverse permutation If J>I:Then L₁(J)→T L₁(I)→L₁(J) T→L₁(I) End L/2→K While KM 2M→V:π^r(B/M)→θ \\ ^r - radian sign isin(θ)−2sin(θ/2)²→P 1→W For(K,1,M) For(I,K,L,V) I+M→J WL₁(J)→T L₁(I)−T→L₁(J) L₁(I)+T→L₁(I) End W+WP→W End V→M End L₁/√(L/L^A)→L₁``` thornahawkLast edited by Guest on 09 Jun 2010 09:48:20 am; edited 1 time in total
thornahawk
μολών λαβέ

Active Member

Joined: 27 Mar 2005
Posts: 569

 Posted: 09 Jun 2010 09:35:15 am    Post subject: One can do better than the Cooley-Tukey FFT if the input is real-valued, which is often the case in applications. Edson modified the original algorithm to get rid of the redundancies in the calculations. To wit: Code: ```PROGRAM:FFTRE :dim(L₁)→L :1→J :For(I,1,L-1) \\ bit-reversal permutation :If J>I:Then :L₁(J)→T :L₁(I)→L₁(J) :T→L₁(I) :End :L/2→K :While K
 Display posts from previous: All Posts Oldest FirstNewest First
Register to Join the Conversation
Have your own thoughts to add to this or any other topic? Want to ask a question, offer a suggestion, share your own programs and projects, upload a file to the file archives, get help with calculator and computer programming, or simply chat with like-minded coders and tech and calculator enthusiasts via the site-wide AJAX SAX widget? Registration for a free Cemetech account only takes a minute.

»
 Page 1 of 1 » All times are UTC - 5 Hours