Haskell FFT 13: Optimisation Part 3

In this article, we’ll finish up with optimisation, tidying up a couple of little things and look at some “final” benchmarking results. The code described here is the pre-release-4 version in the GitHub repository. I’m not going to show any code snippets in this section, for two reasons: first, if you’ve been following along, you should be familiar enough with how things work to find the sections of interest; and second, some of the optimisation means that the code is getting a little more unwieldy, and it’s getting harder to display what’s going on in small snippets. Look in the GitHub repository if you want to see the details.

Rader’s algorithm improvements

There are two things we can do to make our implementation of Rader’s algorithm go a bit more quickly.

First, so far we’ve always calculated the convolution involved in Rader’s algorithm using a transform for the next power-of-two size greater than the actual convolution size. This is based on the observation that powers of two usually have a pretty efficient FFT plan. It also allows us to avoid recursive calls to Rader’s algorithm if we end up with a convolution transform size that has large prime factors. However, obviously there’s no reason to expect that the padded convolution will be faster in all cases. Sometimes the unpadded convolution may be quicker because of specialised base transforms (e.g. an $N=22$ FFT takes about 3 µs while the power of two needed for the corresponding padded convolution, $N=64$, takes about 33 µs). As in other cases like this, the best way to deal with the question is to test empirically which is quicker.

Unfortunately, in order to do this, we’re going to have to change the types of some of the planning functions to run in the IO monad. This is because we’re going to have to recursively benchmark different plans for the convolution transforms while we’re deciding just how to do the Rader’s algorithm base transform. This isn’t all that messy when you get down to it, but it made me decide that the default planning API should also be monadic, with signature plan :: Int -> IO Plan, since there may be reads and writes of wisdom files going on during the planning process. To make it easy to decide which convolution approach to take, we also record the execution times of the selected transform plans in the wisdom files, so once a plan has been generated for a given input length, we can just read the timing information from the wisdom file.

So, in principle, what we do is quite simple. When we’re constructing a Rader base transform, we just determine whether the unpadded or padded transform for the convolution is quicker. We save the relevant FFT-transformed “$b$” sequence for the convolution and record the transform size that we’re using for the convolution. We can then set the code up so that everything works the same for the padded and unpadded case without too much trouble.

The second thing we can do is to try to avoid conversions between mutable and immutable vectors in the RaderBase branch of applyBase. Doing this effectively ends up being slightly messy, because what we really need is a specialised version of execute that works on mutable vectors. I call this executeM and it has signature

executeM :: Plan -> Direction -> MVCD s -> MVCD s -> ST s ()

taking a plan, a transform direction, input and output mutable vectors, and running in the ST monad. This allows us to avoid a couple of vector allocations in the convolution step. The original convolution code in applyBase looked like this:

let conv = execute cplan Inverse $
             zipWith (*) (execute cplan Forward apadfr)
                         (if sign == 1 then bfwd else binv)

which did at least two vector allocations, one for each call to execute, and possibly a third associated with the call to zipWith (though that may possibly get fused away). Instead of this, we can use mutable vectors and the new executeM to avoid some of these allocations (in particular, the multiplication involved in the convolution can be done in place), giving a slight speed-up in some cases.

There are a couple of other possibilities that we might explore, but we’re getting to a point of diminishing returns with this so we’ll leave it for now. (One particular possibility is to experiment with padding to other sizes instead of a power of two: any highly composite size that takes advantage of specialised base transforms would be good, and the best option could be determined empirically.)

Compiler flags

All the way through, we’ve been using GHC’s -O2 flag to enable the full suite of “non-dangerous” optimisations. Now, without getting into lots of messing around with specific GHC optimisation flags (of which there are lots), the best option for getting some more “free” performance improvements is to try a different code generator. Specifically, so far we’ve been using GHC’s native code generator, but there’s another LLVM-based generator that tends to give good performance for numerically-intensive code that makes a lot of use of Vectors. Sounds perfect for us.

We can enable the LLVM code generator simply by adding the -fllvm option to the ghc-options field in our Cabal file. Benchmarking with this version of the code reveals that we get, on average a 17% speed-up compared to the native code generator (for code version pre-release-4). Here’s a histogram of the speed-ups of the LLVM-generated code compared to that from the native code generator for input vector lengths from 8 to 1024:

1.05244031897248 0.963743600627491 0.931961289329561 0.93224761522285 0.947264875711808 0.92659561189943 0.905305035837386 0.832628223275681 0.931291017179891 0.966273780642196 0.941829026168194 0.949171318407216 0.943439977382738 0.939046643520132 0.957722140802244 0.910213927269674 0.961214877079652 0.794660853011878 0.91178028664853 0.917529420573993 0.907826790709158 0.805425686549305 0.879643660174976 0.808154410409529 0.837417772549392 0.917193589095891 0.894234582213008 0.915699534338577 0.925122460937026 0.894165913267138 0.966699306477892 0.882482223274525 0.863396461163997 0.878633966171333 0.875016526246948 0.868996020453305 0.896077537830065 0.850559977266995 0.917159201968766 0.798471429555276 0.8642120477022 0.903383755713734 0.824929342623959 0.88166259458636 0.874061652819158 0.869580185925691 0.88033071238122 0.881363755086047 0.858904938760706 0.961780232383833 0.796716677453264 0.801399969629395 0.842295830090548 0.845207611225441 0.796121521097552 0.884545221979207 0.759061339789604 0.862293208020415 0.876787269264349 0.869019209466159 0.874736960675178 0.919948484549157 0.836209061104246 0.832373551170287 0.872778040404262 0.856118627797577 0.873545145413546 0.804945776945542 0.956137688191692 0.864968251968581 0.847350756321035 0.839097346907303 0.814477880665038 0.889508403927967 0.8533038656117 0.761256154350629 0.827837758066341 0.865805922351558 0.847253427904907 0.785238644139046 0.889951977047002 0.893655398151388 0.815182731036954 0.851518291541223 0.89340845142892 0.78889310762893 0.797965526058581 1.03433137290734 0.762533521682859 0.823494334138154 0.814853278931339 0.820483843570467 0.787556422108773 0.801960947956207 0.794969837022505 0.736312272589061 0.86914295108155 0.809075133995224 0.819077786397516 0.749791830259736 0.868602672308836 0.86799272241481 0.83304735423269 0.866306141789508 0.737478356009534 0.791472386392478 0.90018976597745 0.883539696303863 0.777636375370075 0.856772677244313 0.789787749362994 0.852318750514246 0.812594443747026 0.854616965486094 0.837930550872471 0.851658223906933 0.776852638731867 0.794124212339041 0.843885658646829 0.825398708442419 0.802644675381312 0.850580529707276 0.863106209956301 0.84802355213607 0.864662466550007 0.878789982797906 0.853172782413889 0.843358721047291 0.879084741310126 0.852486974180997 0.880958515923011 0.730822547118574 0.805171130796048 0.790104816748994 0.828062671505572 0.835720819958955 0.85461177751645 0.772299915572331 0.858302316652476 0.888380595395674 0.854613866537792 0.705100952531419 0.793761336476277 0.812963776463257 0.857410122218767 0.859766830098765 0.843552256503313 0.771087542417166 0.869107526173836 0.84997729069053 0.810415980323161 0.847646965394981 0.803927721713599 0.879999605290764 0.887893352876251 0.867005436644342 0.840167424023941 0.845900120730139 0.766103738847846 0.730587576144722 0.83371695343999 0.829332667185718 0.881652549034348 0.858449010712449 0.855927767252239 0.722934432840815 0.778104796941868 0.779477456876357 0.881394993025833 0.815889398026689 0.884882109619103 0.727119906362312 0.809386580817056 0.842465248430373 0.827554251442433 0.82063433166099 0.857629155106988 0.861844577330117 0.781490333437551 0.818956338831358 0.797662018024215 0.871736737491071 0.840497284607876 0.751989386724812 0.771928867590687 0.797887957990168 0.819734704530058 0.860378853964783 0.843531461571738 0.838923730779773 0.867787310610545 0.86913650478728 0.814698353224251 0.857136391805232 0.806535738523959 0.775016163471249 0.849573965173498 0.846105040326569 0.766316784994453 0.860881815847723 0.854098378978241 0.845128306877828 0.840343035171069 0.820756582673544 0.845577169294666 0.822683474823585 0.767096198821415 0.842220821831635 0.880926558307682 0.760647022149937 0.87129797458002 0.837254793092686 0.780614984143943 0.830474012648503 0.874605421112823 0.741667463900475 0.7811273647031 0.813896929959134 0.812058481369659 0.746599923388857 0.848552414229375 0.741632494330616 0.852249456078546 0.873252081595062 0.77648596831951 0.741264859630924 0.864581334521661 0.788504789513442 0.796464094489702 0.820992263576079 0.783357613270366 0.743009774815679 0.829334942021056 0.828078224443311 0.875108932519018 0.886795311659002 0.826349753393723 0.860871334780163 0.851774235500315 0.827543007592983 0.773105055805101 0.763861996918486 0.803151871384671 0.810774360966234 0.85081852087029 0.851278306008834 0.843713125794054 0.780982882360374 0.779153526081754 0.787991265208364 0.851292462910008 0.855099649910118 0.857694983224144 0.755750050813069 0.854390979866743 0.855415882304001 0.876589100468537 0.827777073018583 0.786162298544507 0.879478237188692 0.833991257149631 0.825186163028938 0.840539404534123 0.806833139687941 0.780439848344537 0.848998033587016 0.858335472467709 0.711961477800522 0.846779158292132 0.85169365736207 0.749433840057294 0.763855149814444 0.818817366042914 0.786091640325543 0.782015302793959 0.68481251396519 0.814331647627071 0.788863102007391 0.854499286143074 0.838190081359508 0.829355494933916 0.819257250597647 0.773641750092803 0.801615945686548 0.837828011662174 0.830110282104668 0.845760976642923 0.797162224384594 0.871928213972045 0.871645585007309 0.750451502599893 0.826357525472589 0.807419741623003 0.843573711173788 0.800900608516007 0.804330400353783 0.7793064768227 0.820760676327265 0.869167097967885 0.881199914306575 0.857842177219516 0.768340560615675 0.752153377028867 0.70358766104788 0.82137700779644 0.840599683769358 0.848518525544256 0.826254619201571 0.798593534459328 0.716160455939141 0.84277212825862 0.812908422250371 0.767457200376808 0.769485014193441 0.752751356686632 0.805152876715233 0.864722414200345 0.76737056016324 0.867564927069997 0.862116884836568 0.840021763312132 0.796314521065349 0.872515743279342 0.864639726895049 0.758126455503294 0.864164095909887 0.739454489269252 0.848926156077698 0.831464629916491 0.838722496793492 0.841100838150485 0.806327301857313 0.776357636843031 0.73987578975606 0.812915221572417 0.887496659498511 0.829722530839381 0.766434637671443 0.749579624140402 0.711932603645938 0.786519353087248 0.711442342349084 0.783399732818392 0.867063851355597 0.772343698561593 0.791997568340553 0.805178176210819 0.815697361244756 0.87032785144098 0.857020979085122 0.737022707348134 0.702220933274163 0.84478786432239 0.924137330848254 0.832812352990996 0.817903348054378 0.842474672831475 0.83314871116218 0.8280062144719 0.784495477159197 0.747415822647535 0.809909852561337 0.849590556901887 0.820270804901155 0.751325096867819 0.717613832237912 0.790390689801502 0.783969586259727 0.797871502515798 0.832044581897426 0.855761364043146 0.84603130991059 0.768964869736751 0.841039968003341 0.747726820463687 0.72748229020587 0.774056580708402 0.858298385467909 0.806944602975838 0.849171083899882 0.815488332596752 0.834716529060949 0.852474080431683 0.821182049163898 0.824136522144883 0.837428462115658 0.822009296717942 0.80708809190219 0.857242350668384 0.831091560808217 0.864069990880686 0.824918601501028 0.803268058048539 0.811999274432107 0.849216035689032 0.842618326070755 0.797322461763732 0.835470342767359 0.772992445847372 0.855181577514516 0.823190108116154 0.824691741071972 0.838725277252122 0.873633845459171 0.810432695621463 0.791192844301742 0.818623668674434 0.770734539965661 0.770556856810762 0.738303592212578 0.801466092394887 0.721050500914703 0.820501254690437 0.820334666102133 0.836168009066191 0.790946395055056 0.838583391461645 0.749857494364995 0.821004892145144 0.820301196029515 0.759355705985485 0.803974101355254 0.835789551866731 0.719924865658823 0.83812433095292 0.840967172474133 0.760140792983527 0.770102967960922 0.862941716097654 0.852926035662134 0.851062522417908 0.728492330186638 0.804579532076071 0.870866579891682 0.7976471291098 0.786326388071553 0.854741751526465 0.863584402533512 0.747701276206668 0.742850869486622 0.739740922100927 0.75856101532849 0.816562283594862 0.822517345011873 0.813268124670259 0.811025958094364 0.760480609008414 0.832063181610761 0.802885495236863 0.724519976024516 0.753693292773487 0.851582210217457 0.762152726690172 0.731314957509002 0.831842227072932 0.82735768806154 0.705386755674072 0.757585140074305 0.715473381703412 0.711028473801613 0.837542802031279 0.838248046253848 0.791362694769826 0.838367516356212 0.773336577529352 0.843256274135755 0.826639907594953 0.762013587839558 0.800960012689983 0.877026653099864 0.749706983849598 0.738036772654572 0.842648289930936 0.857311241016674 0.849595713024602 0.854787130679551 0.875388778779291 0.809028280092945 0.886546683195939 0.890323587952932 0.86654114750938 0.87982668989675 0.790472178717122 0.828232000993893 0.869504408771582 0.859340580383746 0.815684051665177 0.894027526932688 0.771600756111267 0.797983756535787 0.808814837713056 0.776630662564512 0.884745715228819 0.79333617880333 0.848707981561639 0.756688287600476 0.869410379392937 0.804754489210018 0.844082429370352 0.889287313721126 0.876005427599644 0.800494468776284 0.77142712114411 0.866315844294301 0.788936393747412 0.800702620252742 0.771904703588709 0.784569096519979 0.82027707437477 0.845067092912841 0.857300645809096 0.723517000628143 0.845091625769789 0.855518663426561 0.777414538016003 0.773120641298394 0.830921461869603 0.793165669934941 0.852792139918794 0.761152507030018 0.826560567061301 0.85190522535097 0.841820832650923 0.793117671916772 0.780036934635186 0.828048608759255 0.87055232160353 0.776513463099501 0.916267726778191 0.770102207202173 0.884911307626108 0.923764223550285 0.883881052137324 0.899656778760871 0.864246745463143 0.860308557466085 0.786006236697224 0.901162608501265 0.93904586398009 0.903648082267975 0.933444947015812 0.913655000925839 0.842631373041246 0.845333333348913 0.828216960909357 0.87455680872839 0.900938265839488 0.915325984267702 0.781296839597627 0.767075113853872 0.827848457519628 0.882816910757244 0.883243049584682 0.872363947095607 0.850376990344293 0.87913052271662 0.889662947895348 0.857824895035262 0.771946760325433 0.897450684929767 0.921508796621271 0.965175854787775 0.781668509096511 0.820391941660037 0.84110748261077 0.79207767242239 0.854724848359955 0.788711967835297 0.778502373200251 0.793399255825629 0.90277635999521 0.826669119391874 0.790443994198453 0.801478139556927 0.847329307150599 0.864203921315108 0.86401529557919 0.869037042019913 0.874815344270521 0.758109665431334 0.87929034717991 0.803515992231748 0.852150512549607 0.838743605429762 0.911971659307853 0.888326478708239 0.918995340376392 0.891104473511629 0.785886028522187 0.916457418595438 0.834081113616276 0.806776302825434 0.83660615314949 0.863150135264816 0.869232470109966 0.874522555300379 0.820899172747772 0.874746527693308 0.83525178064699 0.850101653874434 0.765948731213874 0.808608493531803 0.835176402321796 0.88439898262533 0.827181139359263 0.856802275023476 0.914174907276343 0.859410441735268 0.807841320539497 0.804949703019537 0.79968670098377 0.741952346736583 0.797433607879379 0.832724624728327 0.721871776615257 0.916335870016036 0.857107108708873 0.821986286919309 0.874667386044399 0.778368322602107 0.892027213457752 0.889654520729182 0.845051781961317 0.837153566258392 0.814119057467093 0.830849492386315 0.732552829084376 0.838682337626625 0.879360477890897 0.842014081896415 0.829341637846134 0.827774240677431 0.799498997533064 0.811829476690923 0.811090639589983 0.714270664575615 0.772798317976526 0.860771145355928 0.873967583824117 0.688217407182588 0.899924146476079 0.836284705967669 0.865717671639708 0.806400697393636 0.918125247470427 0.745504432819657 0.888118515029017 0.894508891378426 0.863903606945564 0.866374241194829 0.80654485233653 0.762816267176269 0.823440894395537 0.836110467433496 0.898986247602091 0.823512657150508 0.773506958822561 0.865736501092419 0.85862001981996 0.751508500177247 0.746100036795737 0.746543235503184 0.845820623610577 0.818982931753248 0.800208087506291 0.819322867008355 0.845564816218009 0.805182474363679 0.807240728825476 0.820030577847678 0.808097007701015 0.817107957041464 0.816200184141528 0.758628432611322 0.793512243703041 0.723279103519209 0.821908461558485 0.8847215803231 0.809537179390113 0.741545697305162 0.812856923691803 0.791119542073137 0.787216219534629 0.731173236613738 0.742913542926291 0.831926540941896 0.70973881690631 0.751750893930522 0.786964899947718 0.800804440887047 0.712076191026775 0.735027323696645 0.791248938450461 0.775291981844543 0.882415526083172 0.889395168491388 0.758562942781436 0.808332218519816 0.8256134857236 0.819823385856714 0.838240256495804 0.739002317872295 0.827537098148779 0.837760630474419 0.906580030278852 0.773827872582427 0.860102927899598 0.869884266813434 0.77227893730102 0.770341622401125 0.743057366057318 0.753036941229513 0.846859390531386 0.79301363816758 0.899832137735555 0.848743388452746 0.826028754193106 0.787835522414094 0.865908107331836 0.862182722042402 0.89626055663776 0.90034255972639 0.844494232673807 0.858763178358024 0.827212782983216 0.831577717112743 0.800955400363091 0.842234433035433 0.769332474599608 0.872727112486682 0.837726039387983 0.784294900679117 0.925914344908217 0.835379499818658 0.86644518561184 0.727322210202352 0.782794620082892 0.742811945418305 0.682595851938926 0.713283629411802 0.83372150361507 0.786708077685485 0.823988837999932 0.866385629711783 0.788230077971434 0.846998254400185 0.813819667358532 0.845634351128485 0.910577387017404 0.879919244584013 0.889972731067391 0.834619189140998 0.888204075575039 0.853368357341649 0.860792066891498 0.901021715682968 0.778648619468803 0.827368016861152 0.7423698310687 0.797696312669282 0.780147188961232 0.779084712711395 0.847225652756616 0.82880697395792 0.795855029402935 0.754390848750533 0.879259747592127 0.771742877409265 0.845345379108353 0.902036326293642 0.836490744630964 0.848049941422824 0.873270757117502 0.865244986024917 0.878135585987939 0.827282430445656 0.865661444432269 0.892612941200488 0.899105928354752 0.74850366231174 0.866798373540923 0.899985912556306 0.873177109485688 0.857505911203368 0.886753359118435 0.841611539304978 0.907775091810807 0.885084672984438 0.88232228909841 0.785295642282507 0.822986899364814 0.823245231133693 0.828898839943932 0.954016014290808 0.840568173934346 0.872754930329494 0.884291044171533 0.868599277408849 0.815389265008108 0.829104580184869 0.84640359633147 0.833809719689428 0.857985904800948 0.896163705674645 0.819477998654736 0.872669823321358 0.91209928589645 0.907774520156003 0.830155860234269 0.839660749796558 0.851378708692762 0.846174410056969 0.876365650263634 0.742867758817161 0.954232098428304 0.755834268862333 0.804964840519329 0.842306903627508 0.827047282945842 0.784102526458204 0.857844440094726 0.821277470899465 0.779503730381804 0.87419177443334 0.732558846903309 0.902941142122641 0.782501106534749 0.776007437573304 0.875289884365872 0.89936166150934 0.741897717063947 0.769174904017063 0.857721650192313 0.771076087417529 0.86867800029826 0.85154529897666 0.856468492190296 0.837423450668859 0.826860856825276 0.916764391282027 0.848183724755608 0.715877402896954 0.851577057588681 0.868301464066147 0.909327894875292 0.750008506376467 0.862684708136944 0.82248773261676 0.779616345792386 0.747243032243018 0.922731823185466 0.875699970227932 0.897343407988988 0.886923912932727 0.723498486778963 0.754079485535401 0.831246857036462 0.759900519324741 0.875029807330289 0.864244259224625 0.807855340127217 0.833934503733648 0.803660255123202 0.872007276386758 0.969113680013422 0.857113097296137 0.847809114538051 0.788098647065277 0.906209939176726 0.782167448118713 0.734553456153857 0.838481630955225 0.82570135813595 0.806478295204552 0.811278037658163 0.761410382473865 0.810607740932749 0.775917001071465 0.771006405639151 0.729120407458795 0.77961160610813 0.85472281307863 0.860045398316728 0.876782765907744 0.757112904080706 0.785999720468068 0.77018729104408 0.745710390109575 0.799798990566601 0.80308975917059 0.738215311463622 0.74717956339214 0.809019866193458 0.810062702442329 0.849052638153784 0.853025974729656 0.8319870015621 0.841611850761867 0.847740026774991 0.71337717598631 0.748430991532157 0.913238217174339 0.839389677144017 0.828129658733459 0.826646896726394 0.809467851540674 0.716659591985141 0.866649930686233 0.754966193765379 0.880912697418699 0.880879239587827 0.795736693501123 0.82620892812894 0.90394941900709 0.751160052903302 0.832889942540265 0.901586303712888 0.757839633806517 0.860833299786589 0.795023330515327 0.76749524076925 0.804515423693265 0.801777734603445 0.880116650372584 0.767854952270867 0.707201835180963 0.755198704637607 0.851260196402785 0.908760699545556 0.86713543174194 0.916050898230416 0.871718780840166 0.861182398281583 0.78238418065833 0.920398228946103 0.863678087302624 0.83417608166993 0.904182109741157 0.848861850091504 0.772583850492239 0.970246725128332 0.872622004345513 0.857387451650762 0.741541709208255 0.944420907369366 0.920642966927199 0.838506203772232 0.792012040306128 0.806824763480195 0.863317653805443 0.751057060323939 0.907111190481545 0.79489859376045 0.799322743799463 0.789952251181145 0.798746816514525 0.859225794450341 0.848025013197521 0.807059559806975 0.792498633437368 0.903314078607686 0.92678041359083 0.867946514803042 0.750787595877541 0.928373551491665 0.764346311920935 0.904951075817293 0.879971774659337 0.873878361898319 0.758990542297091 0.886460810309059 0.852161383154553 0.839808396449532 0.87369898294028 0.844879855164588 0.724696677758059 0.812073868246767 0.86318661119882 0.898967765177799 0.762248003467174 0.839070509151166 0.862512038569583 0.915328012575352 0.905841926604032 0.787570014868761 0.881163827006747 0.826030174164938 0.850229668109661 0.753384609875482 0.731240988815286 0.717573371638048 0.856845387440207 0.797337340824378 0.838602189759803 0.694801673673559 0.78592572017134 0.814978271863107 0.828942411914391 0.721505259488582 0.820594420258562 0.828398199045805 0.804888897827744 0.817546764854064 0.776985043358247 0.811783978355165 0.729620011215467 0.824397959350228 0.824499113505605 0.809812051516555 0.816583828390477 0.715627313972642 0.725860821618945 0.79270024779958 0.778951913025012 0.810269481018692 0.798798081539445 0.746174575327272

Final benchmarking

We can benchmark our final pre-release code version (pre-release-4) in the same way as we’ve done before. Here are the results shown in the usual way:

Size FFT FFTW 8 0.3876487521157585 0.22610646900817707 9 0.4040362621392692 0.24952405139610367 10 0.41976656161115544 0.2597171216824601 11 0.4827029112296101 0.2858073248754566 12 0.4825251638391707 0.29104777697019724 13 0.5459175298700899 0.3318301329658772 14 0.5282560003392216 0.33064482663763445 15 0.5726726906482985 0.34729216753780645 16 0.5836267112779879 0.35449756701772894 17 2.4140906458896967 0.491571608449439 18 2.532748213229658 0.4261638671770866 19 6.524682218794835 0.5439286316062765 20 0.7332278590174395 0.42935310272072363 21 3.1757468436476497 0.47082918679438596 22 2.8078729970786815 0.49926138480035764 23 6.77071394100463 0.6740530556157257 24 2.8251680868295184 0.5059985334645506 25 0.906571284338316 0.5394891572786834 26 3.0114605263439342 0.5714040690389824 27 3.4068906725012593 0.5817709787511117 28 2.9387450950931973 0.5881545070147131 29 6.931523044892982 1.8166656472853275 30 3.0029936556909225 0.6242836860257268 31 7.032738908796958 1.9764060952833749 32 1.0875933242065596 0.6110964419120347 33 3.8010996068184055 0.7090859976247579 34 6.993187332141496 0.9202332692218929 35 5.195615485302241 0.7359392443315164 36 3.8889414023175384 1.740371701972827 37 9.307707459570794 2.21959304596697 38 15.046622966873434 1.0608113825817964 39 4.1614660577915705 0.8222182757031486 40 3.4360293555450627 1.847660062568531 41 8.78351473488977 2.4103279092482204 42 4.034588933349073 0.8562280392436751 43 10.03705473678125 2.555763242500172 44 4.951262250700909 0.8971136959871407 45 4.2326172559621025 0.9004380058198389 46 15.50015182492614 1.3271150023548666 47 18.202244902281144 2.6702041604689217 48 4.259229580808425 1.964485166328297 49 7.702283980517129 1.0082275379289642 50 4.178450278509392 0.9726104241967578 51 9.768291344058866 1.3520153678220892 52 5.484833903323636 1.0329210041474475 53 13.07926472576791 2.9706115701368887 54 6.944109192682275 2.083694455879079 55 6.237029637121791 1.1124055472126637 56 5.367024786095375 1.0724541956668014 57 22.044061215683104 1.537206402689509 58 16.30646324155119 2.705966947334156 59 18.89007312226661 3.3282394387892302 60 4.789786071220809 2.162372586982595 61 12.088306850837494 3.6119575479200887 62 16.473053836795906 3.061210630195483 63 8.592757885259042 1.2575942435418936 64 2.89954291633475 1.1353916329834564 65 6.897967896919883 1.282200478413421 66 7.789204201490659 1.3005995562963661 67 18.225825479556672 4.074489591377119 68 12.8497788672145 1.700390237194086 69 22.914408190460332 2.0006329127688396 70 6.790368554520084 1.3190073788964845 71 16.27412739503847 4.539405820625164 72 7.934271789719766 2.5796051004103284 73 18.39948908485 4.90657043244157 74 19.92496450016381 3.5308952310255575 75 5.851398066461159 1.3903569401899323 76 29.406960362927155 1.9434959555750226 77 9.442406593469983 1.524305627883382 78 8.531861469230936 1.5026866981551106 79 19.93692155314603 4.990016935127117 80 6.446089316095214 2.803718564765796 81 11.01539085323372 1.5600438017920364 82 18.983542566683216 3.881370542304853 83 35.72721512247467 5.609905240791178 84 8.516114947148626 2.851402280586108 85 15.97545661452692 2.1386490174777535 86 21.66732012427279 4.1579360940626655 87 23.84539011542744 3.740703580634932 88 10.934604392546413 1.6496039517381134 89 25.268274199247685 3.9175045125562105 90 8.881918029770956 2.9610748269728266 91 10.402671273282333 1.7557747764004965 92 30.243719967880427 2.486334062901442 93 24.187606672768464 3.998195646064618 94 38.57353515618915 4.56324767853532 95 36.3744893460085 2.455798225677392 96 6.628479368112879 3.054058072822435 97 16.465066814396003 5.917465207832192 98 10.337390228254456 1.827028539368373 99 12.19877253443776 1.9392166533848907 100 7.835415739159123 3.1684989907911842 101 19.175797780323965 6.685173032539223 102 19.578291935675438 2.522175455359774 103 36.946135414912106 4.96940510688756 104 11.960629156638626 1.8994316642135847 105 10.892671246665284 1.9618571320441285 106 27.895866076107165 5.259429929511881 107 37.15846040507871 5.124104474425837 108 12.14228561819381 3.259098050849778 109 28.78308113756943 6.649410245673988 110 13.872359315532112 2.064202052859768 111 30.320393215477868 4.799282071845866 112 11.180022652926189 3.435527799384933 113 25.69960448317 4.8852495526656545 114 33.91296220431614 2.88774119666922 115 37.62135947085161 3.119672518504968 116 31.757863635057934 4.670536039131023 117 13.329266662576375 2.301140646136085 118 39.85541985245241 5.941307065742349 119 23.330093049129143 3.005236666203116 120 10.500880740920833 3.4498329141310267 121 17.8983359272991 2.494128006062425 122 26.01679469085705 6.308471677558755 123 28.4057457294417 5.354797361152507 124 32.12847156054259 4.875576017158367 125 10.086225105038322 2.4895056050390263 126 13.318776245095904 3.695404050605635 127 30.914404491996066 6.885444638984536 128 8.923568933174032 4.4774169900587575 129 32.19697328887956 5.803024289863443 130 15.207609393355717 2.462266623421083 131 34.199511678539274 8.04892730500016 132 16.165324429405942 3.843223569648603 133 35.2696973900486 3.43131628724169 134 38.38184661859154 7.645999906318518 135 13.939116517680558 3.8622970559767285 136 26.703657656256386 3.354002695534676 137 56.996238210834285 8.089458463447425 138 45.513610576687796 3.754767266180753 139 75.57537354351506 6.384267359819217 140 12.839137700867347 3.960048673408369 141 57.867813607828225 6.26794051911149 142 34.97970510778346 7.6340789773634405 143 19.803190404686323 2.9416772608124737 144 14.304883116012167 3.7955398538282914 145 39.63867568963279 5.4573173501661785 146 39.498523038913746 8.313571927802894 147 24.88392215300962 2.9741823797545313 148 40.61973201860856 5.993759153144692 149 76.07592010486223 8.218204496162269 150 12.524014706861452 4.086410520332197 151 30.07628510210229 8.177673337715003 152 37.57708173473272 3.8146764711340793 153 29.82041861789375 3.8782589931929046 154 20.00750790217094 3.1188315989482467 155 40.16354417794253 5.941307065742349 156 17.953916652753772 4.379665372627117 157 40.383914369460825 6.652973695224062 158 42.151806116037605 8.540069577949378 159 42.07469260685944 7.281219480293129 160 11.768236674414654 4.196083066718915 161 49.85632408981916 4.399273995934186 162 23.050101247290378 4.680072782295085 163 51.00635059055063 9.581958768623204 164 38.30194233479551 6.697093961494301 165 20.66284286972535 3.1334032344087954 166 75.13231235068469 9.853755948798987 167 77.3608637914535 8.202511069202234 168 17.96649185177826 4.3939704873732115 169 25.713208366801094 3.4758020673424084 170 34.257018553850415 4.2704203556677225 171 39.548726862062615 4.465063133232651 172 44.23125305168688 7.076179502265785 173 77.24509832582302 8.264241637240199 174 48.67766284935026 6.530200956123207 175 15.431079776783305 3.5935622488051093 176 22.109280796338236 4.827892301338054 177 61.40025797747562 8.385097501533362 178 53.17830703726839 8.39437491892438 179 77.28492018743229 8.637499416561798 180 16.205187479627664 4.520332334297039 181 37.99717527110962 10.101711271064612 182 22.70262672157563 3.8155632400441752 183 39.01810960202413 8.768951413886878 184 52.442642669592544 6.704246518867349 185 51.24715335544319 7.18823623444352 186 49.22513297744214 6.744777677314613 187 36.35238729935125 5.005691514025086 188 77.63104786579858 8.01078033234391 189 27.749487002646262 5.185520169990398 190 41.401905178957236 4.883092683896492 191 80.76555094986905 10.182773587959144 192 13.55470357620247 4.641925809638836 193 32.63193159098072 10.013496396797034 194 35.92439373113704 10.16846847321305 195 22.76917839046623 3.7523871151226458 196 23.68766541312924 5.276119230048991 197 52.90069244376248 8.349777989404108 198 25.724812874386263 5.314266202705241 199 58.00464514018217 8.473863553383788 200 17.432824815994955 5.12353133942399 201 57.56844280067812 10.459339139716956 202 41.044117089409326 11.64904784943375 203 57.53924099595413 7.18823623444352 204 37.71371078485297 6.225025174873209 205 48.64053767060443 8.122837064521644 206 77.06535720813368 11.787330625312658 207 55.77673164994586 5.812728612949221 208 24.25197968912588 5.159294126289225 209 44.07485046379623 5.719060213128795 210 23.00237642481848 5.159294126289225 211 52.54451722356972 11.489307401435704 212 56.61467361441321 9.205257413642736 213 52.4508003820921 10.697757718818519 214 77.50616666993928 11.663352964179845 215 54.92031224559812 8.695041654365394 216 26.518772354083406 5.3500289895704745 217 57.91736320818061 7.731830594795082 218 59.825069774184136 11.517917630927892 219 59.26888557093116 12.345230100410314 220 24.675556614673688 5.359565732734538 221 40.213007421991854 5.908605414487071 222 62.654122959386974 8.344566343086097 223 79.33335652058364 12.242710111396642 224 17.878331519433207 5.357181546943521 225 19.152785204428092 5.638515470283364 226 55.03981955837276 11.74203109528336 227 79.8841034383082 12.278472898261876 228 45.33155479424058 6.918823240058754 229 79.6195990617285 10.202166957693377 230 58.16925762001404 6.332645651278421 231 31.2781314405789 4.834648146289666 232 64.66411009278832 7.8820342996290655 233 79.60487320831339 10.151042878611152 234 28.49989570450819 6.124889371650552 235 97.76710864460594 9.608184812324376 236 80.46205812329494 10.564243314521644 237 63.725649152381905 10.35380485112474 238 40.5402310278421 6.36184004276115 239 81.26258356418425 10.464361069677496 240 21.633201536550185 5.7577247598341454 241 50.560782945991235 14.18820571686539 242 39.31781578057707 6.489669797675942 243 35.020863683544164 5.089873730901596 244 52.66370437613552 11.360561368720859 245 42.570865138815854 5.139177337280543 246 59.02663156251361 9.577190397041175 247 48.40458842678644 6.74821355983215 248 65.47927436817972 8.537685392158362 249 112.99609438560542 11.643316971609618 250 22.14908459977736 6.382381437080238 251 51.82816109282306 12.624179837959142 252 28.35867074190847 6.2345619180372704 253 61.62870632508745 7.4059754071795165 254 64.20611935559988 12.013828275459142 255 42.488649183635324 6.2966229768625 256 18.66741196311537 5.905544278877115 257 44.25846007767278 14.450466153877109 258 67.9608351053824 10.330593107002112 259 74.25731616538202 9.598648069160314 260 31.249350865631293 6.182109830634928 261 72.6987142059812 8.94776534821305 262 72.11960802568977 14.54344939972672 263 152.8358366222135 12.985131458150695 264 35.20048366443359 6.465827939765785 265 70.23145836266806 11.296188352363439 266 49.527306450659 7.213755338076758 267 79.79504708670264 11.969088745097833 268 77.50987512912582 13.267910001533359 269 160.0795228743838 12.962416016208234 270 29.954696485684032 6.582653043525551 271 68.22490272511334 14.197742460029454 272 44.06602897636945 7.96071243073258 273 34.695924256921245 5.733779874046027 274 116.24772644025222 14.421855924384923 275 29.7597760517919 5.923090667715148 276 63.70078550056133 8.675968168037269 277 138.35643882730173 12.663510322550337 278 155.07167307512157 14.517223356025548 279 74.34725295160966 9.670173642890784 280 28.551046837653438 6.456291196601723 281 65.85870070674389 12.617545971483162 282 119.17221866935101 11.55606460358414 283 160.2970136004309 13.01526942617864 284 70.3551850568755 13.809120176093908 285 51.70955322257105 7.384542177497435 286 43.34641770386753 7.543479917304848 287 71.52945930068206 10.859882352607581 288 22.778509600372452 6.892597196357582 289 72.84296417224502 9.329066558607993 290 81.75551366792729 9.658252713935704 291 54.784910360883345 14.374172208564609 292 80.43667355693178 15.389835355537267 293 161.16485722836046 15.3183097818068 294 35.3570966218087 7.176315305488441 295 101.68515073319715 13.058101651923986 296 84.76584625230839 10.383045194404456 297 39.035780626122246 6.489811747671425 298 156.2126384308886 14.71749496247086 299 67.84522113789404 8.791162528229805 300 26.349495162921286 6.771003721015785 301 79.74736337088234 12.08535384918961 302 63.43114544086314 14.841472623603673 303 63.178875877642334 16.6153068521193 304 53.34834716788361 8.821403501289222 305 67.41332588185158 13.928329465644689 306 61.50331982689635 9.157573697822423 307 132.54355545022662 18.000518796699378 308 42.68599823975619 7.7032203653028954 309 116.66972732526195 16.90856170441422 310 82.81856250749637 10.428344724433753 311 163.19883261762905 16.34504634575458 312 37.68463696367921 7.388507840888832 313 85.96881699548769 16.501390339389477 314 85.2528162001233 14.912998197334142 315 36.57624301389148 7.579242704170082 316 86.00621891008424 15.685474393623203 317 162.77020899431088 15.461360929267736 318 86.74255447373504 13.601696012275548 319 93.66545758913367 10.976707456367343 320 24.048883155500757 7.021343229072426 321 118.10639794649813 17.16843795563492 322 69.93920737807463 9.302308756139848 323 85.99399995790529 10.791035713670855 324 39.58463414503639 7.5959320047071905 325 38.439453685922274 7.126089927986671 326 107.02664389960712 18.384372709052894 327 90.86528854355926 16.901409147041175 328 79.78074197195657 12.109195707099765 329 139.9600421903388 12.996112821357578 330 43.62225252780176 7.951175687568518 331 100.36467906391742 18.02674484040055 332 151.41724607655925 17.630969999091953 333 94.26746450136508 11.94945525910172 334 158.47205183217451 18.372451780097812 335 99.39465604494421 16.631996152656406 336 37.91914812717882 7.781898496406408 337 85.46322059618043 16.614889356798805 338 55.27943023036985 8.492385862129066 339 83.61368846880008 15.115195100933507 340 50.697941674047705 9.632026670234533 341 96.94132886598914 11.942302701728673 342 77.53315600214397 10.464107511298987 343 63.84951328085802 7.427109146106334 344 89.63441289251759 12.884056089179843 345 71.6545800101899 10.695373533027503 346 158.34727944244474 18.649017331855628 347 162.48145760406567 18.415367124336093 348 96.87865883948243 11.367713926093908 349 162.9225319754037 16.699164056751343 350 34.12588833534456 8.077537534492347 351 44.38727831833861 7.571840616565939 352 35.25424421150021 8.134757993476722 353 81.01596903787663 16.64325489995203 354 123.40848333166014 15.451824186103671 355 89.64363174424284 15.823016984096812 356 107.97298225973343 18.293773648994296 357 73.90750312793347 9.624110871451615 358 158.54834577748704 18.916046140449374 359 164.32165050479992 16.74002304074488 360 35.32691784903297 8.051311490791175 361 167.7843823430262 12.340238658640516 362 80.19264512891019 18.668090818183753 363 56.50748459489213 9.179031369941566 364 46.80657919514651 8.683120725410316 365 101.58153035074147 18.632328031318515 366 81.67445135103277 16.236221311347812 367 166.00935602161505 19.905483243720862 368 73.85743522632212 11.238967893379064 369 89.34481379176887 13.825809476631017 370 104.70371334352986 13.210689542548986 371 103.87346649153555 15.50666045929703 372 98.91867038166642 12.378608701484533 373 165.47529840442755 18.691088252567813 374 74.4787805344141 11.582290647285312 375 34.130289909112584 8.685504911201331 376 159.03101094540162 14.59828567292008 377 102.09339670018173 12.879287717597814 378 43.81840958126951 8.89292907501969 379 98.85804394298063 18.33192062165055 380 61.884681181377395 10.87657165314469 381 98.22708620328685 17.373477933662265 382 159.1984337698372 17.821704862373206 383 167.1594276425562 16.829030869855366 384 29.74325769592997 8.225357053535316 385 54.12683151236607 8.47278833084208 386 71.06178243525495 18.751537320869296 387 101.00675817619975 14.655506131904453 388 76.37420823827144 19.07578658844742 389 158.00528123620023 19.555007932441562 390 48.93302606645401 9.183799741523595 391 114.39501539848384 13.916196646127675 392 46.9514390352765 9.066974637763831 393 109.8565190631363 21.045124051826345 394 109.21219285311439 18.813526151435706 395 109.8326772052262 17.05957258197649 396 52.550385988593746 9.24102020050797 397 116.10129769625401 18.06600560365841 398 121.04272079448421 18.858825681465 399 93.96365111199569 11.245706971468671 400 36.49505182208932 8.532917020576331 401 85.07593941675233 22.196685788886903 402 117.51651064537097 18.718158719795078 403 116.1195764539851 13.811504361884923 404 84.14342474924135 21.34791564728533 405 44.665095392792 9.472286222236486 406 104.92672641444337 13.646995542304845 407 124.56091204537199 15.067970273750158 408 76.8427007462061 11.801635740058751 409 165.5533804890833 21.30500030304705 410 99.68126923682131 14.884387967841954 411 177.1250262257776 21.014129636543146 412 163.89104122562074 21.943962095039247 413 145.02476806619327 18.067275998847816 414 104.83025858936071 13.11055373932633 415 191.1418658662207 20.16608269531717 416 45.47645016366918 10.058795926826331 417 232.02576827967437 21.33122634674822 418 86.9840331076245 13.003265378730624 419 167.05511951419928 19.892727954538316 420 43.24141858411687 9.708320615547033 421 98.99411283205355 20.575847221111047 422 109.04990064164447 21.636402127998224 423 176.1299266812524 16.724979398506015 424 116.86264769218505 17.764484403388828 425 60.473893425584635 11.472945840931494 426 108.49108417201182 19.872104642646644 427 97.97759819015562 18.882667539375156 428 159.0747210182368 22.12516021515643 429 62.88777316690651 10.809814450996253 430 113.36782868685458 15.93819808747086 431 167.17194461795904 20.4723051804435 432 46.67906636197874 9.703552243965001 433 106.87827418384316 23.069297788398625 434 118.87708600344395 14.846240995185704 435 109.60021909060214 14.529144284980626 436 121.52909469585137 21.939193723457215 437 172.45768451664065 15.802382446974025 438 123.17721730993166 22.15853881623065 439 171.01286792728519 21.20428260424516 440 54.98828552237584 10.011112211006019 441 73.25849593301915 10.394966123359534 442 80.96413960163824 13.30605697418961 443 170.69934749576663 21.55457638152594 444 126.23591093564193 15.482818601386876 445 135.51925773599308 21.37725182181717 446 163.15406290666456 23.820316312568554 447 234.52280553146474 22.058403013007997 448 36.864940643251416 9.691631315009923 449 85.93305420862245 21.82514803523341 450 42.08601748936677 10.087406156318519 451 118.58959293347729 17.113601682441566 452 114.50786685925858 22.210990903632997 453 97.43553652066971 21.49335098053729 454 165.8120646474085 22.590076444404477 455 59.67388617464846 9.704366475110634 456 90.46744740789843 13.461029050605626 457 169.73315620395758 23.703491208808785 458 165.52715444538214 23.004924772041203 459 90.58315989162246 14.290725705879064 460 86.71789836870241 13.75905227448258 461 171.01465606662845 21.70104695876846 462 63.8765340531562 10.924255368965003 463 139.42526931741415 21.795013490235497 464 111.98738511385649 14.691268918769689 465 123.35624798842068 15.196716306465001 466 165.80222988102057 23.052608487861516 467 170.8224310872278 22.42270965572625 468 59.04052203625258 10.790740964668128 469 142.03356857278516 22.649681089179868 470 201.3598049705734 18.124496457832187 471 128.42090884102632 21.85813140656268 472 164.50553083393194 20.67080688263689 473 135.63274497964548 18.200790403144687 474 130.68913574197467 22.461330411689637 475 74.10631773195101 14.121448514716954 476 83.59987970973765 14.130985257881017 477 138.56076354959183 21.13572311188494 478 167.9924025532923 23.5985870340041 479 176.0670437810144 22.81224587754834 480 41.84708196460168 11.07207488800797 481 156.83709526035412 17.85031509186539 482 110.04486974062665 27.90919494416038 483 131.16358947734554 14.706990149690451 484 79.5977206509404 11.925613401191564 485 96.89636993393 25.401031492011924 486 76.55156517016984 11.765872953193517 487 169.06618022892093 27.053272245185767 488 118.4884637195084 22.68544387604511 489 169.3967290602777 28.4313316323928 490 66.0006958006748 11.858856199043126 491 143.82997216095046 25.065134277301183 492 123.9362553681259 17.838394162910312 493 173.60716009113406 19.969856260078288 494 100.70067896146556 15.62825393463883 495 71.99830012839469 12.264167783515783 496 132.82727355935745 16.729747770088046 497 132.8518306730049 22.350605132054035 498 243.3200537360138 27.4561996438674 499 182.48549651886754 25.815299917111002 500 51.79309509268832 12.249862668769689 501 254.58851051295068 27.42282104279319 502 114.40177059155837 24.185096738593945 503 182.6020970341882 25.75389098908224 504 62.590118026627 12.133037565009923 505 113.1327877042903 28.808032987373274 506 124.7494794670251 17.433082578437656 507 86.95870113359499 12.938892362373204 508 141.67141075112997 25.374805448310752 509 189.3638725259476 24.14607849117224 510 90.23459192897596 14.889156339423986 511 151.2410556791084 25.610839841621303 512 42.257455348901985 11.603748319404454 513 108.18224041262165 15.613948819892736 514 95.5859192437968 27.732765195625216 515 199.59584808319195 26.845848081367404 516 135.42412872293167 18.908893583076328 517 228.90486907923489 20.625507352607592 518 153.50049463884218 18.76822662140641 519 238.06689770980947 27.401363370674044 520 66.0586315153965 11.62282180573258 521 147.4854587976421 27.644550321357638 522 147.35141457428065 17.25903701569352 523 317.2511886592422 26.338987013831193 524 146.3606529233474 27.475273130195532 525 52.91242263785426 11.994754789131017 526 309.2598747249161 27.842437742011935 527 165.2961864468775 20.90445709015642 528 69.18978271473736 11.939918515937656 529 221.43640708887847 20.739948270576342 530 148.59331046186736 21.603023526924005 531 184.86617946598136 22.93578338410175 532 98.54622650131283 15.723621366279453 533 144.86815261817168 20.229732511298995 534 163.44307804081063 25.412952420967 535 197.87787192178013 27.56348800446311 536 173.8625659939966 27.129566190498267 537 255.93279393478505 28.183376310127173 538 347.38770675446284 30.19324493195335 539 87.94977736459778 12.602590543710587 540 58.86878631583282 12.411987302558751 541 131.20841140725784 32.17450332428734 542 149.28793067910846 31.325733182685784 543 128.35848652213423 29.98820495392601 544 79.19999821968966 15.072738645332187 545 162.91140460941415 30.44835281159203 546 81.6687889097791 14.228736875312658 547 172.37632417652225 30.74732503019178 548 255.42218081120916 28.970157621162336 549 136.33822555520703 25.03625106598653 550 70.52132516147051 13.52301788117203 551 209.38497434313206 24.681007383125202 552 128.52798045745917 17.032539365547034 553 165.7573288809212 28.78657531525413 554 293.20231628205113 31.735813138740472 555 172.36887359592532 20.146286008613448 556 330.8086227412733 29.380237577217027 557 371.7445487954783 31.266764973435684 558 160.76934729658416 19.516860959785316 559 175.3842725751123 22.253906247871278 560 65.03967612120167 13.320362088935704 561 113.3926033605259 18.248474118965 562 142.8794755933009 29.411231992500223 563 316.30030822541045 30.748220360751116 564 252.90957641388707 22.18714904572284 565 149.73533545576393 28.507625577705298 566 355.17445754791976 30.066883085029527 567 93.65542170192515 14.154827115791173 568 165.77540779087167 28.791343686836164 569 360.1931686380077 30.953800199287347 570 106.60574340803939 17.20181655670914 571 227.58237075592805 28.03940605159318 572 87.55161833749817 15.44228744293961 573 254.2261909480606 26.798164365547088 574 149.58547706582718 21.729385373847837 575 106.10524779083312 17.78594207550797 576 46.83880680997678 13.792430875556798 577 110.64389642061926 31.874095914619378 578 157.922495841714 21.4647407510451 579 111.29219627362625 27.630245206611544 580 135.95797035891522 19.173538205879062 581 280.901892089418 30.87750625397484 582 117.90816671178715 27.453815458076388 583 177.42275142643064 26.047145841377162 584 169.6857705113611 29.146587369697492 585 77.26417181215119 14.381324765937658 586 352.18230438019526 32.03860473419946 587 370.93869399811507 29.8490505641888 588 79.13037610040718 14.090454099433751 589 201.0883483883678 25.49878310944357 590 219.9804642991649 26.66703414704123 591 171.1058511731348 28.624450681465067 592 180.68401956531613 21.21916961457049 593 369.1982383706736 30.09464247325747 594 88.18238449083373 14.58159637238297 595 131.5361726932324 17.90753555084977 596 334.9589462258985 30.5508728006057 597 193.74505615203972 29.168045041816633 598 135.35212631204297 19.793426511543128 599 286.82700347687535 30.321140123403953 600 59.275298205192215 13.863956449287265 601 139.47462196328806 35.90575408722681 602 169.76087236377813 23.574745176093938 603 185.5420961377343 28.798496244209204 604 134.97637863137888 28.982078550117414 605 99.78953963043278 15.15380096222672 606 133.3522712705391 33.0661888101272 607 281.0358833308732 34.435954754114576 608 90.23967819199673 17.876541135566562 609 182.7582612034997 20.463382718818526 610 142.59575864980144 27.999794004218973 611 264.2606849649124 25.06724548126973 612 114.7830416359716 18.410598752754066 613 246.36260223175813 37.884628293769794 614 284.0294670100724 37.209903714912365 615 156.18747202531685 23.41738891388691 616 89.37803344712374 14.94637679840836 617 191.09717559601597 35.45966180159696 618 247.53767840032066 34.18437194611353 619 364.3774147012401 36.30715220677577 620 153.89672469879918 20.742332456367357 621 151.0229026792305 20.081912992256022 622 337.79374313141614 35.171424863594005 623 202.70414515873608 31.3734168985061 624 82.39332275376434 14.157211301582189 625 63.54093151990657 15.09419631745133 626 181.41438783887702 35.90098571564478 627 131.98804016091995 20.046150205390788 628 182.80832910511106 30.405437467353746 629 222.44179752864397 27.584945676582254 630 79.70994906943467 14.383708951728671 631 173.72547531101318 31.142150876777578 632 184.71886934522468 29.318248746650617 633 169.7608723637781 32.56550979401391 634 338.22289657379895 30.839359281318597 635 171.65123367282962 29.222881315009992 636 186.40010499927604 26.600276944892794 637 94.44713033026176 14.80669635971238 638 177.30466079499055 22.122776029365415 639 173.49003696415036 29.745018003242414 640 55.3201679815794 13.968860624091954 641 127.2797508237811 35.19526672150416 642 248.58663787799242 34.16291427399439 643 366.046344754951 34.38782482141896 644 137.65071983316125 20.546829221504073 645 177.4710311886987 23.94190978791035 646 183.20708417865842 24.1326446511916 647 361.48301315094716 34.25570656906583 648 89.52242388028877 15.311157224433751 649 250.13723564112462 29.294406888740465 650 87.33793568597838 15.320693967597812 651 185.15279115918946 23.190891263740422 652 225.77125422124348 35.836612699287365 653 364.70881652619124 37.455474851386974 654 193.7474403378307 33.75521850373072 655 194.175571986303 35.085594175117436 656 170.0675382611475 24.533187864082233 657 190.67660903900259 34.11999892975611 658 271.38224792267613 27.472888944404513 659 373.8927001931834 35.307405110894486 660 86.27160859094667 15.203868863838048 661 192.17162275287708 34.39739909919357 662 207.07095173396638 35.798465726631115 663 119.1000428631321 19.82203674103532 664 306.2505554194962 32.33901214386742 665 158.51258299062172 19.678985593574374 666 193.04444612745112 23.481761930244332 667 239.23594347600405 27.437126157539282 668 319.19859161334375 35.37408065583033 669 245.5651620225534 34.96161651398462 670 202.2630707873982 32.0290679910354 671 164.25310516330822 30.20755004669945 672 61.57300307524284 14.605438230293124 673 142.0054351804513 34.98892814229081 674 177.70468139621823 35.2167243936233 675 64.49335697708894 14.955913541572423 676 104.17900907059948 16.038333890693515 677 226.5690917947464 35.98681640412135 678 171.94478654834842 31.506931302802975 679 136.16870994546576 32.20788192536157 680 108.516943417899 18.913661954658362 681 248.19293212855138 33.266460416572514 682 190.34377288605504 23.653423307197457 683 354.5998687722851 34.31656206565679 684 129.7868305551154 19.97700881745133 685 308.6679964060233 34.04847335602564 686 93.47581303900199 15.5781860330275 687 249.18634287480774 33.51203155304712 688 183.0920472142419 25.10300826813497 689 211.521204811882 28.855716703193586 690 139.60885162332227 20.944988248603686 691 294.30619430329136 34.54587183237732 692 321.1245368953263 35.700714109199474 693 99.96652003681784 16.33635711457047 694 329.4443244912795 35.21434020783228 695 393.4234170908371 34.68981933380884 696 175.94329070832063 22.289669034736512 697 203.6516887116798 29.973899839179918 698 329.48008727814465 35.264408109443615 699 249.12514877283846 33.788597104804936 700 72.35965788980627 15.413677213447421 701 161.2946628992047 34.56531211651946 702 97.24837793607493 16.972934720771644 703 255.68126233383288 30.352985379951406 704 73.94802756047343 16.51755523468766 705 281.5484161355667 27.1963233926467 706 174.6907725331506 35.81753921295923 707 158.9565713668154 39.46772765900416 708 262.8731559749161 32.12920379425805 709 366.9880981424021 35.954292709705456 710 189.5304968694644 32.39861678864281 711 205.73137991738562 34.42994308258814 712 228.94540023768215 36.3611335733108 713 250.01994323517613 31.90509032990258 714 128.3844958216726 21.49335098053729 715 111.98975060183511 18.474971769111484 716 333.57284774737695 36.55186843659205 717 254.71202087189485 35.631572721260014 718 345.3015441873242 37.708198545234644 719 370.7026596048045 37.1115436553395 720 75.88399314868542 16.40311431671891 721 292.57677307086334 39.30798721100613 722 336.4705200174024 27.851974485175997 723 168.2427420613489 41.88529205109402 724 173.24893617603396 38.41630172516628 725 163.17359161164097 23.817932126777542 726 121.78376908716447 17.85031509186539 727 263.5692710855179 47.2663993814163 728 105.10700754002556 16.882335660713046 729 115.45399125399321 17.783557889716953 730 216.85837300583003 38.41391753937527 731 235.9664300279245 33.49295806671899 732 172.21479558918094 34.11999892975611 733 370.34026336457003 39.64654159333034 734 342.31177520539063 41.19387817169949 735 100.88988113388116 17.161285398261874 736 125.08153152446472 22.46371459748065 737 246.16836102768053 37.05493163849634 738 191.54649625475318 27.782833097236544 739 370.018398282783 39.650409698423694 740 226.96255238815422 28.302585599677954 741 142.49991531350784 23.195659635322453 742 216.34952163665875 30.941879270332265 743 361.83110427643544 38.56118740748703 744 199.1724128701859 24.709617612617386 745 395.1138048166672 36.09648895050807 746 333.40922546173834 39.29845046784206 747 346.0091142649097 38.068210599678 748 142.34232063272165 22.396957395332212 749 290.227873229555 39.33659744049831 750 75.99075169021651 16.972934720771644 751 177.980138505904 38.88360214020534 752 287.9046554544144 31.120693204658437 753 171.6852083203516 36.30868148590846 754 196.00859832550816 26.981746671455294 755 172.0639958378992 36.942874906318615 756 100.61825425269043 17.90515136505875 757 211.1839408853226 37.72556548642496 758 211.26064736472108 37.25520324494166 759 174.97054290558629 24.657165525215042 760 140.61974639871295 21.598255155341977 761 289.7333259561234 37.02574072937881 762 208.02973501992457 34.76372909333033 763 228.97242100998037 38.28517150666042 764 337.7127437586231 36.299144742744396 765 131.84828428769268 23.11221313263691 766 352.1131629922558 36.29437637116236 767 301.25950088458404 35.63395690705103 768 64.74554119099467 16.47225570465836 769 144.5769424417191 40.831481931465106 770 113.9867235817724 17.645275113838046 771 153.5728468892299 42.90572356964871 772 149.91335466149306 37.10261535431667 773 311.2362976052933 39.07091653340366 774 217.2238366260213 29.76647567536155 775 177.80057143952183 27.522956846015838 776 160.83054139855363 36.981021878974865 777 236.54022407496248 30.41020583893578 778 332.93245124763683 40.91492843415065 779 242.7076454141312 35.01645278717798 780 105.74156775824972 17.774021146552894 781 228.58816973332839 38.03960037018581 782 235.82926940705113 30.138408658759992 783 214.51941680695347 27.038967130439666 784 104.94793564917485 18.548881528632972 785 228.70618692998355 39.26507186676785 786 233.20156923894362 42.459880826728785 787 370.5429191568065 40.194315075807836 788 229.58754094406234 37.6414413430862 789 491.4950485208194 43.14652633454129 790 232.76764742497866 36.44219589020533 791 216.41332499150707 38.380538938301044 792 120.66753664864346 19.307052610175937 793 209.07911736594164 36.964332578437755 794 253.2839635209666 39.715682981269794 795 231.62443033818664 32.37477493073267 796 254.8428236639924 37.629520414131115 797 390.73935699249967 41.75646262325971 798 147.5733413693629 23.68918609406269 799 373.74249648834945 37.77018737580104 800 76.11605389901095 17.99336623932633 801 264.7256683345352 42.757904050605745 802 180.3881661548299 44.855987546699495 803 252.54764747584127 42.612468717353785 804 250.1153778071915 38.79777145172878 805 212.0994682290726 25.7634277322463 806 219.30686187531282 28.765117643134992 807 497.8059883096377 42.50518035675809 808 181.42252111408322 44.18126296784207 809 386.2737770059275 46.90638732697294 810 100.05183982833913 19.469177243965003 811 231.59661483729155 44.61995315338895 812 203.4496421792679 26.88876342560568 813 221.38673655156575 44.68432616974638 814 268.49499892975615 30.71061324860375 815 284.1749023433244 43.58283233429715 816 135.17829174441945 23.67249679352559 817 265.62682342316435 39.83250808502956 818 349.9125595071484 43.625747678535426 819 116.02054179779124 20.11529159333024 820 210.4438934323131 31.251823423164304 821 380.85929107453103 43.62138919165276 822 389.6367340082566 41.53004836823269 823 380.3943748452829 44.00755378170585 824 335.254648208086 44.076358793037386 825 103.49920218316271 21.128570554511892 826 315.25467147784576 42.943870542304964 827 395.36706161286094 45.048154576548484 828 183.85640334870152 25.210296628730674 829 380.5326576211618 43.83448360805413 830 400.8352546686569 41.91867065216824 831 452.0725364663762 41.27732467438503 832 92.65285982389233 19.13062286164078 833 189.52398443195423 24.423207577753374 834 493.1449610385153 45.49971771027372 835 416.5786294931808 44.74869918610379 836 174.17899322296907 30.28622817780295 837 259.31833496051195 29.456531522529524 838 352.5065536477734 44.038211820381136 839 386.98188018585904 42.92126070212557 840 98.70034708280342 19.619380948798984 841 336.17488097931647 36.3444442727737 842 216.37478065455238 44.78207778717801 843 212.30015236960384 42.476570127265894 844 229.97775268519194 43.842708585517855 845 138.95725364663767 21.319305417793146 846 368.4209938028025 34.584915159004154 847 155.21763822743816 20.627891538398607 848 246.10080909693497 35.12135696198268 849 509.55525588776266 43.94284438874051 850 135.6270229337471 25.260364530342 851 344.1070671060254 38.20172500397487 852 241.99047279322417 44.22894668366238 853 379.4597740152048 45.228557968068685 854 209.57128143280136 39.145862577217066 855 155.241405484932 25.668060300605678 856 347.4968461985035 45.03718566681668 857 380.90220641876925 45.20993643532413 858 146.80993949018773 20.86154174591814 859 305.1947708108597 44.84614747563542 860 247.93226114873346 35.04744720246119 861 230.00596555038558 33.29268646027368 862 347.1969718911816 43.92377090241238 863 386.6361732461618 44.865605508058856 864 78.74867001689282 19.18069076325211 865 412.02298354889604 46.23881530548856 866 228.60088539088034 48.985397336738565 867 220.248615262764 31.442558286445543 868 225.20056915070344 28.81041717316429 869 264.2487640359574 43.77595138336942 870 215.49693298126988 29.041683194892805 871 297.71230926471094 44.65571594025418 872 281.7686258948274 44.095432279365504 873 178.37016725513547 42.86042403961942 874 354.49734878327143 34.31073379303736 875 99.47827284661489 21.545803067939634 876 263.4816001887833 45.45203399445341 877 396.10139083649375 49.22143173004911 878 360.2551574685741 46.582138059394815 879 515.4966468789736 47.26163100983427 880 115.46948846163482 19.37619399811539 881 253.19329452301793 46.63135024471857 882 116.45634269696612 20.4443092324904 883 257.70417403961943 45.84657445439858 884 154.23985714358946 26.09721374298849 885 317.9602455134903 37.99191665436549 886 339.3816108682325 45.81204604889676 887 369.1124076821971 45.993571840410155 888 266.8570632913285 31.170761106269765 889 241.80927467310696 40.039932248847926 890 282.5884651179824 44.87744521881863 891 128.72760183141602 21.59110259796893 892 335.95917510933117 46.66320037628934 893 432.7630157449408 40.819561002510035 894 489.8357111605856 45.785820005195596 895 405.73177623695517 45.44249725128933 896 86.50108647333192 19.0877075174025 897 192.7637214639359 30.19562911774437 898 185.42378091785514 45.72621536042019 899 333.2971687295606 39.66084670807643 900 87.72476983057066 19.652759549873203 901 285.91147613312535 42.54571151520535 902 244.561419804536 34.24874496247095 903 247.09700139328106 34.31311797882837 904 234.85937309229638 42.536174772041285 905 207.957528250254 47.24255752350614 906 207.1939076011886 44.2313308694534 907 368.6975593545604 55.904304502265916 908 335.4042558664723 45.81443023468777 909 219.16320146802744 48.66114806916044 910 129.20116538980176 20.50868224884782 911 278.98064803864287 53.65914962760042 912 161.06597137238313 27.227317807929904 913 470.8408470132511 50.62810134674833 914 353.9585227945019 49.438392637031534 915 218.19828741860624 41.11043166901394 916 345.44108200020025 45.354282377021754 917 275.26186218219146 50.570880887763956 918 196.22794341828157 27.563488004463103 919 383.8323707559274 55.86785934439728 920 178.68748855377964 27.990257261054907 921 434.1959114053411 54.65260696198272 922 357.86381912018544 46.67750549103544 923 268.42347335602574 43.940460202949495 924 143.83897908504994 21.93442535187518 925 245.6401939370804 33.66223525788111 926 298.28540038849644 48.69452667023466 927 371.8519001001756 50.33961486603544 928 188.505565641182 31.46878433014672 929 407.740985868232 56.02687247585323 930 235.55508804108433 31.485473630683835 931 234.40352630402379 29.302148859506325 932 340.1564712503125 46.93261337067411 933 506.01712417389547 53.16249084259795 934 360.6485481240917 47.70270538117216 935 182.33767699982457 28.08800887848655 936 136.6181289670723 21.486198423164243 937 292.56335449005894 59.088407788856514 938 337.4113868709122 48.88049316193388 939 292.17479934649816 57.68052291657257 940 364.39887237335927 40.11622619416041 941 398.67154311920854 52.86208343292998 942 282.26326217608795 45.559322355049105 943 319.70015716339867 44.35054015900418 944 352.23958778328125 42.536174772041285 945 131.03412742593454 23.171817777412297 946 301.58899536090235 38.70717239167018 947 395.64124297882773 52.10107916364911 948 308.649523162416 47.50720214630888 949 308.0104942300491 50.96903991486357 950 164.13441848542024 28.333580014961164 951 530.2785987832704 46.594058988349886 952 187.51471185657587 29.761707303779524 953 397.3554725625679 51.348029666397935 954 295.4788040156876 41.56819534088894 955 432.2551841714545 47.94350814606475 956 361.2690954203051 52.18020629669951 957 259.6472854592972 37.08831023957057 958 363.0327339151073 48.60631179596708 959 454.9693222024602 51.0191078164749 960 85.64911710282607 21.912967679756036 961 393.2117576577828 43.96907043244168 962 296.22546386505894 39.17924117829127 963 375.4406957621019 50.287162778633096 964 226.4161764777131 54.924404142158494 965 193.4361337931181 47.39991378571317 966 198.87915801789097 31.351959226386967 967 404.10510253693315 59.46627807404327 968 171.4059164861635 23.65103912140644 969 280.04876327301787 37.89893340851589 970 206.22660936597666 49.858009336250284 971 396.15384292389615 59.65282169968954 972 137.4926483152168 23.0502243020705 973 582.5447196939148 51.555549619453416 974 357.4251918787401 52.32087325836943 975 135.34696856392665 22.89286803986347 976 234.32968648239245 44.7510833718948 977 392.19609451081016 53.064739225166306 978 342.21349048561285 52.78102111603545 979 335.92692565705084 52.211200711982706 980 122.45793437940016 22.52331924225604 981 288.44116439776747 50.74015807892607 982 289.60696410919957 51.10255431916044 983 388.6174316384958 52.93578765860626 984 334.51548766876965 37.11215209748073 985 289.0825103755508 47.264015195625284 986 370.48093032624007 40.848171232002215 987 433.19932174469665 40.98168563629909 988 190.11727523590855 30.395900724189683 989 366.17270660187484 48.09371185089872 990 152.66496997385747 23.41977309967793 991 331.046497342842 52.15549133292265 992 214.13794708039097 32.49398422028345 993 316.54236602730003 56.095039365547166 994 267.62674560504325 45.64515304352566 995 314.172727965883 46.470081327217066 996 464.2263768506899 50.17987441803739 997 374.30039596344704 50.2018712849899 998 345.7068557717969 51.71529006745145 999 289.1487907405412 35.49805831696314 1000 101.33394182628984 21.233474729316583 1001 161.27002631269758 24.022972104804886 1002 475.1490707376163 52.52352905060576 1003 403.12758636261674 49.753105161445596 1004 223.21262550318508 46.408092496650674 1005 306.1308692927872 45.678531644599886 1006 347.23988723541987 47.77661514069364 1007 351.3311500528027 48.150932309883096 1008 125.2913398740741 21.555339811103693 1009 274.08353042389683 56.629096982734666 1010 222.1949755347199 51.95609283234404 1011 267.96053161578527 53.141033170478806 1012 218.94684982086946 31.92177963043969 1013 374.9631996133494 56.680636087964665 1014 165.2133359906397 23.91091537262715 1015 292.52043914582066 33.04234695221704 1016 272.94109573321686 44.126426694648714 1017 258.7294410701308 48.713600156562784 1018 346.34581756378907 47.73369979645536 1019 374.8916740396189 48.89479827667997 1020 152.94543456818394 28.188144681709208 1021 333.661949155586 48.03621899632235 1022 303.670389556459 51.741516111152634 1023 268.64043426300816 35.4003066995315 1024 87.65026402460143 20.65888595368181

and here are the ratio plots showing the relative performance of the original unoptimised version of the code (pre-release-1), the current version (pre-release-4) and FFTW:

size,rel2,rel4,speedup 8,31.0035623439637,1.63676343916201,18.9419934500962 9,23.0236843367442,1.55019707211861,14.8521015494361 10,20.8464275202564,1.52725723153741,13.6495850795686 11,280.324183098903,1.56435086736902,179.195210579811 12,31.3217344925748,1.54102540511759,20.3252551116668 13,238.564872414651,1.5142891238375,157.542485552615 14,220.196265658982,1.40227308701968,157.028090817157 15,24.4004823296537,1.51632067661145,16.091901077404 16,41.613223688593,1.41958755282134,29.3136014090073 17,75.6522121597436,4.38124782902846,17.2672752402868 18,31.659967533097,5.19758925027499,6.09127924670499 19,428.745816685474,11.0372843127242,38.8452271897355 20,31.1467155085507,1.50172187974857,20.740668381129 21,243.187456369924,5.79700866099656,41.9505076827189 22,297.173923636788,4.89193999730343,60.7476632584616 23,338.913321074374,8.88142754852406,38.1597799703602 24,39.9146205525711,4.80993853354735,8.29836395500337 25,30.844757712075,1.45579836111016,21.1875205633241 26,254.636204069331,4.61884540213681,55.1298391480107 27,35.8707950145261,5.025285774866,7.13806072361777 28,256.327406474509,4.29205300130751,59.721398220484 29,136.255087213481,3.60365033698868,37.8102963583696 30,34.4694643926202,4.22661227826201,8.15534099730437 31,140.631775111143,3.70681317795991,37.9387275159471 32,55.796267061807,1.53996138286642,36.2322508100497 33,365.283997243452,4.70208669204362,77.6855088319718 34,99.4332853296993,6.87360486240698,14.4659588847649 35,296.647448889548,6.19788716426123,47.8626733639329 36,22.1364583157872,2.20197339103689,10.0530089990612 37,312.918980821529,4.27237236251994,73.242441030342 38,531.142250661184,13.1362383584803,40.4333597005946 39,357.94137972657,4.47059144754442,80.0657774092012 40,20.4687655988403,1.88201220199891,10.876000472845 41,279.270424648104,3.54659664218119,78.7432157710355 42,318.924524672781,4.14994140804612,76.8503680689162 43,281.747643338043,4.06448791039616,69.3193458928462 44,424.1869719843,4.88827996227309,86.7763252633039 45,40.0534922145836,4.13065578851163,9.69664243774129 46,427.682735934799,10.7107268012327,39.9303188169804 47,256.424329809441,6.64590987404611,38.5837808019095 48,30.1298650675711,2.21984675642496,13.5729482138194 49,371.29467467343,6.79095103147479,54.6749156270673 50,45.9285788055788,3.76573523012641,12.1964439873902 51,108.93295754923,6.5767137346704,16.5634330372279 52,418.450271063551,4.6358703902462,90.2635828525239 53,233.262880194168,4.26660400045692,54.6717905315767 54,30.8789814952158,3.32955411810945,9.274209218365 55,519.369414156701,4.90764204091986,105.82870751905 56,338.902214071608,4.36027235295829,77.7250104208914 57,481.308370331345,13.1161994235707,36.6957191476062 58,228.591352563704,5.72930040117016,39.8986501941871 59,211.712173908992,5.49540482226518,38.5253099191562 60,26.415368131313,2.14231319678089,12.3303017369288 61,217.957897546566,3.64562736745699,59.7861151395193 62,217.582717709118,5.42006629572176,40.1439218337353 63,399.561169721661,5.95303222745183,67.1189327481083 64,77.1386234280048,2.19715772781031,35.1083686217107 65,481.857605313242,4.69757132547056,102.575899742187 66,524.756015432184,5.18566481752392,101.193585373832 67,493.973069731807,4.36885772689544,113.066870246386 68,129.768483217381,6.72846159270372,19.2865012944564 69,451.222572680023,10.7982225457984,41.7867450653344 70,412.985101384841,4.4137334021936,93.5682026421418 71,446.168666714429,3.52618788072942,126.530032376532 72,43.3313245255458,3.42810248293288,12.6400318372262 73,422.209119515195,3.77233597095442,111.922459390163 74,438.762564712467,5.66676561614072,77.4273358797008 75,56.3774648955331,3.59735767593472,15.6719097666273 76,546.277651021967,13.5352193701864,40.359719047128 77,555.351526550351,5.33531469468432,104.089741342466 78,483.562604732599,4.90865287355765,98.5122837545706 79,421.277925273441,4.05189514945009,103.970589004658 80,32.5702339374315,2.29366377665251,14.2000908193119 81,60.8374213913291,6.02230511579752,10.1020157932122 82,391.400568530886,4.74294180424299,82.5227432014331 83,376.43862980617,6.43201931606345,58.5257306155852 84,258.660069203734,2.95991650669191,87.3876234748325 85,147.352980120585,6.68779503122347,22.033118454234 86,371.070479141964,5.09480975517009,72.8330393034619 87,242.132373957657,6.12549523669456,39.5286200709408 88,551.401191875935,5.69908677196007,96.7525524596098 89,502.646686053713,6.0849103185434,82.6054386573171 90,35.490493816823,2.886158536488,12.296792905912 91,478.318094027619,5.05503643457953,94.6220863524606 92,460.329737004008,10.8497727426219,42.427592533405 93,231.280967852096,5.72917887747017,40.3689556214769 94,349.468105493579,8.4761250732814,41.2297013637964 95,602.254428424729,13.1754544213742,45.7103344722372 96,48.3820658264393,2.21747325535186,21.8185566430934 97,361.023447620726,2.82363817519637,127.857545910824 98,448.542659597839,4.81597455498339,93.136426382009 99,516.505095013952,5.40387864511537,95.5804393351481 100,39.1023293337295,2.40981148522821,16.2263021706972 101,307.671136213038,2.7574790075825,111.576964091841 102,149.505035197283,6.89374551808903,21.6870545634423 103,406.730452669845,7.08064824241602,57.4425446293689 104,500.501671424073,5.31987717037946,94.0814337238492 105,425.162572970627,4.74143707007673,89.6695593945206 106,305.97788291228,5.20765860122859,58.7553651923523 107,383.150072000661,6.70958502449636,57.1048836257084 108,49.2275128714945,3.53973794321518,13.9071065884557 109,326.228891955307,4.42092542277739,73.7919916663869 110,565.622120091478,5.73825576447872,98.5703919983533 111,639.112844687001,6.10011551312085,104.770613492863 112,273.996433022369,3.16891395029057,86.4638287187461 113,409.337945427271,4.93010978201938,83.0281603302565 114,613.23874996535,10.395843600868,58.9888395314211 115,500.922741873498,10.6860811063151,46.8761875274812 116,296.500529084055,6.67424636799331,44.4245706160831 117,451.719074313888,4.95426533168229,91.1778122631355 118,259.845133913181,6.28971626447753,41.312695674479 119,154.671595437838,6.90173763511877,22.410529581827 120,46.499174900736,2.89426726052016,16.0659575344052 121,610.328310244978,6.26484536902882,97.4211292208783 122,259.930403508287,4.0919402715776,63.5225311849612 123,573.313354046854,5.10297348419401,112.348879691936 124,289.453788865766,6.31544279159588,45.8326990549181 125,71.0629719495507,3.50390856959131,20.2810577211606 126,297.680059140862,3.45310154210278,86.2065755991608 127,307.710885330496,4.40920991472868,69.7882140522746 128,56.4045482855623,1.97222531830717,28.5994443748325 129,549.339852550991,5.50354284542707,99.8156765523213 130,497.35505670896,5.27719651045514,94.2460747337349 131,695.928907841214,4.09163858870681,170.085625294967 132,395.531989644992,3.90619502086852,101.257614515378 133,617.28480992687,9.14001831552102,67.5364959475666 134,618.695555789857,5.20017639419773,118.975878679844 135,49.9844159596429,3.3877707853077,14.7543677324388 136,188.083940308365,7.09931909507802,26.4932365751476 137,719.295889668846,7.06490245547373,101.812571964324 138,502.525446836379,10.9852975303071,45.7452741220685 139,872.942812789777,11.3013142084304,77.2425929135383 140,332.551356100159,3.10424242223272,107.1280238033 141,491.668951166375,8.76619662786181,56.0869179689276 142,587.18482651983,4.46790832478531,131.422756206182 143,523.972874511054,5.8245516014578,89.9593497257215 144,67.7299881544339,3.50715038463533,19.3119714658248 145,312.101861576098,6.94831294503479,44.9176460595552 146,546.709253613293,4.69215341661894,116.515638997848 147,417.177229780238,7.30798337339484,57.0851366875022 148,662.169036336561,6.64018888432046,99.7214157416738 149,701.786347622189,9.14085381725311,76.7747041635855 150,65.1752883721421,3.00552919715258,21.6851290061959 151,700.753969942058,3.60450366623251,194.41066921552 152,503.801432706304,7.05263643530718,71.4344823141817 153,181.329392680331,6.85940760788887,26.4351388699787 154,541.043311835516,5.59613344161645,96.6816316087049 155,288.826578404247,6.46731080362966,44.6594554017952 156,386.526618980629,4.0998314722036,94.2786603793928 157,834.542331338152,5.7246650871687,145.780114405068 158,538.769792982785,4.89504689855652,110.064276021882 159,435.714709146841,5.55165816743913,78.4837063100064 160,63.7782579786892,2.64838201887133,24.0819706236602 161,544.872701910037,10.136592540599,53.7530437104697 162,65.8962179141201,4.82006775077625,13.6712223398743 163,602.396566061772,5.16534007927235,116.622827697074 164,578.970676300861,5.47963781865232,105.658566398327 165,545.964865486633,5.66641733122414,96.3509804472319 166,481.151118987848,7.69587309600932,62.520666984146 167,698.678541154153,8.96732763145295,77.9137966035203 168,344.667718728519,3.7016554210472,93.1117782516376 169,517.912065422364,6.31928877926352,81.9573346801099 170,187.773527222397,7.21552902702464,26.0235287695635 171,684.342512136198,7.86167436305867,87.0479341337088 172,542.342627134465,5.94467846841586,91.2316166494012 173,691.446918204287,8.91819932223255,77.5321220372986 174,323.690545705247,7.36868947621973,43.9278309596113 175,416.771335598153,3.83723726543242,108.612344447037 176,426.574487709098,4.29366778390924,99.349672396106 177,396.512956199167,7.2122219567504,54.9779192289062 178,474.673162247135,5.37361420051765,88.3340605660543 179,682.272685691075,8.81262761066135,77.4198928893438 180,65.140155932268,3.37692441829449,19.2897879441338 181,563.065132198392,3.58883612910634,156.89351977701 182,457.635660262831,5.13712755194056,89.0839590093415 183,372.875240298742,4.30921614767945,86.5297138783672 184,447.231871511689,7.8256470523751,57.1495070654833 185,664.294696626511,6.76620023093984,98.1783976165657 186,299.688065640459,6.92426518817358,43.2808474973368 187,193.714881150811,6.51292217158049,29.7431592221532 188,478.597326529552,9.2877990222524,51.5296816159451 189,307.919880322086,5.03467648518066,61.1598145836052 190,654.515562164685,7.52033089433827,87.0328142951052 191,584.268659113577,7.89867100153976,73.9705019995997 192,84.3939794660343,2.68455674529526,31.4368394759905 193,592.160682445265,3.21003403885168,184.471776709601 194,505.150491642247,3.49133701210559,144.686831976039 195,536.307975198127,5.21042280876202,102.929837919536 196,347.849331181805,4.23182719058969,82.1983780328547 197,674.131604545726,5.94794616280849,113.338551845166 198,432.409036710015,4.4170346812402,97.8957757670591 199,672.32728119474,6.51295722558765,103.229187281217 200,74.1495001282507,3.23424301050514,22.9263849028678 201,747.263302135204,5.29427979332923,141.145411898471 202,424.436484409191,3.33771650651002,127.163731126161 203,351.113850141492,7.52822571037472,46.6396550328743 204,151.827104640608,5.65997089181679,26.8247147454629 205,588.799652391248,5.68794776880192,103.517063855752 206,407.659571435643,5.99498792044962,68.0000655289175 207,520.313314974387,8.64698656278165,60.1727909713563 208,402.793691683496,4.29423199691294,93.7987728592816 209,627.466437344979,6.96871266240051,90.0405093081906 210,354.025897583459,4.18606870316163,84.5724049669974 211,511.040444728673,4.45879525586792,114.614019124589 212,422.391924997952,5.9741714545898,70.7030134987905 213,736.175247364266,4.76409476756209,154.525735377213 214,408.079797739854,6.02592605943284,67.7206779032835 215,542.166398734392,5.95878458806846,90.9860711897516 216,90.6417415134905,4.50175902651671,20.1347386609509 217,328.04316595483,7.06015013331852,46.4640495967241 218,451.260037872095,5.11489310298884,88.2247250892506 219,670.902993282901,4.88991574817308,137.20134002995 220,463.914388694385,4.09764451062795,113.214893944837 221,213.42503126647,6.10715600497038,34.9467135099827 222,632.89136298718,7.0288072252617,90.0424983505812 223,466.967602378254,6.14180094716028,76.0310544733888 224,379.99709156789,3.05103298083667,124.547028483345 225,75.685162555707,2.94068723479471,25.7372364052141 226,448.964506679869,4.66111014943399,96.3213681475405 227,502.185119847148,6.64961260599658,75.5209588291324 228,569.731831319062,5.99081677322171,95.1008606815853 229,555.812350340781,7.34095773840578,75.7138741492722 230,457.060724940688,7.36705964477915,62.0411326878011 231,578.855477893771,5.65084857932878,102.436911866877 232,357.783442762585,7.71442618496528,46.3784906594702 233,562.08338002122,7.42265078376306,75.7254242986575 234,388.464908783067,4.25283916789152,91.3424875588843 235,492.16793745969,9.5725412942168,51.4145535999965 236,361.390406862752,7.2658677686901,49.7380930079744 237,662.478082979693,5.17616221098393,127.986345090558 238,190.842998544489,5.72694448036949,33.3237032764418 239,546.493120794215,7.34036374110265,74.4504141850771 240,83.1914014040263,3.49017300370652,23.835896190727 241,421.258869670249,3.49095589083705,120.671495957871 242,617.866795051413,5.60775813132937,110.180714036064 243,89.7270342015239,6.022580406774,14.8984369059817 244,343.105586126694,4.51919598698607,75.9218204111385 245,450.304106696642,7.20509118982626,62.498044068128 246,579.070826575427,5.90342471306688,98.0906600356381 247,677.300422052894,6.43369570582211,105.273928550892 248,335.336750312789,7.25838240683012,46.1999287881606 249,553.810902657188,7.61500681252114,72.7262517673094 250,78.8365200760403,3.20481517686718,24.5993967593182 251,523.399742696637,4.13845183049496,126.472353463164 252,377.449894087009,4.16071179335792,90.7176254528281 253,576.834639475515,7.57077885540754,76.1922452752007 254,417.632242312575,5.01418489408449,83.2901560541334 255,189.178267404063,5.93266087882364,31.8875916335158 256,110.734191742325,2.92178087703896,37.8995538688538 257,158.04862300712,3.03681720430436,52.0441674207797 258,549.7790952933,6.38726294390543,86.0742856715936 259,771.640801166783,7.04852836803097,109.475448047653 260,430.246987615493,4.65318810508936,92.4628400783791 261,346.359379184053,7.5015570030073,46.1716653016435 262,975.801001719577,4.80850358008868,202.932364605119 263,1315.66173593951,11.3951719718132,115.457821891051 264,576.222160143937,4.97484243894201,115.827218091048 265,412.358846415636,5.74353096634222,71.7953553018358 266,660.267723190285,6.1584546803647,107.213214590253 267,589.265515745625,5.66229249038105,104.068363961532 268,836.299919499441,5.56224407242757,150.352970601387 269,1319.61240409077,11.9865929919981,110.090699248044 270,76.9386078845709,4.20653083224705,18.2902755151023 271,1203.06911393861,4.65387893355974,258.508897870788 272,158.813219162244,5.11026919590893,31.0772707021743 273,531.625846529593,5.26292150619059,101.013447740815 274,940.392060345556,7.75933640221694,121.19490786311 275,675.192450291204,4.42969719369742,152.424064392453 276,527.43144793996,6.84242461376165,77.0825369239987 277,1319.80680856013,10.277829665352,128.412987131843 278,955.268634472655,10.4054136521036,91.8049648395796 279,325.468398428997,7.24227009104575,44.9401077752405 280,400.933471805248,4.00004185338329,100.232319185894 281,1325.77960338102,4.9118157113997,269.916397780165 282,489.345546650158,9.88271931591126,49.5152731761093 283,1293.72834674038,11.6748748761547,110.813037438436 284,806.928750634983,4.95971079636046,162.696734500553 285,695.647937109771,6.26837239860235,110.977442448199 286,538.657203479221,5.28855704057084,101.853340967478 287,727.55331718038,6.18238108794256,117.681732463779 288,109.277615313159,3.12552842019265,34.9629248632535 289,223.571813289553,7.16202842807971,31.2162700182827 290,382.752054496402,8.04802999151378,47.5584776522942 291,561.479960811569,3.69502056068951,151.955842082458 292,753.966911082262,5.22920425959736,144.183870748303 293,1103.35906346806,10.0535133817513,109.748604450145 294,391.558967307844,4.49421413598571,87.1251247626553 295,370.546474356103,7.39323907173502,50.1196391406757 296,809.916210213678,7.57621328307539,106.902509202448 297,661.862949786433,5.31042119312058,124.634737192569 298,940.101921882978,10.1240311473805,92.8584580783534 299,558.638305291894,6.51956331529195,85.6864606225359 300,101.182083440555,3.48332969097975,29.0475184426472 301,699.758177310983,6.52683236530832,107.212524873531 302,940.827322153705,4.11601585904305,228.577185893653 303,481.038853666049,3.65366157121042,131.659389981948 304,652.219475009659,5.61677966742443,116.119825527843 305,353.135312599842,4.65760211581875,75.8191240510817 306,169.682263138503,6.19098386593491,27.4079640349506 307,905.898978825545,7.12293211472156,127.18062789806 308,626.613220392914,5.2004177199461,120.492863100122 309,460.96160034408,6.4585405258265,71.3724096799858 310,384.06120650799,7.49156758033583,51.2658001665886 311,998.025430316007,9.63661686586908,103.565955169475 312,516.468589757692,4.64917193003444,111.08829648162 313,970.632427693536,4.93974712133624,196.494355652557 314,925.845936398627,5.42376894354759,170.701581508199 315,421.336899752695,4.44187646196928,94.8556096415832 316,738.784541906404,5.41990801224091,136.3094244843 317,1096.9846367387,10.4713583394471,104.760490585658 318,452.321710322474,6.24938953959902,72.3785431291097 319,409.605786037976,8.04094282777195,50.9400196980971 320,102.287460999453,3.1553270983591,32.4173874247925 321,472.127167529192,6.6827192830028,70.648960031888 322,540.059488113134,6.81509876050291,79.2445578695151 323,622.636523327125,7.3981404559442,84.1612195706361 324,122.590179913927,4.77130175112903,25.69323557977 325,591.747207938315,4.86244721240049,121.697405049294 326,779.196514122214,5.73035315165429,135.977049494283 327,489.872495455394,5.31042542758677,92.2473165540728 328,726.483441465791,6.260795659741,116.036919418617 329,613.982257355448,10.1444447007423,60.5239887906846 330,634.252608881127,5.08976508685377,124.613336383505 331,901.985690895881,5.35929574098963,168.303026085536 332,659.708705342733,8.47152254002399,77.8736882568531 333,752.99016577877,7.37556219190177,102.092579004423 334,775.2938758776,8.439562837187,91.8642222155685 335,846.09125333199,5.66677773537919,149.307294699352 336,494.73393126766,4.48801000722954,110.234587371845 337,979.880865238625,4.89417494128454,200.213698323877 338,589.055704975882,5.96841402841206,98.6955164591028 339,487.216641835129,4.8447674233329,100.565537880857 340,198.591406523838,4.8919755521036,40.5953391239745 341,409.586472040896,7.6046274951649,53.8601624210147 342,609.139831752487,6.97285929075553,87.3586869248991 343,562.070367675752,7.63484495279803,73.6190939240703 344,695.329369579615,6.65550991577794,104.474244404809 345,523.856265790079,6.29700440466113,83.1913449833883 346,784.839938486554,8.33031953761429,94.2148659415439 347,933.457314250363,8.6596843402609,107.793457310043 348,427.456671139366,8.04349991061574,53.143118777836 349,950.074101468039,9.06205946665952,104.840859295118 350,494.113338108466,3.67127606204135,134.588990247092 351,574.903207511164,5.18790579653571,110.81604602286 352,638.893719088529,3.99126801207957,160.07286836036 353,968.134511027729,4.54486547218059,213.017198628594 354,381.673866122807,7.67087849845298,49.7562132159675 355,881.13644748383,5.13737973341,171.514759120008 356,618.922357178502,5.759699430787,107.45740548026 357,198.607151994154,6.93913375175162,28.6213177464724 358,781.547601605375,8.19999261521092,95.3107689579635 359,959.608426416626,9.21417720260633,104.144776610677 360,109.74304887471,3.92845032477607,27.9354554091161 361,751.637490270261,12.5526274776228,59.8788971958406 362,783.005691204304,4.12612995944813,189.767578554174 363,621.147351103776,5.64206009594483,110.092296172141 364,559.608020154014,4.91569044220145,113.841184007388 365,796.609802272414,5.23242323333337,152.24490962382 366,374.941868803699,4.79466543030541,78.1997981410386 367,840.824731314084,8.14210721436228,103.268688212667 368,513.812163735259,6.22078883514413,82.5959821739157 369,674.572209462169,6.05809363313358,111.35057500147 370,801.260072138537,7.50088789903639,106.822029994805 371,540.62672699841,6.37256112045472,84.8366483709509 372,390.405340803122,7.50701596131035,52.0053963938791 373,900.6418234615,8.41484726114433,107.030085693917 374,216.000750046229,5.89991755227253,36.6108082244353 375,149.916344129949,3.61062727399239,41.5208584973052 376,620.918231999434,10.388553715758,59.7694586742703 377,476.307825573929,7.499623852073,63.5108953420739 378,451.850366440746,4.38554348954287,103.031783293944 379,923.209964002848,5.21444984086693,177.048392865422 380,611.099378902982,5.26843223057695,115.992643002273 381,494.253379913041,5.66352712573916,87.2695352100984 382,816.215954231671,8.39721498147583,97.2007928857645 383,976.669541180908,9.31226500243959,104.879912773643 384,152.641402495647,3.27024948100198,46.6757669047556 385,675.67591693434,5.68500767169711,118.852243647481 386,787.938100127915,3.6216683404359,217.562191250532 387,682.843173868159,6.55022539967252,104.247278864983 388,638.418893624038,3.90189887420475,163.617488357936 389,851.727837497005,7.68751198640299,110.793692289972 390,556.42205513466,4.8951011702227,113.669163472947 391,523.733161797886,7.55597048284735,69.3138178592415 392,485.807529115287,4.73185551754285,102.667447751565 393,1060.21601867565,5.04470765402127,210.164015714672 394,831.571970107557,5.71959916498163,145.389903404224 395,819.216150348264,5.68045751329172,144.216579110288 396,628.65757491269,5.20114735299737,120.869018361958 397,914.596515194875,5.98180911388771,152.896305746617 398,824.264738519433,6.26564016193443,131.553156136715 399,675.839046197227,7.62157315116603,88.6744813429797 400,156.70936927354,3.88529322160385,40.3339877675565 401,764.497773429644,3.69670689941294,206.805081990961 402,1022.25299664792,6.00090330364025,170.349853167574 403,434.342447179386,7.91709319763724,54.8613533195504 404,545.515295272911,3.56100842792824,153.191239592288 405,127.87834857968,4.09236981845031,31.2479942558331 406,386.998118999461,7.20549559266565,53.7087441137817 407,848.052117943561,7.78404031166005,108.947549600074 408,188.738867582271,6.03136126523553,31.2929137026086 409,793.507881855528,7.40771034664317,107.119183219024 410,694.736328914123,6.26191990096739,110.946217757719 411,1087.24836606028,8.24293518263694,131.900632720063 412,579.225239637382,7.21479800927357,80.2829460911965 413,449.896522495776,7.6428707652119,58.8648606415763 414,481.608974102715,7.48183955351905,64.3703958976496 415,683.947511404036,8.28230090815064,82.5794086678208 416,560.362439390747,4.385113859198,127.787432067552 417,1091.42931780311,10.6817246382677,102.177256460349 418,647.620097051185,6.12578913312164,105.720272601216 419,855.774804797403,7.96583532876967,107.430642170904 420,492.476568201643,4.12690418266153,119.33317237427 421,831.529675540752,4.60107126012412,180.725233001134 422,686.189350142989,4.74973722682027,144.468907936274 423,608.430142029746,10.0212454416168,60.7140245765283 424,525.783827437897,6.4352465154793,81.7037585387258 425,194.488630624881,4.76692187317194,40.7996262157045 426,987.814650377906,5.26808378865114,187.509289906497 427,430.692521759793,4.90697868970632,87.7714269807781 428,584.783053385078,6.87788933597804,85.0236205933257 429,564.437273863266,5.37346053625163,105.041671015416 430,658.774352361513,6.64776873465221,99.0970622861142 431,832.205734282893,7.76679292150943,107.149211095634 432,149.789830487304,4.39301345151843,34.0972847318574 433,731.316001578312,4.33591500465811,168.664745686355 434,390.388355988516,7.55148478089593,51.6969003203366 435,391.03670022181,7.28894748168562,53.6478965178907 436,599.785054162366,5.44015864785354,110.251390260285 437,562.314650063609,9.75145692036191,57.6646807401103 438,892.027263732429,5.39193778184675,165.437232368603 439,801.909006806316,7.6494306247857,104.832509259966 440,623.218920572504,4.95274485041268,125.83303590141 441,472.803385486657,6.2468634342978,75.6865249992142 442,284.931102399285,5.53547412978692,51.4736580315755 443,783.428649920795,7.4389234792412,105.314788101666 444,898.468106781393,7.59887774523923,118.236947205039 445,766.860466046303,5.9303393239855,129.311397569563 446,663.550758009001,6.80319979533089,97.5350978909076 447,1065.54188317982,10.4203881944936,102.255488307324 448,492.35403534789,3.41197830930699,144.301631110865 449,809.662746988605,3.75296723897789,215.739359134164 450,147.451863291934,3.77201910358311,39.0909640812441 451,756.091147986454,6.48606312284935,116.571660445744 452,595.314067501916,5.05358569899699,117.800330885864 453,1058.42510903773,4.28480204239349,247.018438323581 454,689.063268549226,7.18845734468546,95.856904410605 455,600.91663917742,5.38563997518527,111.577573314627 456,674.309731096883,6.32016922269077,106.691720955187 457,750.736157491946,7.07683134652074,106.083658170127 458,661.960722893855,7.15171158820548,92.5597620554991 459,189.440774013471,6.18505572427405,30.6287901772633 460,551.772203810844,5.87048330374678,93.9909331585495 461,811.473144674888,7.67510370221381,105.727971394162 462,633.814173185857,5.3768884124323,117.877501738807 463,810.681501264912,6.22173760985763,130.298246583154 464,391.236056774239,7.10092172193747,55.096517338807 465,380.206821299068,7.59001904750258,50.092999624839 466,652.613015692748,7.14519568000966,91.3359192553093 467,785.84208906336,7.44283914121426,105.583645454838 468,542.084077773696,4.98983936016438,108.637581021414 469,1038.32601978614,6.04511716199487,171.762761905427 470,608.355664929834,10.5179224269714,57.8399079432086 471,944.885671612098,5.37734930652325,175.715881143496 472,460.496214669603,7.7817148366845,59.1767013227901 473,684.112195487549,6.72618717152283,101.708765760181 474,864.527279588159,5.61700257565444,153.912565989421 475,771.698207770463,4.89274396985433,157.722989906099 476,266.473262695194,5.59528602106853,47.6246007249342 477,508.686673582495,6.66875243606987,76.2791359341992 478,655.437300677378,7.11601773744166,92.1073168815654 479,785.891318553757,7.65488244831632,102.665367346903 480,148.789986940107,3.6644691199445,40.6034222338761 481,971.222766756003,8.45121392330103,114.921096018907 482,554.715783997261,3.93865496146435,140.838887748376 483,694.26212830919,8.3271621796523,83.3731964540864 484,646.186870301022,6.15318145645042,105.016709628093 485,724.487746474418,3.95313883803676,183.268986027877 486,168.409212113894,6.05040286501071,27.8343799365493 487,687.822122514261,6.40240280383259,107.43187262484 488,424.012366373052,5.15227920531328,82.2960770324307 489,797.536079428995,5.88174935839609,135.595046784938 490,490.169254027678,5.18911498669616,94.4610507349273 491,688.379490586977,5.4474714998763,126.366790648213 492,819.768972919284,6.55951902427568,124.973945480676 493,450.75665922744,8.52571617394483,52.8702398755642 494,783.673478318083,5.96671007489725,131.340968218835 495,627.791370972855,5.68945453177952,110.342980590882 496,430.758887795221,7.75092293223226,55.5751736356334 497,1002.35062404769,5.56733103805451,180.041498735444 498,763.618257042825,9.19690076867435,83.0299550087342 499,728.733682452732,7.29388618937792,99.910207471291 500,177.537235352487,4.07819888015864,43.5332460651307 501,837.000531352696,9.15817598478558,91.3938029519414 502,664.732949242104,4.71177311937794,141.079150544894 503,740.496411688008,7.19768602553609,102.879787901398 504,488.327379387896,5.07508243179089,96.2205808380487 505,583.733087791724,3.90810878918681,149.364595327241 506,600.164605506714,6.97950896971682,85.9895170434984 507,603.505737174284,6.37222807505323,94.7087470922395 508,542.214598197208,5.86485263473014,92.4515298110568 509,773.371742646601,8.00944694940629,96.5574461672323 510,253.479245875098,5.72767688872876,44.2551580334268 511,909.571298558846,5.66144030976592,160.660759239984 512,191.836498116332,3.41849022981593,56.1173164817446 513,732.721224371974,6.49534214975691,112.807178971996 514,203.959819983088,3.39939344217644,59.9988861108421 515,575.122412159116,6.68889039425816,85.9817366199945 516,759.434785432332,6.68422936568084,113.615907516809 517,634.635289856642,10.4440483881157,60.7652575201386 518,867.797608652772,7.73574526316025,112.180220409462 519,824.111659460536,8.45866153984936,97.4281398514513 520,565.18307163623,5.07383283710044,111.391740678476 521,1498.25459791786,5.1053144610599,293.469601010005 522,520.869833196188,7.98315104212318,65.2461453438389 523,1551.39940316362,11.4915239227771,135.003800504528 524,1072.27513227212,5.07979408329489,211.086338282557 525,496.446050570955,4.00397399200315,123.988330484282 526,1240.86848905617,10.8721457114637,114.132805242647 527,410.132072917508,7.53036068935294,54.4638019128868 528,626.510905262879,5.29300621632866,118.365798122459 529,653.465571117176,10.125320099112,64.5377691490944 530,576.432722269123,6.51537698966783,88.4726583255639 531,448.798779660079,7.60795714905048,58.9907081319579 532,795.055841530106,5.82506541467312,136.488740457298 533,896.232103806864,6.75377440891398,132.700923889902 534,777.302708365584,6.03950554321713,128.703037492624 535,587.686567138934,6.74832058178945,87.0863439304921 536,1104.59737008177,6.76169203839275,163.361088291198 537,804.759193188106,8.86661404093707,90.7628537198688 538,1261.51856059997,12.1362520416372,103.946305356212 539,726.098874970669,6.51323702143681,111.480493122066 540,170.061347621322,4.38975987523666,38.7404670083814 541,1385.49522203287,4.25694660421781,325.4669017131 542,1260.903377379,5.20984537887143,242.023186041682 543,807.992663068268,4.45424897331231,181.39818135658 544,234.526631063782,4.86455413703312,48.2113312869448 545,637.435073965456,5.92229152647252,107.633180689626 546,573.25506277815,5.84569260626933,98.0645239818719 547,1400.76348486921,5.65668974648638,247.629540888165 548,1098.34495754179,9.07992034043053,120.964162279172 549,428.21642409432,5.33398573261271,80.2807591846649 550,681.193482488049,5.02804345553242,135.478837546347 551,535.035858791042,9.11232453363817,58.7156281381283 552,650.750667048643,7.13475830249594,91.2085090283986 553,939.947384473715,6.175071206677,152.216444639111 554,1256.47507964087,10.1193420432122,124.165689258788 555,916.245660731232,8.36210132460401,109.571222012742 556,1098.05693562896,11.7022828109106,93.83271224698 557,1386.65889150992,12.1485188844183,114.142218051655 558,524.108548674871,8.10595905419229,64.6571917241316 559,799.13154953098,7.66683827226862,104.232216873738 560,540.523334755136,4.86288239635866,111.152869985069 561,266.762661882614,6.19213292409693,43.0809004187388 562,1286.22687536678,4.95733070258012,259.45956655612 563,1445.42082564087,10.4238848667998,138.664312212863 564,726.396844237268,11.0754427353918,65.5862579575308 565,631.584554468889,5.32108897282594,118.694605125812 566,1267.22683419539,12.2029700056616,103.845771448054 567,475.20381990524,6.35243159686285,74.8066016389566 568,1010.87332174474,6.19610715982229,163.146520173117 569,1457.87210841751,12.1397222044667,120.091060064052 570,796.256209167334,5.93431937412018,134.178186067949 571,1503.79701598318,8.01483185400126,187.626770389754 572,606.443552778871,5.75869147669246,105.309262570042 573,857.184394886198,9.19244588509806,93.2487833598005 574,823.574399805857,6.62117625592903,124.384908054422 575,677.600101062989,5.58337601390817,121.36028441844 576,190.063066625296,3.41498854289748,55.6555503006271 577,1366.23434339652,3.54288523291388,385.627603938173 578,268.390001282356,7.24559323510984,37.0418256412496 579,837.415055509825,3.93295667782809,212.922522190677 580,471.591710735791,6.86735717433307,68.6714989134944 581,814.489698512036,9.08201233993726,89.6816331035355 582,753.861098194257,4.15695175592509,181.349494162338 583,568.744369625575,6.8518663117772,83.0057598537787 584,918.716211917827,5.74715222150621,159.855903673463 585,566.157202838182,5.24149848322371,108.01437883656 586,1197.6385242667,11.3385518035309,105.625351898446 587,1395.09553251849,12.141802479261,114.900199941599 588,518.813606204685,5.43046019815844,95.5376869129108 589,559.276920152753,8.05582390081343,69.4251670640765 590,489.068368362511,8.30349736251222,58.8990815569482 591,823.379947292871,5.97074967726284,137.902272210201 592,929.258609434265,8.1490647899677,114.032546480459 593,1388.42007465563,11.9994148660581,115.707314911077 594,748.249202000277,5.79291247609112,129.166322655227 595,259.623375175152,7.06607898619062,36.7422124324592 596,1064.27412315248,11.3037770256769,94.15208038295 597,825.71323631448,6.75568775547254,122.22489644309 598,671.715852046562,6.61682577736479,101.516327412519 599,1373.58178467059,9.23673888179233,148.708521724937 600,190.421089625676,4.12524307814985,46.1599682778159 601,1204.97073943955,3.92096689320629,307.31469360972 602,790.150694961337,6.98083584193909,113.188551178114 603,1083.42056362943,6.16423421712628,175.75914955005 604,1039.35736325981,4.55245060760721,228.307224579885 605,699.591073980053,6.16711781316787,113.438902121556 606,635.103150356197,3.85319027131681,164.825276105339 607,1228.3312046364,8.03902083004798,152.796121642724 608,787.869923321634,4.90163511777552,160.736143019799 609,485.792080496192,8.42377666750146,57.6691547830744 610,469.539917738897,5.12249147893378,91.6624106979732 611,718.89456610235,10.1904367662041,70.5460013732201 612,246.301311426979,6.09738381576806,40.3945887070509 613,1129.94223342683,6.49283720353658,174.029041235065 614,1022.32627451459,7.72433535716289,132.351358044879 615,809.708663900494,6.62869021240698,122.152135332098 616,697.438607682519,5.69139420256608,122.542664039694 617,1197.24461561026,5.31408303695375,225.296557709902 618,687.922357513737,7.36097643222815,93.4553131432191 619,1163.18878738785,9.70072078618196,119.907459767807 620,483.72726147557,7.08880357825006,68.2382091894529 621,691.039050680961,7.22048424514535,95.705360917528 622,1060.45527363896,9.08749401737319,116.69391711418 623,829.186845320996,6.33828711351301,130.821912998103 624,623.082918985416,5.33161498261693,116.865700358503 625,185.411126618826,3.81559096755941,48.5930300693162 626,1067.68237278954,4.90030081145065,217.880986060011 627,831.675785680329,6.34222706713891,131.133082571185 628,1021.10184670803,5.98943841207216,170.48373761552 629,948.257944091708,8.05010876625382,117.794426339532 630,520.458170342153,5.15399995549776,100.981407612738 631,1350.03416524413,5.44963260611805,247.729390735168 632,947.673534642313,6.15639005074959,153.933315925447 633,691.70739238333,5.02498672569535,137.653576047529 634,1244.82851268428,11.1589404794215,111.554364411201 635,588.117229793036,5.69057024161472,103.349436844163 636,628.303008148543,6.89327321713906,91.14726608926 637,645.333590863415,5.83011120441156,110.689756719409 638,535.273235513216,7.65741146898357,69.9026345497231 639,1059.02619837487,5.65982246304366,187.112971350229 640,186.796588030041,3.70786820561626,50.3784324769427 641,1201.03553075966,3.5621432773882,337.166541947821 642,645.032398916213,7.31694930751662,88.1559201528946 643,1221.92995714235,10.4010289754838,117.481641482064 644,646.63197032523,6.48432544442444,99.7223189778726 645,781.860362175706,6.90715255815611,113.195756947987 646,750.451534889,7.42888455233244,101.018063964042 647,1221.86908164988,10.2931552116762,118.706952000863 648,214.863474871702,5.66276105583057,37.9432352439578 649,539.598795341489,8.25469062061373,65.3687485263221 650,614.168829833405,5.39044485645549,113.936575957713 651,458.988628167404,7.85561113018796,58.4281248856093 652,821.63896723908,6.07965901432378,135.145567424634 653,1144.02233995556,9.73663504045274,117.496684963799 654,673.971344075337,5.873867651051,114.740641790719 655,1124.27020602021,5.39474178920782,208.401115372993 656,843.02688487024,6.83398311674054,123.358057880646 657,999.578910478347,5.62860868515041,177.58898626502 658,713.000242574187,9.86808012856652,72.2531873763535 659,1200.67169165136,10.4499873207634,114.896952005455 660,696.580426121324,5.23526858447892,133.055337062646 661,1191.60035759226,5.33187107362349,223.486341124609 662,1021.86302922336,5.59044654185529,182.78737155838 663,286.589693627204,5.57850375732662,51.3739357530784 664,822.662777572089,8.78430387105964,93.6514480427294 665,771.799655220865,7.48640591545508,103.093482231246 666,939.315204610539,7.66330929802286,122.573051416949 667,568.141191887983,8.36625070058969,67.908697960478 668,842.787494589472,8.78271287912091,95.9598140334321 669,635.985171234099,6.65626678128311,95.5468270926938 670,1116.34581408648,6.14091469767802,181.788197531647 671,510.454282219038,5.19131763515576,98.3284626550736 672,518.090150540254,3.81315418809747,135.869184665399 673,1162.49495229153,3.85066477092853,301.894613384173 674,1018.37232837763,4.76328443633686,213.796245424469 675,184.206884561851,3.89340782201769,47.3125069303396 676,763.245320149297,5.87802488351934,129.847242104957 677,1149.83369661697,6.06299618408454,189.647768480426 678,658.714126920765,5.17101143773156,127.385935005731 679,749.831736234241,4.00015722235298,187.450566203789 680,246.728031639254,5.29077755438329,46.6336051937858 681,685.366494014556,7.22825818953031,94.817655380278 682,475.116569315815,7.53328465364152,63.0689786939284 683,1184.62454049305,9.79011517254363,121.002104634615 684,769.438729510337,6.05539241846815,127.066699618616 685,1139.44056987355,8.68321930125727,131.223286011971 686,559.3982097035,5.39236364361152,103.738962480068 687,668.919915625723,7.27436331032118,91.9558024654378 688,795.073583813363,6.86413996442611,115.830036673769 689,615.794581609889,6.94210245288475,88.7043350035837 690,661.073178425251,6.18806546772236,106.830346555556 691,1164.93615155336,7.99345343188465,145.736278003023 692,831.058130277,8.69201430219884,95.611684631808 693,736.425280665839,5.53389328736211,133.075439374234 694,1023.31218976872,8.89024464143303,115.105065275658 695,1158.03252705707,10.9696431454976,105.567019063184 696,514.28870148554,7.31974807924209,70.2604373699691 697,856.225019097665,6.44187303693948,132.915537792787 698,1016.98754809235,8.81858563417589,115.323203774432 699,665.588439830414,7.19693966669527,92.4821480594741 700,526.391986344262,4.21949681545386,124.752312744107 701,1165.37448932601,4.38045756830065,266.039442490959 702,678.216658066484,5.40339211433159,125.516831596883 703,912.726735088656,8.19770964779994,111.339236726152 704,792.667262489475,4.24658509609169,186.659926635875 705,721.328206250743,9.83528745803807,73.3408361807691 706,1006.81905594603,4.6348105131083,217.22982052848 707,632.417690190266,3.91199587812754,161.66113408406 708,483.788170621505,8.28952396106429,58.3613935967671 709,1180.0578098656,10.0809700432916,117.057962160187 710,1094.1049679917,5.70314973767663,191.842230752549 711,983.484023434481,6.03141293589908,163.060303429196 712,839.796815738163,6.27347932910202,133.864602349518 713,498.163250755859,7.79280763067061,63.9260295346197 714,249.375683499672,5.76549542786498,43.2531231044646 715,648.673776919271,5.90636315191071,109.826260295123 716,810.439719305663,8.80286145124323,92.0654861824735 717,664.880282833152,7.28110754270968,91.3158168497145 718,1040.49619508955,9.17530187152301,113.401848752126 719,1142.49809814831,9.81760167974898,116.372423267586 720,183.427577741298,4.40541149021632,41.6368773152428 721,647.524237020807,7.25837308482294,89.2106577401983 722,767.783152354092,12.0808790347792,63.5535833231793 723,558.192381813456,4.05721166371335,137.580296045628 724,818.244915678415,4.60383692718187,177.731081404589 725,513.802585053426,6.46345236829243,79.4935207651522 726,748.129377662551,6.36606732587643,117.518294948217 727,930.797796519286,5.69582745852376,163.417484693353 728,684.647624065403,5.77955485165742,118.46026928338 729,219.996001887404,6.22927586112627,35.3164648334627 730,1011.95963548093,5.95706375069698,169.875575926567 731,794.028616515608,7.01042329901881,113.264004561143 732,467.282532768426,5.1528992886352,90.6834204578819 733,1069.25759805572,9.13085642517322,117.103757661531 734,931.874988870851,8.5458002977408,109.044788832382 735,544.254437821785,5.51656772847817,98.658162939282 736,641.717463267959,5.37048520959107,119.489662148576 737,1165.98758881702,6.71601966563961,173.612890799356 738,817.687504453665,6.57516837356925,124.359933920566 739,1072.7956761926,9.22215383286713,116.32810465265 740,953.010948098821,8.3579434240636,114.024575155053 741,849.048333348047,5.89507782431695,144.026653871431 742,638.561325896524,6.64361530426113,96.1165414690641 743,1101.80914542846,9.15332777371353,120.37252163007 744,470.074441260341,7.62859769479656,61.6200329427487 745,1160.7361991702,10.8239375151478,107.237888018642 746,963.431883446816,8.28802997043873,116.243774079381 747,866.168298826463,8.84608304235113,97.915460964998 748,283.192328350644,5.91012647281937,47.9164582438369 749,671.166116811921,7.0807393923008,94.7875750859733 750,243.898551471721,4.19171819214378,58.1858179132465 751,1039.24436450975,4.22355202194928,246.05932615697 752,698.067699980212,9.45936138067153,73.7964934299461 753,619.866164920823,4.39815783894736,140.937680642489 754,579.504392641967,6.92500055170117,83.6829381189881 755,1154.57758197929,4.60267613414812,250.849190411913 756,520.387945916268,5.36259542193208,97.0403144320701 757,1101.42467261315,5.37904101902734,204.762274300766 758,1068.15167862711,5.69988994821451,187.398649505805 759,736.558970969195,6.68514753929943,110.178416652624 760,841.498250114011,5.98737345871683,140.545475560557 761,1088.83706609367,7.20782438773424,151.06320680434 762,614.669904182212,5.45141118139912,112.75427292653 763,703.795711843656,5.68953453700622,123.700050903283 764,898.560993838497,9.29212766591708,96.7013181635848 765,250.019721989229,5.5636315514103,44.9382241938455 766,1076.33731223984,9.43700971799439,114.054911926973 767,578.379875701866,8.36706241482018,69.1257991188651 768,261.407844067136,3.60221544480678,72.5686311861222 769,1058.46047755996,3.51520480954299,301.109191329757 770,828.635444204477,5.64472671726314,146.798150860037 771,258.596043228279,3.65510906985955,70.7492001704386 772,830.785979683635,4.02040738188502,206.642238154013 773,1081.6329280676,7.83627784137471,138.028914997971 774,737.43211989366,6.83458862814405,107.897074720342 775,504.162201253966,6.48153149782499,77.7844250889081 776,750.254809125945,3.95000320655516,189.937772172152 777,988.268425641431,7.91180514339074,124.910612398865 778,953.815990154617,8.26735842704149,115.371312199893 779,868.741963483235,6.62289603331585,131.172520165364 780,715.504137445214,5.18499617711808,137.995113786739 781,1148.47685489369,6.03083766717465,190.434052162398 782,657.222686080398,7.62297873178148,86.2159936692891 783,494.965452359725,7.73470287206196,63.9928204802228 784,557.261352455066,5.48394851631976,101.616809639387 785,1102.54097434532,6.07368414528363,181.527545386349 786,1166.32732004847,5.54559146119544,210.316127361652 787,1074.62700041157,8.8998722055267,120.746340576019 788,854.61724157712,6.13633141588185,139.271689166792 789,1351.62926970938,11.219692212782,120.469371536729 790,1047.1671153504,6.23921949354871,167.83623599605 791,694.924970297679,5.53485607606488,125.554298205302 792,828.658324291027,6.1987878440561,133.68070421794 793,583.586339299211,5.57504510726259,104.678317048767 794,956.992678411413,6.25472340166733,153.003197256701 795,630.877350374125,6.8770409745273,91.7367444386193 796,840.838421331531,6.78928080801114,123.84793693308 797,1063.22014224949,9.52246292402638,111.653902013822 798,796.297391599454,5.65434238678711,140.829355056428 799,715.927689486895,9.86975411949112,72.5375405323479 800,261.285513892916,4.05362467622819,64.4572536340578 801,840.624134476516,6.48458391043287,129.634244245658 802,873.391146435482,3.97840066613087,219.533229488644 803,1031.80263140242,5.98427091837876,172.419104261067 804,1154.10913902807,6.51883044910028,177.042361822336 805,694.861207698147,7.94807907594487,87.4250496325796 806,564.497626576878,7.17964930696825,78.6246796245329 807,1383.46235940519,11.5619749634335,119.6562320694 808,673.43442131044,4.14958579815937,162.28955227511 809,948.197174728681,8.43882313873835,112.361304312208 810,208.623502843133,4.96579818612887,42.0120784259594 811,1057.66977184788,5.15522384859885,205.164664602363 812,593.651575758216,7.22807711349676,82.1313284898012 813,1396.12970397736,5.20764747205385,268.09220698396 814,977.665387314612,8.41429764093197,116.190967925675 815,944.894761745995,6.46839564012012,146.078690036413 816,252.951492564745,5.51978130692761,45.8263613174815 817,784.156766770674,6.99570660005625,112.091145555528 818,869.600167578196,7.87243636560573,110.461377798801 819,710.005098724058,5.50309249180486,129.01929229454 820,867.109088620376,6.72263215338102,128.983569059967 821,996.9140740984,8.47642794943843,117.610163154215 822,1126.36882497793,8.88531494012666,126.767462106624 823,1003.32995882055,8.46871277992595,118.474906977459 824,651.138598600569,7.56538358905936,86.068153839841 825,844.515428048511,4.99906689654685,168.934612303722 826,576.106357758339,8.31997517305508,69.2437592391028 827,992.109951666725,8.69421125713478,114.111553345631 828,644.278867143651,6.8390019653782,94.2065626542077 829,995.569189170372,8.40461371746591,118.455079868983 830,888.341440629926,9.27021884347079,95.8274508541515 831,1359.79569761804,10.5044294025864,129.449744055897 832,717.403415146655,4.50788710920317,159.144050808643 833,282.673947745812,7.18068756064488,39.3658609093453 834,1172.80276287497,11.7091856344188,100.16091635165 835,917.107055683623,9.11941039624942,100.566485752281 836,816.923640135252,6.3934086393777,127.77591519862 837,464.807691998318,8.59350796187048,54.0882366154401 838,871.791737168063,7.90450888893931,110.29043668835 839,1022.18824326786,8.74245131163486,116.922383303123 840,517.664181967137,4.56942708146627,113.288640509616 841,614.596857512926,8.87431988711801,69.2556573721301 842,866.811056971428,4.84157421287707,179.034962361205 843,1385.64909866304,4.94427040509522,280.253502566342 844,721.138910002951,5.16607141981822,139.59135509364 845,766.459058456285,6.28742039651727,121.903580501924 846,704.343411540687,10.5172162374966,66.970517258124 847,853.05006857076,6.86250901488793,124.305857627305 848,627.915550526086,6.8619150165845,91.5073341783574 849,1361.37466659606,11.6567072987945,116.788955208376 850,264.582605698173,5.22141664542672,50.6725710023377 851,938.370400044133,8.7910250297975,106.741864215321 852,1126.48315768714,6.02621798200202,186.930370101366 853,979.827315102371,8.22642997111633,119.107233458818 854,505.472876614513,5.23536674086463,96.5496595814476 855,791.750397920969,5.79928212229199,136.525587344258 856,676.154932193,7.80009581582238,86.6854649171655 857,980.277431315768,8.26757531265417,118.568914614588 858,734.001552531788,6.46964545506599,113.453133966875 859,976.72574024949,6.61205773000456,147.718876654275 860,846.300973131295,7.44076212734995,113.738479828639 861,838.113161688194,6.7662433894219,123.866836212021 862,854.539016707292,7.63843565109149,111.873563611835 863,961.92479533997,8.21724556847167,117.061707274604 864,265.61340634876,3.7675920348921,70.4995137182804 865,894.324214970059,8.85877921888969,100.953437586872 866,814.037656409623,4.79656317905701,169.712693447657 867,354.813887078032,6.74212255100211,52.6264369112209 868,537.911300179912,7.30644314516087,73.6214994755931 869,1027.66604448814,6.11944653115932,167.934475651583 870,563.239265660982,7.16282295996165,78.6336991447849 871,1155.46921480469,6.74651209655846,171.269123699358 872,679.536842775566,6.54903469382497,103.761374697907 873,796.368567195073,4.09809608674832,194.326475108826 874,677.264357933236,10.1142345854229,66.9615038303876 875,547.431218112839,4.37188267386351,125.216356190333 876,1031.71986009956,5.94382843533884,173.578337821042 877,930.584545334349,8.11978348096504,114.607064032667 878,843.986776560976,7.50751451531843,112.418933701546 879,1293.52419141863,11.1188728178447,116.335910357987 880,782.904081094442,5.31759710225515,147.228920514196 881,934.64249263278,5.17238453228517,180.698570804026 882,623.226757624836,5.00169119192411,124.603205937847 883,970.418087129436,5.34674534314898,181.496971493672 884,303.442999442797,5.10890753980062,59.3948896273506 885,577.747766711815,7.9388103494478,72.7751062540499 886,846.511407749841,6.85323718340145,123.519934462518 887,926.231749745451,7.50618241684804,123.395848689538 888,993.086757584895,8.07749727783695,122.944858218613 889,658.641755700138,5.72367481631878,115.073231243376 890,872.453537277444,6.33804050887301,137.653512320731 891,797.358096929358,5.58361874545927,142.803105526821 892,666.490000569727,6.89938929096423,96.6013037476512 893,721.157101755568,10.0881652009048,71.4854572059238 894,1122.95075245574,10.9739659186592,102.328616726098 895,872.8020371521,8.4384510216238,103.431546253633 896,540.599731505117,3.93771639218296,137.287625025078 897,706.755078699019,5.98862192111668,118.016312936187 898,830.819157805731,3.67774353356128,225.904593461747 899,566.615005602821,7.93713998203914,71.3878055426776 900,271.187799297243,3.92609539932955,69.0731558238634 901,640.227831174316,6.19045180704092,103.42182624637 902,868.025803785126,6.41593790326442,135.292114243106 903,819.601359106328,6.81449205634646,120.273287037296 904,643.576442058412,5.06626012589972,127.03185901733 905,909.228848969586,4.40907620394749,206.217540117711 906,1100.01551637581,4.38446410339901,250.889388174722 907,807.99126506455,6.5042272373228,124.225559099182 908,711.79127060755,7.3585357114343,96.7300151172074 909,669.293105264384,4.21228556515497,158.890724503803 910,750.572267105405,5.68648946584241,131.992202151071 911,805.286978853394,4.93314934893751,163.239934956933 912,796.653528995929,5.59249094734205,142.450571041971 913,906.049765633183,9.57374609770754,94.6390009079246 914,860.082070314086,7.4264781870869,115.812912749086 915,528.897388614536,5.10146066915519,103.675677009997 916,725.916567325999,7.6165850238381,95.307354287263 917,1171.23104351,5.23507908183863,223.727478649405 918,271.115300648325,6.90657062855633,39.2546916884271 919,818.176466723655,6.80818727139773,120.17537622106 920,706.895049202311,6.03838191700707,117.066965772957 921,1129.85449184923,8.05363614390336,140.291226430006 922,830.569449354848,7.26352222623394,114.348028888113 923,1161.48155942179,6.02872257370251,192.65798769514 924,799.323463012984,6.17711733171301,129.400725304228 925,1026.06950758535,7.05544322910433,145.429489582273 926,867.636345570733,6.28542853165981,138.039330365533 927,677.359690770258,7.20771292456925,93.9770628851369 928,574.472527508353,6.05826381636739,94.8246139358146 929,813.483449106188,7.30120749106197,111.417659353202 930,531.893023362667,7.16985955006981,74.1845805553455 931,817.296013892808,7.58390641472478,107.767154445097 932,713.33088051632,7.42628177136628,96.0549171816682 933,1128.85728471138,9.27830227151485,121.666362193983 934,865.10116525594,7.54645816325339,114.636713878366 935,322.616153216964,6.0544173650657,53.2860775470281 936,720.972783584823,5.94554949433137,121.262598902291 937,778.06898147789,4.95602360965658,156.994607524036 938,1225.72719274588,7.27546359227065,168.474101643237 939,1168.23272198486,5.36011300850278,217.949270870163 940,765.901421943323,9.68520758686671,79.0795050156589 941,873.780025960545,7.54826679507052,115.759027824928 942,1112.44187725866,5.96549467070427,186.479401737079 943,882.998832097523,7.15128047545791,123.474227465674 944,575.434546744269,8.37017594281979,68.7482020300774 945,561.337326365201,5.50821831486128,101.909055574413 946,860.873094722788,7.76963546177053,110.799676375887 947,916.186682340258,7.82892276574291,117.025893568554 948,1053.07552206902,6.86382589509963,153.423985130633 949,1059.71160884098,6.08183818173075,174.241993485497 950,885.428522146107,5.57082744036225,158.940216983014 951,1346.16794720647,11.5902924741034,116.146158538645 952,276.925778486357,6.41786145411041,43.1492297654691 953,906.203977861731,7.84972926133348,115.443978727464 954,612.51743960058,6.76534728208795,90.5374719228815 955,910.89966686315,9.03533872521194,100.815220609428 956,697.293608862074,7.17228861535023,97.2205172237098 957,574.775710556546,7.45623254088008,77.0866127639178 958,856.841283734152,7.5473979729973,113.528037980734 959,1216.39447043105,9.17099860735247,132.634898609172 960,265.643639706113,3.80760425408198,69.7666096525991 961,574.173781708331,8.79751696155629,65.2654361699303 962,1030.97988591845,7.71773367834711,133.585833469606 963,655.361295957022,6.99537557792581,93.6849335188007 964,591.623032423643,4.09745863896031,144.387798524249 965,921.532980372998,4.19253766643819,219.803148758803 966,679.377025302583,6.21081358300074,109.38615629393 967,758.56647143844,6.7541568458606,112.311053585221 968,836.087844217789,6.84253110434275,122.189849263111 969,861.816646050012,7.54126557854249,114.280108169401 970,837.305406645717,4.35981566855886,192.050643949011 971,773.056494583846,6.6839984607787,115.657790635365 972,269.738705701556,5.71159260778726,47.2265310613698 973,1200.69158015954,11.6970528933106,102.64906819787 974,780.18977261685,6.80017251913039,114.730879315489 975,733.226488871681,5.62803285758601,130.281131511762 976,555.196730673397,5.30130803373895,104.728253317856 977,857.108003346016,7.38134769535594,116.118090993773 978,952.428525591511,6.50987729759852,146.305142485997 979,895.483515207574,6.55316117369628,136.649090640705 980,691.721941873944,5.03912244230137,137.270318352898 981,726.616137700927,5.79639551291027,125.356548924679 982,764.194888551527,5.26784395151202,145.067867534721 983,915.523888569179,7.25925208793643,126.118211281106 984,892.514888148552,8.5138339334884,104.831136609081 985,1005.63589199243,6.16271684835684,163.1806095814 986,568.845855194287,9.01718229882504,63.0846573067963 987,745.562092716827,10.5046803032647,70.9742772928671 988,1041.59114555383,5.50326221462461,189.267947797555 989,881.607367727917,7.34930171027716,119.957977299406 990,794.837361604731,5.85799270066536,135.684252647575 991,865.27837268516,5.94047899888039,145.658013915753 992,557.587178042882,6.1900366855673,90.0781701896781 993,1162.79627857404,5.62961439304765,206.54989798414 994,1185.59999212125,5.53102262783689,214.354572724814 995,942.413740908592,6.3137889802588,149.262787187728 996,934.298073132544,8.82010989166804,105.9281669512 997,870.93256880831,6.77095092972731,128.627806913288 998,812.641234560375,6.40692310560812,126.83798777748 999,1002.54718922372,7.14543610266103,140.305948415151 1000,291.449573656779,3.99018792068546,73.0415658234743 1001,776.653452684421,5.67712107032245,136.804102478003 1002,951.175605458871,8.38602789497823,113.42385422167 1003,593.159494315019,7.46548345115731,79.453594425029 1004,728.070226435854,4.76308964253058,152.856712990402 1005,1206.14720083557,5.78413280950817,208.526885629745 1006,878.910059385352,6.64649023509853,132.23671867357 1007,682.884348313215,6.82699019290724,100.027146519514 1008,559.048888273261,4.80850368562756,116.262547524761 1009,772.817533157271,4.3348413456067,178.280465544722 1010,730.999061202589,3.8148273381136,191.62048407781 1011,1131.82282383852,4.60962537080109,245.534665573446 1012,709.310865376529,5.85491570662902,121.147920980901 1013,806.677018536328,6.21137133728591,129.871001866201 1014,812.985332707849,6.03211400319479,134.776188294397 1015,613.07278843776,7.79899655181658,78.6091882929427 1016,668.043216728699,5.60852060576386,119.112197972876 1017,741.805247009802,5.05568094758426,146.727068954827 1018,846.833273326224,6.67139133984688,126.935032017723 1019,909.122842257941,7.05661884635465,128.832640964813 1020,295.142025029424,4.92560907112068,59.9199044763561 1021,930.461123973853,6.3584680673454,146.334166361916 1022,1030.02961536967,5.49102839930514,187.584099091532 1023,559.605990143784,6.94169606381837,80.6151673883523 1024,319.068029697597,3.61210863075487,88.3328997862718

The pre-release-4 tab is the one to look at: for most input sizes we’re within a factor of 4-8 of the performance of the vector-fftw package. To be exact, the execution times for our code are between 1.40 and 13.54 slower than vector-fftw, with a median of 6.12 and quartiles of 4.98 (25%) and 7.50 (75%). To my mind, that’s pretty amazing: FFTW is an immensely clever piece of software and I really didn’t expect to get that close to it. To be sure, we’ve done quite a bit of work to get to this point, but it’s still significantly less than the investment of time that’s gone into the development of FFTW. I have a feeling that we’ve eaten most of the low-hanging fruit, and getting that last factor of five or so speed-up to become competitive with FFTW would be pretty hard.

I’ve also done benchmarking measurements with this optimised code for larger input sizes: a selection of about 100 input lengths between $2^{10}$ and $2^{18}$. The results are shown below: they are similar to those for smaller input sizes, except that there is a longer tail to larger ratios: the maximum here is 15.22—the median is 5.99 and the quartiles are very similar to those for the smaller input sizes.

Size FFT FFTW 1024 87.49394674086957 20.55630031973121 2048 181.76302257925252 42.040198482573054 3478 1853.3776694908738 185.09373012930132 4096 390.79889599233843 85.48960033804164 8192 1010.2127486839914 177.04471889883263 8657 4708.614199794836 461.3350326195357 9086 3996.2647849693935 421.82430569082476 9415 6228.613703884183 778.119414485992 16384 2492.0199805870634 691.6926795616749 16856 5834.0738708153385 1007.6545173302316 19529 12992.324679531164 2444.8989326134306 21248 11021.344512142237 2074.8566085472694 23940 5932.366698421538 1743.7408858910205 24536 15700.454562343673 2414.4195014610873 24892 19178.597777523133 2179.910987056791 32768 7220.911830104882 2469.6110183373075 33571 29878.780692257034 4232.5590545311625 34780 18574.447482265557 3609.1516906395605 35958 18349.516242183774 3696.982710994785 40560 12912.015765346594 3462.7817565575288 42283 58961.57011333845 5712.201445735994 47665 62793.82452312847 6190.686076320708 50629 79750.49480739965 7187.00870815664 53443 58903.643935359934 6701.130717433986 54766 52524.26370922472 7452.642768062646 58940 22296.769469417668 7018.902152217919 59602 36258.537619747265 7731.134741939597 61202 48808.75334087757 8651.556819118548 65536 20226.907580532166 6319.017260707914 69202 50523.447840847046 9465.596526302385 74816 52708.96658245469 9562.048762477922 75673 63984.76108852763 10680.599063076072 75751 64004.59513012309 10679.452269710591 77841 39791.10225979244 9158.537238277482 81656 66113.01407162088 11950.569003261626 84755 44277.13140789421 11546.24685589224 88199 69382.6864654197 13635.709136165688 90725 55190.458148159014 11444.983332790433 93660 57280.29474560164 12409.379332698883 96173 40183.734744228466 12950.794547237463 99036 56893.52020565413 12472.44343105704 100779 97239.72544018176 13037.111609615393 101709 60115.625708736385 13058.013766445227 106188 126711.16337124267 14746.949523128584 106209 96156.72811809923 14851.078837551191 107943 72885.19367519753 15714.075415767747 108551 100098.40950313954 17052.57400814446 109616 47534.053176082656 12279.069274105135 110169 84087.73168865577 14926.893561519699 113756 134987.54724804324 16488.289683498468 116014 68652.34360042948 16784.331648983087 118128 89945.02052608869 15719.864218868333 121263 95224.32312313463 19073.588698543637 121809 115526.07282940303 17266.30911175164 122061 63832.17796627422 17255.163043178643 123091 162360.06960216924 21242.50158611688 124041 150720.79881969854 20417.518466152284 129699 123027.34121624388 20322.377532161805 130879 104332.14411083609 18590.02813640985 131072 62110.156863368946 13977.713435329508 133646 90496.5613776817 19275.166838802426 134256 105349.81474224478 18415.689318813413 135216 72718.66783443824 17970.90992275628 135518 143011.14067379397 21178.917735256284 137148 121270.22489849485 18165.948241390317 141628 124246.3181907312 21401.333659328553 144408 72285.35398785012 19518.00092998895 145198 92906.57743755722 20470.599978603455 146904 73992.79817882912 19883.439391292664 147366 101851.801722683 20557.763426937192 152342 76302.57114712134 22209.9851066247 155398 267659.1442519795 25328.59548870478 156978 99721.5102607384 17671.720832027517 161247 106458.11065975577 26277.75654140864 162423 194756.10718075177 25739.190428890328 164114 89873.88595882794 24654.161780513863 171892 100253.61522976308 22691.40943828974 174477 94842.68411938097 24811.680167354683 175813 94590.00334087753 25121.812670864205 178006 454508.38789287984 29861.605017818554 178025 128048.97770229737 24939.82538525019 182054 247542.43597332353 30033.895819820507 191258 233205.59725109462 29777.14285198604 192971 274799.59711376537 33996.438830532185 194666 222909.6673423422 32729.911654628864 199696 95961.14143673326 26793.114989437203 199942 176959.82202831662 33223.25453106319 202646 198171.88247982404 31819.317191280472 209466 118132.82951656735 27772.071211971383 212612 118961.6726333276 31378.276198543652 216113 412601.07730838243 41592.48565646518 218624 98954.9205205092 26820.80482455596 220362 133916.99289294562 32758.80311938631 222030 181025.3379246841 30516.612281526195 230270 257068.13072177314 34406.480540956145 234516 323926.16247149877 39456.29333468785 235846 123777.90187808362 34379.61553546298 237494 338569.7886845725 39272.682418550154 239491 265270.29012652783 36486.801852906836 241869 155717.2963521131 38900.701751435896 246308 269440.89149447833 40395.154704774526 248269 214511.25835391408 37460.25537463536 248329 333294.25071689056 41736.941089357024 254882 308638.6058232443 39243.81708117833 255579 307024.3499180929 39959.3660733353 256148 410313.2150075096 40429.47744342198 258840 193172.57856341713 33525.90536090243 259688 156256.30830737433 32994.611015046714 262144 204532.68741580367 26947.984447206105

size,rel4 1024,4.25630806030244 2048,4.32355291221089 3478,10.0131844995298 4096,4.57130334505071 8192,5.70597504950854 8657,10.2064960752245 9086,9.4737660468016 9415,8.00470157655514 16384,3.60278495670397 16856,5.78975608254369 19529,5.31405388837209 21248,5.31185840348695 23940,3.40209187409757 24536,6.50278650948708 24892,8.79788114808171 32768,2.92390654904287 33571,7.05927083528116 34780,5.14648567707446 35958,4.9633762656267 40560,3.72879859982365 42283,10.3220397028105 47665,10.1432739035685 50629,11.096479501533 53443,8.79010519554758 54766,7.04773666789864 58940,3.17667478273252 59602,4.68993735461021 61202,5.64161507129192 65536,3.20095779866032 69202,5.33758730371147 74816,5.51230890907898 75673,5.99074646568557 75751,5.9932469862387 77841,4.34470060278712 81656,5.53220637892446 84755,3.83476396793811 88199,5.08830789602262 90725,4.82224015041033 93660,4.61588716163002 96173,3.10280072760478 99036,4.56153764257501 100779,7.4586862759128 101709,4.60373428792162 106188,8.59236435118419 106209,6.47473016404474 107943,4.63821075989386 108551,5.86998827598295 109616,3.87114463767424 110169,5.63330416620823 113756,8.18687382616398 116014,4.09026376719557 118128,5.72174283910983 121263,4.99247019678082 121809,6.69083775123513 122061,3.69930888549376 123091,7.64317088286251 124041,7.38193522731767 129699,6.05378681807988 130879,5.61226391618496 131072,4.44351339371301 133646,4.69498200116769 134256,5.72065551923814 135216,4.04646554609657 135518,6.75252354541824 137148,6.67568922288273 141628,5.80554091480995 144408,3.70352241744109 145198,4.53853709879858 146904,3.72132792132693 147366,4.95442036215014 152342,3.43550753324738 155398,10.5674688662204 156978,5.64299941180641 161247,4.0512632991328 162423,7.56652031146063 164114,3.64538396230783 171892,4.41813081300247 174477,3.82250147832261 175813,3.76525390823335 178006,15.2204942641788 178025,5.13431733078723 182054,8.24210210551376 191258,7.83169823949515 192971,8.08318772691474 194666,6.81057956081641 199696,3.58155972064333 199942,5.32638432104423 202646,6.22803692764751 209466,4.25365571818227 212612,3.79121121506506 216113,9.92008702524484 218624,3.68948363659507 220362,4.08796964910159 222030,5.93202601437746 230270,7.47150323660013 234516,8.20974640784922 235846,3.60032827448013 237494,8.62099983587196 239491,7.27030807457284 241869,4.00294311776433 246308,6.6701289662998 248269,5.72636935356189 248329,7.98559362564021 254882,7.86464286042323 255579,7.68341392990638 256148,10.1488626851958 258840,5.76188999175226 259688,4.73581301613515 262144,7.58990668918132

This shows that we’re pretty successful at maintaining good $O(N \log N)$ scaling for larger input sizes, which is nice.

In the next and last article, we’ll wrap-up with some comments on what we’ve done, the lessons learned, and things left to do.