/ Usenet 1994 January / usenetsourcesnewsgroupsinfomagicjanuary1994.iso / sources / misc / volume1 / 8707 / 70

< prev

next >

view JSON data

view as text

open on a Mac

open on a PC

+--------+-------------------------+-------------------------+--------+--------+
|00000000| 46 72 6f 6d 3a 20 61 65 | 75 73 65 6d 72 73 40 63 |From: ae|usemrs@c|
|00000010| 73 75 6e 2e 55 55 43 50 | 20 28 4d 69 6b 65 20 53 |sun.UUCP| (Mike S|
|00000020| 74 75 6d 70 29 0a 4e 65 | 77 73 67 72 6f 75 70 73 |tump).Ne|wsgroups|
|00000030| 3a 20 63 6f 6d 70 2e 73 | 6f 75 72 63 65 73 2e 6d |: comp.s|ources.m|
|00000040| 69 73 63 0a 53 75 62 6a | 65 63 74 3a 20 46 61 73 |isc.Subj|ect: Fas|
|00000050| 74 20 46 6f 75 72 69 65 | 72 20 54 72 61 6e 73 66 |t Fourie|r Transf|
|00000060| 6f 72 6d 0a 4d 65 73 73 | 61 67 65 2d 49 44 3a 20 |orm.Mess|age-ID: |
|00000070| 3c 33 36 36 39 40 6e 63 | 6f 61 73 74 2e 55 55 43 |<3669@nc|oast.UUC|
|00000080| 50 3e 0a 44 61 74 65 3a | 20 32 38 20 4a 75 6c 20 |P>.Date:| 28 Jul |
|00000090| 38 37 20 32 33 3a 34 36 | 3a 31 31 20 47 4d 54 0a |87 23:46|:11 GMT.|
|000000a0| 53 65 6e 64 65 72 3a 20 | 61 6c 6c 62 65 72 79 40 |Sender: |allbery@|
|000000b0| 6e 63 6f 61 73 74 2e 55 | 55 43 50 0a 4f 72 67 61 |ncoast.U|UCP.Orga|
|000000c0| 6e 69 7a 61 74 69 6f 6e | 3a 20 43 61 6c 69 66 6f |nization|: Califo|
|000000d0| 72 6e 69 61 20 53 74 61 | 74 65 20 55 6e 69 76 65 |rnia Sta|te Unive|
|000000e0| 72 73 69 74 79 2c 20 4e | 6f 72 74 68 72 69 64 67 |rsity, N|orthridg|
|000000f0| 65 0a 4c 69 6e 65 73 3a | 20 32 35 39 0a 41 70 70 |e.Lines:| 259.App|
|00000100| 72 6f 76 65 64 3a 20 61 | 6c 6c 62 65 72 79 40 6e |roved: a|llbery@n|
|00000110| 63 6f 61 73 74 2e 55 55 | 43 50 0a 58 2d 41 72 63 |coast.UU|CP.X-Arc|
|00000120| 68 69 76 65 3a 20 63 6f | 6d 70 2e 73 6f 75 72 63 |hive: co|mp.sourc|
|00000130| 65 73 2e 6d 69 73 63 2f | 38 37 30 37 2f 37 30 0a |es.misc/|8707/70.|
|00000140| 0a 41 6c 6c 20 72 69 67 | 68 74 2c 20 68 65 72 65 |.All rig|ht, here|
|00000150| 20 69 74 20 69 73 21 0a | 0a 23 21 20 2f 62 69 6e | it is!.|.#! /bin|
|00000160| 2f 73 68 0a 23 20 54 68 | 69 73 20 69 73 20 61 20 |/sh.# Th|is is a |
|00000170| 73 68 65 6c 6c 20 61 72 | 63 68 69 76 65 2c 20 6d |shell ar|chive, m|
|00000180| 65 61 6e 69 6e 67 3a 0a | 23 20 31 2e 20 52 65 6d |eaning:.|# 1. Rem|
|00000190| 6f 76 65 20 65 76 65 72 | 79 74 68 69 6e 67 20 61 |ove ever|ything a|
|000001a0| 62 6f 76 65 20 74 68 65 | 20 23 21 20 2f 62 69 6e |bove the| #! /bin|
|000001b0| 2f 73 68 20 6c 69 6e 65 | 2e 0a 23 20 32 2e 20 53 |/sh line|..# 2. S|
|000001c0| 61 76 65 20 74 68 65 20 | 72 65 73 75 6c 74 69 6e |ave the |resultin|
|000001d0| 67 20 74 65 78 74 20 69 | 6e 20 61 20 66 69 6c 65 |g text i|n a file|
|000001e0| 2e 0a 23 20 33 2e 20 45 | 78 65 63 75 74 65 20 74 |..# 3. E|xecute t|
|000001f0| 68 65 20 66 69 6c 65 20 | 77 69 74 68 20 2f 62 69 |he file |with /bi|
|00000200| 6e 2f 73 68 20 28 6e 6f | 74 20 63 73 68 29 20 74 |n/sh (no|t csh) t|
|00000210| 6f 20 63 72 65 61 74 65 | 20 74 68 65 20 66 69 6c |o create| the fil|
|00000220| 65 73 3a 0a 23 09 66 66 | 74 2e 64 6f 63 0a 23 09 |es:.#.ff|t.doc.#.|
|00000230| 66 66 74 2e 63 0a 23 20 | 54 68 69 73 20 61 72 63 |fft.c.# |This arc|
|00000240| 68 69 76 65 20 63 72 65 | 61 74 65 64 3a 20 53 75 |hive cre|ated: Su|
|00000250| 6e 20 4a 75 6c 20 32 36 | 20 31 31 3a 33 32 3a 33 |n Jul 26| 11:32:3|
|00000260| 35 20 31 39 38 37 0a 65 | 78 70 6f 72 74 20 50 41 |5 1987.e|xport PA|
|00000270| 54 48 3b 20 50 41 54 48 | 3d 2f 62 69 6e 3a 24 50 |TH; PATH|=/bin:$P|
|00000280| 41 54 48 0a 69 66 20 74 | 65 73 74 20 2d 66 20 27 |ATH.if t|est -f '|
|00000290| 66 66 74 2e 64 6f 63 27 | 0a 74 68 65 6e 0a 09 65 |fft.doc'|.then..e|
|000002a0| 63 68 6f 20 73 68 61 72 | 3a 20 77 69 6c 6c 20 6e |cho shar|: will n|
|000002b0| 6f 74 20 6f 76 65 72 2d | 77 72 69 74 65 20 65 78 |ot over-|write ex|
|000002c0| 69 73 74 69 6e 67 20 66 | 69 6c 65 20 22 27 66 66 |isting f|ile "'ff|
|000002d0| 74 2e 64 6f 63 27 22 0a | 65 6c 73 65 0a 63 61 74 |t.doc'".|else.cat|
|000002e0| 20 3c 3c 20 5c 53 48 41 | 52 5f 45 4f 46 20 3e 20 | << \SHA|R_EOF > |
|000002f0| 27 66 66 74 2e 64 6f 63 | 27 0a 09 09 44 6f 63 75 |'fft.doc|'...Docu|
|00000300| 6d 65 6e 74 61 74 69 6f | 6e 20 66 6f 72 20 66 66 |mentatio|n for ff|
|00000310| 74 2e 63 0a 0a 09 54 68 | 69 73 20 70 72 6f 67 72 |t.c...Th|is progr|
|00000320| 61 6d 20 69 73 20 61 20 | 64 69 72 65 63 74 20 74 |am is a |direct t|
|00000330| 72 61 6e 73 6c 61 74 69 | 6f 6e 20 66 72 6f 6d 20 |ranslati|on from |
|00000340| 46 4f 52 54 52 41 4e 20 | 49 56 20 6f 66 20 45 2e |FORTRAN |IV of E.|
|00000350| 20 4f 2e 20 42 72 69 67 | 68 61 6d 27 73 0a 70 72 | O. Brig|ham's.pr|
|00000360| 6f 67 72 61 6d 20 6f 6e | 20 74 68 65 20 66 61 73 |ogram on| the fas|
|00000370| 74 20 46 6f 75 72 69 65 | 72 20 74 72 61 6e 73 66 |t Fourie|r transf|
|00000380| 6f 72 6d 2c 20 54 68 65 | 20 46 61 73 74 20 46 6f |orm, The| Fast Fo|
|00000390| 75 72 69 65 72 20 54 72 | 61 6e 73 66 6f 72 6d 2e |urier Tr|ansform.|
|000003a0| 20 20 49 20 73 75 67 67 | 65 73 74 0a 72 65 61 64 |  I sugg|est.read|
|000003b0| 69 6e 67 20 74 68 65 20 | 62 6f 6f 6b 2c 20 74 6f |ing the |book, to|
|000003c0| 20 67 65 74 20 74 68 65 | 20 64 65 74 61 69 6c 73 | get the| details|
|000003d0| 20 6f 66 20 74 68 65 20 | 6d 65 74 68 6f 64 2e 20 | of the |method. |
|000003e0| 20 0a 0a 09 49 6e 20 74 | 72 61 6e 73 6c 61 74 69 | ...In t|ranslati|
|000003f0| 6e 67 20 74 68 69 73 20 | 70 72 6f 67 72 61 6d 20 |ng this |program |
|00000400| 66 72 6f 6d 20 46 4f 52 | 54 52 41 4e 2c 20 49 20 |from FOR|TRAN, I |
|00000410| 72 65 74 61 69 6e 65 64 | 20 74 68 65 20 62 69 74 |retained| the bit|
|00000420| 20 73 77 61 70 70 69 6e | 67 0a 66 75 6e 63 74 69 | swappin|g.functi|
|00000430| 6f 6e 20 64 65 73 63 72 | 69 62 65 64 20 62 79 20 |on descr|ibed by |
|00000440| 42 72 69 67 68 61 6d 2e | 20 20 55 73 69 6e 67 20 |Brigham.|  Using |
|00000450| 62 69 74 20 6f 70 65 72 | 61 74 6f 72 73 2c 20 49 |bit oper|ators, I|
|00000460| 20 61 73 73 75 6d 65 20 | 74 68 61 74 20 61 20 6d | assume |that a m|
|00000470| 6f 72 65 20 0a 65 66 66 | 69 63 69 65 6e 74 20 6d |ore .eff|icient m|
|00000480| 61 6e 6e 65 72 20 6f 66 | 20 62 69 74 20 73 77 61 |anner of| bit swa|
|00000490| 70 70 69 6e 67 20 63 61 | 6e 20 62 65 20 70 65 72 |pping ca|n be per|
|000004a0| 66 6f 72 6d 65 64 2e 20 | 20 0a 0a 09 49 20 75 73 |formed. | ...I us|
|000004b0| 65 64 20 70 6f 69 6e 74 | 65 72 73 20 74 6f 20 74 |ed point|ers to t|
|000004c0| 68 65 20 64 61 74 61 20 | 74 6f 20 62 65 20 74 72 |he data |to be tr|
|000004d0| 61 6e 73 66 6f 72 6d 65 | 64 20 74 6f 20 61 6c 6c |ansforme|d to all|
|000004e0| 6f 77 20 74 68 65 20 72 | 6f 75 74 69 6e 65 20 74 |ow the r|outine t|
|000004f0| 6f 0a 62 65 20 6d 6f 72 | 65 20 67 65 6e 65 72 61 |o.be mor|e genera|
|00000500| 6c 2e 20 20 54 68 75 73 | 20 66 66 74 28 29 20 6e |l.  Thus| fft() n|
|00000510| 65 65 64 73 20 74 6f 20 | 6b 6e 6f 77 20 74 68 65 |eeds to |know the|
|00000520| 20 6e 75 6d 62 65 72 20 | 6f 66 20 64 61 74 61 20 | number |of data |
|00000530| 70 6f 69 6e 74 73 20 77 | 68 65 6e 20 69 74 20 69 |points w|hen it i|
|00000540| 73 0a 63 61 6c 6c 65 64 | 20 77 68 69 63 68 20 69 |s.called| which i|
|00000550| 73 20 6f 6e 6c 79 20 6c | 69 6d 69 74 65 64 20 62 |s only l|imited b|
|00000560| 79 20 6d 65 6d 6f 72 79 | 20 73 69 7a 65 2c 20 77 |y memory| size, w|
|00000570| 68 69 63 68 20 63 61 6e | 20 67 65 74 20 75 73 65 |hich can| get use|
|00000580| 64 20 75 70 20 71 75 69 | 63 6b 6c 79 20 0a 73 69 |d up qui|ckly .si|
|00000590| 6e 63 65 20 65 61 63 68 | 20 70 6f 69 6e 74 20 69 |nce each| point i|
|000005a0| 73 20 72 65 70 72 65 73 | 65 6e 74 65 64 20 62 79 |s repres|ented by|
|000005b0| 20 74 77 6f 20 38 2d 62 | 79 74 65 20 6e 75 6d 62 | two 8-b|yte numb|
|000005c0| 65 72 73 2e 20 20 41 20 | 73 6f 6c 75 74 69 6f 6e |ers.  A |solution|
|000005d0| 20 6d 69 67 68 74 20 62 | 65 20 74 6f 20 0a 68 6f | might b|e to .ho|
|000005e0| 6c 64 20 74 68 65 20 64 | 61 74 61 20 6f 6e 20 64 |ld the d|ata on d|
|000005f0| 69 73 6b 20 61 6e 64 20 | 75 73 65 20 64 69 73 6b |isk and |use disk|
|00000600| 20 61 63 63 65 73 73 20 | 66 75 6e 63 74 69 6f 6e | access |function|
|00000610| 73 2c 20 69 66 20 79 6f | 75 20 72 75 6e 20 6f 75 |s, if yo|u run ou|
|00000620| 74 20 6f 66 20 6d 65 6d | 6f 72 79 0a 66 6f 72 20 |t of mem|ory.for |
|00000630| 74 68 65 20 64 61 74 61 | 2e 20 20 54 68 69 73 20 |the data|.  This |
|00000640| 6d 65 74 68 6f 64 20 73 | 68 6f 75 6c 64 20 62 65 |method s|hould be|
|00000650| 20 61 76 6f 69 64 65 64 | 20 66 6f 72 20 73 6d 61 | avoided| for sma|
|00000660| 6c 6c 20 64 61 74 61 20 | 73 65 74 73 2c 20 73 69 |ll data |sets, si|
|00000670| 6e 63 65 20 74 68 65 0a | 63 61 6c 63 75 6c 61 74 |nce the.|calculat|
|00000680| 69 6f 6e 20 74 69 6d 65 | 20 69 6e 63 72 65 61 73 |ion time| increas|
|00000690| 65 73 20 64 72 61 6d 61 | 74 69 63 61 6c 6c 79 20 |es drama|tically |
|000006a0| 77 69 74 68 20 6d 6f 72 | 65 20 64 61 74 61 20 70 |with mor|e data p|
|000006b0| 6f 69 6e 74 73 20 74 6f | 20 74 72 61 6e 73 66 6f |oints to| transfo|
|000006c0| 72 6d 2e 0a 57 69 74 68 | 20 64 69 73 6b 20 6f 76 |rm..With| disk ov|
|000006d0| 65 72 68 65 61 64 2c 20 | 63 61 6c 63 75 6c 61 74 |erhead, |calculat|
|000006e0| 69 6f 6e 20 74 69 6d 65 | 20 77 69 6c 6c 20 73 6c |ion time| will sl|
|000006f0| 6f 77 20 64 6f 77 6e 20 | 63 6f 6e 73 69 64 65 72 |ow down |consider|
|00000700| 61 62 6c 79 2e 20 20 54 | 6f 20 73 61 76 65 0a 6d |ably.  T|o save.m|
|00000710| 65 6d 6f 72 79 20 73 70 | 61 63 65 20 79 6f 75 20 |emory sp|ace you |
|00000720| 63 61 6e 20 72 65 64 65 | 66 69 6e 65 20 74 68 65 |can rede|fine the|
|00000730| 20 76 61 72 69 61 62 6c | 65 20 74 79 70 65 73 20 | variabl|e types |
|00000740| 66 72 6f 6d 20 64 6f 75 | 62 6c 65 20 74 6f 20 73 |from dou|ble to s|
|00000750| 69 6e 67 6c 65 0a 70 72 | 65 63 69 73 69 6f 6e 20 |ingle.pr|ecision |
|00000760| 61 74 20 74 68 65 20 65 | 78 70 65 6e 73 65 20 6f |at the e|xpense o|
|00000770| 66 20 70 72 65 63 69 73 | 69 6f 6e 2e 0a 0a 09 49 |f precis|ion....I|
|00000780| 20 68 61 76 65 20 63 6f | 6d 70 61 72 65 64 20 74 | have co|mpared t|
|00000790| 68 65 20 70 65 72 66 6f | 72 6d 61 6e 63 65 20 6f |he perfo|rmance o|
|000007a0| 66 20 74 68 65 20 66 66 | 74 20 74 6f 20 61 20 72 |f the ff|t to a r|
|000007b0| 65 67 75 6c 61 72 20 46 | 6f 75 72 69 65 72 20 74 |egular F|ourier t|
|000007c0| 72 61 6e 73 2d 0a 66 6f | 72 6d 2c 20 61 6e 64 20 |rans-.fo|rm, and |
|000007d0| 74 68 65 20 66 66 74 20 | 77 69 6e 73 20 6f 75 74 |the fft |wins out|
|000007e0| 20 65 73 70 65 63 69 61 | 6c 6c 79 20 77 68 65 6e | especia|lly when|
|000007f0| 20 74 68 65 72 65 20 61 | 72 65 20 6d 6f 72 65 20 | there a|re more |
|00000800| 74 68 61 6e 20 35 31 32 | 20 64 61 74 61 20 70 6f |than 512| data po|
|00000810| 69 6e 74 73 2e 0a 54 68 | 65 20 72 65 73 74 72 69 |ints..Th|e restri|
|00000820| 63 74 69 6f 6e 20 6f 66 | 20 68 61 76 69 6e 67 20 |ction of| having |
|00000830| 74 68 65 20 64 61 74 61 | 20 62 65 20 61 20 6d 75 |the data| be a mu|
|00000840| 6c 74 69 70 6c 65 20 6f | 66 20 32 20 69 73 20 75 |ltiple o|f 2 is u|
|00000850| 73 75 61 6c 6c 79 20 6e | 6f 74 20 70 72 6f 68 69 |sually n|ot prohi|
|00000860| 62 69 2d 0a 74 69 76 65 | 20 73 69 6e 63 65 20 74 |bi-.tive| since t|
|00000870| 68 65 20 64 61 74 61 20 | 75 73 75 61 6c 6c 79 20 |he data |usually |
|00000880| 61 72 65 20 67 65 6e 65 | 72 61 74 65 64 20 62 79 |are gene|rated by|
|00000890| 20 61 20 63 6f 6d 70 75 | 74 65 72 20 69 6e 20 62 | a compu|ter in b|
|000008a0| 61 73 65 20 32 2c 20 65 | 67 2e 20 72 61 64 69 6f |ase 2, e|g. radio|
|000008b0| 0a 61 73 74 72 6f 6e 6f | 6d 79 20 28 6d 79 20 6f |.astrono|my (my o|
|000008c0| 72 69 67 69 6e 61 6c 20 | 70 75 72 70 6f 73 65 20 |riginal |purpose |
|000008d0| 66 6f 72 20 77 72 69 74 | 69 6e 67 20 74 68 69 73 |for writ|ing this|
|000008e0| 20 70 72 6f 67 72 61 6d | 29 2c 20 69 6d 61 67 65 | program|), image|
|000008f0| 20 61 6e 61 6c 79 73 69 | 73 2c 20 65 74 63 2e 0a | analysi|s, etc..|
|00000900| 0a 09 45 6e 63 6c 6f 73 | 65 64 20 69 73 20 73 6f |..Enclos|ed is so|
|00000910| 6d 65 20 73 61 6d 70 6c | 65 20 64 61 74 61 20 61 |me sampl|e data a|
|00000920| 6e 64 20 69 74 73 20 74 | 72 61 6e 73 66 6f 72 6d |nd its t|ransform|
|00000930| 2e 20 20 55 73 65 20 74 | 68 69 73 20 74 6f 20 64 |.  Use t|his to d|
|00000940| 65 62 75 67 20 74 68 65 | 0a 70 72 6f 67 72 61 6d |ebug the|.program|
|00000950| 20 69 66 20 6e 65 63 65 | 73 73 61 72 79 20 28 20 | if nece|ssary ( |
|00000960| 49 20 68 61 74 65 20 74 | 6f 20 72 65 63 65 69 76 |I hate t|o receiv|
|00000970| 65 20 61 20 64 61 74 61 | 20 61 6e 61 6c 79 73 69 |e a data| analysi|
|00000980| 73 20 70 72 6f 67 72 61 | 6d 20 77 69 74 68 20 6e |s progra|m with n|
|00000990| 6f 20 64 61 74 61 20 0a | 74 6f 20 74 65 73 74 20 |o data .|to test |
|000009a0| 74 68 65 20 70 72 6f 67 | 72 61 6d 20 29 2e 20 20 |the prog|ram ).  |
|000009b0| 54 68 65 73 65 20 64 61 | 74 61 20 68 61 76 65 20 |These da|ta have |
|000009c0| 62 65 65 6e 20 63 68 65 | 63 6b 65 64 20 66 6f 72 |been che|cked for|
|000009d0| 20 63 6f 72 72 65 63 74 | 6e 65 73 73 20 62 79 20 | correct|ness by |
|000009e0| 75 73 69 6e 67 0a 61 20 | 73 74 61 6e 64 61 72 64 |using.a |standard|
|000009f0| 20 46 46 54 20 66 72 6f | 6d 20 61 20 6d 61 69 6e | FFT fro|m a main|
|00000a00| 66 72 61 6d 65 20 63 6f | 6d 70 75 74 65 72 20 6d |frame co|mputer m|
|00000a10| 61 74 68 20 6c 69 62 72 | 61 72 79 2e 0a 0a 09 46 |ath libr|ary....F|
|00000a20| 69 6e 61 6c 6c 79 20 69 | 66 20 79 6f 75 20 68 61 |inally i|f you ha|
|00000a30| 76 65 20 61 6e 79 20 71 | 75 65 73 74 69 6f 6e 73 |ve any q|uestions|
|00000a40| 20 6f 72 20 73 75 67 67 | 65 73 74 69 6f 6e 73 2c | or sugg|estions,|
|00000a50| 20 70 6c 65 61 73 65 20 | 63 6f 6e 74 61 63 74 20 | please |contact |
|00000a60| 6d 65 3a 0a 0a 09 09 09 | 4a 69 6d 20 50 69 73 61 |me:.....|Jim Pisa|
|00000a70| 6e 6f 0a 09 09 09 50 2e | 4f 2e 20 42 6f 78 20 33 |no....P.|O. Box 3|
|00000a80| 31 33 34 0a 09 09 09 43 | 68 61 72 6c 6f 74 74 65 |134....C|harlotte|
|00000a90| 73 76 69 6c 6c 65 2c 20 | 56 41 20 32 32 39 30 33 |sville, |VA 22903|
|00000aa0| 0a 0a 09 4f 72 20 63 6f | 6e 74 61 63 74 20 61 65 |...Or co|ntact ae|
|00000ab0| 75 73 65 6d 72 73 40 63 | 73 75 6e 2e 75 75 63 70 |usemrs@c|sun.uucp|
|00000ac0| 20 28 4d 69 6b 65 20 53 | 74 75 6d 70 29 2e 0a 0a | (Mike S|tump)...|
|00000ad0| 09 09 09 49 4e 50 55 54 | 09 09 09 20 20 20 20 20 |...INPUT|...     |
|00000ae0| 20 20 4f 55 54 50 55 54 | 0a 69 6e 64 65 78 09 09 |  OUTPUT|.index..|
|00000af0| 72 65 61 6c 09 09 69 6d | 61 67 69 6e 61 72 79 09 |real..im|aginary.|
|00000b00| 72 65 61 6c 09 09 69 6d | 61 67 69 6e 61 72 79 0a |real..im|aginary.|
|00000b10| 5f 5f 5f 5f 5f 5f 5f 5f | 5f 5f 5f 5f 5f 5f 5f 5f |________|________|
|00000b20| 5f 5f 5f 5f 5f 5f 5f 5f | 5f 5f 5f 5f 5f 5f 5f 5f |________|________|
|00000b30| 5f 5f 5f 5f 5f 5f 5f 5f | 5f 5f 5f 5f 5f 5f 5f 5f |________|________|
|00000b40| 5f 5f 5f 5f 5f 5f 5f 5f | 5f 5f 5f 5f 5f 5f 5f 5f |________|________|
|00000b50| 5f 5f 5f 5f 5f 5f 5f 5f | 5f 5f 5f 5f 5f 0a 0a 20 |________|_____.. |
|00000b60| 31 09 09 2d 32 38 2e 36 | 36 09 09 30 2e 30 09 09 |1..-28.6|6..0.0..|
|00000b70| 2d 30 30 2e 31 31 09 09 | 30 2e 30 0a 20 32 09 09 |-00.11..|0.0. 2..|
|00000b80| 2d 33 32 2e 34 33 09 09 | 30 2e 30 09 09 2d 32 39 |-32.43..|0.0..-29|
|00000b90| 2e 39 38 36 34 34 09 2d | 33 38 2e 32 31 31 0a 20 |.98644.-|38.211. |
|00000ba0| 33 09 09 2d 38 2e 34 32 | 09 09 30 2e 30 09 09 2d |3..-8.42|..0.0..-|
|00000bb0| 36 32 2e 33 32 39 34 34 | 09 2d 32 33 2e 39 31 30 |62.32944|.-23.910|
|00000bc0| 32 35 0a 20 34 09 09 34 | 30 2e 32 32 09 09 30 2e |25. 4..4|0.22..0.|
|00000bd0| 30 09 09 2d 35 38 2e 33 | 32 38 37 32 09 2d 31 30 |0..-58.3|2872.-10|
|00000be0| 2e 30 32 32 35 33 0a 20 | 35 09 09 20 31 2e 31 34 |.02253. |5.. 1.14|
|00000bf0| 09 09 30 2e 30 09 09 2d | 35 38 2e 34 36 38 30 34 |..0.0..-|58.46804|
|00000c00| 09 2d 37 2e 37 38 37 34 | 38 0a 20 36 09 09 2d 32 |.-7.7874|8. 6..-2|
|00000c10| 35 2e 30 35 09 09 30 2e | 30 09 09 2d 36 38 2e 31 |5.05..0.|0..-68.1|
|00000c20| 31 30 36 38 09 2d 35 2e | 32 38 39 39 35 0a 20 37 |1068.-5.|28995. 7|
|00000c30| 09 09 31 32 2e 31 34 09 | 09 30 2e 30 09 09 2d 38 |..12.14.|.0.0..-8|
|00000c40| 36 2e 38 30 39 32 39 09 | 2d 31 31 2e 37 37 37 34 |6.80929.|-11.7774|
|00000c50| 36 0a 20 38 09 09 32 37 | 2e 38 32 09 09 30 2e 30 |6. 8..27|.82..0.0|
|00000c60| 09 09 2d 31 33 37 2e 36 | 38 09 09 2d 30 2e 30 36 |..-137.6|8..-0.06|
|00000c70| 38 38 33 0a 20 39 09 09 | 32 2e 34 09 09 30 2e 30 |883. 9..|2.4..0.0|
|00000c80| 09 09 2d 33 33 2e 30 33 | 33 30 34 09 32 30 32 2e |..-33.03|304.202.|
|00000c90| 32 34 0a 31 30 09 09 2d | 31 39 2e 36 38 09 09 30 |24.10..-|19.68..0|
|00000ca0| 2e 30 09 09 38 32 2e 34 | 33 37 36 35 09 37 32 2e |.0..82.4|3765.72.|
|00000cb0| 34 33 39 39 35 0a 31 31 | 09 09 37 2e 35 35 09 09 |43995.11|..7.55..|
|00000cc0| 30 2e 30 09 09 32 35 2e | 39 30 34 36 31 09 31 38 |0.0..25.|90461.18|
|00000cd0| 2e 31 35 31 37 0a 31 32 | 09 09 31 37 2e 32 32 09 |.1517.12|..17.22.|
|00000ce0| 09 30 2e 30 09 09 38 2e | 32 36 39 31 32 09 09 36 |.0.0..8.|26912..6|
|00000cf0| 2e 35 35 35 0a 31 33 09 | 09 2d 30 2e 35 38 09 09 |.555.13.|.-0.58..|
|00000d00| 30 2e 30 09 09 2d 34 2e | 33 33 31 39 35 09 33 2e |0.0..-4.|33195.3.|
|00000d10| 39 31 32 35 33 0a 31 34 | 09 09 2d 31 32 2e 35 09 |91253.14|..-12.5.|
|00000d20| 09 30 2e 30 09 09 2d 38 | 2e 35 34 35 37 35 09 2d |.0.0..-8|.54575.-|
|00000d30| 31 31 2e 35 36 37 32 0a | 31 35 09 09 30 2e 38 39 |11.5672.|15..0.89|
|00000d40| 09 09 30 2e 30 09 09 2d | 32 30 2e 33 32 35 38 36 |..0.0..-|20.32586|
|00000d50| 09 2d 33 2e 38 36 32 38 | 39 0a 31 36 09 09 31 30 |.-3.8628|9.16..10|
|00000d60| 2e 34 35 09 09 30 2e 30 | 09 09 2d 38 2e 30 35 35 |.45..0.0|..-8.055|
|00000d70| 32 31 09 31 30 2e 37 34 | 38 31 36 0a 31 37 09 09 |21.10.74|816.17..|
|00000d80| 2d 31 2e 31 36 09 09 30 | 2e 30 09 09 31 2e 37 37 |-1.16..0|.0..1.77|
|00000d90| 09 09 30 2e 30 0a 31 38 | 09 09 2d 37 2e 30 36 09 |..0.0.18|..-7.06.|
|00000da0| 09 30 2e 30 09 09 2d 38 | 2e 30 35 35 32 09 09 2d |.0.0..-8|.0552..-|
|00000db0| 31 30 2e 37 34 38 31 36 | 0a 31 39 09 09 2d 30 2e |10.74816|.19..-0.|
|00000dc0| 32 33 09 09 30 2e 30 09 | 09 2d 32 30 2e 33 32 35 |23..0.0.|.-20.325|
|00000dd0| 38 36 09 33 2e 38 36 32 | 38 39 0a 32 30 09 09 34 |86.3.862|89.20..4|
|00000de0| 2e 35 39 09 09 30 2e 30 | 09 09 2d 38 2e 35 34 35 |.59..0.0|..-8.545|
|00000df0| 37 35 09 31 31 2e 35 36 | 37 32 0a 32 31 09 09 31 |75.11.56|72.21..1|
|00000e00| 2e 34 35 09 09 30 2e 30 | 09 09 2d 34 2e 33 33 31 |.45..0.0|..-4.331|
|00000e10| 39 35 09 2d 33 2e 39 31 | 32 35 33 0a 32 32 09 09 |95.-3.91|253.22..|
|00000e20| 2d 33 2e 34 09 09 30 2e | 30 09 09 38 2e 32 36 39 |-3.4..0.|0..8.269|
|00000e30| 31 33 09 09 2d 36 2e 35 | 35 35 30 31 0a 32 33 09 |13..-6.5|5501.23.|
|00000e40| 09 33 2e 30 33 09 09 30 | 2e 30 09 09 32 35 2e 39 |.3.03..0|.0..25.9|
|00000e50| 30 34 36 09 09 2d 31 38 | 2e 31 35 31 36 39 0a 32 |046..-18|.15169.2|
|00000e60| 34 09 09 33 2e 30 35 09 | 09 30 2e 30 09 09 38 32 |4..3.05.|.0.0..82|
|00000e70| 2e 34 33 37 36 33 09 2d | 37 32 2e 34 33 39 39 36 |.43763.-|72.43996|
|00000e80| 0a 32 35 09 09 33 2e 36 | 37 09 09 30 2e 30 09 09 |.25..3.6|7..0.0..|
|00000e90| 2d 33 33 2e 30 32 39 39 | 36 09 2d 32 30 32 2e 32 |-33.0299|6.-202.2|
|00000ea0| 34 0a 32 36 09 09 2d 30 | 2e 35 31 09 09 30 2e 30 |4.26..-0|.51..0.0|
|00000eb0| 09 09 2d 31 33 37 2e 36 | 38 09 09 30 2e 30 36 38 |..-137.6|8..0.068|
|00000ec0| 38 34 0a 32 37 09 09 2d | 34 2e 33 35 09 09 30 2e |84.27..-|4.35..0.|
|00000ed0| 30 09 09 2d 38 36 2e 38 | 30 39 33 31 09 31 31 2e |0..-86.8|0931.11.|
|00000ee0| 37 37 37 34 36 0a 32 38 | 09 09 2d 31 2e 34 35 09 |77746.28|..-1.45.|
|00000ef0| 09 30 2e 30 09 09 2d 36 | 38 2e 31 31 30 36 36 09 |.0.0..-6|8.11066.|
|00000f00| 35 2e 32 38 39 39 35 0a | 32 39 09 09 35 2e 36 34 |5.28995.|29..5.64|
|00000f10| 09 09 30 2e 30 09 09 2d | 35 38 2e 34 36 38 30 35 |..0.0..-|58.46805|
|00000f20| 09 37 2e 37 38 37 34 37 | 0a 33 30 09 09 2d 30 2e |.7.78747|.30..-0.|
|00000f30| 39 36 09 09 30 2e 30 09 | 09 2d 35 38 2e 33 32 38 |96..0.0.|.-58.328|
|00000f40| 37 32 09 31 30 2e 30 32 | 32 35 33 0a 33 31 09 09 |72.10.02|253.31..|
|00000f50| 2d 34 2e 34 36 09 09 30 | 2e 30 09 09 2d 36 32 2e |-4.46..0|.0..-62.|
|00000f60| 33 32 39 34 35 09 32 33 | 2e 39 31 32 30 35 0a 33 |32945.23|.91205.3|
|00000f70| 32 09 09 2d 31 2e 32 35 | 09 09 30 2e 30 09 09 2d |2..-1.25|..0.0..-|
|00000f80| 32 39 2e 39 38 36 34 33 | 09 33 38 2e 32 31 31 30 |29.98643|.38.2110|
|00000f90| 31 0a 53 48 41 52 5f 45 | 4f 46 0a 66 69 20 23 20 |1.SHAR_E|OF.fi # |
|00000fa0| 65 6e 64 20 6f 66 20 6f | 76 65 72 77 72 69 74 69 |end of o|verwriti|
|00000fb0| 6e 67 20 63 68 65 63 6b | 0a 69 66 20 74 65 73 74 |ng check|.if test|
|00000fc0| 20 2d 66 20 27 66 66 74 | 2e 63 27 0a 74 68 65 6e | -f 'fft|.c'.then|
|00000fd0| 0a 09 65 63 68 6f 20 73 | 68 61 72 3a 20 77 69 6c |..echo s|har: wil|
|00000fe0| 6c 20 6e 6f 74 20 6f 76 | 65 72 2d 77 72 69 74 65 |l not ov|er-write|
|00000ff0| 20 65 78 69 73 74 69 6e | 67 20 66 69 6c 65 20 22 | existin|g file "|
|00001000| 27 66 66 74 2e 63 27 22 | 0a 65 6c 73 65 0a 63 61 |'fft.c'"|.else.ca|
|00001010| 74 20 3c 3c 20 5c 53 48 | 41 52 5f 45 4f 46 20 3e |t << \SH|AR_EOF >|
|00001020| 20 27 66 66 74 2e 63 27 | 0a 2f 2a 0a 49 6e 74 72 | 'fft.c'|./*.Intr|
|00001030| 6f 64 75 63 65 64 20 69 | 6e 74 6f 20 55 73 65 4e |oduced i|nto UseN|
|00001040| 65 74 20 42 79 3a 20 61 | 65 75 73 65 6d 72 73 40 |et By: a|eusemrs@|
|00001050| 63 73 75 6e 2e 75 75 63 | 70 20 28 4d 69 6b 65 20 |csun.uuc|p (Mike |
|00001060| 53 74 75 6d 70 29 20 53 | 75 6e 20 4a 75 6c 20 32 |Stump) S|un Jul 2|
|00001070| 36 20 31 31 3a 32 36 3a | 33 31 20 50 44 54 20 31 |6 11:26:|31 PDT 1|
|00001080| 39 38 37 0a 48 45 41 44 | 45 52 3a 0a 54 49 54 4c |987.HEAD|ER:.TITL|
|00001090| 45 3a 09 09 46 61 73 74 | 20 46 6f 75 72 69 65 72 |E:..Fast| Fourier|
|000010a0| 20 54 72 61 6e 73 66 6f | 72 6d 3b 0a 44 41 54 45 | Transfo|rm;.DATE|
|000010b0| 3a 09 09 30 35 2f 31 38 | 2f 31 39 38 35 3b 0a 44 |:..05/18|/1985;.D|
|000010c0| 45 53 43 52 49 50 54 49 | 4f 4e 3a 09 22 50 65 72 |ESCRIPTI|ON:."Per|
|000010d0| 66 6f 72 6d 73 20 66 61 | 73 74 20 66 6f 75 72 69 |forms fa|st fouri|
|000010e0| 65 72 20 74 72 61 6e 73 | 66 6f 72 6d 20 75 73 69 |er trans|form usi|
|000010f0| 6e 67 20 6d 65 74 68 6f | 64 20 64 65 73 63 72 69 |ng metho|d descri|
|00001100| 62 65 64 0a 09 09 62 79 | 20 45 2e 20 4f 2e 20 42 |bed...by| E. O. B|
|00001110| 72 69 67 68 61 6d 2e 20 | 20 46 6f 72 20 64 65 74 |righam. | For det|
|00001120| 61 69 6c 73 20 6f 66 20 | 74 68 65 20 6d 65 74 68 |ails of |the meth|
|00001130| 6f 64 2c 20 72 65 66 65 | 72 0a 09 09 74 6f 20 42 |od, refe|r...to B|
|00001140| 72 69 67 68 61 6d 27 73 | 20 62 6f 6f 6b 2e 20 54 |righam's| book. T|
|00001150| 48 45 20 46 41 53 54 20 | 46 4f 55 52 49 45 52 20 |HE FAST |FOURIER |
|00001160| 54 52 41 4e 53 46 4f 52 | 4d 22 3b 0a 4b 45 59 57 |TRANSFOR|M";.KEYW|
|00001170| 4f 52 44 53 3a 20 09 46 | 6f 75 72 69 65 72 2c 20 |ORDS: .F|ourier, |
|00001180| 74 72 61 6e 73 66 6f 72 | 6d 3b 0a 46 49 4c 45 4e |transfor|m;.FILEN|
|00001190| 41 4d 45 3a 09 46 46 54 | 2e 43 3b 0a 57 41 52 4e |AME:.FFT|.C;.WARN|
|000011a0| 49 4e 47 53 3a 0a 20 20 | 22 54 68 69 73 20 70 72 |INGS:.  |"This pr|
|000011b0| 6f 67 72 61 6d 20 69 73 | 20 73 65 6c 66 2d 63 6f |ogram is| self-co|
|000011c0| 6e 74 61 69 6e 65 64 2c | 20 61 6c 6c 20 74 68 61 |ntained,| all tha|
|000011d0| 74 20 69 73 20 6e 65 65 | 64 65 64 20 69 73 20 61 |t is nee|ded is a|
|000011e0| 20 6d 61 6e 6e 65 72 20 | 6f 66 20 67 65 74 74 69 | manner |of getti|
|000011f0| 6e 67 0a 20 20 74 68 65 | 20 64 61 74 61 20 69 6e |ng.  the| data in|
|00001200| 74 6f 20 74 68 65 20 61 | 72 72 61 79 20 72 65 61 |to the a|rray rea|
|00001210| 6c 5f 64 61 74 61 20 28 | 26 20 69 6d 61 67 5f 64 |l_data (|& imag_d|
|00001220| 61 74 61 2c 20 69 66 20 | 61 70 70 6c 69 63 61 62 |ata, if |applicab|
|00001230| 6c 65 29 2e 20 20 54 68 | 65 0a 20 20 74 72 61 6e |le).  Th|e.  tran|
|00001240| 73 66 6f 72 6d 65 64 20 | 64 61 74 61 20 77 69 6c |sformed |data wil|
|00001250| 6c 20 72 65 73 69 64 65 | 20 69 6e 20 74 68 65 73 |l reside| in thes|
|00001260| 65 20 74 77 6f 20 61 72 | 72 61 79 73 20 75 70 6f |e two ar|rays upo|
|00001270| 6e 20 72 65 74 75 72 6e | 20 77 69 74 68 20 74 68 |n return| with th|
|00001280| 65 0a 20 20 6f 72 69 67 | 69 6e 61 6c 20 64 61 74 |e.  orig|inal dat|
|00001290| 61 20 62 65 69 6e 67 20 | 64 65 73 74 72 6f 79 65 |a being |destroye|
|000012a0| 64 2e 22 0a 41 55 54 48 | 4f 52 53 3a 09 4a 69 6d |d.".AUTH|ORS:.Jim|
|000012b0| 20 50 69 73 61 6e 6f 3b | 0a 43 4f 4d 50 49 4c 45 | Pisano;|.COMPILE|
|000012c0| 52 53 3a 09 44 65 53 6d | 65 74 3b 0a 52 45 46 45 |RS:.DeSm|et;.REFE|
|000012d0| 52 45 4e 43 45 53 3a 09 | 41 55 54 48 4f 52 53 3a |RENCES:.|AUTHORS:|
|000012e0| 09 45 2e 20 4f 2e 20 42 | 72 69 67 68 61 6d 3b 0a |.E. O. B|righam;.|
|000012f0| 09 09 54 49 54 4c 45 3a | 09 09 22 54 48 45 20 46 |..TITLE:|.."THE F|
|00001300| 41 53 54 20 46 4f 55 52 | 49 45 52 20 54 52 41 4e |AST FOUR|IER TRAN|
|00001310| 53 46 4f 52 4d 22 3b 0a | 09 09 43 49 54 41 54 49 |SFORM";.|..CITATI|
|00001320| 4f 4e 3a 09 22 22 3b 0a | 09 45 4e 44 52 45 46 0a |ON:."";.|.ENDREF.|
|00001330| 2a 2f 0a 0a 2f 2a 09 66 | 69 6c 65 20 6e 61 6d 65 |*/../*.f|ile name|
|00001340| 20 66 66 74 2e 63 0a 2a | 09 70 72 6f 67 72 61 6d | fft.c.*|.program|
|00001350| 20 6e 61 6d 65 20 66 66 | 74 28 29 20 2e 2e 2e 20 | name ff|t() ... |
|00001360| 46 61 73 74 20 46 6f 75 | 72 69 65 72 20 54 72 61 |Fast Fou|rier Tra|
|00001370| 6e 73 66 6f 72 6d 0a 2a | 0a 2a 09 50 65 72 66 6f |nsform.*|.*.Perfo|
|00001380| 72 6d 20 66 61 73 74 20 | 66 6f 75 72 69 65 72 20 |rm fast |fourier |
|00001390| 74 72 61 6e 73 66 6f 72 | 6d 20 75 73 69 6e 67 20 |transfor|m using |
|000013a0| 6d 65 74 68 6f 64 20 64 | 65 73 63 72 69 62 65 64 |method d|escribed|
|000013b0| 20 62 79 20 45 2e 20 4f | 2e 20 42 72 69 67 68 61 | by E. O|. Brigha|
|000013c0| 6d 2e 0a 2a 20 20 46 6f | 72 20 64 65 74 61 69 6c |m..*  Fo|r detail|
|000013d0| 73 20 6f 66 20 74 68 65 | 20 6d 65 74 68 6f 64 2c |s of the| method,|
|000013e0| 20 72 65 66 65 72 20 74 | 6f 20 42 72 69 67 68 61 | refer t|o Brigha|
|000013f0| 6d 27 73 20 62 6f 6f 6b | 0a 2a 0a 2a 09 54 72 61 |m's book|.*.*.Tra|
|00001400| 6e 73 6c 61 74 65 64 20 | 74 6f 20 43 20 66 72 6f |nslated |to C fro|
|00001410| 6d 20 46 4f 52 54 52 41 | 4e 20 62 79 0a 2a 0a 2a |m FORTRA|N by.*.*|
|00001420| 09 09 4a 69 6d 20 50 69 | 73 61 6e 6f 0a 2a 09 09 |..Jim Pi|sano.*..|
|00001430| 50 2e 4f 2e 20 42 6f 78 | 20 33 31 33 34 0a 2a 09 |P.O. Box| 3134.*.|
|00001440| 09 55 6e 69 76 65 72 73 | 69 74 79 20 53 74 61 74 |.Univers|ity Stat|
|00001450| 69 6f 6e 0a 2a 09 09 43 | 68 61 72 6c 6f 74 74 65 |ion.*..C|harlotte|
|00001460| 73 76 69 6c 6c 65 2c 20 | 56 41 20 32 32 39 30 33 |sville, |VA 22903|
|00001470| 0a 2a 0a 2a 20 20 54 68 | 69 73 20 70 72 6f 67 72 |.*.*  Th|is progr|
|00001480| 61 6d 20 69 73 20 69 6e | 20 74 68 65 20 70 75 62 |am is in| the pub|
|00001490| 6c 69 63 20 64 6f 6d 61 | 69 6e 20 26 20 6d 61 79 |lic doma|in & may|
|000014a0| 20 62 65 20 75 73 65 64 | 20 62 79 20 61 6e 79 6f | be used| by anyo|
|000014b0| 6e 65 20 66 6f 72 20 63 | 6f 6d 6d 65 72 63 69 61 |ne for c|ommercia|
|000014c0| 6c 0a 2a 20 20 6f 72 20 | 6e 6f 6e 2d 63 6f 6d 6d |l.*  or |non-comm|
|000014d0| 65 72 63 69 61 6c 20 70 | 75 72 70 6f 73 65 73 2e |ercial p|urposes.|
|000014e0| 0a 2a 0a 2a 20 20 72 65 | 61 6c 5f 64 61 74 61 20 |.*.*  re|al_data |
|000014f0| 2e 2e 2e 20 70 74 72 2e | 20 74 6f 20 72 65 61 6c |... ptr.| to real|
|00001500| 20 70 61 72 74 20 6f 66 | 20 64 61 74 61 20 74 6f | part of| data to|
|00001510| 20 62 65 20 74 72 61 6e | 73 66 6f 72 6d 65 64 0a | be tran|sformed.|
|00001520| 2a 20 20 69 6d 61 67 5f | 64 61 74 61 20 2e 2e 2e |*  imag_|data ...|
|00001530| 20 70 74 72 2e 20 74 6f | 20 69 6d 61 67 20 20 22 | ptr. to| imag  "|
|00001540| 20 20 20 22 20 20 20 22 | 20 20 20 22 20 20 22 20 |   "   "|   "  " |
|00001550| 20 20 20 20 20 22 0a 2a | 20 20 69 6e 76 20 2e 2e |     ".*|  inv ..|
|00001560| 2e 2e 2e 20 53 77 69 74 | 63 68 20 74 6f 20 66 6c |... Swit|ch to fl|
|00001570| 61 67 20 6e 6f 72 6d 61 | 6c 20 6f 72 20 69 6e 76 |ag norma|l or inv|
|00001580| 65 72 73 65 20 74 72 61 | 6e 73 66 6f 72 6d 0a 2a |erse tra|nsform.*|
|00001590| 20 20 6e 5f 70 74 73 20 | 2e 2e 2e 20 4e 75 6d 62 |  n_pts |... Numb|
|000015a0| 65 72 20 6f 66 20 72 65 | 61 6c 20 64 61 74 61 20 |er of re|al data |
|000015b0| 70 6f 69 6e 74 73 0a 2a | 20 20 6e 75 20 2e 2e 2e |points.*|  nu ...|
|000015c0| 2e 2e 2e 20 6c 6f 67 61 | 72 69 74 68 6d 20 69 6e |... loga|rithm in|
|000015d0| 20 62 61 73 65 20 32 20 | 6f 66 20 6e 5f 70 74 73 | base 2 |of n_pts|
|000015e0| 20 65 2e 67 2e 20 6e 75 | 20 3d 20 35 20 69 66 20 | e.g. nu| = 5 if |
|000015f0| 6e 5f 70 74 73 20 3d 20 | 33 32 2e 0a 2a 0a 2a 20 |n_pts = |32..*.* |
|00001600| 20 54 68 69 73 20 70 72 | 6f 67 72 61 6d 20 69 73 | This pr|ogram is|
|00001610| 20 73 65 6c 66 2d 63 6f | 6e 74 61 69 6e 65 64 2c | self-co|ntained,|
|00001620| 20 61 6c 6c 20 74 68 61 | 74 20 69 73 20 6e 65 65 | all tha|t is nee|
|00001630| 64 65 64 20 69 73 20 61 | 20 6d 61 6e 6e 65 72 20 |ded is a| manner |
|00001640| 6f 66 20 67 65 74 74 69 | 6e 67 0a 2a 20 20 74 68 |of getti|ng.*  th|
|00001650| 65 20 64 61 74 61 20 69 | 6e 74 6f 20 74 68 65 20 |e data i|nto the |
|00001660| 61 72 72 61 79 20 72 65 | 61 6c 5f 64 61 74 61 20 |array re|al_data |
|00001670| 28 26 20 69 6d 61 67 5f | 64 61 74 61 2c 20 69 66 |(& imag_|data, if|
|00001680| 20 61 70 70 6c 69 63 61 | 62 6c 65 29 2e 20 20 54 | applica|ble).  T|
|00001690| 68 65 0a 2a 20 20 74 72 | 61 6e 73 66 6f 72 6d 65 |he.*  tr|ansforme|
|000016a0| 64 20 64 61 74 61 20 77 | 69 6c 6c 20 72 65 73 69 |d data w|ill resi|
|000016b0| 64 65 20 69 6e 20 74 68 | 65 73 65 20 74 77 6f 20 |de in th|ese two |
|000016c0| 61 72 72 61 79 73 20 75 | 70 6f 6e 20 72 65 74 75 |arrays u|pon retu|
|000016d0| 72 6e 20 77 69 74 68 20 | 74 68 65 0a 2a 20 20 6f |rn with |the.*  o|
|000016e0| 72 69 67 69 6e 61 6c 20 | 64 61 74 61 20 62 65 69 |riginal |data bei|
|000016f0| 6e 67 20 64 65 73 74 72 | 6f 79 65 64 2e 0a 2a 2f |ng destr|oyed..*/|
|00001700| 0a 0a 23 69 6e 63 6c 75 | 64 65 09 3c 73 74 64 69 |..#inclu|de.<stdi|
|00001710| 6f 2e 68 3e 0a 23 69 6e | 63 6c 75 64 65 09 3c 6d |o.h>.#in|clude.<m|
|00001720| 61 74 68 2e 68 3e 09 09 | 20 20 20 20 2f 2a 20 64 |ath.h>..|    /* d|
|00001730| 65 63 6c 61 72 65 20 6d | 61 74 68 20 66 75 6e 63 |eclare m|ath func|
|00001740| 74 69 6f 6e 73 20 74 6f | 20 75 73 65 20 2a 2f 0a |tions to| use */.|
|00001750| 23 64 65 66 69 6e 65 09 | 09 50 49 09 09 33 2e 31 |#define.|.PI..3.1|
|00001760| 34 31 39 35 32 37 0a 0a | 66 66 74 28 20 72 65 61 |419527..|fft( rea|
|00001770| 6c 5f 64 61 74 61 2c 20 | 69 6d 61 67 5f 64 61 74 |l_data, |imag_dat|
|00001780| 61 2c 20 6e 5f 70 74 73 | 2c 20 6e 75 2c 20 69 6e |a, n_pts|, nu, in|
|00001790| 76 20 29 0a 64 6f 75 62 | 6c 65 20 2a 72 65 61 6c |v ).doub|le *real|
|000017a0| 5f 64 61 74 61 2c 20 2a | 69 6d 61 67 5f 64 61 74 |_data, *|imag_dat|
|000017b0| 61 3b 0a 69 6e 74 20 6e | 5f 70 74 73 2c 20 6e 75 |a;.int n|_pts, nu|
|000017c0| 2c 20 69 6e 76 3b 0a 7b | 0a 09 69 6e 74 20 6e 32 |, inv;.{|..int n2|
|000017d0| 2c 20 6a 2c 20 6a 31 2c | 20 6c 2c 20 69 2c 20 69 |, j, j1,| l, i, i|
|000017e0| 62 2c 20 6b 2c 20 6b 31 | 2c 20 6b 32 3b 0a 09 69 |b, k, k1|, k2;..i|
|000017f0| 6e 74 20 73 67 6e 3b 0a | 09 64 6f 75 62 6c 65 20 |nt sgn;.|.double |
|00001800| 74 72 2c 20 74 69 2c 20 | 61 72 67 2c 20 6e 75 31 |tr, ti, |arg, nu1|
|00001810| 3b 09 2f 2a 20 69 6e 74 | 65 72 6d 65 64 69 61 74 |;./* int|ermediat|
|00001820| 65 20 76 61 6c 75 65 73 | 20 69 6e 20 63 61 6c 63 |e values| in calc|
|00001830| 73 2e 20 2a 2f 0a 09 64 | 6f 75 62 6c 65 20 63 2c |s. */..d|ouble c,|
|00001840| 20 73 3b 09 20 20 20 20 | 20 20 20 2f 2a 20 63 6f | s;.    |   /* co|
|00001850| 73 69 6e 65 20 26 20 73 | 69 6e 65 20 63 6f 6d 70 |sine & s|ine comp|
|00001860| 6f 6e 65 6e 74 73 20 6f | 66 20 46 6f 75 72 69 65 |onents o|f Fourie|
|00001870| 72 20 74 72 61 6e 73 2e | 20 2a 2f 0a 0a 09 6e 32 |r trans.| */...n2|
|00001880| 20 3d 20 6e 5f 70 74 73 | 20 2f 20 32 3b 0a 09 6e | = n_pts| / 2;..n|
|00001890| 75 31 20 3d 20 6e 75 20 | 2d 20 31 2e 30 3b 0a 09 |u1 = nu |- 1.0;..|
|000018a0| 6b 20 3d 20 30 3b 0a 2f | 2a 0a 2a 20 73 69 67 6e |k = 0;./|*.* sign|
|000018b0| 20 63 68 61 6e 67 65 20 | 66 6f 72 20 69 6e 76 65 | change |for inve|
|000018c0| 72 73 65 20 74 72 61 6e | 73 66 6f 72 6d 0a 2a 2f |rse tran|sform.*/|
|000018d0| 0a 09 73 67 6e 20 3d 20 | 69 6e 76 20 3f 20 2d 31 |..sgn = |inv ? -1|
|000018e0| 20 3a 20 31 3b 09 0a 2f | 2a 0a 2a 20 43 61 6c 63 | : 1;../|*.* Calc|
|000018f0| 75 6c 61 74 65 20 74 68 | 65 20 63 6f 6d 70 6f 6e |ulate th|e compon|
|00001900| 65 74 73 20 6f 66 20 74 | 68 65 20 46 6f 75 72 69 |ets of t|he Fouri|
|00001910| 65 72 20 73 65 72 69 65 | 73 20 6f 66 20 74 68 65 |er serie|s of the|
|00001920| 20 66 75 6e 63 74 69 6f | 6e 0a 2a 2f 0a 09 66 6f | functio|n.*/..fo|
|00001930| 72 28 20 6c 20 3d 20 30 | 3b 20 6c 20 21 3d 20 6e |r( l = 0|; l != n|
|00001940| 75 3b 20 6c 2b 2b 20 29 | 0a 09 7b 0a 09 09 64 6f |u; l++ )|..{...do|
|00001950| 0a 09 09 7b 0a 09 09 09 | 66 6f 72 28 20 69 20 3d |...{....|for( i =|
|00001960| 20 30 3b 20 69 20 21 3d | 20 6e 32 3b 20 69 2b 2b | 0; i !=| n2; i++|
|00001970| 20 29 0a 09 09 09 7b 0a | 09 09 09 09 6a 20 3d 20 | )....{.|....j = |
|00001980| 6b 20 2f 20 28 20 70 6f | 77 28 20 32 2e 30 2c 20 |k / ( po|w( 2.0, |
|00001990| 6e 75 31 20 29 20 29 3b | 0a 09 09 09 09 69 62 20 |nu1 ) );|.....ib |
|000019a0| 3d 20 62 69 74 5f 73 77 | 61 70 28 20 6a 2c 20 6e |= bit_sw|ap( j, n|
|000019b0| 75 20 29 3b 0a 09 09 09 | 09 61 72 67 20 3d 20 32 |u );....|.arg = 2|
|000019c0| 2e 30 20 2a 20 50 49 20 | 2a 20 69 62 20 2f 20 6e |.0 * PI |* ib / n|
|000019d0| 5f 70 74 73 3b 0a 09 09 | 09 09 63 20 3d 20 63 6f |_pts;...|..c = co|
|000019e0| 73 28 20 61 72 67 20 29 | 3b 0a 09 09 09 09 73 20 |s( arg )|;.....s |
|000019f0| 3d 20 73 67 6e 20 2a 20 | 73 69 6e 28 20 61 72 67 |= sgn * |sin( arg|
|00001a00| 20 29 3b 0a 09 09 09 09 | 6b 31 20 3d 20 6b 3b 0a | );.....|k1 = k;.|
|00001a10| 09 09 09 09 6b 32 20 3d | 20 6b 31 20 2b 20 6e 32 |....k2 =| k1 + n2|
|00001a20| 3b 0a 09 09 09 09 74 72 | 20 3d 20 2a 28 72 65 61 |;.....tr| = *(rea|
|00001a30| 6c 5f 64 61 74 61 2b 6b | 32 29 20 2a 20 63 20 2b |l_data+k|2) * c +|
|00001a40| 20 2a 28 69 6d 61 67 5f | 64 61 74 61 2b 6b 32 29 | *(imag_|data+k2)|
|00001a50| 20 2a 20 73 3b 0a 09 09 | 09 09 74 69 20 3d 20 2a | * s;...|..ti = *|
|00001a60| 28 69 6d 61 67 5f 64 61 | 74 61 2b 6b 32 29 20 2a |(imag_da|ta+k2) *|
|00001a70| 20 63 20 2d 20 2a 28 72 | 65 61 6c 5f 64 61 74 61 | c - *(r|eal_data|
|00001a80| 2b 6b 32 29 20 2a 20 73 | 3b 0a 09 09 09 09 2a 28 |+k2) * s|;.....*(|
|00001a90| 72 65 61 6c 5f 64 61 74 | 61 2b 6b 32 29 20 3d 20 |real_dat|a+k2) = |
|00001aa0| 2a 28 72 65 61 6c 5f 64 | 61 74 61 2b 6b 31 29 20 |*(real_d|ata+k1) |
|00001ab0| 2d 20 74 72 3b 0a 09 09 | 09 09 2a 28 69 6d 61 67 |- tr;...|..*(imag|
|00001ac0| 5f 64 61 74 61 2b 6b 32 | 29 20 3d 20 2a 28 69 6d |_data+k2|) = *(im|
|00001ad0| 61 67 5f 64 61 74 61 2b | 6b 31 29 20 2d 20 74 69 |ag_data+|k1) - ti|
|00001ae0| 3b 0a 09 09 09 09 2a 28 | 72 65 61 6c 5f 64 61 74 |;.....*(|real_dat|
|00001af0| 61 2b 6b 31 29 20 3d 20 | 2a 28 72 65 61 6c 5f 64 |a+k1) = |*(real_d|
|00001b00| 61 74 61 2b 6b 31 29 20 | 2b 20 74 72 3b 0a 09 09 |ata+k1) |+ tr;...|
|00001b10| 09 09 2a 28 69 6d 61 67 | 5f 64 61 74 61 2b 6b 31 |..*(imag|_data+k1|
|00001b20| 29 20 3d 20 2a 28 69 6d | 61 67 5f 64 61 74 61 2b |) = *(im|ag_data+|
|00001b30| 6b 31 29 20 2b 20 74 69 | 3b 0a 09 09 09 09 6b 2b |k1) + ti|;.....k+|
|00001b40| 2b 3b 0a 09 09 09 7d 0a | 09 09 09 6b 20 2b 3d 20 |+;....}.|...k += |
|00001b50| 20 6e 32 3b 0a 09 09 7d | 20 77 68 69 6c 65 28 20 | n2;...}| while( |
|00001b60| 6b 20 3c 20 6e 5f 70 74 | 73 20 2d 20 31 29 3b 0a |k < n_pt|s - 1);.|
|00001b70| 09 09 6b 20 3d 20 30 3b | 0a 09 09 6e 75 31 20 2d |..k = 0;|...nu1 -|
|00001b80| 3d 20 31 2e 30 3b 0a 09 | 09 6e 32 20 2f 3d 20 32 |= 1.0;..|.n2 /= 2|
|00001b90| 3b 0a 09 7d 0a 09 66 6f | 72 28 20 6b 20 3d 20 30 |;..}..fo|r( k = 0|
|00001ba0| 3b 20 6b 20 21 3d 20 6e | 5f 70 74 73 3b 20 6b 2b |; k != n|_pts; k+|
|00001bb0| 2b 20 29 0a 09 7b 0a 09 | 09 69 62 20 3d 20 62 69 |+ )..{..|.ib = bi|
|00001bc0| 74 5f 73 77 61 70 28 20 | 6b 2c 20 6e 75 20 29 3b |t_swap( |k, nu );|
|00001bd0| 0a 09 09 69 66 28 20 69 | 62 20 3e 20 6b 29 0a 09 |...if( i|b > k)..|
|00001be0| 09 7b 0a 09 09 09 73 77 | 61 70 28 20 28 72 65 61 |.{....sw|ap( (rea|
|00001bf0| 6c 5f 64 61 74 61 2b 6b | 29 2c 20 28 72 65 61 6c |l_data+k|), (real|
|00001c00| 5f 64 61 74 61 2b 69 62 | 29 20 29 3b 0a 09 09 09 |_data+ib|) );....|
|00001c10| 73 77 61 70 28 20 28 69 | 6d 61 67 5f 64 61 74 61 |swap( (i|mag_data|
|00001c20| 2b 6b 29 2c 20 28 69 6d | 61 67 5f 64 61 74 61 2b |+k), (im|ag_data+|
|00001c30| 69 62 29 20 29 3b 0a 09 | 09 7d 0a 09 7d 0a 2f 2a |ib) );..|.}..}./*|
|00001c40| 0a 2a 20 49 66 20 63 61 | 6c 63 75 6c 61 74 69 6e |.* If ca|lculatin|
|00001c50| 67 20 74 68 65 20 69 6e | 76 65 72 73 65 20 74 72 |g the in|verse tr|
|00001c60| 61 6e 73 66 6f 72 6d 2c | 20 6d 75 73 74 20 64 69 |ansform,| must di|
|00001c70| 76 69 64 65 20 74 68 65 | 20 64 61 74 61 20 62 79 |vide the| data by|
|00001c80| 20 74 68 65 20 6e 75 6d | 62 65 72 20 6f 66 0a 2a | the num|ber of.*|
|00001c90| 20 64 61 74 61 20 70 6f | 69 6e 74 73 2e 0a 2a 2f | data po|ints..*/|
|00001ca0| 0a 09 69 66 28 20 69 6e | 76 20 29 0a 09 09 66 6f |..if( in|v )...fo|
|00001cb0| 72 28 20 6b 20 3d 20 30 | 3b 20 6b 20 21 3d 20 6e |r( k = 0|; k != n|
|00001cc0| 5f 70 74 73 3b 20 6b 2b | 2b 29 0a 09 09 7b 0a 09 |_pts; k+|+)...{..|
|00001cd0| 09 09 2a 28 72 65 61 6c | 5f 64 61 74 61 2b 6b 29 |..*(real|_data+k)|
|00001ce0| 20 2f 3d 20 6e 5f 70 74 | 73 3b 0a 09 09 09 2a 28 | /= n_pt|s;....*(|
|00001cf0| 69 6d 61 67 5f 64 61 74 | 61 2b 6b 29 20 2f 3d 20 |imag_dat|a+k) /= |
|00001d00| 6e 5f 70 74 73 3b 0a 09 | 09 7d 0a 7d 0a 2f 2a 0a |n_pts;..|.}.}./*.|
|00001d10| 2a 20 42 69 74 20 73 77 | 61 70 69 6e 67 20 72 6f |* Bit sw|aping ro|
|00001d20| 75 74 69 6e 65 20 69 6e | 20 77 68 69 63 68 20 74 |utine in| which t|
|00001d30| 68 65 20 62 69 74 20 70 | 61 74 74 65 72 6e 20 6f |he bit p|attern o|
|00001d40| 66 20 74 68 65 20 69 6e | 74 65 67 65 72 20 69 20 |f the in|teger i |
|00001d50| 69 73 20 72 65 6f 72 64 | 65 72 65 64 2e 0a 2a 20 |is reord|ered..* |
|00001d60| 53 65 65 20 42 72 69 67 | 68 61 6d 27 73 20 62 6f |See Brig|ham's bo|
|00001d70| 6f 6b 20 66 6f 72 20 64 | 65 74 61 69 6c 73 0a 2a |ok for d|etails.*|
|00001d80| 2f 0a 62 69 74 5f 73 77 | 61 70 28 20 69 2c 20 6e |/.bit_sw|ap( i, n|
|00001d90| 75 20 29 0a 69 6e 74 20 | 69 2c 20 6e 75 3b 0a 7b |u ).int |i, nu;.{|
|00001da0| 0a 09 69 6e 74 20 69 62 | 2c 20 69 31 2c 20 69 32 |..int ib|, i1, i2|
|00001db0| 3b 0a 0a 09 69 62 20 3d | 20 30 3b 0a 0a 09 66 6f |;...ib =| 0;...fo|
|00001dc0| 72 28 20 69 31 20 3d 20 | 30 3b 20 69 31 20 21 3d |r( i1 = |0; i1 !=|
|00001dd0| 20 6e 75 3b 20 69 31 2b | 2b 20 29 0a 09 7b 0a 09 | nu; i1+|+ )..{..|
|00001de0| 09 69 32 20 20 3d 20 69 | 20 2f 20 32 3b 0a 09 09 |.i2  = i| / 2;...|
|00001df0| 69 62 20 3d 20 69 62 20 | 2a 20 32 20 2b 20 69 20 |ib = ib |* 2 + i |
|00001e00| 2d 20 32 20 2a 20 69 32 | 3b 0a 09 09 69 20 20 20 |- 2 * i2|;...i   |
|00001e10| 3d 20 69 32 3b 0a 09 7d | 0a 09 72 65 74 75 72 6e |= i2;..}|..return|
|00001e20| 28 20 69 62 20 29 3b 0a | 7d 0a 2f 2a 0a 2a 20 53 |( ib );.|}./*.* S|
|00001e30| 69 6d 70 6c 65 20 65 78 | 63 68 61 6e 67 65 20 72 |imple ex|change r|
|00001e40| 6f 75 74 69 6e 65 20 77 | 68 65 72 65 20 2a 78 31 |outine w|here *x1|
|00001e50| 20 26 20 2a 78 32 20 61 | 72 65 20 73 77 61 70 70 | & *x2 a|re swapp|
|00001e60| 65 64 0a 2a 2f 0a 73 77 | 61 70 28 20 78 31 2c 20 |ed.*/.sw|ap( x1, |
|00001e70| 78 32 20 29 0a 64 6f 75 | 62 6c 65 20 2a 78 31 2c |x2 ).dou|ble *x1,|
|00001e80| 20 2a 78 32 3b 0a 7b 0a | 09 69 6e 74 20 2a 74 65 | *x2;.{.|.int *te|
|00001e90| 6d 70 5f 69 79 3b 0a 09 | 64 6f 75 62 6c 65 20 2a |mp_iy;..|double *|
|00001ea0| 74 65 6d 70 5f 78 3b 0a | 0a 09 2a 74 65 6d 70 5f |temp_x;.|..*temp_|
|00001eb0| 78 20 3d 20 2a 78 31 3b | 0a 09 2a 78 31 20 3d 20 |x = *x1;|..*x1 = |
|00001ec0| 2a 78 32 3b 0a 09 2a 78 | 32 20 3d 20 2a 74 65 6d |*x2;..*x|2 = *tem|
|00001ed0| 70 5f 78 3b 0a 7d 0a 53 | 48 41 52 5f 45 4f 46 0a |p_x;.}.S|HAR_EOF.|
|00001ee0| 66 69 20 23 20 65 6e 64 | 20 6f 66 20 6f 76 65 72 |fi # end| of over|
|00001ef0| 77 72 69 74 69 6e 67 20 | 63 68 65 63 6b 0a 23 09 |writing |check.#.|
|00001f00| 45 6e 64 20 6f 66 20 73 | 68 65 6c 6c 20 61 72 63 |End of s|hell arc|
|00001f10| 68 69 76 65 0a 65 78 69 | 74 20 30 0a 2d 2d 20 0a |hive.exi|t 0.-- .|
|00001f20| 4d 69 6b 65 20 53 74 75 | 6d 70 2c 20 43 61 6c 20 |Mike Stu|mp, Cal |
|00001f30| 53 74 61 74 65 20 55 6e | 69 76 2c 20 4e 6f 72 74 |State Un|iv, Nort|
|00001f40| 68 72 69 64 67 65 20 43 | 6f 6d 70 20 53 63 69 20 |hridge C|omp Sci |
|00001f50| 44 65 70 61 72 74 6d 65 | 6e 74 0a 75 75 63 70 3a |Departme|nt.uucp:|
|00001f60| 20 7b 73 64 63 72 64 63 | 66 2c 20 69 68 6e 70 34 | {sdcrdc|f, ihnp4|
|00001f70| 2c 20 68 70 6c 61 62 73 | 2c 20 74 74 69 64 63 61 |, hplabs|, ttidca|
|00001f80| 2c 20 70 73 69 76 61 78 | 2c 20 63 73 75 73 74 61 |, psivax|, csusta|
|00001f90| 6e 7d 21 63 73 75 6e 21 | 61 65 75 73 65 6d 72 73 |n}!csun!|aeusemrs|
|00001fa0| 0a                      |                         |.       |        |
+--------+-------------------------+-------------------------+--------+--------+