/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / comp / lang / function / 1025

< prev

next >

MacOS 8.1

Win98

DOS

browse contents

view JSON data

view as text

+--------+-------------------------+-------------------------+--------+--------+
|00000000| 4e 65 77 73 67 72 6f 75 | 70 73 3a 20 63 6f 6d 70 |Newsgrou|ps: comp|
|00000010| 2e 6c 61 6e 67 2e 66 75 | 6e 63 74 69 6f 6e 61 6c |.lang.fu|nctional|
|00000020| 0a 50 61 74 68 3a 20 73 | 70 61 72 6b 79 21 75 75 |.Path: s|parky!uu|
|00000030| 6e 65 74 21 6d 63 73 75 | 6e 21 73 75 6e 34 6e 6c |net!mcsu|n!sun4nl|
|00000040| 21 66 77 69 2e 75 76 61 | 2e 6e 6c 21 70 69 65 74 |!fwi.uva|.nl!piet|
|00000050| 65 72 0a 46 72 6f 6d 3a | 20 70 69 65 74 65 72 40 |er.From:| pieter@|
|00000060| 66 77 69 2e 75 76 61 2e | 6e 6c 20 28 50 69 65 74 |fwi.uva.|nl (Piet|
|00000070| 65 72 20 48 2e 20 48 61 | 72 74 65 6c 29 0a 53 75 |er H. Ha|rtel).Su|
|00000080| 62 6a 65 63 74 3a 20 52 | 65 3a 20 46 46 54 73 20 |bject: R|e: FFTs |
|00000090| 69 6e 20 4d 69 72 61 6e | 64 61 0a 4d 65 73 73 61 |in Miran|da.Messa|
|000000a0| 67 65 2d 49 44 3a 20 3c | 31 39 39 32 41 75 67 32 |ge-ID: <|1992Aug2|
|000000b0| 31 2e 30 37 34 33 33 32 | 2e 36 33 30 33 40 66 77 |1.074332|.6303@fw|
|000000c0| 69 2e 75 76 61 2e 6e 6c | 3e 0a 53 65 6e 64 65 72 |i.uva.nl|>.Sender|
|000000d0| 3a 20 6e 65 77 73 40 66 | 77 69 2e 75 76 61 2e 6e |: news@f|wi.uva.n|
|000000e0| 6c 0a 4e 6e 74 70 2d 50 | 6f 73 74 69 6e 67 2d 48 |l.Nntp-P|osting-H|
|000000f0| 6f 73 74 3a 20 63 61 72 | 6f 6c 2e 66 77 69 2e 75 |ost: car|ol.fwi.u|
|00000100| 76 61 2e 6e 6c 0a 4f 72 | 67 61 6e 69 7a 61 74 69 |va.nl.Or|ganizati|
|00000110| 6f 6e 3a 20 46 57 49 2c | 20 55 6e 69 76 65 72 73 |on: FWI,| Univers|
|00000120| 69 74 79 20 6f 66 20 41 | 6d 73 74 65 72 64 61 6d |ity of A|msterdam|
|00000130| 0a 52 65 66 65 72 65 6e | 63 65 73 3a 20 3c 66 61 |.Referen|ces: <fa|
|00000140| 72 72 65 6c 6c 2e 37 31 | 34 32 30 30 39 38 39 40 |rrell.71|4200989@|
|00000150| 63 6f 72 61 6c 2e 63 73 | 2e 6a 63 75 2e 65 64 75 |coral.cs|.jcu.edu|
|00000160| 2e 61 75 3e 20 3c 31 39 | 39 32 41 75 67 32 30 2e |.au> <19|92Aug20.|
|00000170| 30 37 33 36 32 39 2e 31 | 30 39 33 36 40 63 61 6e |073629.1|0936@can|
|00000180| 6f 6e 2e 63 6f 2e 75 6b | 3e 0a 44 61 74 65 3a 20 |on.co.uk|>.Date: |
|00000190| 46 72 69 2c 20 32 31 20 | 41 75 67 20 31 39 39 32 |Fri, 21 |Aug 1992|
|000001a0| 20 30 37 3a 34 33 3a 33 | 32 20 47 4d 54 0a 4c 69 | 07:43:3|2 GMT.Li|
|000001b0| 6e 65 73 3a 20 32 39 0a | 0a 41 74 20 74 68 65 20 |nes: 29.|.At the |
|000001c0| 6c 61 73 74 20 41 54 41 | 42 4c 45 2d 39 32 20 77 |last ATA|BLE-92 w|
|000001d0| 6f 72 6b 73 68 6f 70 20 | 69 6e 20 4d 6f 6e 74 72 |orkshop |in Montr|
|000001e0| 65 61 6c 20 77 65 20 70 | 72 65 73 65 6e 74 65 64 |eal we p|resented|
|000001f0| 20 61 20 70 61 70 65 72 | 0a 64 69 73 63 75 73 73 | a paper|.discuss|
|00000200| 69 6e 67 20 74 68 65 20 | 46 46 54 20 69 6e 20 4d |ing the |FFT in M|
|00000210| 69 72 61 6e 64 61 2e 20 | 54 68 65 20 70 72 6f 63 |iranda. |The proc|
|00000220| 65 65 64 69 6e 67 73 20 | 61 72 65 20 6e 6f 74 20 |eedings |are not |
|00000230| 6f 75 74 20 79 65 74 2c | 20 62 75 74 20 49 0a 63 |out yet,| but I.c|
|00000240| 61 6e 20 73 65 6e 64 20 | 6f 75 74 20 63 6f 70 69 |an send |out copi|
|00000250| 65 73 20 6f 66 20 61 20 | 74 65 63 68 6e 69 63 61 |es of a |technica|
|00000260| 6c 20 72 65 70 6f 72 74 | 20 74 6f 20 74 68 6f 73 |l report| to thos|
|00000270| 65 20 69 6e 74 65 72 65 | 73 74 65 64 3a 0a 0a 5c |e intere|sted:..\|
|00000280| 74 69 74 6c 65 7b 20 41 | 72 72 61 79 73 20 69 6e |title{ A|rrays in|
|00000290| 20 61 20 4c 61 7a 79 20 | 46 75 6e 63 74 69 6f 6e | a Lazy |Function|
|000002a0| 61 6c 20 4c 61 6e 67 75 | 61 67 65 20 2d 2d 20 5c |al Langu|age -- \|
|000002b0| 5c 0a 20 20 20 20 20 20 | 20 20 61 20 63 61 73 65 |\.      |  a case|
|000002c0| 20 73 74 75 64 79 3a 20 | 74 68 65 20 46 61 73 74 | study: |the Fast|
|000002d0| 20 46 6f 75 72 69 65 72 | 20 54 72 61 6e 73 66 6f | Fourier| Transfo|
|000002e0| 72 6d 7d 0a 0a 5c 61 75 | 74 68 6f 72 7b 50 69 65 |rm}..\au|thor{Pie|
|000002f0| 74 65 72 20 48 2e 20 48 | 61 72 74 65 6c 20 61 6e |ter H. H|artel an|
|00000300| 64 20 57 69 6c 6c 65 6d | 20 47 2e 20 56 72 65 65 |d Willem| G. Vree|
|00000310| 20 5c 5c 0a 20 20 20 20 | 20 20 20 20 44 65 70 61 | \\.    |    Depa|
|00000320| 72 74 6d 65 6e 74 20 6f | 66 20 43 6f 6d 70 75 74 |rtment o|f Comput|
|00000330| 65 72 20 53 79 73 74 65 | 6d 73 20 5c 5c 0a 20 20 |er Syste|ms \\.  |
|00000340| 20 20 20 20 20 20 55 6e | 69 76 65 72 73 69 74 79 |      Un|iversity|
|00000350| 20 6f 66 20 41 6d 73 74 | 65 72 64 61 6d 20 5c 5c | of Amst|erdam \\|
|00000360| 0a 20 20 20 20 20 20 20 | 20 4b 72 75 69 73 6c 61 |.       | Kruisla|
|00000370| 61 6e 20 34 30 33 2c 20 | 31 30 39 38 20 53 4a 20 |an 403, |1098 SJ |
|00000380| 41 6d 73 74 65 72 64 61 | 6d 2c 20 54 68 65 20 4e |Amsterda|m, The N|
|00000390| 65 74 68 65 72 6c 61 6e | 64 73 7d 0a 0a 5c 62 65 |etherlan|ds}..\be|
|000003a0| 67 69 6e 7b 61 62 73 74 | 72 61 63 74 7d 0a 54 68 |gin{abst|ract}.Th|
|000003b0| 65 20 61 72 72 61 79 20 | 70 6c 61 79 73 20 61 20 |e array |plays a |
|000003c0| 70 72 6f 6d 69 6e 65 6e | 74 20 72 6f 6c 65 20 69 |prominen|t role i|
|000003d0| 6e 20 69 6d 70 65 72 61 | 74 69 76 65 20 70 72 6f |n impera|tive pro|
|000003e0| 67 72 61 6d 6d 69 6e 67 | 20 6c 61 6e 67 75 61 67 |gramming| languag|
|000003f0| 65 73 0a 62 65 63 61 75 | 73 65 20 74 68 65 20 64 |es.becau|se the d|
|00000400| 61 74 61 20 73 74 72 75 | 63 74 75 72 65 20 62 65 |ata stru|cture be|
|00000410| 61 72 73 20 61 20 63 6c | 6f 73 65 20 72 65 73 65 |ars a cl|ose rese|
|00000420| 6d 62 6c 61 6e 63 65 20 | 74 6f 20 74 68 65 0a 6d |mblance |to the.m|
|00000430| 61 74 68 65 6d 61 74 69 | 63 61 6c 20 6e 6f 74 69 |athemati|cal noti|
|00000440| 6f 6e 20 6f 66 20 61 20 | 76 65 63 74 6f 72 20 61 |on of a |vector a|
|00000450| 6e 64 20 62 65 63 61 75 | 73 65 20 61 72 72 61 79 |nd becau|se array|
|00000460| 20 6f 70 65 72 61 74 69 | 6f 6e 73 20 63 61 6e 20 | operati|ons can |
|00000470| 62 65 0a 69 6d 70 6c 65 | 6d 65 6e 74 65 64 20 65 |be.imple|mented e|
|00000480| 66 66 69 63 69 65 6e 74 | 6c 79 2e 20 4e 6f 74 20 |fficient|ly. Not |
|00000490| 61 6c 6c 20 6c 61 7a 79 | 20 66 75 6e 63 74 69 6f |all lazy| functio|
|000004a0| 6e 61 6c 20 6c 61 6e 67 | 75 61 67 65 73 20 6f 66 |nal lang|uages of|
|000004b0| 66 65 72 20 61 72 72 61 | 79 73 0a 61 73 20 61 20 |fer arra|ys.as a |
|000004c0| 70 72 69 6d 69 74 69 76 | 65 20 64 61 74 61 20 73 |primitiv|e data s|
|000004d0| 74 72 75 63 74 75 72 65 | 20 62 65 63 61 75 73 65 |tructure| because|
|000004e0| 20 6c 61 7a 69 6e 65 73 | 73 20 6d 61 6b 65 73 20 | lazines|s makes |
|000004f0| 69 74 20 64 69 66 66 69 | 63 75 6c 74 20 74 6f 0a |it diffi|cult to.|
|00000500| 69 6d 70 6c 65 6d 65 6e | 74 20 61 72 72 61 79 73 |implemen|t arrays|
|00000510| 20 65 66 66 69 63 69 65 | 6e 74 6c 79 2e 20 57 65 | efficie|ntly. We|
|00000520| 20 73 74 75 64 79 20 38 | 20 64 69 66 66 65 72 65 | study 8| differe|
|00000530| 6e 74 20 76 65 72 73 69 | 6f 6e 73 20 6f 66 20 74 |nt versi|ons of t|
|00000540| 68 65 20 46 61 73 74 0a | 46 6f 75 72 69 65 72 20 |he Fast.|Fourier |
|00000550| 54 72 61 6e 73 66 6f 72 | 6d 2c 20 77 69 74 68 20 |Transfor|m, with |
|00000560| 61 6e 64 20 77 69 74 68 | 6f 75 74 20 61 72 72 61 |and with|out arra|
|00000570| 79 73 2c 20 74 6f 20 61 | 73 73 65 73 73 20 74 68 |ys, to a|ssess th|
|00000580| 65 20 69 6d 70 6f 72 74 | 61 6e 63 65 20 6f 66 0a |e import|ance of.|
|00000590| 61 72 72 61 79 73 20 69 | 6e 20 61 20 6c 61 7a 79 |arrays i|n a lazy|
|000005a0| 20 66 75 6e 63 74 69 6f | 6e 61 6c 20 6c 61 6e 67 | functio|nal lang|
|000005b0| 75 61 67 65 2e 0a 0a 41 | 6e 20 65 66 66 69 63 69 |uage...A|n effici|
|000005c0| 65 6e 74 20 69 6d 70 6c | 65 6d 65 6e 74 61 74 69 |ent impl|ementati|
|000005d0| 6f 6e 20 6f 66 20 61 72 | 72 61 79 73 20 63 6f 6e |on of ar|rays con|
|000005e0| 74 72 69 62 75 74 65 73 | 20 73 69 67 6e 69 66 69 |tributes| signifi|
|000005f0| 63 61 6e 74 6c 79 20 74 | 6f 20 74 68 65 0a 70 65 |cantly t|o the.pe|
|00000600| 72 66 6f 72 6d 61 6e 63 | 65 20 6f 66 20 66 75 6e |rformanc|e of fun|
|00000610| 63 74 69 6f 6e 61 6c 20 | 6c 61 6e 67 75 61 67 65 |ctional |language|
|00000620| 73 20 69 6e 20 63 65 72 | 74 61 69 6e 20 61 72 65 |s in cer|tain are|
|00000630| 61 73 2e 20 48 6f 77 65 | 76 65 72 2c 20 61 20 63 |as. Howe|ver, a c|
|00000640| 6c 65 61 72 0a 64 69 73 | 74 69 6e 63 74 69 6f 6e |lear.dis|tinction|
|00000650| 20 73 68 6f 75 6c 64 20 | 62 65 20 6d 61 64 65 20 | should |be made |
|00000660| 62 65 74 77 65 65 6e 20 | 61 72 72 61 79 20 63 6f |between |array co|
|00000670| 6e 73 74 72 75 63 74 69 | 6f 6e 20 61 6e 64 20 61 |nstructi|on and a|
|00000680| 72 72 61 79 0a 73 75 62 | 73 63 72 69 70 74 69 6f |rray.sub|scriptio|
|00000690| 6e 2e 20 20 49 6e 20 74 | 68 65 20 46 46 54 20 65 |n.  In t|he FFT e|
|000006a0| 78 61 6d 70 6c 65 20 77 | 65 20 63 6f 75 6c 64 20 |xample w|e could |
|000006b0| 6e 6f 74 20 67 61 69 6e | 20 65 66 66 69 63 69 65 |not gain| efficie|
|000006c0| 6e 63 79 20 62 79 20 75 | 73 69 6e 67 0a 61 72 72 |ncy by u|sing.arr|
|000006d0| 61 79 20 63 6f 6e 73 74 | 72 75 63 74 69 6f 6e 2c |ay const|ruction,|
|000006e0| 20 6f 74 68 65 72 20 74 | 68 61 6e 20 66 6f 72 20 | other t|han for |
|000006f0| 73 74 6f 72 69 6e 67 20 | 70 72 65 63 6f 6d 70 75 |storing |precompu|
|00000700| 74 65 64 20 64 61 74 61 | 20 6c 69 6b 65 20 74 68 |ted data| like th|
|00000710| 65 0a 69 6e 70 75 74 2e | 20 55 73 69 6e 67 20 61 |e.input.| Using a|
|00000720| 72 72 61 79 20 73 75 62 | 73 63 72 69 70 74 69 6f |rray sub|scriptio|
|00000730| 6e 20 69 6d 70 72 6f 76 | 65 73 20 70 65 72 66 6f |n improv|es perfo|
|00000740| 72 6d 61 6e 63 65 2e 0a | 5c 65 6e 64 7b 61 62 73 |rmance..|\end{abs|
|00000750| 74 72 61 63 74 7d 0a    |                         |tract}. |        |
+--------+-------------------------+-------------------------+--------+--------+