So far in this series, we’ve been looking at code piecemeal, writing little test modules to explore the algorithms we’ve been developing. Before we start trying to optimise this code, it makes sense to put it into a Cabal package with a more organised module structure, to provide a sensible API and to make a few other small changes.
From now on, the code we’re going to be talking about will be the arb-fft package, which is hosted on GitHub. In this article, we’ll be talking about the version of the code tagged pre-release-1. (We’ll be uploading a version of the code to Hackage once it’s ready, but there will be a few pre-release versions that we’ll look at before we get to that point.)
“Cabalisation” and module structure
Setting up a new package with Cabal, Haskell’s package and build manager, is pretty easy: go to an empty directory, type cabal
init and answer some questions about your project–the project name, a one-line synopsis of what it does, author details, license details and a couple of other things. Cabal generates an initial Cabal package description file to which you add the details of libraries, executables, test suites and so on. Here’s the Cabal file for the arb-fft package.
name: arb-fft
version: 0.1.0.0
synopsis: Pure Haskell arbitrary length FFT library
homepage: https://github.com/ian-ross/arb-fft
license: GPL-3
license-file: LICENSE
maintainer: ian@skybluetrades.net
copyright: Copyright (2013) Ian Ross
category: Math
build-type: Simple
extra-source-files: README.md
cabal-version: >=1.10
Library
exposed-modules: Numeric.FFT
other-modules: Numeric.FFT.Plan
Numeric.FFT.Execute
Numeric.FFT.Special
Numeric.FFT.Types
Numeric.FFT.Utils
ghc-options: -O2
build-depends: base >= 4.6 && < 5,
containers >= 0.5.0.0 && < 0.6,
vector >= 0.10.9.1 && < 0.11
default-language: Haskell2010
Test-Suite basic-test
type: exitcode-stdio-1.0
hs-source-dirs: test
main-is: basic-test.hs
build-depends: arb-fft,
base >= 4.6 && < 5,
containers >= 0.5.0.0 && < 0.6,
vector >= 0.10.9.1 && < 0.11,
QuickCheck >= 2.6 && < 2.7,
tasty >= 0.3,
tasty-quickcheck >= 0.3
default-language: Haskell2010We define a single library and one test suite. The modules in the library are:
Numeric.FFT: The main “exposed” module implementing the public API. Exports functions for performing FFT and inverse FFT transforms, along with re-exporting some data types and additional API from a couple of the hidden modules.
`Numeric.FFT.Plan: Functions for pre-planning of FFT calculations.
Numeric.FFT.Execute: Functions to execute pre-planned FFTs.
Numeric.FFT.Types: Type definitions, the most important of which are Plan and BaseTransform.
Numeric.FFT.Utils: Utility functions, including prime factorisation, primitive root calculation for $\mathbb{Z}_p^{\times}$ and some other small things.
Numeric.FFT.Special: Base transform implementations specialised to small fixed input lengths.
Code changes for packaging
Pre-planning
The plan function in the Numeric.FFT.Plan module (also re-exported from Numeric.FFT) takes a problem size as input and returns a value of the Plan abstract data type that includes all of the information required to execute an FFT that can be calculated in advance: input vector permutation, size and factor information for the Danielson-Lanczos steps used to build up the final results, powers of $\omega_N$ for all the $N$ values required, and a “base transform” used at the “bottom” of the Cooley-Tukey decomposition, which is either a reference to a specialised hard-coded transform for small input lengths (defined in Numeric.FFT.Special), or (for prime lengths) all the information needed to perform a prime-length transform using Rader’s algorithm, or (for any other lengths) an indicator that a simple DFT should be used for the base transform.
At the current stage of development of the code, this pre-planning is relatively lightweight, since we always use the same prime factor decomposition of the input size. Later on, we’ll add some benchmarking code to the planner to select the best decomposition of the input size from a list of likely good plans.
The plans generated by the plan function are executed by code in the Numeric.FFT.Execute module. This is where most of the work is done, and is where we’ll be concentrating our optimisation effort. As well as the main Cooley-Tukey driver function (execute) and a function to perform a single Danielson-Lanczos step, this module also has code to apply the relevant “base transforms”.
Special base transforms
Up to now, we’ve been using a simple DFT for the small prime-length factors at the “bottom” of the FFT decomposition. For arbitrary prime lengths, we can use Rader’s algorithm, but this will be much less efficient than a “straight-line” hand-coded transform. The idea here is that for small input lengths that occur at the “bottom” of many transform decompositions, we can write optimal or near-optimal hand-coded transforms once and for all.
Here such a specialised base transform for input vectors of length 5:
-- | Length 5 hard-coded FFT.
kp951056516, kp559016994, kp250000000, kp618033988 :: Double
kp951056516 = 0.951056516295153572116439333379382143405698634
kp559016994 = 0.559016994374947424102293417182819058860154590
kp250000000 = 0.250000000000000000000000000000000000000000000
kp618033988 = 0.618033988749894848204586834365638117720309180
special5 :: Int -> VCD -> VCD
special5 sign xs =
let ar:+ai=xs!0 ; br:+bi=xs!1 ; cr:+ci=xs!2 ; dr:+di=xs!3 ; er:+ei=xs!4
ts = br - er ; t4 = br + er ; tt = cr - dr ; t7 = cr + dr
t8 = t4 + t7 ; ta = t4 - t7 ; te = bi - ei ; tm = bi + ei
tn = ci + di ; th = ci - di ; to = tm + tn ; tq = tm - tn
ti = te + kp618033988 * th ; tk = th - kp618033988 * te
t9 = ar - kp250000000 * t8 ; tu = ts + kp618033988 * tt
tw = tt - kp618033988 * ts ; tp = ai - kp250000000 * to
tb = t9 + kp559016994 * ta ; tj = t9 - kp559016994 * ta
tr = tp + kp559016994 * tq ; tv = tp - kp559016994 * tq
r4 = (tb + kp951056516 * ti) :+ (tr - kp951056516 * tu)
r3 = (tj - kp951056516 * tk) :+ (tv + kp951056516 * tw)
r2 = (tj + kp951056516 * tk) :+ (tv - kp951056516 * tw)
r1 = (tb - kp951056516 * ti) :+ (tr + kp951056516 * tu)
in generate 5 $ \i -> case i of
0 -> (ar + t8) :+ (ai + to)
1 -> if sign == 1 then r1 else r4
2 -> if sign == 1 then r2 else r3
3 -> if sign == 1 then r3 else r2
4 -> if sign == 1 then r4 else r1
This code (which is actually a bit of a cheat, as I’ll explain) demonstrates the principal problem with these hand-coded transforms: they are very tedious to write, and doing them properly is very error-prone. The code above is adapted from equivalent code in FFTW (translated from C to Haskell), and I still made a couple of confusing errors with the translation that took some time to track down.
The right way to do this (and the way that FFTW does it) is to generate the code for these small transforms. FTTW comes with an OCaml program called genfft that generates C “codelets” for fixed transform sizes. It does this the way it should be done, which is to build a directed acyclic graph of the expressions relating the FFT output vector elements to the input vector elements, then recursively partitioning the expression DAG to find an optimal schedule of sub-expressions to calculate, exploiting sharing in the expression DAG. It performs a range of other optimisations and produces code with information about variable lifetimes to help a C compiler allocate variables to registers. It’s quite a complicated piece of code and while it would be quite possible to implement something similar here in Haskell, it’s not something I want to get into.
Instead, I’m just going to translate pre-computed codelets from FFTW into Haskell as needed. For the moment, there are just codelets for sizes 2, 3 and 5. I know that this is a bit of a cop-out!
Benchmarking of full FFT with new prime length algorithm
We can benchmark the pre-release-1 version of our code as we did before. The only real difference in the benchmarking code is that we now split out the FFT pre-planning and execution steps, just as we do for the FFTW comparison:
doit :: Environment
-- ^ Criterion timing environment.
-> Int
-- ^ Problem size to benchmark.
-> Criterion (Int, Double, Double)
-- ^ (Problem size, DFT, my FFT, FFTW) result.
doit env sz = do
let v = tstvec sz
let myplan = FFT.plan sz
myffts <- runBenchmark env $ nf (FFT.fftWith myplan) v
let fftwPlan = FFTW.plan FFTW.dft sz
fftws <- runBenchmark env $ nf (FFTW.execute fftwPlan) v
let mean xs = VU.sum xs / fromIntegral (VU.length xs)
return (sz, mean myffts, mean fftws)
Here are some results (compare with the plot here):
Size FFT FFTW
8 7.342840123514666 0.23683859428961027
9 6.00078759494703 0.26063541817111363
10 5.729639396269459 0.2748499420681072
11 86.49804982527789 0.30856435170546825
12 9.807447052829982 0.31311953861159786
13 86.00520456247791 0.3605107646065841
14 82.95103119597552 0.376714068913601
15 9.215392287643182 0.37767254610552514
16 17.10820078605275 0.4111241396263765
17 41.68476763757921 0.5510052706662386
18 15.427676628374963 0.48729287584540376
19 253.45276312991297 0.591149238701132
20 15.207635871685895 0.4882580915317034
21 133.2241923628109 0.5478250990057529
22 170.57172329906302 0.5739794434572908
23 258.3689542309871 0.7623452315534346
24 23.44427301857189 0.5873605384195926
25 19.207997729037253 0.6227313538442145
26 166.0213344179246 0.6519942245632964
27 24.318592499040978 0.6779496381162733
28 175.50596609255493 0.6846945026536149
29 262.0829405422722 1.923472700374467
30 24.49043727490109 0.7104966005838027
31 266.81316515164707 1.8972466566732948
32 39.40595410198777 0.7062471411991911
33 295.29035707669595 0.8083856925160968
34 101.16316042021744 1.0173973442070452
35 248.676046897613 0.8382881694364539
36 39.09556291431992 1.7661164381674357
37 681.7192147352878 2.1785805800131386
38 608.3855186988209 1.1454285889354168
39 333.19101507908573 0.9308535809232481
40 37.370256895617544 1.8257210829428263
41 691.6421959974948 2.476603803890092
42 310.0596445346522 0.9722038305231503
43 695.7620690443699 2.4694512465170453
44 429.65234353074027 1.0128843456008882
45 41.04217610687821 1.0246840871452063
46 618.926004080901 1.4471615337198382
47 702.3114274122897 2.738864240901811
48 57.81030253108061 1.9187043287924357
49 421.12172677048613 1.1341981329004562
50 50.962234775934874 1.1095974685318295
51 161.7964395654523 1.4852845567176596
52 495.0807594649851 1.183129259796313
53 715.0668213942233 3.065497694270951
54 64.40112148810711 2.085597334163529
55 660.056785254607 1.2708811248085148
56 417.15205742844523 1.230892098392441
57 808.9226792433446 1.6806744472082669
58 650.6058727790211 2.846152601497514
59 727.7459214308445 3.4374306776693886
60 59.05950751349141 2.235801038997514
61 722.7129052260105 3.3158372023275913
62 661.2929855872486 3.039271650569779
63 576.7367386214794 1.443425393471645
64 101.79822154115053 1.319679001481808
65 707.5652634192799 1.4684115299151743
66 788.2175003577565 1.5020647256584347
67 2060.737044630308 4.171759901302201
68 247.82727675601143 1.9097647642291187
69 957.5185333777761 2.122053707753631
70 635.3625809241627 1.5384636849940467
71 2059.1658661940287 4.615218458431107
72 100.28944802726365 2.3144791701010297
73 2059.3160698988627 4.877478895442826
74 1542.7369187452982 3.516108808772904
75 91.70258250619682 1.6265822288412721
76 1186.8566582777687 2.1726253235097874
77 982.85765996469 1.769793748600743
78 840.4931580115652 1.738126872892376
79 2072.8534768202494 4.920394239681107
80 91.53505371794812 2.8103898146322797
81 111.27765236777216 1.8290987655770699
82 1566.5740082838724 4.002482710140092
83 2090.9613679030135 5.554587660091263
84 744.2030464698171 2.8771470167807163
85 351.9891279483484 2.3887479415774444
86 1578.096778211851 4.252822218196732
87 942.5753663160987 3.892810163753373
88 1057.950885114927 1.918659046629275
89 2087.296874342222 4.152612425896258
90 109.21910661937943 3.0774186232260288
91 984.3224595167821 2.057882550978609
92 1283.168227491636 2.7874980135825185
93 976.4284203627295 4.221827802913529
94 1590.3753350355814 4.550845442073685
95 1662.6900742628764 2.760776834156036
96 144.62385255074702 2.989203748958451
97 2105.1830361464213 5.831153211849076
98 962.7875839759207 2.1464794114324626
99 1165.9640381910988 2.2574105259496102
100 127.13982341663234 3.25146418597017
101 2139.5773003676127 6.954104719417436
102 424.5954854679961 2.8400079295504073
103 2122.2800324537943 5.217902958882975
104 1125.273139295835 2.2482904724256056
105 976.7410313178395 2.29733540394516
106 1639.0317986586283 5.356700239436967
107 2121.929557142515 5.538116033914917
108 168.86406031969423 3.4302781202963417
109 2123.9608834364603 6.51064616228853
110 1367.403895674009 2.4175219587466943
111 3176.6861985304486 4.970462141292435
112 966.6675637343116 3.5280297377279823
113 2133.7908814528178 5.212785438754142
114 2000.4862855055521 3.262165487126482
115 1763.5459015944193 3.520594603069111
116 1410.8294556715675 4.758269605892044
117 1215.3333733656593 2.6904628174305394
118 1646.5348313429547 6.336600599544389
119 522.8397404242847 3.380321635296074
120 168.7067040574872 3.6281655409506386
121 1743.676097212095 2.856947757367188
122 1652.6526520827006 6.35805827166353
123 3191.353709516777 5.566508589046341
124 1472.534568128843 5.087287245052201
125 204.55931354390123 2.878564010651325
126 1148.1660912611671 3.857047376888138
127 2157.4610779860213 7.01132517840181
128 255.2091133292943 4.524619398372513
129 3213.7626717665325 5.8502266981772015
130 1433.2574914076515 2.8817591619388314
131 5816.845328626883 8.358390150325638
132 1636.862189588804 4.138381300227982
133 2381.991774854918 3.8588213034711045
134 4566.513926801927 7.380873976009232
135 205.6628509671712 4.1145394423178265
136 707.4663197089527 3.7614392730663586
137 5802.933604536305 8.067519483821732
138 2082.0325921156596 4.143138631531957
139 5837.63781291033 6.687308409418286
140 1375.4314492323585 4.135997114436966
141 3245.627314863456 6.6012452223471225
142 4597.129256544358 7.829100904720169
143 1781.4821313002299 3.3999510622808935
144 276.25549455838546 4.078776655452591
145 1780.4760048964215 5.7047913649252475
146 4602.195651350266 8.417994795101029
147 1420.502097425718 3.405032672022908
148 4050.657183943041 6.117255506770951
149 5840.706260023368 8.322627363460404
150 271.5848745937858 4.166991529720169
151 5847.150714216483 8.344085035579546
152 2684.2993805983238 5.328090009944779
153 788.3069073249196 4.34737521409252
154 1934.3585084059428 3.5752378157000746
155 1793.6820099928568 6.21023875262056
156 1692.6712105848978 4.37918406512056
157 5887.171656904471 7.054371522969544
158 4639.408023176437 8.611113844173294
159 3302.1778176405555 7.57876139666353
160 283.4023298855339 4.443557081477982
161 2679.929168043392 4.918450050165793
162 315.12305910832157 4.7821114638022015
163 5948.504836378348 9.874732313411576
164 4046.9283173658932 6.989867506282669
165 1990.8851693251324 3.6465444851485143
166 4697.322280225998 9.762675581233841
167 6027.478606519949 8.626969702780771
168 1672.8920052626322 4.853637037532669
169 2107.3860238173197 4.06900353267252
170 891.4885078955983 4.747679404454764
171 3442.634970960867 5.030573009726613
172 4035.288722334156 7.4404786207846225
173 5988.976390180838 8.661512883352529
174 2138.3041451552103 6.606013593929154
175 1676.0057519056986 4.021403606129205
176 2196.549804029722 5.149276075618607
177 3375.6584237196566 8.513362226741656
178 4697.455794630296 9.896189985530716
179 5983.390242872489 8.769793029031938
180 312.5946300769495 4.798800764339311
181 5961.510569868338 10.587603864925239
182 2022.4398682692238 4.4193231513201745
183 3376.225859937919 9.0545724013022
184 2997.071177778497 6.701381025569779
185 5031.363398847823 7.5739930250814975
186 2130.505473432798 7.109076795833451
187 1081.2348435499855 5.581578643450855
188 4000.303180036792 8.358390150325638
189 1697.1534798720072 5.511672315852982
190 3603.3243249037373 5.505330252173733
191 5974.268348036062 10.225207624690869
192 426.1170404697108 5.049140272395951
193 6019.6703980543725 10.165602979915478
194 5197.78671961809 10.28958064104829
195 2343.627841291685 4.369929125939037
196 1947.0876763441752 5.597503004329544
197 5995.687873182546 8.893942714973047
198 2518.350512800474 5.824000654476029
199 5987.772376356375 8.90603809162105
200 399.6716516757655 5.390078840511185
201 8125.521571455261 10.873706159847115
202 5219.323069868334 12.29706507708343
203 2683.6103509047207 7.643134413020951
204 1011.6595337965675 6.663234052913529
205 5035.125644026046 8.551509199397904
206 5240.449340162522 12.854964552181082
207 3356.241614637626 6.450424231028649
208 2274.805934248228 5.6475709059408725
209 3968.521983442554 6.324676105760653
210 1945.366294203062 5.4949830153158725
211 6022.33830195452 11.784465132015074
212 4002.8280327894777 9.476573286311968
213 8104.998500166199 11.009604749935
214 5248.770148573168 12.862117109554129
215 4996.983439741379 9.216697035091263
216 533.9485509587184 5.890757856624466
217 2691.0752366163897 8.203418073909623
218 5278.050334272631 11.696250257747495
219 8131.770522413513 12.120635328548273
220 2793.6405251600904 6.0218880751303265
221 1405.3124497511574 6.584571834952974
222 5641.5337632277115 8.91390543963228
223 6031.798751173271 12.916953382747487
224 2226.6930649855326 5.859763441341264
225 492.93976062465316 6.513030348079544
226 5301.510722456224 11.80830698992523
227 6032.92408686663 12.013346967952574
228 4311.069876966722 7.5668404677084515
229 6028.308303175224 10.845941619467675
230 3608.8866303541768 7.895858106868607
231 3204.0351937391893 5.535121141804549
232 2999.0238259413386 8.382232008235794
233 6028.112799940361 10.724588226950925
234 2603.2513688185395 6.701381025569779
235 5026.652247724777 10.21328669573579
236 4002.029330549488 11.073977766292423
237 8156.01292353656 12.311370191829523
238 1350.95062953021 7.078858746894385
239 6050.033004102958 11.070648053740346
240 515.6467460982858 6.198317823665482
241 6101.245314893974 14.483363447444745
242 4332.065017042406 7.01132517840181
243 521.7561279822681 5.814926712170394
244 3998.324305830249 11.653334913509214
245 2660.5958054640464 5.90844224135939
246 5789.961249647389 9.998709974544388
247 5095.741183576828 7.523605504528788
248 3025.1378129103323 9.021193800227982
249 8217.782409010193 14.838607130306068
250 544.8541199256275 6.911189375179155
251 6554.829509077325 12.523562727229914
252 2572.6312707045263 6.815821943538529
253 4695.629508314378 8.140338993136517
254 5347.737700758227 12.804896650569752
255 1354.8606942274757 7.161819974456423
256 707.4865852881763 6.389052686946732
257 2303.3947060682963 14.573962507503339
258 5849.68033534075 10.640055952327582
259 8129.352958021424 10.535151777522895
260 2889.403731642023 6.715686140315873
261 3356.6207001783973 9.691150007503373
262 14635.402591047558 14.99834757830412
263 17646.092803297317 13.412332608956154
264 4077.1740983107175 7.075698194759232
265 5042.292506513839 12.227923689143982
266 5309.981734571703 8.04216463727002
267 8304.14000254657 14.092356977718186
268 11653.839976606636 13.935000715511155
269 17623.26660853413 13.354880989222602
270 547.8796516944263 7.120997724788529
271 17636.74441081074 14.659793195979901
272 1369.4519112684914 8.623034773128373
273 3504.754931745779 6.592521704173177
274 14088.632495222362 14.981658277767005
275 4536.106021223313 6.718241620247578
276 4910.218150434738 9.309680280940873
277 17766.763598737987 13.461639600208656
278 14236.349494276317 14.902980146663493
279 3341.1735604384066 10.265738783138135
280 2861.737639723078 7.137687025325638
281 17776.34325724629 13.408218991989909
282 5900.844962415946 12.058646497981867
283 17762.998969373977 13.730084073777025
284 11446.558863935736 14.185340223567792
285 5738.5939667799585 8.249279068694236
286 4414.977462110765 8.196265516536576
287 8417.7106927016 11.569888410823667
288 796.4033196547215 7.2878907301596225
289 2273.885638532896 10.170716983844166
290 3888.1677697279547 10.158450422542431
291 8324.88718729999 14.826686201350993
292 11597.670943556097 15.38220149065763
293 17687.618167219436 16.03070002581388
294 3080.491454420342 7.86724787737642
295 5096.4230607130585 13.753802595393967
296 9061.681659040712 11.188418684261173
297 4865.214259443527 7.350788046095362
298 14505.664737043651 15.429885206477943
299 5813.416869459402 10.406405744808055
300 765.3874466993993 7.564456281917435
301 8549.916178999209 12.218386945979914
302 14498.912722883495 15.41081172014982
303 8318.092257795595 17.291934309261137
304 6194.800765333428 9.498030958431107
305 5111.219317732102 14.473826704280683
306 1685.68077784564 9.934336958186966
307 16856.972606001174 18.60800486590176
308 5143.358142194993 8.208186445491654
309 8326.999575910828 18.064410505550203
310 4245.759875593432 11.054904279964298
311 16901.84298258809 16.93528287875031
312 4186.322123823413 8.105666456477984
313 16892.38730174092 17.403485418142726
314 14552.790553388866 15.718371687190833
315 3469.461829481375 8.234412489192826
316 11723.458201704292 15.86857539202482
317 17051.886946974075 15.544326124446695
318 6278.299720106377 13.880164442317795
319 4771.320254621751 11.648566541927183
320 779.6019623854345 7.621676740901811
321 8344.09418803241 17.67340403582364
322 5542.30156641985 10.26239088175936
323 7237.359912214536 11.623731729614779
324 1017.057330427427 8.296401319759232
325 4677.981765089279 7.905371926278567
326 14553.167254743847 18.67714625384121
327 8382.07903605487 17.110736189143957
328 9257.511527357367 12.742907820003348
329 8470.940024671814 13.796717939632249
330 5435.914428053149 8.570582685726029
331 16891.679198560985 18.72721415545254
332 11791.419417677194 17.87367564226895
333 9624.008567152287 12.781054792659596
334 14557.911784467968 18.777282057063868
335 14840.347201643259 17.539889631526762
336 4180.001647291429 8.448989210384232
337 17110.907466230663 17.46223247462205
338 5455.831916151294 9.26199656512056
339 8408.655555067324 17.25855570818692
340 2058.100135145445 10.363490400569775
341 5221.2757180311755 12.747676191585377
342 6773.194701490657 11.11927729632172
343 4700.543315229661 8.362908962212568
344 9364.487559614445 13.467700300472092
345 5961.040885267507 11.37915354754242
346 14918.667704878122 19.008548078792384
347 17514.438063917434 18.762976942317774
348 5148.434073744065 12.044341383235773
349 17080.938250837597 17.97853264755286
350 4592.968852339036 9.295375166194779
351 4918.822676954513 8.555914478628118
352 5643.247992811452 8.832843122737748
353 17257.79476862935 17.825823345879105
354 6140.338809309257 16.08792048479825
355 15375.205905256544 17.44929057146817
356 11602.496535597114 18.746287641780665
357 2115.330130872984 10.650825560074741
358 15111.36475306538 19.335181532161524
359 17113.24158412007 17.833567435442816
360 986.8735383131689 8.992583570735794
361 10046.743781385685 13.366475077997043
362 15217.964083967481 19.43531733538418
363 6221.038729963555 10.015399275081498
364 5328.516394911059 9.521872816341263
365 15465.27090769795 19.413859663265036
366 6386.92560893084 17.034442243831453
367 17143.568427381786 20.388991651790427
368 6100.327403364433 11.872680006282653
369 9948.596389112738 14.748008070247478
370 11184.663207350042 13.958842573421311
371 8812.276751814152 16.30011302019864
372 5144.304663954026 13.176829633968191
373 17710.835368452346 19.664682348842135
374 2726.7283509352374 12.623698530452566
375 1417.1189377882667 9.45273142840181
376 9505.197436628605 15.308291731136146
377 6484.0430329420715 13.613135633724047
378 4514.68888026262 9.991557417171341
379 17502.657801924026 18.958480177181055
380 7178.167731580991 11.746318159358824
381 8572.232158003115 17.343800783944676
382 15474.21398860005 18.958480177181055
383 17531.666190443313 17.950458626205815
384 1388.2893632033058 9.095103559749466
385 6433.095366773859 9.520977743238113
386 15460.357100782667 19.621283827083396
387 10529.679686842232 15.42034846331388
388 12496.156127271921 19.573600111263087
389 17505.988509474075 20.553500471370505
390 5562.1761391737555 9.996325788753373
391 7929.1552613356325 15.139685320127917
392 4820.38441401506 9.922416029231888
393 23087.887198744094 21.776587782161513
394 15878.350169477737 19.094378767268946
395 15839.692981062206 19.335181532161524
396 6351.71356898333 10.103614149349072
397 17751.45951014546 19.409060952263868
398 15923.5519478896 19.318492231624415
399 8332.178027448914 12.32864255821255
400 1471.9909737684914 9.39312678362642
401 17594.136626539505 23.013980207698623
402 20018.920333204544 19.58313685442715
403 6370.477111158623 14.666945753352948
404 12890.035540876657 23.629100141780654
405 1395.6946442702003 10.914237318294376
406 5635.482699690114 14.562041578548259
407 13570.60614329365 16.002089796321687
408 2404.6320031264017 12.740523634212332
409 17733.94289713887 22.348792372005267
410 11059.259803114204 15.918643293636146
411 23362.903029737747 21.48810130144863
412 13157.655627546577 22.71595698382167
413 8536.862761793398 18.975169477718165
414 6747.96524745013 14.011294660823655
415 15784.382254896436 23.07835322405605
416 5811.318785963308 10.370642957942822
417 23707.756430921832 21.721751508968154
418 9195.975692091251 14.199645338313886
419 17946.83876734761 20.971450277268158
420 5160.135657606371 10.477931318538525
421 17890.734107313427 21.515448736906347
422 15754.320056257522 22.959143934505267
423 10693.556697187689 17.575652418391996
424 9548.117549238468 18.159777937190825
425 2467.3122475722025 12.686151574232735
426 20343.08615427998 20.59403162981777
427 8599.633605299257 19.96699076678066
428 13525.1087258437 23.128421125667373
429 6605.836779890315 11.703402815120544
430 11234.418780622747 17.053515730159578
431 17912.341983137405 21.523934821925216
432 1591.6294167616559 10.625750837581489
433 18026.596934614456 24.649531660335338
434 6145.5768654921185 15.742213545100991
435 5879.821212110769 15.036494550960366
436 13398.751647291454 22.3392556288412
437 9944.717318830753 17.685324964778715
438 20378.097922621047 22.844703016536517
439 17927.7080605605 22.356287195176197
440 6919.342906294125 11.10258799578461
441 5544.680983839283 11.7272446730307
442 4167.520434675464 14.626414594905683
443 17977.165610609325 22.946780938413237
444 14925.74873667744 16.612441358821687
445 17524.184615431102 22.851855573909564
446 15913.24749690083 23.981959638850963
447 23981.243998823444 22.5061486342123
448 5319.671065626391 10.80456477190766
449 18539.14204340962 22.89736326929037
450 1645.1829979994488 11.15742426897797
451 13824.185759840282 18.283755598323637
452 13489.064605055126 22.6587365248373
453 24068.37406855611 22.73979884173183
454 15894.231231031688 23.066432295100967
455 6658.267409620538 11.08018479690441
456 9652.127654371525 14.314086256282634
457 18005.914122877395 23.984343824641982
458 15321.154029188428 23.145110426204486
459 2774.4525979139967 14.645488081233806
460 8150.696189222596 14.771849928157636
461 18081.03266459492 22.281738814460688
462 7529.606253919859 11.8798325636557
463 18166.868121443065 22.409377903772533
464 6170.114905653251 15.770823774593175
465 6179.284484205499 16.252429304378328
466 15143.699080763134 23.204715070979876
467 18036.05499964741 22.95124586816732
468 6414.019496259942 11.832148847835386
469 24396.078021345416 23.495585737483783
470 11646.632582960397 19.144446668880274
471 22565.59315424946 23.881823835628307
472 9734.894664106632 21.14001017596035
473 13795.039088545116 20.164878187434958
474 20114.700228987014 23.26670390154628
475 11688.270003614694 15.146167097347083
476 3981.4108918287848 14.941127119319745
477 10569.295317945745 20.77761393572597
478 15473.329455671583 23.607642469661517
479 18075.987727461135 23.00062018845763
480 1699.1347382643412 11.419684705989688
481 18023.89088374165 18.55793696429043
482 15498.597056684766 27.939708051936897
483 10935.527713117866 15.751295176866872
484 8359.0907166579 12.936026869075613
485 17758.099467573436 24.511248884456432
486 2130.765349684019 12.652308759944752
487 18163.096339521682 26.40667658831385
488 9751.13573771503 22.997290907161517
489 22969.357402143756 28.800399122493538
490 6234.495074568047 12.71906596209319
491 18175.33198100117 26.40307015176059
492 15488.802821455274 18.894107160823634
493 9178.65219813373 20.362765608089255
494 13226.124675092966 16.877085981624422
495 7944.507033643981 12.65469294573577
496 7381.898791609067 17.136962232845125
497 23918.84270411519 23.862750349300182
498 20202.853114424026 26.45674448992518
499 18232.16381770161 25.018966814236965
500 2254.7215531447123 12.69999247576507
501 23267.812163648883 27.799041090266975
502 16139.70461588887 24.279982862727916
503 18786.065013227737 25.369555769222057
504 6022.457511244072 12.332827863948664
505 16898.033053694042 28.948218641536506
506 10727.147490797308 17.87367564226895
507 8235.749633131287 13.646514234798264
508 13097.738654432565 24.156005201595107
509 18284.491927442825 23.642565300964296
510 3993.3461258986085 15.754134474056068
511 24298.502833662307 26.714236555354866
512 2371.374995527525 12.361438093440851
513 12203.733355818062 16.655356703059972
514 5735.048682508717 28.11852198626307
515 17161.597640333446 29.839904127376347
516 15386.335284529005 20.26024561907558
517 13909.463317213329 21.91725474383144
518 17219.719321546825 19.843013105647852
519 23194.415004072467 28.14474802996424
520 7358.385951338071 13.019473371761158
521 43282.49874812154 28.888613996761116
522 9614.11181193378 18.457801161067774
523 42830.116183576865 27.60740792876259
524 30894.7342942336 28.812320051448616
525 6560.522944746271 13.21497660662444
526 35296.6970513442 28.44515543963221
527 9002.658755598331 21.950633344905658
528 8189.703852949403 13.071925459163504
529 14291.011721906933 21.869571028011123
530 13146.445185957224 22.806556043880267
531 10905.386836347847 24.29905634905604
532 13450.450331983837 16.917617140071687
533 19224.13769465474 21.44995432879238
534 21035.620600996288 27.062327680843147
535 17232.460410414013 29.32253581072596
536 28402.377993879596 25.71287852312831
537 23229.19073802022 28.86477213885096
538 36109.66864329366 28.62396937395838
539 9804.684550581243 13.503236113645404
540 2280.6042740919784 13.410479841487717
541 42703.99513941792 30.82218867327478
542 36131.14062052755 28.654963789241584
543 23283.996016798297 28.81708842303065
544 3818.337352094898 16.281039533870516
545 17534.672648725784 27.50817042376307
546 8008.810908613464 13.970763502376391
547 42685.47001582174 30.473003099311374
548 30896.93012934712 28.130442915218147
549 10945.336253462103 25.56029063250331
550 9554.147155103949 14.025599775569749
551 12294.170291242866 22.978217420833392
552 11722.845465956003 18.01434260393887
553 25230.991275129592 26.84298258806971
554 36405.66769343404 28.97444468523768
555 18886.668116865432 20.613105116145896
556 31040.670306501663 28.268725691097053
557 42431.74734812765 30.599989375847155
558 10394.894511518743 19.83347636248379
559 18280.691535291946 22.875697431819717
560 7229.3466637709325 13.374717054622487
561 4885.055453596359 18.312365827815825
562 37071.446807203574 28.82185679461268
563 43859.56469279317 30.343802935969677
564 16587.392718611034 22.83516627337245
565 17772.77651530293 28.13997965838221
566 36883.365542707725 29.105574903743538
567 7006.043822584407 14.743239698665448
568 27045.68091136006 26.75476771380213
569 43255.97944956807 29.670626936214237
570 14304.165274915966 17.964274702327547
571 42700.54522257832 28.395152250425767
572 9219.996363935734 15.203387556331458
573 23706.283004102985 27.655989942806038
574 18606.175811109817 22.591979322688857
575 12876.963050184519 19.003779707210352
576 2606.839568434018 13.715655622737719
577 42667.34066706685 31.229884443538456
578 5849.737555799734 21.79566126848964
579 23696.615130720413 28.29733592058924
580 9336.437613783146 19.797713575618555
581 25191.740424452106 30.92947703387049
582 21382.58639079121 28.36409312273768
583 14727.110297498974 25.894076643245494
584 27125.27218562154 29.525191602962288
585 8345.641524610779 14.74085551287443
586 37199.37983256368 31.060607252376343
587 42620.93010645894 30.550545903847745
588 7559.933097181578 14.571578321712323
589 13960.592181501659 24.961859998958385
590 12956.647307691843 26.492507276790416
591 23595.885665235797 28.6573479750326
592 20603.858859358104 22.172362623470107
593 42718.936831770225 30.768020148632417
594 11390.194327650337 15.222461042659583
595 4832.929999647385 18.615157423274805
596 31537.081630049037 29.632479963557987
597 23680.469424543655 28.67880564715174
598 13740.450770674022 20.455748853938864
599 42653.61967783956 31.052843124349348
600 2736.145884809749 14.368922529475995
601 42862.60071497945 35.571486768977906
602 19214.98718958882 24.318129835384166
603 32610.721022901813 30.09978037859705
604 30816.082389173785 29.649169264095097
605 11320.01581889179 16.18090373064786
606 21979.824931440624 34.60827570940759
607 42941.193015394485 34.95896941583069
608 14504.777819929393 18.41011744524746
609 10539.514453230171 21.69552546526699
610 13070.670993147165 27.837188062923225
611 18642.534644422805 25.93222361590174
612 4636.613757429368 18.82496577288418
613 42874.24746256856 37.943751631038445
614 37591.68568354635 36.770732221858765
615 19078.633220014846 23.56234293963222
616 10952.622325239447 15.704066572444738
617 43053.53584986715 35.96051741516642
618 23133.71124964742 33.62837534930017
619 43691.570193586624 37.561890784473654
620 10501.636893568304 21.709830580013076
621 14453.701407728466 20.915896711604876
622 39418.47506266622 37.17127543474939
623 26518.144042310993 31.980902967708378
624 9628.953368482853 15.453727064388099
625 3087.6463959791795 16.652972517268953
626 39526.74570780782 37.021071729915406
627 17307.99856883076 20.81099253680019
628 31165.84721308736 30.521781263606815
629 26202.403933821002 27.63214808489588
630 8049.2228577711785 15.465647993343175
631 43036.906153974815 31.878382978694706
632 28434.38807230977 30.004412946956425
633 23368.191153822223 33.78334742571619
634 37730.24025660543 30.309588728206425
635 17740.05833369282 30.16415339495447
636 16989.859969435012 27.040870008724006
637 10454.329879102972 16.199884876774735
638 12394.06290751484 23.154647169368545
639 32462.236316023158 30.65291148211268
640 2786.9433472731275 14.919669447200603
641 42914.47344523457 35.731227216975945
642 21914.383799848827 33.97408228899744
643 43003.72544032124 35.193281897181095
644 13726.848990736278 21.228225050227923
645 20088.96771174458 25.693805036800182
646 18507.224948225292 24.661452589290416
647 42910.54669123677 35.118776091211856
648 3396.7703888990995 15.808970747249429
649 16351.158053694044 30.302436170833378
650 9950.985343275333 16.202361402767
651 10818.130404768255 23.569495497005263
652 30511.984259901325 37.135512647884156
653 42852.0769188979 37.457377729671265
654 22230.705649671825 32.98464518572595
655 40466.405780134475 35.99348765398767
656 20979.201228437694 24.885566053645885
657 33862.06570368795 33.876330671565796
658 19608.23240977315 27.501017866390022
659 42959.13162928609 35.77924917193775
660 11478.897960005072 16.478926954524812
661 42947.73283701924 36.042061051239756
662 37849.954993543906 37.04014521624353
663 6118.637950239433 21.349818525569724
664 28680.807978925983 34.863383589046265
665 16341.614157972608 21.173388777034567
666 23662.04682093648 25.190741834895885
667 16246.201426801954 28.595359144466194
668 30630.23749094991 36.34396296526697
669 23462.972075758255 36.89232569720056
670 36769.03906565694 32.93696146990564
671 16150.755317030224 31.639964399593143
672 8365.873725233338 16.14752512957364
673 42870.67595225362 36.87816094835196
674 37992.593676863 37.30717402483728
675 3051.3423989393855 16.564757643001375
676 13527.357013044628 17.723471937434965
677 42968.32266551046 37.36916285540369
678 21903.34740382222 33.2516739943197
679 25524.901778517044 34.040839491145874
680 5060.536296186691 20.510585127132224
681 23533.0719063857 34.33647852923181
682 12004.787356672556 25.267035780208385
683 42907.33042460469 36.22019378962569
684 16491.584212599075 21.433265028255267
685 40504.42877512959 35.54764491106775
686 9697.083861646915 17.33484965349942
687 22914.13012248067 34.25541621233727
688 21207.55854350117 26.6737053969076
689 18762.847811994827 30.46932917620447
690 14914.462001142772 22.560984907405658
691 42891.08935099629 36.818403561262976
692 30703.257949171344 36.9447777846029
693 13303.088576612743 18.064410505550203
694 37920.71047526388 37.05683451678063
695 41532.53737193136 35.86474162127282
696 12361.85255747822 24.036795912044326
697 27068.473727522174 31.613738355891968
698 37996.69924479513 37.36201029803063
699 23039.62889414815 34.61542826678064
700 9027.034671125673 17.1488831618002
701 42910.74219447163 36.821418855057495
702 12206.30827647236 17.997653303401766
703 28467.356593427936 31.189353285091194
704 13803.133399305614 17.413527784602934
705 20648.996264753616 28.626353559749397
706 37948.04516535787 37.691027937190796
707 25697.099597273147 40.63311320330407
708 15341.643721876417 31.711489973323616
709 42958.87890559224 36.404046095406784
710 36359.95331507711 33.232600507991584
711 33546.621234236045 34.10998087908533
712 30647.68496256856 36.49416667010095
713 15982.782275495802 32.08342295672205
714 5553.03040247942 22.267730055110736
715 12299.4154999831 18.96086436297207
716 30710.546405134475 37.89368372942712
717 23259.236247358596 34.982592878597046
718 39157.8334878066 37.63380747820642
719 43139.566809950156 37.758983476530965
720 3159.572512922539 17.2251771071127
721 26100.96636515645 40.308863935725945
722 21383.907229719436 27.85149317766932
723 23146.88626032857 41.46757823015954
724 30791.720778761184 37.631423292415406
725 12971.24329310444 25.245578108089244
726 14311.820895490917 19.13014155413418
727 43071.82732325582 46.27409678484704
728 12451.004416761667 18.186003980891996
729 4077.4268220045656 18.534095106380274
730 36838.94100886373 36.40356761004236
731 26726.50280695943 33.65936976458337
732 15617.026717481885 33.42095118548181
733 43368.23645335225 40.559203443782586
734 37327.31524210958 40.05614024187829
735 9953.610331831243 18.28852396990567
736 14945.949942884714 23.29054575945644
737 42738.00078135518 36.653907118099
738 23820.70961695699 29.13180094744471
739 43043.53895884541 40.12277446121781
740 25879.30861216573 27.155310926692756
741 20523.78597956685 24.172694502132213
742 20794.767768202102 32.5650284865072
743 43554.52242594746 39.53000626892655
744 12273.010642347603 26.108653364436904
745 42371.169955549514 36.503703413265015
746 38756.746680555625 40.227801618831414
747 33879.64192133932 39.11438685442712
748 6820.539862928645 24.084479627864635
749 27509.996325788776 40.9883568861654
750 4421.584040937669 18.12878352190762
751 43793.67295008687 42.139918623225945
752 21246.35401469258 30.435950575130253
753 24196.915061292926 39.0357087233236
754 16402.57540446309 28.304488477962284
755 43162.11405497579 37.38346797014978
756 9764.027030287052 18.762976942317774
757 43242.504031477256 39.260518768735814
758 39589.96000987081 37.06398707415368
759 19277.97737818745 26.173026380794322
760 19763.469130811965 23.486048994319717
761 43768.04533701924 40.19705674976914
762 23456.24151927022 38.160712538020874
763 28323.900134382526 40.24449091936853
764 32657.267482099815 36.34396296526697
765 5925.027758894217 23.69824152972011
766 40160.23579340962 37.31194239641931
767 20824.803740797317 36.00540858294275
768 4698.4952996351785 17.973811445491606
769 43533.446223554885 41.12902384783532
770 16733.040244398388 20.193488416927142
771 10865.156085310247 42.01594096209313
772 30978.431136427203 37.28810053850915
773 42959.60846644429 39.7173637670169
774 23437.816531477252 31.783015547054077
775 13830.115229902538 27.43187647845057
776 30547.79473048238 40.71655970598962
777 29546.384246168414 29.89712458636072
778 38410.85377436666 40.270716963069695
779 31836.57351237325 36.646754560725945
780 14591.819674787792 20.39376002337246
781 43530.97143870381 37.90322047259119
782 20332.2547982314 30.936629591243538
783 13727.702529249462 27.734668073909553
784 10664.47439890888 19.137294111507227
785 41516.472728071494 37.65526515032556
786 49046.05093699483 42.05170374895837
787 44741.70151453999 41.634633689088744
788 31975.044638929645 37.41446238543298
789 59210.09960871724 43.806464491145874
790 39066.84580546407 37.30717402483728
791 27171.623141584674 39.10008173968102
792 16130.921275434765 19.466311750667384
793 21886.0501359084 37.50267725970056
794 38753.25623255758 40.494830427425164
795 21248.471171675003 33.680827436702515
796 31561.75795298604 37.53605586077478
797 43627.57387858419 41.03343432365748
798 20782.65848856953 26.099116621272838
799 27110.361487684528 37.86745768572595
800 4906.23179179216 18.777282057063868
801 34317.51194697408 40.82384806658532
802 39601.19667750387 45.34188014055993
803 43544.03916102437 42.20190745379235
804 44281.017215071 38.36813670183923
805 18542.806536970416 26.68562632586268
806 17242.931754408153 30.54562312151697
807 59565.58886271504 43.055445966975945
808 29442.979724226272 43.720633802669305
809 43402.22540598897 45.773417768733765
810 4203.385741529712 20.148188886897845
811 47515.44180613546 44.924647627132195
812 16709.589392957958 28.147132215755256
813 59352.05879908589 42.51185160662438
814 31196.69380885152 31.90937739397791
815 41511.89747553853 43.9328263380697
816 6194.7292397596975 24.48979121233729
817 29774.414927778518 37.969977674739624
818 38651.82343226461 44.44781046892907
819 14968.888194380075 21.082789716975974
820 27143.8044617751 31.30379420305994
821 44792.92336207417 44.93157888515568
822 49393.25991374043 43.851764021175164
823 45067.188174543655 44.91761436837974
824 28854.748637495315 44.314296064632195
825 17484.597594557083 20.703704176204486
826 21829.418570814407 37.8912995436361
827 45115.94954234151 45.474747498044565
828 17320.47978144673 26.883513746516975
829 45076.02635127096 45.27663857178399
830 38411.02066737203 43.239028272884156
831 58520.67414027242 43.03637248064782
832 14745.151431379589 20.553500471370505
833 7460.774810133237 26.39357064784107
834 49393.851191816604 42.11607676531579
835 41893.84880763081 45.68043452288415
836 22255.88026743916 27.243525800960334
837 14026.07146006611 30.17607432390955
838 38878.10173731832 44.595629987972046
839 45246.843726454055 44.26468805961158
840 11181.628138838081 21.60015803362636
841 23282.01237422017 37.881762800472046
842 38738.65071040182 44.690997419612664
843 59497.86129694967 42.93862086321618
844 32102.906138716025 44.51695185686852
845 16939.38675623921 22.10083704973964
846 24673.344523725784 35.03027659441735
847 19294.461638746536 22.61820536639003
848 22520.028979597362 35.86474162127282
849 59510.42595606831 43.71348124529626
850 6872.5699494459805 25.975138960140026
851 36730.62983256368 39.14299708391931
852 45235.3686402419 40.156276045100945
853 45196.403891859336 46.12690746137986
854 20234.035880384716 40.02991419817712
855 21194.42406397847 26.769072828548225
856 30122.92566996602 44.55033045794275
857 45163.161189375205 46.0718157397089
858 16656.047732649124 22.692115125911517
859 45083.02870493917 46.15730583021532
860 28199.438483534137 33.32081538225916
861 28490.11126261739 33.99315577532556
862 38842.16252070455 45.453936872737664
863 45260.29053431538 47.05179734796128
864 5551.742942152271 20.901591596858786
865 41595.136554060264 46.51013117815759
866 38796.47198420553 47.65930872942712
867 11590.899855909614 32.667548475520874
868 16579.603583631786 30.82218867327478
869 44376.47762995747 43.18180781389977
870 16945.32099467305 30.085475263850956
871 50988.92632227926 44.12832957293298
872 29236.699969587604 43.02445155169274
873 34662.04586726217 43.52513056780602
874 23737.675578413287 35.049350080745484
875 12456.306845960886 22.754103956477923
876 45734.69820719746 44.32860117937829
877 45396.01746302632 48.782260236995484
878 40499.50066309957 47.985942182796265
879 59970.77170115499 46.36231165911462
880 17000.448138532913 21.71459895159511
881 45751.66645747213 48.95098052796101
882 14510.833651838573 23.283393202083392
883 46772.52712946919 48.19832580390746
884 9161.059291181826 30.190379438655643
885 23139.59065180806 40.051371870296265
886 41920.39433222798 49.52135783221032
887 45546.93880778341 49.17445209614196
888 32808.703810987754 33.0370972731283
889 27825.77458125142 42.24720698382165
890 38899.29476481466 44.58609324480798
891 18382.70130854634 23.05451136614589
892 32454.094321546832 48.694045362727906
893 30936.262042341506 42.898089704768914
894 50124.21074610738 44.636161146419305
895 41965.46498042134 48.08130961443688
896 11875.528724012644 21.96732264544277
897 22749.26367503194 32.18832713152674
898 41888.08384638814 50.417811689632195
899 23793.35346919087 41.99209910418298
900 6059.42669611956 22.344024000423232
901 29569.487006483356 46.18588191057946
902 33087.23154765157 38.11779719378259
903 29719.168574629104 36.26051646258142
904 29834.622771559036 46.357543287532586
905 42884.48992472677 47.16578227068689
906 51982.752711592 47.25638133074548
907 45801.660449323936 56.68583613421227
908 32443.65874033956 45.58029871966149
909 34822.99986582784 52.02952128435876
910 17053.546340284618 22.720725355403705
911 45540.782840071 56.55224042603317
912 22943.93959742574 28.800399122493538
913 44559.90734797505 49.180419264095086
914 40992.96751719503 47.66169291521813
915 22621.855170545852 42.771727857845086
916 32923.075587568565 45.35380106951501
917 61583.64239436177 52.58026820208337
918 7702.867419538756 28.41177683855799
919 46127.199561415 56.37805710316865
920 20918.40210658101 29.59194880511072
921 60913.87692194966 53.9130280592611
922 40921.02232676534 49.268634138362664
923 51713.926226911826 44.52410441424157
924 18612.868220625198 23.285777387874404
925 35723.32802516012 34.81569987322595
926 41175.11692744283 47.456652937190796
927 34945.549399671836 51.59083109881188
928 17874.967486677444 31.11544352556971
929 45429.546267805374 55.84569214987829
930 17474.55540400532 32.8535149672201
931 25261.00102168111 30.908019361751347
932 32673.701674757285 45.80441218401696
933 61565.26270609884 54.537684736507195
934 41343.56442194966 47.79043894793298
935 9716.059596357609 30.11646967913416
936 16566.669375715526 22.978217420833392
937 45930.86901408224 59.03187263273186
938 56845.08028727559 46.37661677386072
939 63679.28448420553 54.50907450701501
940 28816.482455549514 37.62427073504236
941 46149.83025294331 52.816302595393914
942 52636.28426295308 47.31598597552087
943 39474.729926405234 44.70530253435876
944 24215.838343916213 42.08269816424157
945 13353.564173994335 23.788840589778697
946 33415.96308451681 38.81636363055017
947 46300.26999217061 50.53584698906964
948 47354.23985224751 44.967562971370484
949 53668.362529096885 50.64430933977868
950 26087.56008845357 29.46320277239588
951 61589.82220393208 45.75196009661462
952 8091.115386305116 29.217631635921272
953 45872.29672175435 50.62027737948592
954 26751.903922376907 43.67533427264001
955 43577.90175181417 47.840506849544305
956 35122.76831370382 50.37012797381189
957 20015.329749403274 34.822852430599
958 41214.394004164016 48.10038310076501
959 60344.80992060689 49.609572706477906
960 5975.448520002615 22.49422770525722
961 25663.136870680133 44.695765791194695
962 39571.52548533468 38.38244181658533
963 35173.136622724815 53.669841108577515
964 32691.733271894736 55.25770884539392
965 42517.8712914565 46.138198194759156
966 21754.626662550247 32.02143412615564
967 45385.469825086875 59.830577192561876
968 20944.06309824971 25.050074873225967
969 32004.002959547328 37.135512647884156
970 39605.95312815694 47.30168086077477
971 45818.27822428731 59.2689907468565
972 6493.300826368585 24.072558698909557
973 59797.67266016988 49.802691755550164
974 41007.70655375508 52.56119471575524
975 17633.156211195263 24.0487168409994
976 24540.938765821735 44.20223933245446
977 45541.061789808555 53.133399305599
978 50067.593486128135 52.568347273128296
979 45904.10891276387 51.26181345965173
980 16809.839637098587 24.30144053484706
981 36157.988936720176 49.7621605971029
982 42012.66470652608 54.97637492205406
983 49011.735350904746 53.53408683579238
984 35067.638785658164 39.29081660296228
985 47172.66026240376 46.908290205257195
986 23371.66252833394 41.086108503597046
987 30746.008784590045 41.23869639422204
988 35983.10652476339 34.54628687884118
989 43925.33722620992 49.824149427669305
990 20714.23235636738 26.060969648616584
991 48219.57531672506 55.72723974030291
992 19289.154441175735 34.5939705946615
993 65381.79341059712 56.22807246233727
994 57367.01670390157 48.38648539568688
995 46894.297034559524 49.75977641131188
996 49174.649150190635 52.63272028948571
997 48145.43905955342 55.280329136652256
998 43848.761946974075 53.9583275892904
999 40569.29531794576 40.46622019793298
1000 7401.589782057065 25.39578181292323
1001 22062.401206312454 28.40700846697596
1002 53893.23893290547 56.6596100905111
1003 32029.9357483962 53.99885874773767
1004 34119.54823237447 46.8629906752279
1005 63836.51676875142 52.92597514178064
1006 45917.86328059224 52.244098005550164
1007 35142.65242320089 51.46208506609704
1008 14566.690356550487 26.05620127703456
1009 48863.739402113235 63.22804194475915
1010 42577.10877162008 58.245093641536485
1011 65793.59951716452 58.13065272356774
1012 26524.95566111592 37.39538889910486
1013 48696.84639674214 60.36721671468954
1014 22266.823680219924 27.388961134212288
1015 22994.794280348102 37.50744563128259
1016 32510.61382990865 48.66543513323571
1017 37962.61254054098 51.175982771175164
1018 43963.417441664016 51.91508036639001
1019 48298.28444224385 53.12624674822595
1020 9164.475829420351 31.051070509212284
1021 48826.14317637471 52.47521032135761
1022 56963.736445722854 55.30300837542321
1023 21656.493575392044 38.699538526790406
1024 7742.401988325379 24.265677747981822
Here, we show only results from our FFT code and FFTW, along with a couple of $O(N \log N)$ scaling lines. There are four things to observe in this plot:
The scaling behaviour of our FFT implementation has changed: instead of the upper bound to execution times scaling as $O(N^2)$ seen in the earlier benchmarking plot, we now have something like $O(N \log N)$ scaling for all input vector lengths. This is due to replacing simple DFTs for prime lengths with applications of Rader’s algorithm.
Because of the use of the next highest power of two size for the convolution in our implementation of Rader’s algorithm, the upper range of execution times display a series of plateaus– these all result from prime input sizes, where we need to perform a forward FFT and an inverse FFT both of a size given by the smallest power of two greater or equal than the input vector length (we only need to do one forward FFT because we pre-compute the FFT of the padded $b_q$ series in the Rader algorithm as part of the FFT pre-planning phase).
Although the overall scaling of the new code is $O(N \log N)$ as opposed to the $O(N^2)$ scaling of the original code without Rader’s algorithm, it is often the case that the new code is slightly slower than the old code for a given input vector size. The main reason for this is that, for the base transforms for a given input vector length, we now use either a specialised hard-coded transform (which I’ve so far only implemented for vector lengths 2, 3 and 5), or we use Rader’s algorithm. The prior version of the code used a simple DFT for the base transforms in all cases. Although the asymptotic scaling of Rader’s algorithm is better than the simple DFT ($O(N \log N)$ compared to $O(N^2)$), Rader’s algorithm is more complex and has comparatively unfavourable constant factors compared to the simple DFT. The result is that the simple DFT can be faster for short vector lengths making the overall FFT execution times for the code using Rader’s algorithm slower. (Rader’s algorithm is good for larger prime input vector lengths.) There are two things we can do to fix this. First, we can implement more hard-coded straight-line base transforms. As described above, this is kind of a hassle, but we can cheat by translating FFTW’s codelets into Haskell. Second, we can use empirical measurements of FFT execution times to decide on whether to use Rader’s algorithm or the simple DFT for small factors. We’ll explore both of these issues in the next article when we look at various optimisation approaches.
There’s still a lot of variability in the performance of our algorithm for different input vector sizes, particularly compared to the range of variability in performance for FFTW. Although both the bottom and top range of execution times appear to scale as $O(N \log N)$, there’s quite a wide band of variability between those limits. To some extent, this wide variability may just an artefact of the overall worse performance of our code, so we’ll come back and explore it later.
So, preamble over, we’ll get to optimisation in the next article!