[ Pobierz całość w formacie PDF ]
Algorithmsforprogrammers
ideasandsourcecode
Thisdocumentisworkinprogress:readthe”importantremarks”nearthebeginning
J¨orgArndt
arndt@jjj.de
Thisdocument
1
wasL
A
T
E
X’datSeptember26,2002
1
Thisdocumentisonlineat
http://www.jjj.de/fxt/
. Itwillstayavailableonlineforfree.
Contents
Someimportantremarksaboutthisdocument 6
Listofimportantsymbols
7
1TheFouriertransform 8
1.1ThediscreteFouriertransform................................. 8
1.2SymmetriesoftheFouriertransform.............................. 9
1.3Radix2FFTalgorithms..................................... 10
1.3.1Alittlebitofnotation.................................. 10
1.3.2Decimationintime(DIT)FFT............................. 10
1.3.3Decimationinfrequency(DIF)FFT.......................... 13
1.4Savingtrigonometriccomputations............................... 15
1.4.1Usinglookuptables ................................... 16
1.4.2Recursivegenerationofthe
sin=cos
-values....................... 16
1.4.3Usinghigherradixalgorithms.............................. 17
1.5HigherradixDITandDIFalgorithms............................. 17
1.5.1Morenotation...................................... 17
1.5.2Decimationintime.................................... 17
1.5.3Decimationinfrequency................................. 18
1.5.4 Implementationofradix
r
=
p
x
DIF/DITFFTs.................... 19
1.6SplitradixFouriertransforms(SRFT)............................. 22
1.7InverseFFTforfree....................................... 23
1.8RealvaluedFouriertransforms................................. 24
1.8.1RealvaluedFTviawrapperroutines.......................... 25
1.8.2RealvaluedsplitradixFouriertransforms....................... 27
1.9MultidimensionalFTs...................................... 31
1.9.1Definition......................................... 31
1.9.2Therowcolumnalgorithm............................... 31
1.10ThematrixFourieralgorithm(MFA).............................. 32
1.11AutomaticgenerationofFFTcodes .............................. 33
1
CONTENTS
2
2Convolutions 36
2.1DefinitionandcomputationviaFFT.............................. 36
2.2MassstorageconvolutionusingtheMFA............................ 40
2.3WeightedFouriertransforms .................................. 42
2.4Halfcyclicconvolutionforhalftheprice?........................... 44
2.5ConvolutionusingtheMFA................................... 44
2.5.1Thecase
R
=2...................................... 45
2.5.2Thecase
R
=3...................................... 45
2.6ConvolutionofrealvalueddatausingtheMFA........................ 46
2.7ConvolutionwithouttranspositionusingtheMFA...................... 46
2.8Thez-transform(ZT) ...................................... 47
2.8.1DefinitionoftheZT................................... 47
2.8.2ComputationoftheZTviaconvolution........................ 48
2.8.3ArbitrarylengthFFTbyZT.............................. 48
2.8.4FractionalFouriertransformbyZT........................... 48
3TheHartleytransform(HT) 49
3.1DefinitionoftheHT....................................... 49
3.2radix2FHTalgorithms..................................... 49
3.2.1Decimationintime(DIT)FHT............................. 49
3.2.2Decimationinfrequency(DIF)FHT.......................... 52
3.3ComplexFTbyHT....................................... 55
3.4ComplexFTbycomplexHTandviceversa.......................... 56
3.5RealFTbyHTandviceversa................................. 57
3.6Discretecosinetransform(DCT)byHT............................ 58
3.7Discretesinetransform(DST)byDCT............................ 59
3.8ConvolutionviaFHT....................................... 60
3.9NegacyclicconvolutionviaFHT................................. 62
4Numbertheoretictransforms(NTTs) 63
4.1Primemodulus:Z
=p
Z=F
p
................................... 63
4.2Compositemodulus:Z
=m
Z ................................... 64
4.3PseudocodeforNTTs...................................... 67
4.3.1Radix2DITNTT.................................... 67
4.3.2Radix2DIFNTT.................................... 68
4.4ConvolutionwithNTTs..................................... 69
4.5TheChineseRemainderTheorem(CRT)............................ 69
4.6Amodularmultiplicationtechnique............................... 71
4.7NumbertheoreticHartleytransform............................... 72
5Walshtransforms
73
CONTENTS
3
5.1BasisfunctionsoftheWalshtransforms............................ 77
5.2Dyadicconvolution........................................ 78
5.3Theslanttransform....................................... 80
6TheHaartransform 82
6.1InplaceHaartransform..................................... 83
6.2IntegertointegerHaartransform................................ 86
7Somebitwizardry 88
7.1Trivia............................................... 88
7.2Operationsonlowbits/blocksinaword............................ 89
7.3Operationsonhighbits/blocksinaword........................... 91
7.4Functionsrelatedtothebase-2logarithm........................... 94
7.5Countingthebitsinaword................................... 95
7.6Swappingbits/blocksofaword................................. 96
7.7Reversingthebitsofaword................................... 98
7.8Generatingbitcombinations................................... 99
7.9Generatingbitsubsets......................................101
7.10Bitsetlookup...........................................101
7.11TheGraycodeofaword....................................102
7.12Generatingminimal-changebitcombinations .........................104
7.13Bitwiserotationofaword....................................106
7.14Bitwisezip............................................108
7.15Bitsequency...........................................109
7.16Misc................................................110
7.17Thebitarrayclass ........................................112
7.18Manipulationofcolors......................................113
8Permutations 115
8.1Therevbinpermutation.....................................115
8.1.1Anaiveversion......................................115
8.1.2Afastversion.......................................116
8.1.3Howmanyswaps?....................................116
8.1.4Astillfasterversion...................................117
8.1.5Therealworldversion..................................119
8.2Theradixpermutation......................................120
8.3Inplacematrixtransposition...................................121
8.4Revbinpermutationvs.transposition.............................122
8.4.1Rotateandreverse....................................122
8.4.2Zipandunzip.......................................123
8.5TheGraycodepermutation...................................124
CONTENTS
4
8.6Generalpermutations ......................................127
8.6.1Basicdefinitions.....................................127
8.6.2Compositionsofpermutations..............................128
8.6.3Applyingpermutationstodata.............................131
8.7GeneratingallPermutations...................................132
8.7.1Lexicographicorder ...................................132
8.7.2Minimal-changeorder..................................134
8.7.3Derangementorder....................................136
8.7.4Star-transpositionorder.................................137
8.7.5Yetanotherorder ....................................138
9Sortingandsearching 140
9.1Sorting...............................................140
9.2Searching.............................................142
9.3Indexsorting...........................................143
9.4Pointersorting..........................................144
9.5Sortingbyasuppliedcomparisonfunction...........................145
9.6Unique...............................................146
9.7Misc................................................148
10Selectedcombinatoricalalgorithms 152
10.1O²inefunctions:funcemu....................................152
10.2Combinationsinlexicographicorder..............................155
10.3Combinationsinco-lexicographicorder.............................157
10.4Combinationsinminimal-changeorder.............................158
10.5Combinationsinalternativeminimal-changeorder ......................160
10.6Subsetsinlexicographicorder..................................161
10.7Subsetsinminimal-changeorder................................163
10.8Subsetsorderedbynumberofelements.............................165
10.9Subsetsorderedwithshiftregistersequences .........................166
10.10Partitions.............................................167
11Arithmeticalalgorithms 170
11.1Asymptoticsofalgorithms....................................170
11.2Multiplicationoflargenumbers.................................170
11.2.1TheKaratsubaalgorithm................................171
11.2.2FastmultiplicationviaFFT...............................171
11.2.3Radix/precisionconsiderationswithFFTmultiplication...............173
11.3Division,squarerootandcuberoot...............................174
11.3.1Division..........................................174
11.3.2Squarerootextraction..................................175
[ Pobierz całość w formacie PDF ]