In the last article, we did some basic optimisation of our FFT code. In this article, we’re going to look at ways of reordering the recursive Cooley-Tukey FFT decomposition to make things more efficient. In order to make this work well, we’re going to need more straight line transform “codelets”. We’ll start by looking at our $N=256$ example in detail, then we’ll develop a general approach.
Experiments with N=256 So far, we’ve been using a fixed scheme for decomposing the overall Fourier matrix for our transforms, splitting out single prime factors one at a time in increasing order of size, ending up with a base transform of a prime number length, which we then process using either a specialised straight line codelet, or Rader’s algorithm. However, there’s nothing in the generalised Danielson-Lanczos recursion step that we’re using that requires us to use prime factors (we can build the necessary $I+D$ matrices for any factor size), and there’s nothing that constrains the order in which we process factors of our input length.
For the $N=256$ example, we’ve been decomposing the input length as $2 \times 2 \times 2 \times 2 \times 2 \times 2 \times 2 \times 2$, but there’s no reason why we couldn’t decompose it as $16 \times 16$, $4 \times 8 \times 8$ or any other ordering of factors that multiply to give 256. There are several things that could make one of these other choices of factorisations give a faster FFT:
We could have a specialised straight line transform for $N=16$ say, which would make the $16 \times 16$ factorisation more attractive;
We could save work by doing less recursive calls: there’s going to be less overhead in doing a single Danielson-Lanczos step for the $16 \times 16$ decomposition than in doing seven steps for the $2 \times 2 \times 2 \times 2 \times 2 \times 2 \times 2 \times 2$ decomposition;
We could take advantage of special structure in the Danielson-Lanczos $I+D$ matrices for certain factor sizes (we won’t do this here, but it’s a possibility if we ever develop specialised “twiddlets” as well as “bottomlets”);
One factorisation might result in better cache performance than another (this obviously is more relevant for larger transform sizes).
In order to take advantage of different factorisations in the $N=256$ case, it will be advantageous to have specialised straight line base transforms for various powers-of-two input lengths. I’ve implemented these specialised transforms for $N=2, 4, 8, 16, 32, 64$ (again just converting the FFTW codelets to Haskell).
For $N = 256 = 2^8$, we can think about transform plans that make use of any of these base transforms: if we use the $N=64$ base transform, we account for 6 of those 8 factors of two, leaving us with 2 factors of two to deal with via Danielson-Lanczos steps. We can treat these as a $2 \times 2$ decomposition, or as a single step of size 4. Similarly, if we use the $N=32$ base transform, we have 3 factors of 2 left over to deal with using Danielson-Lanczos steps, which we can treat as one of $\{ 2 \times 2 \times 2, 2 \times 4, 4 \times 2, 8 \}$ –note that the order of factors may be relevant here: it’s quite possible that a $2 \times 4$ decomposition could have different performance behaviour than a $4 \times 2$ decomposition.
For each base transform size, we thus have a number of decomposition possibilities for dealing with the “left over” factors of two. If there are $m$ left over factors, there are $2^{m-1}$ possible decompositions. To see why this is so, note that this decomposition problem is isomorphic to the combinatorical compositions problem, the determination of the number of ways of writing an integer $m$ as the sum of a sequence of strictly positive integers (where the order of the sequence matters, making this distinct from the partition problem). For instance, for $m=3$, we can write $3=1+1+1$, $3=2+1$, $3=1+2$, $3=3$, isomorphic to writing $8=2^1 \times 2^1 \times 2^1$, $8=2^2 \times 2^1$, $8=2^1 \times 2^2$, $8=2^3$.
The composition problem can be solved by thinking of writing down a row of $m$ ones, with $m-1$ gaps (shown as boxes):
If we now assign each box either a comma (”,”) or a plus sign (“+”), we end up with a unique composition. Since there are $m-1$ gaps and two possibilities for each gap, there are $2^{m-1}$ total compositions.
For $N=256$, we can determine the possible compositions of the left over factors for each possible choice of base transform. In the following figure, possible FFT plans for $N=256$ are shown, given the availability of base transforms of sizes 2, 4, 8, 16, 32, 64. Each dot represents a factor of two (eight for each instance: $256=2^8$). The factors for the base transform are surrounded by a frame, and factors that are treated together in a Danielson-Lanczos step are joined by a line (i.e. three dots joined by a line represent a Danielson-Lanczos step of size 8):
In total, there are 126 possiblities:
Base $\;\;\;$ $m$ $\;\;\;$ $2^{m-1}$ 64 2 2 32 3 4 16 4 8 8 5 16 4 6 32 2 7 64 126
It’s not too hard to derive the number of plans for an arbitrary power-of-two input vector length. Suppose $N=2^M$ and we have base transforms for all $2^i$, $i = 1, 2, \dots, B$. Then, if $M > B$, the total number of plans $P$ is
$$P = \sum_{b=1}^B 2^{M-b-1} = 2^{M-1} \sum_{b=1}^B 2^{-b} = 2^{M-1} \frac{2^B-1}{2^B} = 2^{M-B-1} (2^B - 1).$$
For $N=256$ and bases up to $N=64=2^6$, we have $M=8$, $B=6$ and $P = 2 (2^6 - 1) = 126$. It turns out not to be much harder to find a general expression for the number of plans in the more complex mixed-radix case, as we’ll see below.
A priori, we can’t say much about which of these factorisations is going to give us the best FFT performance, but we can measure the performance, using the same benchmarking approach that we’ve been taking all along. We need some code to generate the factorisations and to produce a value of our Plan
type from this information, but given these things we can measure the execution time of the $N=256$ FFT using each of the 126 plans show above. We’d expect plans using larger base transforms to do well, since these straight line base transforms are highly optimised, but it’s not obvious what choice of factorisation for the “left over” factors is going to be faster.
Here are the execution times from the fastest and slowest 20 plans out of the 126 (for comparison, the execution time using the $2 \times 2 \times 2 \times 2 \times 2 \times 2 \times 2 \times 2$ plan we’ve been using up to now is about 145 µs–the top entry in the right hand column here):
Two things stand out from these results. First, the fastest transforms are those using the largest base transforms ($N=64$ or $N=32$). This isn’t too much of a surprise, since these plans offload the largest proportion of the FFT processing to optimised straight line code. Conversely, the slowest plans are those that use the smallest ($N=2$ or $N=4$) base transforms. Further, the slowest of the slow transforms appear to be those that use the largest Danielson-Lanczos steps. For example, the overall slowest plan (by a factor of about two in time) uses an $N=2$ base transform and a single Danielson-Lanczos step of size 128. These larger Danielson-Lanczos steps could be more efficient if we had specialised “twiddlets” for them, but as it is currently, they do a lot of wasted work and so are less efficient than a series of smaller decompositions.
Exactly where the trade-off between larger and smaller Danielson-Lanczos steps lies isn’t immediately obvious. For example, the fastest plans using an $N=16$ base transform use $4 \times 4$, $2 \times 2 \times 4$ and $4 \times 2 \times 2$ Danielson-Lanczos steps for the other factors, but the time differences are small, perhaps not even larger than the margin of error in measurement. We can get a further idea of how this trade-off works by looking at the best plans for $N=1024$. Here shows the best 40 plans for this input length size (for comparison, the execution time for the “standard” $N=1024$ transform from the earlier articles is about 550 µs):
Again we see that the fastest FFTs plans use the largest specialised base transforms along with a combination of smallish Danielson-Lanczos steps to form the overall transform. In particular, we see that none of the fastest plans involve Danielson-Lanczos steps of sizes greater than eight.
The situation here is simpler than for the general mixed-radix transform case that we’ll deal with next, but these results give some idea of two approaches to use for a heuristic to choose reasonable plans to test for a given problem size:
Try the largest few base transforms that are available;
Use relatively small Danielson-Lanczos steps.
Within these constraints, the choice of which plan is best should be settled empirically by benchmarking examples for each plan.
Mixed-radix case Now let’s think about the general mixed-radix case. In terms of base transforms, for larger prime factors we can use Rader’s algorithm (which should now be faster since we’ve improved the performance of the powers-of-two transforms that are used for the necessary convolution), but it would be useful to have some other specialised straight line base transforms available too. I’ve now implemented specialised transforms for all $N$ up to 16, plus 20, 25, 32 and 64. This is the same set of specialised base transforms used in the standard distribution of FFTW (and indeed, the versions I’m using are just Haskell translations of the FFTW C codelets).
As possible base transforms on which to build a full FFT, we should consider any of the specialised base transform sizes that are factors of $N$, and we should also consider transforms using Rader’s algorithm for any prime factors greater than 13 (the largest prime for which we have a specialised base transform). We should never consider the naïve DFT algorithm for a base transform, since it’s almost certain that there will be a better way, now that we have specialised transforms for a range of small prime and other sizes (remember the $O(N^2)$ scaling of the naïve DFT!). Once we’ve selected a base transform size (which we’ll call $N_b$ in what follows) we need to decide what to do with the “left over” factors. Suppose that the prime factorisation of the input length $N$ can be written as
$$N = f_1^{m_1} f_2^{m_2} \dots f_D^{m_D} N_b$$ where the $f_i$, $i = 1, 2, \dots, D$ are unique prime factors and the $m_i$ are “multiplicities”, i.e. the number of powers of each unique factor included in the left over part of $N$. Let’s think about the number of FFT plans that we can build in this case. First of all, we need to decide on an order for the factors. Ignoring the issue of duplicate factors, there are $N_D = m_1 + m_2 + \dots + m_D$ factors and the total number of possible orderings of these is just the factorial of this number. To take account of duplicate factors, we need to divide this overall factorial by the factorials of the individual multiplicities. The total number of distinct orderings of factors is thus
$$\frac{N_D!}{\prod_{i=1}^D m_i!}.$$ Having chosen an ordering for the factors, we then need to compute the number of distinct ways to compose adjacent prime factors to give composite factors. This is entirely analogous to the situation in the $2^N$ case, and we can use the same result. One might thus think that the total number of plans for this choice of base transform is then
$$\frac{N_D!}{\prod_{i=1}^D m_i!} 2^{N_D - 1}.$$ However, because it’s possible for different compositions of different factor permutations to result in the same plan, the number is somewhat less than this. (As an example, think of $12 = 2 \times 2 \times 3$. If we use a base transform of size 2, we have two distinct permutations of the remaining factors, i.e. $(2,3)$ and $(3,2)$. Each of these has two compositions, $(2,3)$ and $(6)$ and $(3,2)$ and $(6)$. Because of the commutativity of ordinary multiplication we get a plan with a single size-6 Danielson-Lanczos step from each permutation.)
In order to get an accurate count of the number of plans for different values of $N$, we need to generate the plans to check for this kind of overlap. This requires a little bit of sneakiness. For a given $N$, we need to determine the possible base transforms, then we need to generate all distinct permutations of the “left over” factors to use for calculating compositions. We need to retain the unique result vectors of factors (some prime, some composite) to use as the sizes for Danielson-Lanczos steps. The most difficult part is the generation of the permutations–because we may have duplicates in the list of factors, we don’t want to use a standard permutation algorithm. If we did this, for the factors $2^{10}$, we would generate $10!$ permutations (all the same, because all of our factors are identical) instead of the single distinct permutation!
Wikipedia is our friend here. There’s a simple algorithm to generate all distinct permutations of a multiset in lexicographic order, starting from the “sorted” permutation, i.e. the one with all the entries in ascending numerical order. It goes like this–for a sequence $a_j$, $1 \leq j \leq n$:
Find the largest index $k$ such that $a_k < a_{k+1}$. If no such index exists, the permutation is the last permutation.
Find the largest index $l$ such that $a_k < a_l$.
Swap the value of $a_k$ with that of $a_l$.
Reverse the sequence from $a_{k+1}$ up to and including the final element $a_n$.
Short and sweet! Here’s some (not very clever or efficient, but good enough) code (here, Data.Vector
is imported, and Data.List is imported qualified as
L`):
-- One step of multiset permutation algorithm.
permStep :: Vector Int -> Maybe ( Vector Int )
permStep v =
if null ks
then Nothing
else let k = maximum ks
l = maximum $ filter ( \ i -> v ! k < v ! i ) $ enumFromN 0 n
in Just $ revEnd k ( swap k l )
where n = length v
ks = filter ( \ i -> v ! i < v ! ( i + 1 )) $ enumFromN 0 ( n - 1 )
swap a b = generate n $ \ i ->
if i == a then v ! b
else if i == b then v ! a
else v ! i
revEnd f vv = generate n $ \ i ->
if i <= f then vv ! i else vv ! ( n - i + f )
-- Generate all distinct multiset permutations in lexicographic order:
-- input must be the "sorted" permutation.
allPerms :: Vector Int -> [ Vector Int ]
allPerms idp = idp : L . unfoldr step idp
where step v = case permStep v of
Nothing -> Nothing
Just p -> Just ( p , p )
It’s more or less a direct Haskell transcription of the algorithm from the Wikipedia page. I’m sure it could be sped up and cleaned up a lot, but it works well enough for this application. (There’s also the Johnson-Trotter loopless permutation algorithm, described in Chapter 28 of Richard Bird’s Pearls of Functional Algorithm Design , which looks monstrously clever and deserved some study. Probably overkill for now, since the code in here is plenty quick enough for what we need here.)
Given a way to generate all the permutations for each set of “left over” factors, we can calculate the compositions of each and retain the distinct ones for counting (we just use a Set
from Data.Set
to hold the results to maintain distinctness). We can do this for each possible base transform for a given $N$ and sum them to get the total number of possible FFT plans. This plot shows the number of plans available for each input vector length in the range 8–1024 (using all the range of specialised base transforms that I’ve implemented):
8 4
9 2
10 3
11 1
12 8
13 1
14 3
15 3
16 8
17 1
18 7
19 1
20 8
21 2
22 2
23 1
24 19
25 2
26 2
27 3
28 7
29 1
30 12
31 1
32 16
33 2
34 2
35 2
36 24
37 1
38 2
39 2
40 19
41 1
42 11
43 1
44 6
45 7
46 2
47 1
48 46
49 1
50 7
51 2
52 6
53 1
54 17
55 2
56 18
57 2
58 2
59 1
60 42
61 1
62 2
63 6
64 32
65 2
66 10
67 1
68 6
69 2
70 11
71 1
72 71
73 1
74 2
75 7
76 6
77 2
78 10
79 1
80 46
81 6
82 2
83 1
84 39
85 2
86 2
87 2
88 16
89 1
90 40
91 2
92 6
93 2
94 2
95 2
96 108
97 1
98 6
99 6
100 24
101 1
102 10
103 1
104 16
105 10
106 2
107 1
108 68
109 1
110 10
111 2
112 44
113 1
114 10
115 2
116 6
117 6
118 2
119 2
120 126
121 1
122 2
123 2
124 6
125 3
126 37
127 1
128 63
129 2
130 10
131 1
132 36
133 2
134 2
135 17
136 16
137 1
138 10
139 1
140 39
141 2
142 2
143 2
144 196
145 2
146 2
147 5
148 6
149 1
150 40
151 1
152 16
153 6
154 10
155 2
156 36
157 1
158 2
159 2
160 108
161 2
162 40
163 1
164 6
165 10
166 2
167 1
168 119
169 1
170 10
171 6
172 6
173 1
174 10
175 6
176 40
177 2
178 2
179 1
180 164
181 1
182 10
183 2
184 16
185 2
186 10
187 2
188 6
189 15
190 10
191 1
192 248
193 1
194 2
195 10
196 21
197 1
198 35
199 1
200 71
201 2
202 2
203 2
204 36
205 2
206 2
207 6
208 40
209 2
210 64
211 1
212 6
213 2
214 2
215 2
216 230
217 2
218 2
219 2
220 36
221 2
222 10
223 1
224 104
225 23
226 2
227 1
228 36
229 1
230 10
231 9
232 16
233 1
234 35
235 2
236 6
237 2
238 10
239 1
240 352
241 1
242 5
243 12
244 6
245 5
246 10
247 2
248 16
249 2
250 17
251 1
252 154
253 2
254 2
255 10
256 126
257 1
258 10
259 2
260 36
261 6
262 2
263 1
264 111
265 2
266 10
267 2
268 6
269 1
270 117
271 1
272 40
273 9
274 2
275 6
276 36
277 1
278 2
279 6
280 119
281 1
282 10
283 1
284 6
285 10
286 9
287 2
288 516
289 2
290 10
291 2
292 6
293 1
294 34
295 2
296 16
297 15
298 2
299 2
300 164
301 2
302 2
303 2
304 40
305 2
306 35
307 1
308 35
309 2
310 10
311 1
312 111
313 1
314 2
315 35
316 6
317 1
318 10
319 2
320 248
321 2
322 10
323 2
324 182
325 6
326 2
327 2
328 16
329 2
330 61
331 1
332 6
333 6
334 2
335 2
336 336
337 1
338 5
339 2
340 36
341 2
342 35
343 2
344 16
345 10
346 2
347 1
348 36
349 1
350 37
351 15
352 96
353 1
354 10
355 2
356 6
357 9
358 2
359 1
360 567
361 2
362 2
363 5
364 35
365 2
366 10
367 1
368 40
369 6
370 10
371 2
372 36
373 1
374 9
375 17
376 16
377 2
378 109
379 1
380 36
381 2
382 2
383 1
384 559
385 9
386 2
387 6
388 6
389 1
390 61
391 2
392 64
393 2
394 2
395 2
396 146
397 1
398 2
399 9
400 196
401 1
402 10
403 2
404 6
405 40
406 10
407 2
408 111
409 1
410 10
411 2
412 6
413 2
414 35
415 2
416 96
417 2
418 9
419 1
420 273
421 1
422 2
423 6
424 16
425 6
426 10
427 2
428 6
429 9
430 10
431 1
432 710
433 1
434 10
435 10
436 6
437 2
438 10
439 1
440 111
441 18
442 9
443 1
444 36
445 2
446 2
447 2
448 240
449 1
450 159
451 2
452 6
453 2
454 2
455 9
456 111
457 1
458 2
459 15
460 36
461 1
462 58
463 1
464 40
465 10
466 2
467 1
468 146
469 2
470 10
471 2
472 16
473 2
474 10
475 6
476 35
477 6
478 2
479 1
480 936
481 2
482 2
483 9
484 18
485 2
486 92
487 1
488 16
489 2
490 34
491 1
492 36
493 2
494 9
495 35
496 40
497 2
498 10
499 1
500 68
501 2
502 2
503 1
504 539
505 2
506 9
507 5
508 6
509 1
510 61
511 2
512 252
513 15
514 2
515 2
516 36
517 2
518 10
519 2
520 111
521 1
522 35
523 1
524 6
525 35
526 2
527 2
528 316
529 2
530 10
531 6
532 35
533 2
534 10
535 2
536 16
537 2
538 2
539 5
540 550
541 1
542 2
543 2
544 96
545 2
546 58
547 1
548 6
549 6
550 35
551 2
552 111
553 2
554 2
555 10
556 6
557 1
558 35
559 2
560 336
561 9
562 2
563 1
564 36
565 2
566 2
567 36
568 16
569 1
570 61
571 1
572 32
573 2
574 10
575 6
576 1312
577 1
578 8
579 2
580 36
581 2
582 10
583 2
584 16
585 35
586 2
587 1
588 145
589 2
590 10
591 2
592 40
593 1
594 105
595 9
596 6
597 2
598 9
599 1
600 567
601 1
602 10
603 6
604 6
605 5
606 10
607 1
608 96
609 9
610 10
611 2
612 146
613 1
614 2
615 10
616 108
617 1
618 10
619 1
620 36
621 15
622 2
623 2
624 316
625 6
626 2
627 9
628 6
629 2
630 262
631 1
632 16
633 2
634 2
635 2
636 36
637 5
638 9
639 6
640 559
641 1
642 10
643 1
644 35
645 10
646 9
647 1
648 688
649 2
650 35
651 9
652 6
653 1
654 10
655 2
656 40
657 6
658 10
659 1
660 260
661 1
662 2
663 9
664 16
665 9
666 35
667 2
668 6
669 2
670 10
671 2
672 900
673 1
674 2
675 66
676 18
677 1
678 10
679 2
680 111
681 2
682 9
683 1
684 146
685 2
686 14
687 2
688 40
689 2
690 61
691 1
692 6
693 32
694 2
695 2
696 111
697 2
698 2
699 2
700 154
701 1
702 105
703 2
704 224
705 10
706 2
707 2
708 36
709 1
710 10
711 6
712 16
713 2
714 58
715 9
716 6
717 2
718 2
719 1
720 1782
721 2
722 8
723 2
724 6
725 6
726 31
727 1
728 108
729 24
730 10
731 2
732 36
733 1
734 2
735 31
736 96
737 2
738 35
739 1
740 36
741 9
742 10
743 1
744 111
745 2
746 2
747 6
748 32
749 2
750 117
751 1
752 40
753 2
754 9
755 2
756 520
757 1
758 2
759 9
760 111
761 1
762 10
763 2
764 6
765 35
766 2
767 2
768 1244
769 1
770 58
771 2
772 6
773 1
774 35
775 6
776 16
777 9
778 2
779 2
780 260
781 2
782 9
783 15
784 180
785 2
786 10
787 1
788 6
789 2
790 10
791 2
792 513
793 2
794 2
795 10
796 6
797 1
798 58
799 2
800 516
801 6
802 2
803 2
804 36
805 9
806 9
807 2
808 16
809 1
810 320
811 1
812 35
813 2
814 9
815 2
816 316
817 2
818 2
819 32
820 36
821 1
822 10
823 1
824 16
825 35
826 10
827 1
828 146
829 1
830 10
831 2
832 224
833 5
834 10
835 2
836 32
837 15
838 2
839 1
840 970
841 2
842 2
843 2
844 6
845 5
846 35
847 5
848 40
849 2
850 35
851 2
852 36
853 1
854 10
855 35
856 16
857 1
858 55
859 1
860 36
861 9
862 2
863 1
864 2060
865 2
866 2
867 8
868 35
869 2
870 61
871 2
872 16
873 6
874 9
875 15
876 36
877 1
878 2
879 2
880 316
881 1
882 138
883 1
884 32
885 10
886 2
887 1
888 111
889 2
890 10
891 36
892 6
893 2
894 10
895 2
896 543
897 9
898 2
899 2
900 754
901 2
902 9
903 9
904 16
905 2
906 10
907 1
908 6
909 6
910 58
911 1
912 316
913 2
914 2
915 10
916 6
917 2
918 105
919 1
920 111
921 2
922 2
923 2
924 249
925 6
926 2
927 6
928 96
929 1
930 61
931 5
932 6
933 2
934 2
935 9
936 513
937 1
938 10
939 2
940 36
941 1
942 10
943 2
944 40
945 105
946 9
947 1
948 36
949 2
950 35
951 2
952 108
953 1
954 35
955 2
956 6
957 9
958 2
959 2
960 2400
961 2
962 9
963 6
964 6
965 2
966 58
967 1
968 56
969 9
970 10
971 1
972 468
973 2
974 2
975 35
976 40
977 1
978 10
979 2
980 145
981 6
982 2
983 1
984 111
985 2
986 9
987 9
988 32
989 2
990 254
991 1
992 96
993 2
994 10
995 2
996 36
997 1
998 2
999 15
1000 230
1001 9
1002 10
1003 2
1004 6
1005 10
1006 2
1007 2
1008 1708
1009 1
1010 10
1011 2
1012 32
1013 1
1014 31
1015 9
1016 16
1017 6
1018 2
1019 1
1020 260
1021 1
1022 10
1023 9
1024 504
All prime input lengths have only a single possible plan, there are some larger highly factorisable input lengths that have thousands of possible plans, and most input lengths have a number of plans lying somewhere between these two extremes.
The primary challenge in selecting a good plan from this range of possibilities is to choose a heuristic that requires us to measure the performance of only a few plans: out of the hundreds or thousands of possibilities for a given input vector length, most plans will be duds. We need to pick out a handful of likely candidate plans for benchmarking. In order to develop some heuristic plan selection rules, we’ll do some benchmarking experiments, as we did for the $N=256$ case in the last section. We’ll look at some input vector lengths that have lots of possible plans, some that have only a few possible plans and some that lie in the middle range:
Size $\;\;\;$ Factors $\;\;\;$ No. of plans 960 26 × 3 × 5 2400 800 25 × 52 516 512 29 252 216 23 × 33 230 378 2 × 33 × 7 109 208 24 × 13 40 232 23 × 29 16 238 2 × 7 × 17 10 92 22 × 23 6 338 2 × 132 5 1003 17 × 59 2 115 5 × 23 2
For each of these problem sizes, the table below shows the execution times for each of the fastest ten plans or for all possible plans, if there are less than ten (the base transform sizes are highlighted in bold):
$N=960$ (235.25 µs) $\;\;\;\;\;\;$ $N=378$ (71.52 µs) $\;\;\;\;\;\;$ $N=92$ (285.60 µs) 3 × 2 × 5:32 115.13 µs 3 × 3 × 3:14 52.16 µs 23:4 43.65 µs 3 × 5:64 116.19 µs 9 × 3:14 59.54 µs 23 × 2:2 65.04 µs 3 × 5 × 2:32 117.68 µs 3 × 9:14 60.95 µs 2 × 23:2 76.00 µs 2 × 5 × 3:32 117.89 µs 3 × 2 × 7:9 68.10 µs 46:2 125.16 µs 5 × 3:64 118.49 µs 2 × 3 × 7:9 68.44 µs 4:23 295.37 µs 2 × 3 × 5:32 118.99 µs 2 × 7 × 3:9 68.74 µs 2 × 2:23 299.11 µs 5 × 2 × 3:32 119.04 µs 7 × 6:9 69.49 µs 5 × 3 × 2:32 119.29 µs 6 × 7:9 69.73 µs $N=338$ (67.50 µs) 6 × 5:32 121.05 µs 7 × 2 × 3:9 69.83 µs 13 × 2:13 66.91 µs 5 × 6:32 124.21 µs 7 × 3 × 2:9 70.76 µs 2 × 13:13 67.30 µs 26:13 106.41 µs $N=800$ (192.05 µs) $N=208$ (32.85 µs) 13 × 13:2 212.18 µs 5 × 5:32 94.64 µs 4 × 4:13 28.97 µs 169:2 1701.35 µs 2 × 4 × 4:25 101.56 µs 2 × 2 × 4:13 30.31 µs 4 × 2 × 4:25 101.67 µs 2 × 4 × 2:13 31.70 µs $N=1003$ (2413.41 µs) 2 × 2 × 2 × 4:25 104.10 µs 4 × 2 × 2:13 32.04 µs 59:17 1843.99 µs 4 × 4 × 2:25 104.20 µs 2 × 8:13 33.21 µs 17:59 2538.96 µs 2 × 2 × 4 × 2:25 104.56 µs 2 × 2 × 2 × 2:13 33.58 µs 2 × 4 × 2 × 2:25 106.56 µs 8 × 2:13 34.26 µs $N=115$ (362.84 µs) 4 × 2 × 2 × 2:25 106.61 µs 13:16 35.31 µs 23:5 46.50 µs 2 × 2 × 2 × 2 × 2:25 107.50 µs 16:13 45.04 µs 5:23 373.16 µs 2 × 5 × 4:20 108.47 µs 2 × 13:8 47.74 µs $N=512$ (278.94 µs) $N=232$ (584.14 µs) 4 × 4:32 55.10 µs 29:8 87.52 µs 2 × 4:64 55.63 µs 29 × 2:4 113.47 µs 4 × 2:64 55.66 µs 2 × 29:4 136.21 µs 2 × 2 × 4:32 56.01 µs 29 × 4:2 142.41 µs 2 × 2 × 2:64 56.65 µs 29 × 2 × 2:2 159.00 µs 4 × 2 × 2:32 57.00 µs 2 × 29 × 2:2 185.15 µs 2 × 4 × 2:32 57.34 µs 2 × 2 × 29:2 229.41 µs 2 × 2 × 2 × 2:32 58.71 µs 4 × 29:2 231.43 µs 8:64 60.27 µs 58:4 254.22 µs 2 × 8:32 62.38 µs 58 × 2:2 294.84 µs $N=216$ (69.19 µs) $N=238$ (316.93 µs) 3 × 6:12 31.10 µs 17:14 51.85 µs 2 × 3 × 3:12 31.18 µs 17 × 2:7 69.44 µs 3 × 2 × 3:12 31.51 µs 2 × 17:7 69.68 µs 6 × 3:12 31.63 µs 34:7 109.80 µs 3 × 3 × 2:12 32.60 µs 17 × 7:2 127.19 µs 2 × 9:12 35.79 µs 7 × 17:2 160.65 µs 3 × 2 × 4:9 36.03 µs 2 × 7:17 327.17 µs 6 × 4:9 36.67 µs 7 × 2:17 329.79 µs 2 × 3 × 4:9 37.00 µs 14:17 339.61 µs 9 × 2:12 37.04 µs 119:2 823.30 µs
It’s important to note that we don’t need to use these results to identify the best plan, just a reasonable set of plans to test empirically. When a call is made to the plan
function, we’re going to use Criterion to benchmark a number of likely looking plans and we’ll take the fastest one. It doesn’t matter if this benchmarking takes a while (a few seconds, say) since we’ll only need to do it once for each input length (we’ll eventually save the best plan away in a “wisdom” file so that we can get at it immediately if a plan for the same input length is requested later on). If some transform takes about 200 µs on average, then we can run 5,000 tests in one second. Since Criterion runs 100 benchmarks to get reasonable timing statistics, we could test about 50 plans in a second. Let’s aim to come up with a heuristic that yields 20-50 plans for a given input length, test them all, then pick the best one.
So, based on these results and the earlier results for the powers-of-two case, what appear to be good heuristics for plan selection?
First, make use of the larger specialised base transforms. In both the $N=256$ and $N=1024$ cases, the fastest plans all made use of the size-64 or size-32 base transforms, and likewise in the general experiments shown above, the faster plans tend to make use of the larger base transforms.
Specialised base transforms are generally faster than using Rader’s algorithm for a larger prime factor as the base transform. For example, for $N = 92 = 2^2 \times 23$, plans using the size-4 or size-2 base transforms are faster than those using Rader’s algorithm for the factor of 23.
Using multiple Danielson-Lanczos steps of smaller sizes is generally faster than trying to fold everything into one big composite step. For example, the results for the $N=256$ case show that the slowest plans tend to be those using the largest Danielson-Lanczos steps.
In cases where there’s no but to use Rader’s algorithm for the base transform, it can make a difference to use a base transform size that doesn’t need any padding for the Rader algorithm convolution. For example, for $N = 1003 = 17 \times 59$, using a base transform of size 17 is significantly faster than using a base transform of size 59, presumably because, for the size-17 transform, Rader’s algorithm requires us to perform a convolution of size 16, and no zero padding is needed, while for the size-59 transform, the convolution requires padding of an intermediate vector to length 128 (the smallest power of two that works).
Based on this, here’s a set of heuristics for choosing plans to test:
Determine the usable base transforms for the given $N$; sort the specialised base transforms in descending order of size, followed by any other prime base transforms, in descending order of size with transform sizes of the form $2^m+1$ before any others (i.e. those that don’t require any padding for the Rader’s algorithm convolution).
For each base transform, generate all the plans that make use of Danielson-Lanczos steps for the remaining “left over” factors that are “small”, in the sense that they involve only one, two or three factors at a time (i.e. don’t bother generating plans that use Danielson-Lanczos steps of larger sizes).
Limit the number of generated plans to around 50 so that the benchmarking step doesn’t take too long.
Benchmark all the generated plans and select the fastest!
This approach may not find the optimal plan every time, but it should have a relatively good chance and won’t require the benchmarking of too many plans.
There is one aspect of all this that would require revisiting if we had specialised “twiddlets” for the Danielson-Lanczos steps. In that case, we would want to pick plans where we could use a large specialised base transform and make use of the largest possible specialised Danielson-Lanczos “twiddlets”. For the moment, since we don’t have such specialised machinery for the Danielson-Lanczos steps, the approach above should be a good choice.
Implementation The code described here is the pre-release-3
version of the GitHub repository.
Generation of the candidate plans for a given input size is basically a question of determining which base transforms are usable, then generating all of the permutations and combinations of the “left over” factors for each base transform. The plans are sorted according to the heuristic ordering described above and we take the first 50 or so for benchmarking.
For the base transforms, we define a helper type called BaseType
to represent base transforms and to allow us to define an Ord
instance for the heuristic ordering of the base transforms. We also define a newtype
wrapper, SPlan
, to wrap the whole of a plan definition, again so that we can write a custom Ord
instance based on the heuristic ordering of plans:
-- | Base transform type with heuristic ordering.
data BaseType = Special Int | Rader Int deriving ( Eq , Show )
-- | Newtype wrapper for custom sorting.
newtype SPlan = SPlan ( BaseType , Vector Int ) deriving ( Eq , Show )
-- | Base transform size.
bSize :: BaseType -> Int
bSize ( Special b ) = b
bSize ( Rader b ) = b
-- | Heuristic ordering for base transform types: special bases come
-- first, then prime bases using Rader's algorithm, ordered according
-- to size compensating for padding needed in the Rader's algorithm
-- convolution.
instance Ord BaseType where
compare ( Special _ ) ( Rader _ ) = LT
compare ( Rader _ ) ( Special _ ) = GT
compare ( Special s1 ) ( Special s2 ) = compare s1 s2
compare ( Rader r1 ) ( Rader r2 ) = case ( isPow2 $ r1 - 1 , isPow2 $ r2 - 1 ) of
( True , True ) -> compare r1 r2
( True , False ) -> compare r1 ( 2 * r2 )
( False , True ) -> compare ( 2 * r1 ) r2
( False , False ) -> compare r1 r2
-- | Heuristic ordering for full plans, based first on base type, then
-- on the maximum size of Danielson-Lanczos step.
instance Ord SPlan where
compare ( SPlan ( b1 , fs1 )) ( SPlan ( b2 , fs2 )) = case compare b1 b2 of
LT -> LT
EQ -> compare ( maximum fs2 ) ( maximum fs1 )
GT -> GT
Here’s the code for the generation of candidate plans:
-- | Generate test plans for a given input size, sorted in heuristic
-- order.
testPlans :: Int -> Int -> [( Int , Vector Int )]
testPlans n nplans = L . take nplans $
L . map clean $
L . sortBy ( comparing Down ) $ P . concatMap doone bs
where vfs = allFactors n
bs = usableBases n vfs
doone b = basePlans n vfs b
clean ( SPlan ( b , fs )) = ( bSize b , fs )
-- | List plans from a single base.
basePlans :: Int -> Vector Int -> BaseType -> [ SPlan ]
basePlans n vfs bt = if null lfs
then [ SPlan ( bt , empty )]
else P . map ( \ v -> SPlan ( bt , v )) $ leftOvers lfs
where lfs = fromList $ ( toList vfs ) \\ ( toList $ allFactors b )
b = bSize bt
-- | Produce all distinct permutations and compositions constructable
-- from a given list of factors.
leftOvers :: Vector Int -> [ Vector Int ]
leftOvers fs =
if null fs
then []
else S . toList $ L . foldl' go S . empty ( multisetPerms fs )
where n = length fs
go fset perm = foldl' doone fset ( enumFromN 0 ( 2 ^ ( n - 1 )))
where doone s i = S . insert ( makeComp perm i ) s
-- | Usable base transform sizes.
usableBases :: Int -> Vector Int -> [ BaseType ]
usableBases n fs = P . map Special bs P .++ P . map Rader ps
where bs = toList $ filter (( == 0 ) . ( n ` mod `)) specialBaseSizes
ps = toList $ filter isPrime $ filter ( > maxPrimeSpecialBaseSize ) fs
The main testPlans
function calls usableBases
to determine what base transforms can be used for a given input size, distinguishing between specialised straight-line transforms (the Special
constructor of the BaseType
type) and larger prime transforms that require use of Rader’s algorithm (the Rader
constructor for BaseType
). For each possible base transform, the basePlans
function determines the “left over” factors of the input size and uses the leftOvers
function to generate a list of possible Danielson-Lanczos steps, which are then bundled up with the base transform information into values of type SPlan
. The leftOvers
function calculates all possible permutations of the multiset of left-over factors (using the multiPerms
function, which is essentially identical to the multiset permutation code shown earlier), and for each permutation calculates all possible compositions of the factors. Plans are collected into an intermediate Set
to remove duplicates.
The full set of candidate plans is then sorted in testPlans
in descending order of desirability according to the planning heuristics, and the first nplans
plans are returned for further processing.
There are several places where this code could be made more efficient (there’s quite a bit of intermediate list construction, for instance), but there’s really not too much point in expending effort on it, since the planning step should only be done once before executing an FFT calculation multiple times using the same plan. In any case, the plan generation is relatively quick even for quite large input sizes.
The top-level code that drives the empirical planning process is shown here:
-- | Globally shared timing environment. (Not thread-safe...)
timingEnv :: IORef ( Maybe Environment )
timingEnv = unsafePerformIO ( newIORef Nothing )
{-# NOINLINE timingEnv #-}
-- | Plan calculation for a given problem size.
empiricalPlan :: Int -> IO Plan
empiricalPlan n = do
wis <- readWisdom n
case wis of
Just p -> return $ planFromFactors n p
Nothing -> do
let ps = testPlans n nTestPlans
withConfig ( defaultConfig { cfgVerbosity = ljust Quiet
, cfgSamples = ljust 1 }) $ do
menv <- liftIO $ readIORef timingEnv
env <- case menv of
Just e -> return e
Nothing -> do
meas <- measureEnvironment
liftIO $ writeIORef timingEnv $ Just meas
return meas
let v = generate n ( \ i -> sin ( 2 * pi * fromIntegral i / 511 ) :+ 0 )
tps <- CM . forM ps $ \ p -> do
let pp = planFromFactors n p
pptest <- case plBase pp of
bpl @ ( RaderBase _ _ _ _ csz _ ) -> do
cplan <- liftIO $ empiricalPlan csz
return $ pp { plBase = bpl { raderConvPlan = cplan } }
_ -> return pp
ts <- runBenchmark env $ nf ( execute pptest Forward ) v
return ( sum ts / fromIntegral ( length ts ), p )
let ( rest , resp ) = L . minimumBy ( compare ` on ` fst ) tps
liftIO $ writeWisdom n resp
let pret = planFromFactors n resp
case plBase pret of
bpl @ ( RaderBase _ _ _ _ csz _ ) -> do
cplan <- liftIO $ empiricalPlan csz
return $ pret { plBase = bpl { raderConvPlan = cplan } }
_ -> return pret
We’ll describe the “wisdom” stuff in a minute, but first let’s look at the Nothing
branch of the case
expression at the top of the empiricalPlan
function. The testPlans
function we looked at above is used to generate a list of candidate plans and we then use Criterion to run benchmarks for each of these plans, choosing the plan with the best execution time. There are a few wrinkles to make things a little more efficient. First, we have a global IORef
that we use to store the Criterion timing environment information–this avoids repeated calls to measureEnvironment
to determine the system clock resolution. Using an IORef
in this way is not thread-safe, which is something we would have to fix to make this a production-ready library. We’ll not worry about it for now. Second, we make Criterion only collect a single sample for each plan, just to make the benchmarking go quicker. If we have a number of plans that are within a few percent of each other in terms of their execution times, it probably doesn’t matter too much exactly which one we choose, so there’s not much to be gained from running lots of benchmarking tests to get accurate timing information. In most cases, the differences between plans are large enough that we can easily identify the best plan from a single benchmark run. Finally, we have to do some slight messing around to fix up the plans for the convolution step in prime base transforms using Rader’s algorithm.
From a user’s point of view, all of this complexity is hidden behind the empiricalPlan
function: you call this with your input size and you get a Plan
back, one that’s hopefully close to the optimal plan that we can generate.
Once the optimal plan for a given input size has been determined on a given machine, it won’t change, since it depends only on fixed details of the machine architecture (processor, cache sizes and so on). Instead of doing the work of running the empirical benchmarking tests every time that empiricalPlan
is called, we can thus save the planning results away in “wisdom” files for reuse later on. Here’s the code to do this:
-- | Read from wisdom for a given problem size.
readWisdom :: Int -> IO ( Maybe ( Int , Vector Int ))
readWisdom n = do
home <- getEnv "HOME"
let wisf = home </> ".fft-plan" </> show n
ex <- doesFileExist wisf
case ex of
False -> return Nothing
True -> do
wist <- readFile wisf
let ( wisb , wisfs ) = read wist :: ( Int , [ Int ])
return $ Just ( wisb , fromList wisfs )
-- | Write wisdom for a given problem size.
writeWisdom :: Int -> ( Int , Vector Int ) -> IO ()
writeWisdom n ( b , fs ) = do
home <- getEnv "HOME"
let wisd = home </> ".fft-plan"
wisf = wisd </> show n
createDirectoryIfMissing True wisd
writeFile wisf $ show ( b , toList fs ) P .++ " \n "
We save one file per input size in a directory called ~/.fft-plan
, writing and reading the (Int, Vector Int)
planning information using Haskell’s basic show
and read
capabilities. Whenever empiricalPlan
is called, we check to see if we have a wisdom file for the requested input size and only generate plans and run benchmarks if there is no wisdom. Conversely, when we benchmark and find an optimal plan, we save that information to a wisdom file for later.
Benchmarking We can measure the performance of the pre-release-3
code in the same way as we’ve done for earlier versions. Here’s a view of the performance of this version of the code that should be pretty familiar by now:
Size FFT FFTW
8 0.37936716504828105 0.9699839812058683
9 0.43314888621526576 0.26649896470731316
10 0.45912192834052834 0.28010058245319397
11 0.5150048515707484 0.3125321483254346
12 0.5502005713363313 0.31548856159024824
13 0.6179205213455793 0.3642253378002243
14 0.5962767708459005 0.36156626113390045
15 0.6597368058316049 0.3849977041675521
16 0.6423603007808711 0.4167012245386672
17 2.384298124658405 0.5497874656231077
18 2.821707351241415 0.4697389105033642
19 8.082091274903968 0.6185002743895786
20 0.7808526980101005 0.481911727410412
21 3.4882053742668977 0.5541363197116053
22 3.046376268182158 0.5819372095754897
23 8.312277198145548 0.7636326197055456
24 3.0504821596123826 0.5902575343574745
25 1.110277220715723 0.6402569984724448
26 3.4436362949507733 0.6638359197131518
27 3.7990180388266883 0.6863594065404387
28 3.3835278954792978 0.6882763760213823
29 8.730124115434464 1.9403475981492222
30 3.5963640100641108 0.7214368429080125
31 8.783253830406535 1.9856471281785193
32 1.2639597244839358 0.7113856753068782
33 4.179204135363742 0.8195921473826989
34 7.735769319978194 1.0360367787189972
35 5.816098062740775 0.8380603545256323
36 4.190343097515095 1.7448443632859418
37 23.21631117084428 2.238370822026175
38 19.00253298677208 1.1569369212220646
39 4.810883398329331 0.9408147571814018
40 4.100664094340965 1.9331950407761758
41 23.511888430668762 2.4767894011277365
42 4.661693579918762 0.9777929297911422
43 23.592860778288145 2.5769252043503936
44 5.4904881980959415 1.0432041501387577
45 5.055984256415163 1.0370926167218624
46 19.558340434771893 1.4652092687588936
47 23.82579123160662 2.650834963871879
48 5.094407323883613 1.9927996855515662
49 8.64586662348671 1.1552619773565291
50 5.222186729379369 1.1255036452652232
51 10.801518718104045 1.525105036669333
52 6.472379475449902 1.1918278761896348
53 24.218084333888715 3.094293521000788
54 7.930665118971157 2.216913149907034
55 7.112244522905499 1.2717136203434138
56 6.285873324678256 1.2336447912602555
57 27.90550871792003 1.706909710714129
58 20.506658423521994 2.9297847014207083
59 24.552478078263917 3.4805316191453204
60 5.825134966510345 2.362348483158987
61 24.904870087924234 3.594972537114071
62 20.72720037531156 3.0632991057175842
63 9.848717400625343 1.452979328954055
64 3.8112489857484007 1.3365203097795433
65 8.153180527051765 1.4822159109196327
66 8.789171407733921 1.5094766395223593
67 50.258256838871915 4.210092471196104
68 14.193996184627135 1.9343749945465216
69 28.783656318200503 2.148602916327965
70 8.17307990780423 1.5322851798319657
71 50.53959076221175 4.72507660205548
72 9.107113599237824 2.681829379155082
73 50.75178329761214 5.113698885991028
74 48.499734655639834 3.714181826664853
75 7.3990714729076394 1.6359342960570544
76 31.739310776223313 2.1799664118974222
77 10.915752924405611 1.7806304947007199
78 10.272586459349618 1.7634406585734688
79 50.99258606250472 5.111314700200013
80 7.8599595836656215 2.8701800566453177
81 13.085922617942852 1.8234492777699265
82 48.802526251098826 4.131414340092588
83 51.01165954883285 5.535699771000794
84 10.31029806956986 3.084756777836725
85 17.924268132421247 2.422159388896915
86 49.553379132197435 4.391290591313292
87 30.084868219958878 4.000284121586729
88 13.114046818814298 1.9346756187307028
89 52.27050964648911 4.213080541259784
90 10.96281755951895 3.0704516630906316
91 12.63560287324421 2.061082363800006
92 38.414423449056116 2.7769330921535804
93 30.623461605236606 4.248239443852355
94 49.87448127453142 4.753686831547669
95 34.32709910930733 2.762014816968868
96 8.334109636453482 3.060914919926568
97 52.05116455371567 6.191350863530092
98 12.831212102602683 2.1514353209743717
99 14.605268233577332 2.296130908075059
100 9.931976579259102 3.2158869963425847
101 52.318193362309415 7.080652163578922
102 22.00559446028063 2.861231308166374
103 52.30865661914535 5.46402700954839
104 14.721136675700885 2.2501544811057617
105 13.473936805756988 2.3149594975635934
106 50.66564948742201 5.478479312016419
107 52.59714309985825 5.549439756279318
108 14.850577875808039 3.568746493412899
109 52.51131241138168 7.1903247099656395
110 16.495643188113625 2.421153899138932
111 72.72731473303254 5.135156558110169
112 13.771210156148102 3.904916689946103
113 52.77595703418442 5.27372604501228
114 37.25611748199113 3.2855705772618222
115 47.162756623601084 3.4921851289287686
116 40.6090552398644 4.767991946293761
117 16.348790526985532 2.683966855947592
118 51.4002482860516 6.112672732426576
119 26.346158005797157 3.4144019082956962
120 13.123784335518653 3.730871127201962
121 20.717693995206776 2.8835283427836207
122 52.06493941637186 6.553747103764469
123 73.52784672473891 5.645372317387514
124 41.13965194219393 5.437948153569153
125 12.877008122739861 2.9111569646327813
126 16.270793591822294 3.9287585478562597
127 53.7940043669481 7.178403781010561
128 11.382446305735133 4.72507660205548
129 75.01010905563557 6.134130404545717
130 18.375916438490776 2.8932392779738376
131 107.20215027148926 9.562589572026189
132 19.1023107957558 4.1171092253464945
133 40.3459996558152 3.90117634021262
134 98.97432510669431 7.466890261723452
135 17.47070368811214 4.150487826420713
136 30.24367825398973 3.7888117008763924
137 107.2402972441455 8.587457583500797
138 52.03980612449155 4.194549308140248
139 107.28559677417479 6.998435622077153
140 16.200913905132158 4.279233859135558
141 75.49732443434077 6.794549868657046
142 99.3677157622119 8.039094851567203
143 24.624798380591393 3.4000172691216948
144 17.565533838447745 4.15287201221173
145 50.87698371593765 5.769349978520326
146 100.14972870166501 8.422948763920719
147 28.580852030040493 3.447077160838103
148 98.39421799902382 6.210424349858217
149 108.2917231779834 8.647062228276187
150 16.086472987163408 4.410364077641417
151 108.55875198657715 8.608915255619937
152 42.17869764719252 5.321123049809388
153 33.63563181704641 4.400101995040424
154 24.522535652803946 3.5730781279023436
155 51.67482701631688 6.310560153080873
156 21.716801905189325 4.474737093998839
157 111.98005859668456 6.991167293093595
158 101.11770813281737 8.88548080737775
159 76.55183578508483 7.643320010258609
160 14.655501443336455 4.51765243823712
161 56.253004157459806 4.928379681506762
162 26.644637775889386 4.980184481694153
163 109.00697891528809 10.308839724614074
164 98.9796273101716 7.035352633549625
165 24.32960000263869 3.657761863334556
166 101.28460113818848 9.688951418950017
167 108.97360031421387 8.688069727176282
168 22.04300398446931 4.734613345219543
169 32.00333361442274 4.070580325387267
170 38.17758267888649 4.772047269979178
171 45.53342212687483 4.954850196540171
172 100.30505121106938 7.483579562260562
173 109.29308121020996 8.795642198703183
174 61.82907113662138 6.606199191166811
175 19.957218502030713 4.039850147766324
176 25.926261082923197 5.082704470707825
177 79.07114212329584 8.644678042485172
178 101.363279269292 9.939290927006656
179 109.52911560352051 8.913207748434052
180 20.32117846585975 4.989721224858216
181 109.80091278369628 10.66885177905743
182 27.792869184771146 4.36565126380079
183 79.89607040698725 9.22403518970197
184 59.32556342729277 6.532289431645328
185 112.49742691333496 7.4883479338425945
186 63.73284349074735 7.149793551518375
187 42.379605036515464 5.614287520830449
188 101.43912648543332 8.356191561772281
189 32.40358161738169 5.609609530522278
190 48.41399566661675 5.4749471957866955
191 112.13026230151857 10.377981112553526
192 17.392776224034773 5.166150973393372
193 111.18374054248535 10.456659243657041
194 102.62689773853027 10.525800631596494
195 27.3546364395116 4.388386437332382
196 28.42354995387418 5.580999301030091
197 111.73687164600098 8.826963288889385
198 30.036360920567187 5.943395541264467
199 112.65716736133302 9.0642742621593
200 22.33811109275608 5.206682131840638
201 146.86546509082524 10.861970828129694
202 103.29446976001465 12.442686007573041
203 74.04619676495027 7.581331179692203
204 44.50418544384784 6.73256103809064
205 125.95983523588919 8.535005496098453
206 104.34827987964354 12.306787417485154
207 63.98628244033229 6.4414658591824825
208 29.165735952756048 5.681135104252749
209 51.8301811951857 6.376077213691583
210 28.88982083413984 5.623914645268372
211 111.75117676074709 12.144662783696091
212 103.33738510425292 9.607889102055486
213 147.7690715056202 11.279203341557427
214 103.58295624072754 12.84561340625468
215 126.08643550139216 9.154893801762517
216 30.7244115206806 5.89809601123517
217 74.84237457292642 8.382417605473453
218 104.91571609790526 12.154199526860154
219 147.9884165983936 12.359239504887496
220 31.872162114270782 5.983926699711733
221 50.034317089961085 6.575708550362745
222 120.90168182666504 8.8473338347215
223 111.47699539478029 13.072111056401162
224 22.847688881667352 5.831338809086732
225 24.3993292027469 5.9886950712937645
226 104.76074402148926 12.104131625248826
227 112.00628464038574 12.38308136279765
228 53.87811271043921 7.714845583989079
229 112.27569763477052 10.740794822455083
230 67.68927332843361 8.005716250492984
231 36.619539875790025 5.566470695715024
232 83.94095750955434 8.346654818608219
233 112.99333755786623 10.76313628758296
234 33.85355928583601 6.539441989018374
235 127.8705217288091 10.277845309330871
236 105.65481369312012 11.407949374272269
237 149.52621643359868 12.45460693652812
238 52.29014563254819 7.096665415226448
239 113.96131698901857 10.97735272727997
240 27.376664243015558 6.1484355192918105
241 113.82065002734865 15.017606661869904
242 45.62189244962001 7.085420535160953
243 40.447700080963216 5.827104997962078
244 106.61087219531738 11.977769778324996
245 49.6901764078179 5.9411621181082825
246 146.74148742969243 10.223009036137512
247 61.330436612223515 7.644791884530726
248 85.8136559755374 9.100057528569158
249 150.9042758208057 13.782598422123817
250 28.968125763007688 6.873227999760562
251 113.64660446460451 12.683488772465617
252 34.67214377517374 6.894685671879703
253 72.2189287254714 8.168482948272533
254 106.68955032642089 12.793161318852336
255 54.99257634714693 7.136637637645948
256 24.51123432012704 6.415464327885561
257 60.596086428715715 15.060522006108185
258 151.44310180957524 10.659315035893368
259 130.31444732959474 10.172941134526184
260 37.63232797519111 6.813623354985172
261 93.66867214768797 9.495832369877752
262 216.0283107023975 16.221620486332792
263 225.20265762622566 13.442804499832036
264 40.4278571197472 7.199861453129703
265 129.93297760303224 11.949159548832812
266 63.50420007338891 8.043271353463686
267 151.70774643237797 14.445402072026155
268 196.04406540210454 13.541795657231239
269 225.56743805225105 13.406428066783134
270 36.899760162437346 7.199861453129703
271 226.88827698047373 14.89362900073709
272 56.98386547448754 8.61368362720197
273 41.933682820735825 6.589824786553015
274 216.1808985930225 15.067674563481232
275 38.85536199578865 6.732886780464527
276 75.82227493303395 9.336091921879705
277 226.65701095874522 13.574114173182393
278 216.19281952197758 16.216852114750758
279 95.25681289695429 10.351755068852356
280 36.26617981837348 7.156946108891421
281 224.65191070850108 13.626703706562013
282 153.846361086919 11.91101257617656
283 226.36375610645027 13.868280577639451
284 199.2674845915577 14.285661624028108
285 66.68741336235634 8.288873684711952
286 52.67926462185686 8.17260925586408
287 157.3725718718311 12.28532974536601
288 28.366112750726973 7.392980502201969
289 86.89973207620474 10.223014252483468
290 101.9140261870166 10.385133669926574
291 153.05957977588383 15.279867098881619
292 197.20277969653813 15.766241000248808
293 227.34842483813972 16.362287448002714
294 43.41494139056621 7.941343234135562
295 132.73916427905766 13.892270968510532
296 137.83416931445805 11.19575683887188
297 46.11994079035571 7.36628137512138
298 218.28613464648933 15.923597262455838
299 85.0017612408369 10.521032260014463
300 34.14327007817131 7.60517303760236
301 171.75159637744633 12.325860903813277
302 218.4053439360401 15.642263339115996
303 154.3494242888233 17.590143130375754
304 68.39838037606675 9.734250948979314
305 133.3685893278858 14.664747164799593
306 70.91188970794025 9.991743014408998
307 226.9621867399952 18.748857424809344
308 49.919399334834154 8.360959933354314
309 155.08852188403813 18.286325381352317
310 107.54959598565709 11.17429916675274
311 227.3436564665577 16.943358093719965
312 45.62095580520212 8.332349703862125
313 227.30550949390147 17.45650638372471
314 218.37911789233894 16.0404223662156
315 45.718196525678536 8.358575747563297
316 201.9234675627491 16.32414047534646
317 227.33650390918467 15.897371218754667
318 156.37121383960454 14.21413605029764
319 107.97462646777832 11.677362368657032
320 31.77838568504041 7.7553767424363445
321 154.59976379687993 18.67971603686989
322 89.38274566943846 10.321117447806404
323 102.0046252470752 11.703807020394999
324 47.18885075332772 8.40149109180158
325 48.43985491250392 8.031096836989214
326 219.32802383716316 18.944360659672626
327 155.91821853931157 17.158605502201926
328 167.75331680591313 12.821771548344524
329 180.7948130827686 13.88273422534647
330 51.90809638683613 8.790113375737127
331 228.80754654224128 18.965818331791766
332 200.93403045947758 17.96922867114724
333 148.31266586597172 12.991048739506633
334 218.32428161914558 19.01827041919411
335 245.1368350249073 17.742731021000754
336 46.67307189387133 8.527852938725406
337 229.2796153288624 17.477202440938367
338 67.63744865834472 9.302713320805486
339 156.93626587207524 18.326856539799582
340 66.05560412773717 10.39705459888165
341 121.77190964038576 12.826539919926555
342 94.6895600775996 11.200525210453911
343 72.47604804161266 8.352750713265117
344 185.2007884245655 13.596631930424596
345 93.52169220264157 11.539079592778126
346 220.39375488574717 19.287683413578876
347 229.37975113208503 19.08979599292458
348 113.42249100024904 12.368776248051557
349 229.49419205005378 17.7540524163458
350 44.1091265652206 8.926011965825015
351 51.54388816540053 8.598481804854755
352 45.64896998824656 9.021379397465642
353 229.06742279346201 17.65045786472209
354 159.83781997974125 16.23354141528787
355 247.35412781055183 17.904855654789817
356 201.99737732227055 18.02883331592263
357 83.01366818256864 10.744790043103716
358 222.31779281909675 19.275762484623797
359 231.0391444426319 17.706368700525488
360 43.6728445225116 9.052373812748845
361 210.85939590747563 13.523512321172348
362 221.99592773730964 19.478418276860122
363 69.44852945132133 10.36606018359845
364 57.167161109056785 9.648420260502752
365 248.6892718535206 19.640542910649184
366 160.64605896289558 17.027475283696067
367 230.34057800586433 20.67289535815895
368 96.40178863818846 12.023069308354296
369 179.36191742236824 14.700509951664827
370 157.83510391528813 13.990022585942173
371 184.45692245776863 16.70084183032693
372 131.02932948332568 13.296224520756631
373 230.53846542651863 19.52269777038392
374 92.25927774722761 12.404539034916791
375 44.20106499517629 9.58404724414533
376 206.031419680669 15.513517306401152
377 127.29129974658696 14.125921176030062
378 52.43607767117326 9.805776522709781
379 231.6280383330128 19.309141085698016
380 80.4825801115771 11.78703491504375
381 159.79013626392094 18.848993228032004
382 224.0487117033741 19.13747970874489
383 232.2240847807667 18.035508590740147
384 39.274308142753675 9.30032913501447
385 63.53638658156764 9.643320753597278
386 223.92950241382331 19.72398941333473
387 196.47321884448735 15.430070803715605
388 204.94184677417485 19.80028335864723
389 232.17401687915535 21.044828341557388
390 57.767070506836156 10.058500216557436
391 135.45236770923344 15.1397739356254
392 58.36474253581118 10.4042071562547
393 321.57621567065917 23.109533236576915
394 224.84979812915535 20.05777542407692
395 250.35581772144053 19.14442816536465
396 60.630280718261915 10.358907626225403
397 231.8449992399952 19.350045948074378
398 223.59810058887214 19.976713107182388
399 113.42487518604005 12.332650202971239
400 47.471050186270105 9.50775329883283
401 233.32081024463386 23.16198532397926
402 307.6263446074268 20.114995883061294
403 143.79224960620607 15.203573153569122
404 206.35805313403813 23.798562930180427
405 56.10733869482444 10.50672714526837
406 134.56306640918461 14.605142520024202
407 170.0016040068409 16.183473513676542
408 91.63887854460833 12.78600876147929
409 234.0265292387745 22.601701663090587
410 191.84551422412602 15.902139590336697
411 323.9580172758837 22.73044769580543
412 213.79432861621586 23.924924777104255
413 190.14797394092292 19.058801577641372
414 127.55594436938969 13.978101656987096
415 252.415754244878 22.63269607837379
416 59.92240460364369 10.29453460986798
417 324.4777697783252 22.76382629687965
418 108.7732793428959 14.073469088627721
419 234.4723719816944 21.119028978069526
420 54.20081934402621 10.676004336430477
421 233.86440460498545 21.74541213468153
422 225.8773822050831 22.964097903324962
423 229.3988246184132 17.428018496586695
424 209.62438766772954 18.257715151860126
425 80.84020798022944 12.797297663768063
426 304.80346863086436 20.966150210453872
427 189.95723907764165 20.081617281987075
428 209.42650024707524 23.538686678959724
429 76.08515631694046 11.887170718266406
430 210.85224335010258 16.93926040942849
431 235.11133377368662 21.56322745492666
432 57.03783477102958 10.819055483891413
433 234.47952453906746 24.34215729053199
434 151.37157623584477 16.219236300541773
435 141.5534991484424 15.205957339360138
436 208.92820541675297 22.470571444584728
437 223.40021316821787 17.55438034351052
438 306.431867526128 22.82343094165504
439 234.3483943205616 22.80084472096543
440 68.95602888423906 11.164762423588678
441 83.42851651020536 11.887170718266406
442 101.05095093066895 14.559842989994905
443 235.37597839648933 23.210648656725038
444 178.20558731372563 16.600706027104273
445 255.0812739592335 22.775747225834728
446 229.05788605029792 24.890520022465584
447 328.34015075977044 22.830583499028087
448 49.71550376598648 10.850049899174616
449 235.49041931445808 23.214059439819426
450 53.140604572418354 11.617757723881642
451 205.38053695972175 18.381692812992938
452 211.12642471606938 22.94502441699683
453 329.6681422453661 22.82104675586402
454 227.88725082690925 23.39325134570777
455 71.32395648548744 11.159747372215522
456 113.58149285083047 14.571763918949983
457 235.78605835254402 24.375535891606205
458 229.4679660063526 23.54583923633277
459 103.51277207716906 14.590837405278108
460 113.46779053027834 14.924623416020294
461 237.309553073003 22.378134327334955
462 78.34536444682327 12.039758608891406
463 236.54899780566905 22.32368819363467
464 146.52929489429204 16.011812136723417
465 167.47171901739532 16.398050234867945
466 228.96490280444831 23.50769226367652
467 237.06159775073738 22.77462996624328
468 69.2646822358808 12.044526980473435
469 357.00760071094203 23.936845706059334
470 263.0158442717335 19.416429446293716
471 327.52475921924315 23.30026809985816
472 214.15434067065922 21.299936221196056
473 227.47001831348152 19.857503817631606
474 317.1344775419971 24.03698150928199
475 96.85716812427243 15.153505251957794
476 104.54855148608887 15.062906191899199
477 234.88722030933113 20.808793948246844
478 230.14269058521006 23.939229891850346
479 243.1341189604542 22.929834919375967
480 51.366770343902736 11.593915865971484
481 196.95720856006352 18.76077835376442
482 229.42028229053233 28.817274020268314
483 152.26326172168461 15.738244079626513
484 91.11384677362969 13.093568728520303
485 259.0795535307667 24.535276339604252
486 83.54995103982783 12.61196319873515
487 237.70294372852058 26.62382309253394
488 215.03410522754402 22.430040286137462
489 333.65926925952624 28.10440246875464
490 74.4228981199307 12.445070193364058
491 238.07010834033701 25.308649099790138
492 213.9826792937061 19.030191348149188
493 195.85809891040532 20.374872134281997
494 124.9098398135259 16.405202792240992
495 77.68613707560745 12.764551089360149
496 164.3463153105518 17.296888278080832
497 361.78074066455525 24.49951355273902
498 312.75949661548344 25.810815737797608
499 241.0932559233448 25.466794421197473
500 59.97746794215049 12.232877657963668
501 331.329919741704 28.88403122241675
502 230.58376495654795 24.306394503666755
503 243.07689850146983 26.65004913623511
504 70.63797325150583 12.425996707035932
505 259.54446976001475 29.38232605273901
506 144.5075053435108 17.726041720463645
507 97.01690857227048 13.51318542773905
508 214.51196853931157 24.458982394291755
509 240.51151459033701 24.493829763852627
510 110.61868851001465 15.999891207768338
511 367.69352142627395 26.495077059819092
512 55.09748052195161 11.946775363041796
513 134.26265899951665 16.758062289311304
514 124.0368861418506 28.46918289478003
515 260.7842463713428 30.65786545093237
516 234.42230408008308 20.310499117924575
517 262.5390071135304 22.315599368168712
518 211.27662842090336 19.96956054980934
519 331.9736499052782 28.64322845752417
520 80.01354944247451 13.136484072758583
521 496.99983780200563 28.98655121143042
522 194.64010537325686 18.651105807377704
523 489.9903315764197 27.93952310187185
524 439.5290393095743 30.459978030278073
525 67.35347958228846 13.377286837651159
526 454.81167022998443 28.698064730717526
527 217.72585098560063 22.08194916064918
528 85.21867405909744 13.165094302250772
529 286.00177948291514 22.05572311694801
530 263.39969818408696 22.647001193119884
531 239.27173797900886 24.318315432621834
532 124.3754405241748 17.242052004887476
533 241.33167450244636 21.44537155444801
534 314.6596926909229 27.112581179692143
535 263.9456767302296 30.381299899174557
536 406.89907257373466 26.890851901127686
537 339.9654406767625 28.895952151371823
538 456.5735835295449 29.286958621098385
539 95.20821218659894 13.563288195296451
540 66.32966001024133 13.472654269291784
541 489.6207827788123 31.468488619877682
542 456.425764010502 29.036619113041745
543 334.05742828662585 28.98655121143042
544 95.31459991748534 16.4981860380906
545 264.09111206348155 27.92082016284644
546 88.5313098858564 14.03055374438944
547 490.3884906035193 30.88415196867866
548 434.1217059355509 30.045129702641354
549 241.7179126005909 25.934793398930427
550 84.1589946013232 14.049627230717563
551 243.5775775175831 23.038007662846447
552 151.35250274951665 18.27440445239724
553 366.0937327605025 28.025724337651123
554 456.55689422900787 29.09383957202612
555 220.8586711149952 20.60136978442848
556 434.14554779346105 29.925920413090573
557 492.94195358569704 30.352885593392852
558 194.1768921338595 20.11738006885231
559 262.4627131682179 23.20013229663551
560 74.99510270977449 13.510801241948036
561 127.17447464282718 18.729783938481223
562 458.87432281787505 29.48007767017065
563 490.800954745365 31.088700340344385
564 276.33867447192875 23.00939743335426
565 268.59483902271006 28.242685244633545
566 458.66928283984765 29.317953036381592
567 102.47032008804644 14.843561099125763
568 408.9470881682171 27.050592349125733
569 491.5829676848182 29.947378085209717
570 131.77595321948732 17.89770309741677
571 490.34319107349 28.53273482589454
572 102.31456939990723 15.54212753589334
573 336.1269015532273 27.48212997729956
574 255.93242828662605 22.811510012699962
575 134.31034271533693 19.156553195073016
576 61.026963820824236 14.075853274418735
577 491.9477481108435 31.389810488774163
578 170.89805786426277 21.94128219897926
579 336.7777842741746 28.895952151371823
580 170.19949142749516 19.783594058110122
581 368.19896881396926 30.285932467533932
582 320.8156604033252 29.210664675785885
583 302.8055209379932 26.018239901615967
584 411.4910144072307 30.660249636723382
585 87.93334292841483 14.726735995365999
586 460.5003375273476 31.776048586918698
587 493.49985306079475 30.35663654516029
588 90.93026446772143 14.929391787602325
589 248.45085327441905 24.97396652515113
590 268.3707255583546 26.578523562504643
591 336.3080996733445 29.70419113452612
592 228.17335312183116 21.731473849369884
593 491.4971369963416 30.469071037550123
594 97.84255408676414 15.525438235356228
595 142.80447450458493 18.920518801762466
596 437.6073855620157 30.014135287358155
597 337.31422607715314 29.30126373584448
598 162.24823181445805 20.615674899174575
599 493.23520843799196 30.600608312166628
600 72.4768415295701 14.612295077397249
601 492.07172577197633 36.42521087939917
602 279.419042513921 24.349309847905033
603 451.8123645048867 30.300237582280026
604 441.77494232471105 30.018903658940182
605 113.42010681445802 16.576864169194117
606 321.69780914600096 35.004236147953854
607 493.4307116728553 35.392069187793076
608 115.4633540373584 18.634416506840594
609 224.25375168140144 21.73862640674293
610 271.3247317534229 27.911283419682373
611 310.5779666167042 25.682069705082768
612 132.82261078174318 19.025422976567157
613 492.74645035083387 37.457563326908925
614 460.5813998442421 36.4156741362351
615 267.48142425830576 23.64835922534644
616 105.30150746687865 15.768625186039822
617 499.47223846728883 35.5908421631698
618 323.850728915288 33.995725558354245
619 493.7335032683143 36.70459752554418
620 191.84789840991706 21.83160965259254
621 177.73351852710454 20.9399241667527
622 462.2550982695351 36.401369021489
623 371.6107386809126 31.556703494145264
624 94.43144130182795 15.520669863774199
625 79.84099399584976 16.712762759282008
626 462.49351684863666 36.99741546924291
627 150.947191165044 20.868398593022235
628 438.7732524138224 30.34792129810034
629 293.00890152271006 27.57749740894019
630 93.98508766195276 15.594579623295683
631 494.9399012785682 31.571008608891358
632 413.8561267119182 30.290700839115964
633 340.8142108183641 33.59041397388158
634 461.33480255420307 30.710317538334714
635 271.50354568774907 29.8996943693894
636 313.23394958789555 27.253248141362064
637 107.6497317888797 16.198741639410702
638 215.3202075224659 23.178674624516365
639 456.74524490649804 30.614950106694085
640 72.57393211381049 14.927007601811308
641 495.6003207426795 36.441900179936276
642 325.40998642261223 34.312822268559316
643 494.5441264372596 35.23640107904744
644 168.5591716032764 21.26417343433082
645 293.87674515063975 25.286294863774177
646 198.3114260893604 24.692632601811287
647 497.16196243579475 35.11454269417334
648 99.00053478556977 15.868760989262478
649 309.62190811450694 30.321695254399167
650 102.3185878110355 16.371824191166773
651 228.151895449712 23.729421542240974
652 440.8713359099161 37.52670471484838
653 495.3952807646521 37.46710007007299
654 326.57585327441893 33.30908005054174
655 542.5163287382848 37.250139163090566
656 280.0746936064503 25.026418612553474
657 459.3630809050332 33.92181579883276
658 330.19504730518054 27.598955081059326
659 496.5587634306678 35.865500366294796
660 101.53255646045409 16.8486613493699
661 495.0495738249549 36.117809013004255
662 464.377023623539 37.26444427783666
663 143.66827194507326 21.6575640898484
664 415.89222137744554 33.49027817065893
665 181.71749298389167 21.364309237553478
666 283.59852020557133 25.255300448490974
667 310.5350512724659 28.96032516772925
668 449.43771545703515 36.482431338383535
669 342.93375198657697 36.52773086841283
670 497.1333522063025 32.36971084888159
671 313.74654953296397 32.033540652348385
672 78.28292858142105 16.20016281421365
673 497.350313113285 37.11930729145376
674 464.3889445524941 37.316896365239
675 80.57547223109451 16.657926486088652
676 128.7385005217334 17.790414736821067
677 501.3605136137732 37.50286285693822
678 330.19504730518054 34.10778229053198
679 377.54259292895944 34.04340927417456
680 133.87165252979008 20.761110232426528
681 343.2270068388719 34.496404574467526
682 238.1797808867237 25.479413912846443
683 498.05126373584363 36.90998980362492
684 158.0759066801807 21.588422701908947
685 545.3439730864293 36.51342575366674
686 113.94224350269043 17.470933840824973
687 347.71642868335425 34.48686783130346
688 306.9730777006885 26.69296448047339
689 373.6063021879927 30.622102664067135
690 178.6418933134815 22.75190536792457
691 496.39425461108766 37.05886116934035
692 445.6540126066934 37.25252334888158
693 117.39120500071061 18.42460815723122
694 466.3344401579629 36.992647097660885
695 546.2022799711949 36.59925644214331
696 223.09265320117683 24.191953585698005
697 364.6203059416549 31.72121231372534
698 467.2332782011758 36.916353152348385
699 345.1987284880417 34.66806595142065
700 91.79554168994628 17.2921199064988
701 499.2028254729041 36.708315734949586
702 108.60539292677848 18.15996353442849
703 522.5344676237828 31.544782565190182
704 95.41235153491697 17.62590591724099
705 345.7828540068405 28.77674286182104
706 467.0520800810586 37.479020999028066
707 379.59537689502383 40.22321884448706
708 347.2467440825242 32.012082980229245
709 499.77503006274793 36.41078337285316
710 510.7065219145544 33.99334137256322
711 464.35079757983783 34.474946902348385
712 421.3210124235881 34.253217623783925
713 320.06702606494633 31.380273745610104
714 158.55512802417485 22.308446810795665
715 137.74046388446774 19.375898287846454
716 452.24390213306054 39.06212036426244
717 350.86832229907685 35.9269160490769
718 470.6760424834023 38.26341812427221
719 500.81453506763063 38.44484446814701
720 92.22538824919818 17.313577578617945
721 382.2561282377973 41.606046603276134
722 429.3509501677287 27.997114108158936
723 345.9640521269577 42.7123088103074
724 459.18188278491607 37.860490725590566
725 208.16526596362797 25.508024142338627
726 139.75343887622563 19.108869479252704
727 497.819997714115 46.331502841069145
728 118.798958338224 18.13612167651833
729 127.86241549711964 18.856145785405047
730 515.6107920866737 37.32166473682104
731 393.5953158598676 33.83360092456518
732 352.3036021452682 33.57610885913549
733 499.4412440520057 41.131593630864025
734 469.2455310087929 40.695287631108165
735 120.32232467944826 18.729783938481223
736 159.47542373950688 23.64359085376441
737 526.814081118656 38.46845810229955
738 339.80093185718243 29.03900329883276
739 503.54442779834346 39.82788830182095
740 266.28933136279795 27.207948611332768
741 170.2829379301807 24.959661410405033
742 382.3252696257368 32.620050356938236
743 500.80022995288454 39.948712684972094
744 250.86364929492683 26.421167300297608
745 549.0132350188023 38.39693252856908
746 469.45295517261127 40.87410156543434
747 465.8862132292519 38.69257156665502
748 168.53771393115727 24.244405673100346
749 383.96558944995553 41.811086581303485
750 93.61281408058419 18.28155700977028
751 500.3520030241736 40.609456942631596
752 357.43913833911586 30.10235016162573
753 349.1755503874558 36.18202392871557
754 238.71622268970222 27.317621157719486
755 550.3889102202183 38.21096603686986
756 111.24867542640312 18.765546725346454
757 506.56995956714235 38.88732498654945
758 469.87734024341205 37.314512179447995
759 202.827073977544 26.270963595463623
760 159.09156982715336 23.581602023198002
761 502.9889125090369 38.705158290954664
762 337.0162028532762 37.54100982959447
763 386.0922831755414 38.52329437549291
764 450.3127116423379 36.75422851855932
765 158.91752426440925 23.729421542240974
766 474.82214157397846 37.64591400439916
767 386.30924408252383 35.5907458525437
768 84.80832430032584 18.210031436039813
769 502.2855777006873 41.38431732471168
770 134.10755175810598 19.733526156498794
771 189.43510238940925 42.39044372852029
772 453.7912387114297 37.77704422290502
773 502.9006976347693 39.76182328264411
774 390.8749598723187 30.965425417973382
775 233.9693087797901 27.85883133228003
776 429.08153717334386 37.650682375981184
777 331.6279429655809 29.65412323291479
778 473.0006236296425 40.71912948901832
779 549.5925921660191 35.96744720752416
780 120.5966344246498 19.452192233158954
781 578.0526179533726 38.09175674731908
782 262.3601931792042 31.072713778569092
783 258.8935870390675 27.632333682133545
784 124.19424240405762 19.17085830981911
785 549.6402758818394 37.60776703174291
786 650.2219218474154 45.005895541264444
787 504.2763728361853 41.067126548615626
788 453.4455317717325 38.07745163257299
789 684.7544688444855 42.7886027556199
790 518.0259722929724 39.35060684497533
791 391.09907333667417 39.61525146777807
792 129.76881045561575 19.919492648198013
793 392.64640991504336 37.436105654789785
794 473.0959910612831 41.57982055957497
795 406.50329773242606 35.23550216968237
796 451.36413757617584 39.22186081226049
797 505.0178546171911 40.85616456072028
798 177.955247805669 25.248147891117927
799 458.02793686206445 38.08698837573705
800 92.25229548883962 19.05164902026833
801 476.70564834888074 41.67995636279762
802 473.4607714873085 45.38498108203593
803 583.5839289885287 42.05188934619607
804 557.6821345549351 39.76307098682104
805 243.54419891650886 26.77879516894995
806 285.37950699146006 29.706575320317135
807 686.9240779143098 43.356038973881624
808 431.5634745817912 46.51508514697735
809 511.68880646045284 46.372033999516404
810 118.44458163201396 20.098306582524184
811 512.2514743071325 46.22659866626445
812 250.12693588550303 28.34520523364722
813 687.427141116214 42.879201815678485
814 326.1228579741259 31.756975100590576
815 559.9661845427281 45.45412246997538
816 163.53569214160652 24.978734896733158
817 554.5898455839879 38.139440463139394
818 476.0261553984413 44.41700165088358
819 135.2187175017139 21.233179019047626
820 322.0935839873096 31.294443057133545
821 512.3063105803259 45.06799500067155
822 653.7195224028353 45.125104830815225
823 510.0055712919958 44.909531795061554
824 431.4275759917033 44.47183792407695
825 123.95343963916505 21.054365084721454
826 395.5312747221722 38.12990371997533
827 511.55767624194704 44.733698092974166
828 215.28444473560063 27.52027694995581
829 511.8032473784216 44.81927333297312
830 521.4925784331091 43.86387054736795
831 687.0432872038606 43.23682968433084
832 122.42756073291505 20.33195679004372
833 202.89383117969243 26.283560446943667
834 667.5930995207551 43.038942263676546
835 555.3313273649937 46.09070007617656
836 202.46706192310063 27.474977419926514
837 289.7807139616749 30.316926882817135
838 478.8347262602577 44.891454623295694
839 510.9997767668493 44.63935245524398
840 118.31930350590417 20.665742800785903
841 442.4687403898966 38.02738373096166
842 476.9130725126991 44.89622299487773
843 689.0984553557159 43.44663803394022
844 456.53066818530664 44.9224490385789
845 161.7976206999561 22.368051455571056
846 449.74050705249414 35.29033844287572
847 167.43622009570805 22.694684908940197
848 432.66973678882243 36.0032099943894
849 689.5204562407257 43.55631058032694
850 161.9978923064014 26.12791244800269
851 560.9699267607457 39.207555697514394
852 615.0170344572787 40.354349062992924
853 514.2994899016151 46.52950089056411
854 397.92022888476987 40.01341049487768
855 189.5209330778858 26.938535616948
856 435.19697372729894 52.74257843311021
857 513.6939067106971 46.32948423043276
858 157.01732818896977 22.623159335209728
859 512.8212947111853 46.58459211007142
860 354.3325442534225 34.334279940678464
861 412.8309268217815 34.07440368945775
862 479.9219149809608 45.89996521289532
863 518.4026736479528 46.179545435131104
864 94.7800433242714 20.646669314457778
865 560.6361407500034 46.510316775395324
866 478.41272537524793 48.54402725513166
867 252.35853378589363 32.62481872852026
868 281.0712832670948 31.177617953373776
869 588.7766856413608 42.957879946782015
870 266.40854065234873 30.45520965869604
871 616.7264956694369 44.65542022998515
872 435.60943786914464 43.58253662402811
873 477.5568026762733 43.59207336719217
874 461.3061923247109 35.31418030078588
875 118.00489609058107 22.91641418750465
876 621.163465426517 44.889070437504685
877 515.6632441740759 48.472501681401184
878 479.31633179004285 48.350908206059394
879 692.1430606108429 46.97761719043439
880 137.27150146777836 21.533586428715587
881 517.5658244353064 47.84417526256402
882 140.30505306700357 22.427656100346447
883 515.7681483488806 47.93990949201865
884 190.80124084766118 28.31897918994605
885 414.41164200122483 39.95380585010229
886 480.87320511157606 48.427202151371894
887 515.7347697478064 48.87396012537578
888 340.15617554004376 33.316232607914785
889 397.87492935474063 40.99331085498512
890 529.0766734343298 42.75283996875466
891 143.55019483810813 23.20490066821754
892 461.0296267729531 48.46296493823713
893 568.039037631107 43.000795291020296
894 661.2440127592806 44.30494491870584
895 563.7522715788609 47.32332413013165
896 107.60030929858887 21.38576690967262
897 231.6280383330128 31.213380740239014
898 480.8970469694862 48.66800491626447
899 459.2963237028847 41.27226059253395
900 111.89894691491733 21.686174319340587
901 514.2065066557653 44.86999695117655
902 388.62905685718204 37.00456802661596
903 444.83623688037505 36.59210388477026
904 441.45546142871495 44.34547607715311
905 564.1194361906773 47.051526949955864
906 661.3656062346224 44.645883486821084
907 517.2201174956092 57.913877413823116
908 462.541200564457 45.21570389087382
909 479.63581268603895 50.02460663135238
910 149.8361605864307 22.925950930668712
911 515.656091616703 56.7382943380129
912 195.75319473560066 28.1902331572312
913 593.0539149504428 50.296403811528165
914 483.1810969572792 47.70956222827619
915 419.14186661059983 41.90406982715309
916 464.26496689136127 45.454122469975395
917 766.8396014433623 52.02017013843246
918 211.20033447559086 30.04274551685034
919 518.3692950468786 56.567391565629634
920 216.9533747893116 30.00459854419409
921 696.119882510257 54.27560989673325
922 482.47299377734754 47.778703616215644
923 707.1467417937042 44.8318499785203
924 156.67877380664555 23.65074341113746
925 316.87460129077635 35.087682650639394
926 482.70425979907606 47.71194641406721
927 482.15589706714246 51.84135620410629
928 242.4164790373585 31.373121188237057
929 518.3335322600135 55.94674465539572
930 294.91148178394053 32.94668381030737
931 265.47632400806157 31.615341045172077
932 464.222051547123 45.60671036060039
933 695.2496546965364 54.18739502246568
934 482.6828021269569 47.728635714604316
935 212.13016693408696 30.328847811772214
936 147.21177439404352 23.657895968510505
937 517.7684802275427 58.53477833154321
938 671.8369502287629 47.52597992236798
939 697.3000544768098 54.20885269458481
940 416.43104736621507 37.855722354008535
941 518.3192271452673 50.98066513354965
942 662.1404666167025 44.738866732670694
943 657.7464122038606 44.9534434538621
944 443.3938044768106 42.31891815478982
945 147.6941746524256 24.02029220874488
946 443.48201935107824 39.016820834233144
947 518.3263797026403 50.809368206904445
948 630.0254840117219 44.40746490771952
949 710.2485675078157 49.07808487231917
950 194.36321441943852 29.782869265629635
951 695.3784007292512 45.75452987964336
952 198.6309069853565 30.33838455493628
953 518.7459964018592 50.789054943965006
954 486.1446398955116 42.023279116703876
955 572.2948092680699 45.49942200000469
956 467.3977870207558 46.02871124561016
957 303.0963916044971 35.1043719511765
958 485.4079264860878 48.372365878178535
959 771.3004130583525 52.26097290332505
960 109.24539749438965 22.837736056401134
961 501.021959231449 45.85466568286602
962 366.8685931425826 37.40272705371557
963 486.8479747038612 52.513696597172704
964 468.949891970707 55.88970367725084
965 569.0547007780796 46.87271301562969
966 241.57962982471201 32.1122187834519
967 519.9523944121131 59.196569369389536
968 185.83259765918461 25.27675812061011
969 312.0108622771046 37.29543869311986
970 535.4782122832066 47.15643112476056
971 520.7415599089392 59.15299378908597
972 159.52999614752227 24.2372531157273
973 773.4867114287139 51.9176501494188
974 486.24239151294324 53.090669558598485
975 153.87973968799324 24.463750765873787
976 447.9309100371133 44.395543978764444
977 519.039251254154 53.19080536182115
978 673.8778132658724 52.713968203618016
979 603.1962413054232 51.05934326465316
980 145.56846802051274 24.01552383716285
981 490.43617431933967 49.65982620532698
982 488.16642944629285 53.33147232349107
983 520.3720111113317 53.33610780728165
984 408.7253588896526 38.296796725346425
985 568.5492533903844 47.79777710254377
986 384.68561355884225 41.05768387134253
987 518.3836001616247 41.420080111576915
988 226.5521067839405 32.02638809497534
989 696.6873187285187 47.77393524463361
990 165.37780784643584 24.785615847660896
991 521.1516398649939 53.363555490372576
992 274.43847839648936 34.42011062915502
993 699.8463649016144 55.54161255176256
994 732.4882525664093 47.71909897144025
995 569.0141696196323 48.138715670659
996 631.6467303496127 50.3631610136766
997 520.8226222258337 53.01613020591243
998 488.810159609867 53.51267044360826
999 392.598726199223 38.330175326420644
1000 132.72233981352588 24.160959170414802
1001 190.94906036670415 27.11973373706519
1002 668.1223887663606 54.92649261768053
1003 530.18055145557 52.29435150439926
1004 469.5459384184609 47.33286087329571
1005 699.5054263334993 48.28176681811994
1006 488.5669726591834 50.14381592090316
1007 587.8206271391634 50.82330887134262
1008 150.50644897497588 24.335004733158943
1009 522.6870555144078 58.51707641895008
1010 537.6144427519566 54.98132889087388
1011 701.6273516875032 55.47723953540514
1012 270.6118602019092 34.67045013721166
1013 522.6751345854528 58.54052205185788
1014 199.00283996875496 26.568986819340576
1015 351.70278732593226 35.74333374316869
1016 450.40807907397857 47.06821625049298
1017 493.4235591154822 51.958181307866056
1018 491.44706909473024 51.5671748381395
1019 521.8645114165075 52.55661194141098
1020 194.95210830981938 30.848600314213623
1021 523.4976786833531 51.88821164461282
1022 737.6285571318391 52.66866867358871
1023 334.2195529204149 37.92247955615697
1024 115.97118561084474 24.442293093754643
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-3
) and FFTW:
size,rel2,rel3,speedup
8,31.0035623439637,1.60179621985251,19.3554972597066
9,23.0236843367442,1.66189572106003,13.8538682331155
10,20.8464275202564,1.6704457890217,12.4795594429108
11,280.324183098903,1.66903548230462,167.955796069613
12,31.3217344925748,1.75715822071013,17.8252214987883
13,238.564872414651,1.71401406562686,139.184897719845
14,220.196265658982,1.58283648010676,139.114980243651
15,24.4004823296537,1.74684872552867,13.9682858470009
16,41.613223688593,1.56244851339704,26.633340767254
17,75.6522121597436,4.32717843474614,17.4830350309282
18,31.659967533097,5.79057788675042,5.46749705336648
19,428.745816685474,13.6718289490855,31.3597996494941
20,31.1467155085507,1.59926217619969,19.4756782046608
21,243.187456369924,6.36737049944889,38.1927604795374
22,297.173923636788,5.30746580371016,55.9916793866199
23,338.913321074374,10.9035602953895,31.0828125761529
24,39.9146205525711,5.19354290947141,7.68543193891385
25,30.844757712075,1.78291523923087,17.3001817660054
26,254.636204069331,5.28169754457152,48.2110537228781
27,35.8707950145261,5.6036876859799,6.40128376609438
28,256.327406474509,4.94166067109643,51.8707016800562
29,136.255087213481,4.53873045026054,30.0205285831987
30,34.4694643926202,5.06176103743359,6.80977709886061
31,140.631775111143,4.6294738744236,30.3774854175309
32,55.796267061807,1.78968473038739,31.1765899962334
33,365.283997243452,5.16981457496605,70.657079078286
34,99.4332853296993,7.60348880801081,13.0773238233664
35,296.647448889548,6.93806530354674,42.7565086102463
36,22.1364583157872,2.37263127558175,9.32991929407973
37,312.918980821529,10.6566226578152,29.3638041684852
38,531.142250661184,16.58988885936,32.0160222388419
39,357.94137972657,5.16824933257253,69.2577615152328
40,20.4687655988403,2.24605178340342,9.11322069690848
41,279.270424648104,9.49360103288939,29.4167011738334
42,318.924524672781,4.79497553245626,66.5122319215274
43,281.747643338043,9.55388805977194,29.4903647159509
44,424.1869719843,5.42064671247213,78.2539417314002
45,40.0534922145836,4.93418832188685,8.11754428523049
46,427.682735934799,13.5149670434498,31.645118671753
47,256.424329809441,8.69915013522599,29.4769403704261
48,30.1298650675711,2.65512890518668,11.3477974680301
49,371.29467467343,7.62288913434979,48.7078675984312
50,45.9285788055788,4.70637945514524,9.75879213380627
51,108.93295754923,7.27235644459564,14.9790454275907
52,418.450271063551,5.47055989179423,76.4913060711063
53,233.262880194168,7.9002128689085,29.5261512651362
54,30.8789814952158,3.80258690834581,8.12051959350187
55,519.369414156701,5.59630982321585,92.8056934950488
56,338.902214071608,5.10676226851052,66.3634209411621
57,481.308370331345,16.603756167218,28.9879208947687
58,228.591352563704,7.20504529965552,31.7265670175083
59,211.712173908992,7.14268312020498,29.6404264820467
60,26.415368131313,2.60539058033635,10.1387363302368
61,217.957897546566,7.51088445187899,29.0189389735639
62,217.582717709118,6.81979196279667,31.9045975150085
63,399.561169721661,6.82315653110256,58.5595783857967
64,77.1386234280048,2.88801214649087,26.709937325483
65,481.857605313242,5.55238116900563,86.7839564046964
66,524.756015432184,5.851393257292,89.6805243397773
67,493.973069731807,12.0472553617441,41.0029550216402
68,129.768483217381,7.43232698104396,17.4600072828272
69,451.222572680023,13.5640564671053,33.2660494133373
70,412.985101384841,5.31249452783532,77.7384521002265
71,446.168666714429,10.9506388955187,40.7436197076146
72,43.3313245255458,3.93484362135793,11.0122100635329
73,422.209119515195,10.4053311937507,40.5762307468662
74,438.762564712467,13.7935818523676,31.8091826625262
75,56.3774648955331,4.54884563578351,12.393796011023
76,546.277651021967,14.6087364594231,37.3939014191471
77,555.351526550351,6.1678107593249,90.0402992602738
78,483.562604732599,5.9101476535227,81.8190395707586
79,421.277925273441,10.3635163319372,40.6500951781388
80,32.5702339374315,2.79675066524323,11.6457410173169
81,60.8374213913291,7.15430072132508,8.50361534426262
82,391.400568530886,12.1930636021138,32.1002646507177
83,376.43862980617,9.18369871364938,40.9898714606876
84,258.660069203734,3.58351450566687,72.180555930413
85,147.352980120585,7.50362473178509,19.6375732246313
86,371.070479141964,11.65188117203,31.8464009084393
87,242.132373957657,7.72831629450731,31.3305466198046
88,551.401191875935,6.8350063769033,80.6731056958802
89,502.646686053713,12.5873797709902,39.9325908329348
90,35.490493816823,3.56234198258888,9.962685780951
91,478.318094027619,6.14009913599561,77.9007119320818
92,460.329737004008,13.780968905404,33.403292625056
93,231.280967852096,7.25360271304837,31.8849786790844
94,349.468105493579,10.9593880762088,31.8875564094882
95,602.254428424729,12.4338550963686,48.4366613376911
96,48.3820658264393,2.78807011377441,17.3532457406321
97,361.023447620726,8.92639288707869,40.4444944545653
98,448.542659597839,5.97779416576827,75.0348116980023
99,516.505095013952,6.46992120648212,79.8317442407913
100,39.1023293337295,3.05461663152092,12.8010595274799
101,307.671136213038,7.52335425956776,40.8954736940322
102,149.505035197283,7.74842711927367,19.2948882264634
103,406.730452669845,10.0248427445541,40.5722526561125
104,500.501671424073,6.5477022903623,76.439283466014
105,425.162572970627,5.86502814635534,72.4911394048181
106,305.97788291228,9.4583693734461,32.3499612704171
107,383.150072000661,9.49729886079637,40.3430572857147
108,49.2275128714945,4.329263504303,11.3708747048004
109,326.228891955307,8.06545327490561,40.4476823355132
110,565.622120091478,6.82336850278927,82.8948516938902
111,639.112844687001,14.6319019571331,43.6794100014751
112,273.996433022369,3.90337133751504,70.1948160527306
113,409.337945427271,10.1243294308307,40.4311167691512
114,613.23874996535,11.4206706033202,53.6955115216326
115,500.922741873498,13.3962474925362,37.3927655601011
116,296.500529084055,8.53441662691396,34.7417453407438
117,451.719074313888,6.07657181547636,74.3378154707906
118,259.845133913181,8.11164400826326,32.0335968452855
119,154.671595437838,7.7939796410792,19.8450089120865
120,46.499174900736,3.6171955737389,12.8550347784132
121,610.328310244978,7.25168807927349,84.1636186737535
122,259.930403508287,8.18881129926315,31.7421410762849
123,573.313354046854,13.2089703174851,43.4033342695867
124,289.453788865766,8.08675625348373,35.7935592211117
125,71.0629719495507,4.4734138532588,15.8856243309084
126,297.680059140862,4.21845831848442,70.5660780945704
127,307.710885330496,7.67244465178409,40.1059765558483
128,56.4045482855623,2.51566934222785,22.4212885766661
129,549.339852550991,12.8217439982295,42.8443940720425
130,497.35505670896,6.37663156629909,77.9965176814532
131,695.928907841214,12.8256935059813,54.2605284865624
132,395.531989644992,4.61588950121717,85.6892240467832
133,617.28480992687,10.4555242346991,59.0391066072295
134,618.695555789857,13.4095671364123,46.1383689343597
135,49.9844159596429,4.24608973447352,11.7718699051094
136,188.083940308365,8.04045368233071,23.3922049351131
137,719.295889668846,13.2928463896741,54.1115024264174
138,502.525446836379,12.5604790842467,40.0084617366741
139,872.942812789777,16.043165681289,54.4121297586475
140,332.551356100159,3.91705154933059,84.8983864297092
141,491.668951166375,11.4368307631961,42.9899647329376
142,587.18482651983,12.6920979779815,46.263811352425
143,523.972874511054,7.24269200629952,72.3450443640727
144,67.7299881544339,4.30656918048351,15.7271334363726
145,312.101861576098,8.91828998843752,34.9957067981346
146,546.709253613293,11.897100335575,45.9531514564528
147,417.177229780238,8.39370860223223,49.7011809141543
148,662.169036336561,16.0846997301511,41.1676343012679
149,701.786347622189,13.0117231552895,53.9349276991728
150,65.1752883721421,3.8604525285041,16.8828104712887
151,700.753969942058,13.0102643397901,53.8616243021978
152,503.801432706304,7.91628849521438,63.641115784356
153,181.329392680331,7.73699765044724,23.4366612053771
154,541.043311835516,6.85899425909997,78.8808521187639
155,288.826578404247,8.32090827337539,34.7109436752731
156,386.526618980629,4.95909776393276,77.942931835669
157,834.542331338152,15.8738532882865,52.5733932512764
158,538.769792982785,11.7426978626277,45.8812616389862
159,435.714709146841,10.1008372976072,43.1364941647022
160,63.7782579786892,3.29814632165406,19.3376071764771
161,544.872701910037,11.4371404779365,47.6406408543427
162,65.8962179141201,5.57173080919878,11.8268847097436
163,602.396566061772,11.03898064834,54.5699449298661
164,578.970676300861,14.16044398856,40.8864776251791
165,545.964865486633,6.67196029055102,81.8297534324119
166,481.151118987848,10.3746765213505,46.3774574559184
167,698.678541154153,12.6317355999393,55.3113652218551
168,344.667718728519,4.54154355054015,75.892197199678
169,517.912065422364,7.86515257542747,65.848953399892
170,187.773527222397,8.04131438257274,23.351098873754
171,684.342512136198,9.05133908976889,75.6067699319474
172,542.342627134465,13.4809944794239,40.2301646189562
173,691.446918204287,12.618243796678,54.7973972722196
174,323.690545705247,9.35951315532283,34.5841220941243
175,416.771335598153,4.96274944191451,83.9799269489964
176,426.574487709098,5.03493320268491,84.7229686148814
177,396.512956199167,9.28788650328097,42.6914084338883
178,474.673162247135,10.2426569636897,46.3427764817134
179,682.272685691075,12.4893615209538,54.6283078239351
180,65.140155932268,4.23463683194973,15.3827018744075
181,563.065132198392,10.3707046641069,54.293816132588
182,457.635660262831,6.28894249936637,72.7683009200576
183,372.875240298742,8.82383693740158,42.2577210961636
184,447.231871511689,8.85273695092553,50.5190512257266
185,664.294696626511,14.8531199514967,44.7242531397972
186,299.688065640459,8.96499578230755,33.4286900872719
187,193.714881150811,7.59276322053467,25.5130939190765
188,478.597326529552,12.1362038216751,39.4355050032025
189,307.919880322086,5.87908347239379,52.3754904600309
190,654.515562164685,8.79402205662429,74.4273277858858
191,584.268659113577,10.966062149267,53.2797143733708
192,84.3939794660343,3.44470054023305,24.4996563504834
193,592.160682445265,10.9372499360987,54.1416430917266
194,505.150491642247,9.97386592502323,50.6474114891483
195,536.307975198127,6.25974372836847,85.6757078996122
196,347.849331181805,5.07789811490752,68.5026212244394
197,674.131604545726,12.5632551531832,53.658991744263
198,432.409036710015,5.15734161147162,83.8433963242215
199,672.32728119474,12.6495267819843,53.1503899538978
200,74.1495001282507,4.14430136436327,17.8919179878809
201,747.263302135204,13.5064772702015,55.3262917625341
202,424.436484409191,8.39992869131938,50.5285818494877
203,351.113850141492,9.68793596496277,36.2423793273743
204,151.827104640608,6.67906681506831,22.7317840717028
205,588.799652391248,14.7295444931238,39.9740570841221
206,407.659571435643,8.11735259603955,50.2207544408678
207,520.313314974387,9.91970142561126,52.4525177371782
208,402.793691683496,5.16429743663344,77.9958351790971
209,627.466437344979,8.19491470052951,76.5677813955081
210,354.025897583459,5.2574904696915,67.337430210165
211,511.040444728673,9.48292311181359,53.890603003206
212,422.391924997952,10.9045096768802,38.7355266320237
213,736.175247364266,13.4218325600193,54.8490859256562
214,408.079797739854,8.05333642653471,50.6721408527382
215,542.166398734392,13.6802191741072,39.6314117364846
216,90.6417415134905,5.21569758399242,17.378642080722
217,328.04316595483,9.12331590303281,35.9565720886395
218,451.260037872095,8.97003003406241,50.3075280861378
219,670.902993282901,12.2096253692106,54.9486960488351
220,463.914388694385,5.29271911344533,87.6514280751991
221,213.42503126647,7.59871990831101,28.0869717323097
222,632.89136298718,13.5632672620827,46.6621611708917
223,466.967602378254,8.63028549314689,54.1080133153257
224,379.99709156789,3.89908041687732,97.4581313899192
225,75.685162555707,3.74623299735451,20.2030046206827
226,448.964506679869,8.87178357666941,50.6058903263301
227,502.185119847148,9.32348702981605,53.8623712610083
228,569.731831319062,7.12029187616211,80.0152355026984
229,555.812350340781,10.3518626205072,53.6920137676199
230,457.060724940688,8.57275705974892,53.3154878594069
231,578.855477893771,6.61585156632207,87.4952335449044
232,357.783442762585,10.0141534411216,35.7277771771901
233,562.08338002122,10.5359138427258,53.3492764283845
234,388.464908783067,5.05172876406586,76.8974200567358
235,492.16793745969,12.5200168700049,39.3104851670616
236,361.390406862752,9.54081865819868,37.8783435478254
237,662.478082979693,12.1453757058522,54.5457052152354
238,190.842998544489,7.38680449803985,25.8356639322363
239,546.493120794215,10.2940059548289,53.0884791782982
240,83.1914014040263,4.41678936476766,18.8352657402313
241,421.258869670249,7.85871668831384,53.6040280338232
242,617.866795051413,6.50688582953719,94.9558377444837
243,89.7270342015239,6.95584004460588,12.8995252372293
244,343.105586126694,9.14852898218243,37.5039076549818
245,450.304106696642,8.41002998387362,53.5436981271302
246,579.070826575427,14.6760419897447,39.4568799258049
247,677.300422052894,8.1517347733485,83.0866608009964
248,335.336750312789,9.51245011202051,35.2524056750676
249,553.810902657188,10.1697062598687,54.4569222065554
250,78.8365200760403,4.1914819852924,18.8087460121913
251,523.399742696637,9.07462252873963,57.6773018424747
252,377.449894087009,5.08700844335338,74.1987944958455
253,576.834639475515,8.8717347995412,65.0193736072167
254,417.632242312575,8.3319337311226,50.1242875651515
255,189.178267404063,7.6785756334682,24.637156216773
256,110.734191742325,3.83644266546826,28.8637681827077
257,158.04862300712,4.15783191410833,38.0122684783938
258,549.7790952933,14.2332993818934,38.6262580826966
259,771.640801166783,12.3694893136352,62.3825916819526
260,430.246987615493,5.60364602944667,76.7798296599361
261,346.359379184053,9.66538254749591,35.8350409290098
262,975.801001719577,14.4034740876984,67.7476139282939
263,1315.66173593951,16.7907152463432,78.356503379214
264,576.222160143937,5.71362090453363,100.850611157404
265,412.358846415636,10.6259231662026,38.8068725856412
266,660.267723190285,7.89640637038064,83.6162289806847
267,589.265515745625,10.7652500339189,54.7377454205877
268,836.299919499441,14.0684646814468,59.4450025952254
269,1319.61240409077,16.8902619375106,78.1285932079072
270,76.9386078845709,5.18182445614152,14.8477835433778
271,1203.06911393861,15.4769084356997,77.7331673788002
272,158.813219162244,6.6083307065007,24.0322747476935
273,531.625846529593,6.36079556540422,83.5785148356373
274,940.392060345556,14.4297042813904,65.1705705125471
275,675.192450291204,5.78356126381128,116.743373069461
276,527.43144793996,8.14445530296676,64.7595730248325
277,1319.80680856013,16.8372514559989,78.3861197303612
278,955.268634472655,14.5066837232806,65.8502420466795
279,325.468398428997,9.2790996253886,35.0754288205378
280,400.933471805248,5.08094284460713,78.9092662655701
281,1325.77960338102,16.7547912845627,79.1283866724469
282,489.345546650158,12.758178217818,38.3554405884331
283,1293.72834674038,16.4866984710444,78.4710382744343
284,806.928750634983,14.0474237100419,57.4431844081234
285,695.647937109771,8.08402925965168,86.0521300413681
286,538.657203479221,6.42722768260405,83.8086388221709
287,727.55331718038,13.6019092219255,53.489058433621
288,109.277615313159,3.89222530921587,28.0758709045994
289,223.571813289553,8.54411072633738,26.166773869209
290,382.752054496402,10.0324382113301,38.1514489732061
291,561.479960811569,10.3232494231878,54.3898474011861
292,753.966911082262,12.8201922082681,58.8108897927451
293,1103.35906346806,14.1820646928734,77.7996072759778
294,391.558967307844,5.51844076445247,70.9546380981574
295,370.546474356103,9.65108837053623,38.3942681000978
296,809.916210213678,12.3193610468252,65.7433617811211
297,661.862949786433,6.27414917980855,105.490470630893
298,940.101921882978,14.1469707470569,66.4525246211141
299,558.638305291894,8.16821516720563,68.3917225313503
300,101.182083440555,4.51364497403331,22.4169344338442
301,699.758177310983,14.0568143026405,49.7807086474449
302,940.827322153705,14.1722154486173,66.3853386624528
303,481.038853666049,8.92609360689958,53.8913073121059
304,652.219475009659,7.20132211354309,90.569407218026
305,353.135312599842,9.21446636420219,38.324011249502
306,169.682263138503,7.13805964166549,23.7714829598863
307,905.898978825545,12.1970188838403,74.2721633419592
308,626.613220392914,6.08166001909623,103.033253819741
309,460.96160034408,8.5853076598535,53.6919139775995
310,384.06120650799,9.72867726956062,39.477227568197
311,998.025430316007,13.4242609405609,74.3449069364042
312,516.468589757692,5.62827943268529,91.7631393278711
313,970.632427693536,13.0609187776226,74.3157846871025
314,925.845936398627,13.8932404856096,66.6400281027026
315,421.336899752695,5.55208967071797,75.8879853787033
316,738.784541906404,12.7247382058147,58.0589187735752
317,1096.9846367387,14.6250472416202,75.0072542409902
318,452.321710322474,11.2658041256961,40.149971122858
319,409.605786037976,9.26934881464948,44.1892730793156
320,102.287460999453,4.16947435129351,24.5324595815586
321,472.127167529192,8.74759403924164,53.9722311542161
322,540.059488113134,8.70973895842436,62.0063920045238
323,622.636523327125,8.77554881855964,70.9512916172598
324,122.590179913927,5.68786982868582,21.5529158729449
325,591.747207938315,6.12746058809492,96.5729929112925
326,779.196514122214,11.7431228976994,66.3534326354421
327,489.872495455394,9.11230334076655,53.7594587379249
328,726.483441465791,13.1644456018571,55.1852666976958
329,613.982257355448,13.1041899873462,46.8538885614699
330,634.252608881127,6.0565422784249,104.721899018275
331,901.985690895881,12.2179169118768,73.8248342496978
332,659.708705342733,11.2418975526385,58.6830383619622
333,752.99016577877,11.6041021865543,64.889997836391
334,775.2938758776,11.6270438371039,66.6802229990314
335,846.09125333199,13.9759622309305,60.5390340465781
336,494.73393126766,5.52410125420776,89.5591714382166
337,979.880865238625,13.130028801419,74.6289958733924
338,589.055704975882,7.30268556922795,80.6628875626311
339,487.216641835129,9.09324444789025,53.5800664578163
340,198.591406523838,6.37387613386562,31.1570859478558
341,409.586472040896,9.55247904090679,42.8775054398879
342,609.139831752487,8.51580166176116,71.5305329958225
343,562.070367675752,8.66636817034509,64.8565069735978
344,695.329369579615,13.7514782993852,50.5639724283826
345,523.856265790079,8.21868619769523,63.7396602314595
346,784.839938486554,11.5944549774234,67.6909729706815
347,933.457314250363,12.2251256736741,76.355641583341
348,427.456671139366,9.4170770647633,45.3916505301648
349,950.074101468039,12.7649011489985,74.4286297542212
350,494.113338108466,4.74527663236614,104.12740423567
351,574.903207511164,6.02435757091219,95.4297949190479
352,638.893719088529,5.16809472940097,123.622679641281
353,968.134511027729,12.8503137470179,75.3393675895581
354,381.673866122807,9.93526914375135,38.416057038863
355,881.13644748383,14.1755979589799,62.1586793046461
356,618.922357178502,10.775326890433,57.4388474216983
357,198.607151994154,7.79410644877617,25.4817089424458
358,781.547601605375,11.4980970025702,67.9719088672391
359,959.608426416626,12.9552959764775,74.0707451345734
360,109.74304887471,4.85654030112485,22.5969604018917
361,751.637490270261,15.7752432617465,47.646649740921
362,783.005691204304,11.4222949852813,68.5506452261371
363,621.147351103776,6.93417481858268,89.577688384663
364,559.608020154014,6.00377280937292,93.2093931469842
365,796.609802272414,12.8098830509263,62.1871252926708
366,374.941868803699,9.43066151878668,39.7577484948201
367,840.824731314084,11.2973011093286,74.4270444044181
368,513.812163735259,8.11963167432927,63.2802304764277
369,674.572209462169,12.1617723944844,55.4666036808996
370,801.260072138537,11.3071770159381,70.8629634973534
371,540.62672699841,11.3162971464796,47.7741720635707
372,390.405340803122,9.94391922208273,39.2607112028965
373,900.6418234615,11.7234777219828,76.8237757446922
374,216.000750046229,7.30841896490696,29.5550584994383
375,149.916344129949,4.67600982107342,32.0607419287956
376,620.918231999434,13.4588119497105,46.1346985394793
377,476.307825573929,9.35062304317648,50.9386191031954
378,451.850366440746,5.24803846706194,86.0989051960416
379,923.209964002848,12.2176480481704,75.5636404292315
380,611.099378902982,6.85172826239624,89.1890856584062
381,494.253379913041,9.21309799705727,53.6468167462139
382,816.215954231671,11.8178624873657,69.0662930884731
383,976.669541180908,12.9369443765489,75.4946077492102
384,152.641402495647,4.31818152313986,35.3485377299881
385,675.67591693434,6.67330481123031,101.250570151878
386,787.938100127915,11.4125815816767,69.0411800773433
387,682.843173868159,12.7411659543175,53.5934604663687
388,638.418893624038,10.4703194920308,60.9741559567452
389,851.727837497005,11.2960815216151,75.4002913193589
390,556.42205513466,5.77883031501719,96.2862767727771
391,523.733161797886,8.94684168429526,58.5383289744822
392,485.807529115287,5.88210999859974,82.5906909647959
393,1060.21601867565,14.7670617126748,71.7960037890036
394,831.571970107557,11.7757063934746,70.6175869473412
395,819.216150348264,12.9482010450746,63.2687233922653
396,628.65757491269,6.00085076706616,104.761407892842
397,914.596515194875,11.945194041598,76.5660659851886
398,824.264738519433,11.5743039315895,71.2150590991294
399,675.839046197227,9.20011060832352,73.4598827089951
400,156.70936927354,5.05380703143697,31.008182207737
401,764.497773429644,10.1382206875534,75.4074898338141
402,1022.25299664792,15.7087369043168,65.0754419578447
403,434.342447179386,9.80383046506696,44.3033413038951
404,545.515295272911,8.73321674950959,62.4644172839915
405,127.87834857968,5.14074754456527,24.875438342595
406,386.998118999461,9.24067313524315,41.8798623580227
407,848.052117943561,10.6237126631997,79.8263417723257
408,188.738867582271,7.19270896358836,26.2403036933267
409,793.507881855528,10.4715514531301,75.7774896496676
410,694.736328914123,12.0516246695986,57.6466947785606
411,1087.24836606028,15.0761583227479,72.11707006418
412,579.225239637382,9.41163644430567,61.5435204137992
413,449.896522495776,10.020884090875,44.8958912622741
414,481.608974102715,9.10379429290307,52.9020053186128
415,683.947511404036,10.9373381971539,62.533268979651
416,560.362439390747,5.77807999433144,96.9807340743789
417,1091.42931780311,14.937919239356,73.0643472035645
418,647.620097051185,7.66028141910001,84.5425985834438
419,855.774804797403,11.1805511245853,76.5413793346567
420,492.476568201643,5.17285499363115,95.2040157336681
421,831.529675540752,10.8696038583582,76.5004581929953
422,686.189350142989,9.8382318979068,69.7472225968758
423,608.430142029746,13.0520801821479,46.6155688241889
424,525.783827437897,11.5433343068818,45.5486961964223
425,194.488630624881,6.37231925751437,30.5208547728578
426,987.814650377906,14.8005730062852,66.7416491211808
427,430.692521759793,9.51356372607113,45.2714181731411
428,584.783053385078,9.05494149856423,64.5816489789362
429,564.437273863266,6.5011140365638,86.8216232923677
430,658.774352361513,12.3641509871894,53.2810019098015
431,832.205734282893,10.9232505914389,76.186637605397
432,149.789830487304,5.36788746911855,27.9048007897044
433,731.316001578312,9.51253467084646,76.8791943349876
434,390.388355988516,9.61564749469123,40.5992790609314
435,391.03670022181,9.41399597284471,41.5378019440183
436,599.785054162366,9.35251419689272,64.1308894630321
437,562.314650063609,12.6319540982782,44.5152543849298
438,892.027263732429,13.4136945139673,66.5012359423861
439,801.909006806316,10.4824379949425,76.5002385125689
440,623.218920572504,6.21080678760844,100.34427762524
441,472.803385486657,7.11407656583366,66.4602610207151
442,284.931102399285,6.90879848065189,41.2417735438709
443,783.428649920795,10.2574726724508,76.376381876688
444,898.468106781393,10.7272365009188,83.7557843256682
445,766.860466046303,11.1623878040987,68.7003963224356
446,663.550758009001,9.55125809148733,69.4726026302648
447,1065.54188317982,14.5889088398115,73.0378052861689
448,492.35403534789,4.6013425635847,107.002256090301
449,809.662746988605,10.2846086051443,78.7256742647084
450,147.451863291934,4.76280217470713,30.9590568499733
451,756.091147986454,11.232951340618,67.3101062275994
452,595.314067501916,9.31766095980876,63.8909346529963
453,1058.42510903773,14.497408026335,73.0078857624115
454,689.063268549226,9.87960547653959,69.7460308699063
455,600.91663917742,6.43707282801041,93.3524686193666
456,674.309731096883,7.93494539694967,84.9797569314212
457,750.736157491946,9.8308321493579,76.3654740601974
458,661.960722893855,9.91431718323335,66.7681606972726
459,189.440774013471,7.06789500650419,26.8029977580509
460,551.772203810844,7.68135278127823,71.8326861846104
461,811.473144674888,10.6504054754915,76.1917606369293
462,633.814173185857,6.59482059423189,96.1078719473002
463,810.681501264912,10.5558038612864,76.799598772207
464,391.236056774239,9.29116303552583,42.1084050810757
465,380.206821299068,10.304411474799,36.8974804848313
466,652.613015692748,9.86717148235079,66.1398270882454
467,785.84208906336,10.3289206656766,76.0817237830808
468,542.084077773696,5.85393939229832,92.6015869735316
469,1038.32601978614,15.1946669770138,68.3348981163518
470,608.355664929834,13.7384928810333,44.2811063919318
471,944.885671612098,13.7143947411011,68.8973658298125
472,460.496214669603,10.1302856000603,45.4573772991022
473,684.112195487549,11.280505451068,60.6455267855734
474,864.527279588159,13.6303998574083,63.4264063147259
475,771.698207770463,6.39483028952172,120.675322539041
476,266.473262695194,6.99736710966748,38.0819326067712
477,508.686673582495,11.3048216718213,44.997319581826
478,655.437300677378,9.74865198339772,67.2336341264013
479,785.891318553757,10.5707636128206,74.3457471322698
480,148.789986940107,4.49809006696661,33.0784810274923
481,971.222766756003,10.6130982629725,91.5117096526332
482,554.715783997261,8.21126268979135,67.5554789748611
483,694.26212830919,9.66671375350174,71.8198703316
484,646.186870301022,7.043418175904,91.7433629756175
485,724.487746474418,10.569822645596,68.5430371697186
486,168.409212113894,6.60353399723646,25.5028916614002
487,687.822122514261,9.00162286357969,76.4109020049229
488,424.012366373052,9.35041027639394,45.3469263742912
489,797.536079428995,11.5852307407411,68.8407591766251
490,490.169254027678,5.85128643421886,83.7711945122227
491,688.379490586977,9.01675854254632,76.3444520931554
492,819.768972919284,11.325366024037,72.3834418401492
493,450.75665922744,9.61844293059089,46.8637868395347
494,783.673478318083,7.40114969785224,105.885370558779
495,627.791370972855,6.13891916688387,102.264153331656
496,430.758887795221,9.59016616116254,44.9167282981678
497,1002.35062404769,15.1608986964558,66.1141957423678
498,763.618257042825,11.8215412608525,64.5954905703857
499,728.733682452732,9.63641934990503,75.6228694489011
500,177.537235352487,4.72263806900699,37.5928099418841
501,837.000531352696,11.9187535521759,70.2255087068136
502,664.732949242104,9.49686687425616,69.9949739259843
503,740.496411688008,9.58144087001976,77.2844524882489
504,488.327379387896,5.72763797814732,85.25807344162
505,583.733087791724,8.96581834529901,65.1065039810659
506,600.164605506714,8.0849349756448,74.232459174336
507,603.505737174284,7.10928130825378,84.8898378059146
508,542.214598197208,8.88027497713681,61.0583117744886
509,773.371742646601,10.1728180308982,76.02335363688
510,253.479245875098,7.02156558915894,36.1001036957429
511,909.571298558846,13.7639539376082,66.0835761789031
512,191.836498116332,4.45720636267936,43.0396267318019
513,732.721224371974,8.0612298729603,90.8944709329941
514,203.959819983088,4.41121642888795,46.2366386394933
515,575.122412159116,8.73944652295611,65.8076470458888
516,759.434785432332,11.5705558801009,65.6351166963735
517,634.635289856642,11.9786446880361,52.9805588515783
518,867.797608652772,10.6474065856847,81.5031906285529
519,824.111659460536,11.7952255089242,69.8682410808524
520,565.18307163623,6.14568248328857,91.9642485880265
521,1498.25459791786,17.2040042439463,87.0875510534158
522,520.869833196188,10.54514043546,49.3943002830636
523,1551.39940316362,17.7485091262743,87.4101251054931
524,1072.27513227212,15.2548992418775,70.2905417643485
525,496.446050570955,5.09675359913428,97.4043655269661
526,1240.86848905617,15.9890731198572,77.6072809070527
527,410.132072917508,9.91888696624468,41.3485983168518
528,626.510905262879,6.51921358680626,96.1022210609615
529,653.465571117176,13.0776126846108,49.9682615532839
530,576.432722269123,11.5492973896322,49.9106311684888
531,448.798779660079,9.84695596988909,45.5774130637383
532,795.055841530106,7.35182972249529,108.143941241916
533,896.232103806864,11.2509178715829,79.658576663379
534,777.302708365584,11.6272220335897,66.8519708422226
535,587.686567138934,9.00146148457189,65.2879055413617
536,1104.59737008177,15.8247188158158,69.8020219466899
537,804.759193188106,11.7778667727358,68.3280944433009
538,1261.51856059997,15.9507431539152,79.0883878216248
539,726.098874970669,7.05077000693103,102.981500496669
540,170.061347621322,4.94610638800848,34.3828729672344
541,1385.49522203287,15.885334684339,87.2185100008501
542,1260.903377379,15.9283315577549,79.1610453867722
543,807.992663068268,11.5923379691491,69.7005785389101
544,234.526631063782,5.85433133548973,40.0603617431166
545,637.435073965456,9.6004608083766,66.3962997910768
546,573.25506277815,6.33689847164025,90.4630341394388
547,1400.76348486921,16.0925554007705,87.044192173615
548,1098.34495754179,15.4324518545244,71.1711248410464
549,428.21642409432,9.45677481042467,45.2814445388163
550,681.193482488049,6.00038472136601,113.524967834558
551,535.035858791042,10.6003687342927,50.4733252401091
552,650.750667048643,8.40177774327569,77.4539254587479
553,939.947384473715,13.6383403580201,68.9194843213436
554,1256.47507964087,15.757226728201,79.7396078202097
555,916.245660731232,10.7144784771898,85.5147231553868
556,1098.05693562896,15.3578039752316,71.4983038851036
557,1386.65889150992,16.1092197625003,86.07858803552
558,524.108548674871,9.79036093244635,53.5331181650226
559,799.13154953098,11.4734299992592,69.6506231861417
560,540.523334755136,5.60722910275363,96.397583342848
561,266.762661882614,6.94473209188808,38.412232229118
562,1286.22687536678,15.9210534591112,80.7877995429198
563,1445.42082564087,16.1746685404277,89.3632424076033
564,726.396844237268,12.1014522584914,60.0255926909573
565,631.584554468889,9.54495498161109,66.1694639404453
566,1267.22683419539,15.7588119924356,80.4138557401198
567,475.20381990524,6.95032585662444,68.3714446931028
568,1010.87332174474,15.2850173300982,66.1349149898704
569,1457.87210841751,16.5680006944788,87.9932428360739
570,796.256209167334,7.33544523244313,108.549131502701
571,1503.79701598318,17.2685529821781,87.0829777998867
572,606.443552778871,6.72972184789819,90.1142077615399
573,857.184394886198,12.1538553582191,70.5277765467665
574,823.574399805857,11.3284641700073,72.6995634577117
575,677.600101062989,7.06755944262905,95.8746943076194
576,190.063066625296,4.4494383279538,42.7161930599681
577,1366.23434339652,15.7524677685008,86.7314482705046
578,268.390001282356,7.84092098693665,34.2293975069391
579,837.415055509825,11.9013954253246,70.3627621453461
580,471.591710735791,8.59692664899954,54.8558490714437
581,814.489698512036,11.9044679743779,68.4188239461912
582,753.861098194257,11.3106263970819,66.6506939340471
583,568.744369625575,11.694007286295,48.6355408972702
584,918.716211917827,13.9369464537512,65.9194763333935
585,566.157202838182,5.96528083811793,94.9087257083452
586,1197.6385242667,14.8258639564143,80.7803530227696
587,1395.09553251849,16.1535526931007,86.3646257280819
588,518.813606204685,6.24024813648575,83.1399000259723
589,559.276920152753,9.95321876193467,56.1905584042487
590,489.068368362511,10.13006140772,48.2789144782282
591,823.379947292871,11.7354927597051,70.1615146591903
592,929.258609434265,10.2908903754038,90.2991457041737
593,1388.42007465563,15.9742854633494,86.9159423650685
594,748.249202000277,6.42751220138249,116.413501609431
595,259.623375175152,7.6714083720847,33.8429871781939
596,1064.27412315248,14.7678286157684,72.0670689539351
597,825.71323631448,11.7617947632576,70.2029964758358
598,671.715852046562,7.93166913482203,84.6878305976682
599,1373.58178467059,15.8837374878319,86.4772403675676
600,190.421089625676,5.04399974186604,37.7520022543121
601,1204.97073943955,13.8333190560119,87.1064084158369
602,790.150694961337,11.4901534125108,68.7676366532231
603,1083.42056362943,15.0104870807016,72.1775754380646
604,1039.35736325981,14.9000782581688,69.7551613656791
605,699.591073980053,7.00950383875233,99.8060761608169
606,635.103150356197,9.29540124585154,68.3244470635023
607,1228.3312046364,14.1145668742,87.0257809243631
608,787.869923321634,6.27173370190341,125.622349539892
609,485.792080496192,10.3364056353655,46.9981633493638
610,469.539917738897,9.746844082819,48.1735332738692
611,718.89456610235,11.9765266263652,60.0252968602575
612,246.301311426979,7.05566280354481,34.9083166649114
613,1129.94223342683,12.9862343381924,87.0107687879684
614,1022.32627451459,12.5257608976969,81.6178979356504
615,809.708663900494,11.3520724549169,71.3269464334491
616,697.438607682519,6.70536558038074,104.012018333968
617,1197.24461561026,13.8894619535323,86.1980557357579
618,687.922357513737,9.630281735333,71.4332536077097
619,1163.18878738785,13.1445327420099,88.4922127106349
620,483.72726147557,8.8369136600513,54.7393898010271
621,691.039050680961,8.49753280854995,81.3223162828696
622,1060.45527363896,12.4358148291408,85.2742894783214
623,829.186845320996,11.6197700564032,71.3600046555196
624,623.082918985416,6.11059331566932,101.967662843418
625,185.411126618826,4.7943989526828,38.6724443352957
626,1067.68237278954,12.49271010366,85.4644319711491
627,831.675785680329,7.2532432510426,114.662607732173
628,1021.10184670803,14.3757419864941,71.0295056538537
629,948.257944091708,10.6039132615561,89.4252829782721
630,520.458170342153,6.07702229498605,85.6436170674519
631,1350.03416524413,15.5258785117599,86.9538019521127
632,947.673534642313,13.7931752720361,68.7059734942687
633,691.70739238333,10.08823094182,68.5657769308106
634,1244.82851268428,15.220754286411,81.784942405624
635,588.117229793036,9.00086742474805,65.3400613563085
636,628.303008148543,11.5837230638969,54.2401613611412
637,645.333590863415,6.64509239465113,97.1143142242637
638,535.273235513216,9.29922213659617,57.5610763621509
639,1059.02619837487,14.9005501540377,71.072959550282
640,186.796588030041,4.86431233417357,38.4014379006313
641,1201.03553075966,13.8702294699584,86.5908911861181
642,645.032398916213,9.57818326495303,67.3439190996077
643,1221.92995714235,14.0522309877804,86.9562959934919
644,646.63197032523,7.94033279769976,81.4363814212614
645,781.860362175706,11.4376498432105,68.3584803603534
646,750.451534889,8.04135220224132,93.3240475003484
647,1221.86908164988,14.1565856721358,86.3110011091776
648,214.863474871702,6.26230109273842,34.3106266673845
649,539.598795341489,10.2177233001657,52.8100810219376
650,614.168829833405,6.31504169469777,97.2549128771505
651,458.988628167404,9.67996516848233,47.4163512139338
652,821.63896723908,11.8719604086315,69.2083648326275
653,1144.02233995556,13.225572925577,86.5007774251602
654,673.971344075337,9.90084481538531,68.0721046175804
655,1124.27020602021,15.0726246357007,74.5902079560371
656,843.02688487024,11.2545036348658,74.9057366029536
657,999.578910478347,13.5600010921667,73.7152529475664
658,713.000242574187,12.0066482233272,59.383787157929
659,1200.67169165136,13.878400886627,86.5136914158686
660,696.580426121324,6.16135727408969,113.056327548258
661,1191.60035759226,13.73532920665,86.7544082609496
662,1021.86302922336,12.5371275115815,81.5069503185155
663,286.589693627204,6.72925026379068,42.5886513939465
664,822.662777572089,11.9291984472819,68.9621168771429
665,771.799655220865,8.58235282492848,89.9286793452582
666,939.315204610539,11.2580455972405,83.4350151185014
667,568.141191887983,10.8596310927104,52.3168040458898
668,842.787494589472,12.3662275323842,68.1523522337281
669,635.985171234099,9.29553085921605,68.4183809258782
670,1116.34581408648,15.0934794838477,73.9621248553816
671,510.454282219038,9.9161473625741,51.4770770900011
672,518.090150540254,4.84798307810332,106.867153245705
673,1162.49495229153,13.4863100632872,86.1981481099192
674,1018.37232837763,12.4477116450398,81.8120115100379
675,184.206884561851,4.86427112111343,37.8693703486836
676,763.245320149297,7.26372919347794,105.076235611125
677,1149.83369661697,13.4164234707033,85.7034439266021
678,658.714126920765,9.9301781727316,66.3345728004763
679,749.831736234241,11.0908719812024,67.6080057100205
680,246.728031639254,6.52695433601742,37.8014030644806
681,685.366494014556,9.9959874029211,68.5641614368455
682,475.116569315815,9.42650269539292,50.4022100951631
683,1184.62454049305,13.7506515461686,86.1504297825894
684,769.438729510337,7.37526020752278,104.326994283606
685,1139.44056987355,15.3412124614938,74.2731757827829
686,559.3982097035,6.57301596380957,85.1052565190007
687,668.919915625723,10.1506992800199,65.8988998858817
688,795.073583813363,11.5084527302411,69.0860537424048
689,615.794581609889,12.2617173495164,50.2209082183888
690,661.073178425251,7.91817795396167,83.4880426114317
691,1164.93615155336,13.4822318894171,86.4052896514694
692,831.058130277,12.0627065401493,68.894831148459
693,736.425280665839,6.49847970209948,113.322702297265
694,1023.31218976872,12.5843031721123,81.3165556942757
695,1158.03252705707,15.2295055054076,76.0387477220374
696,514.28870148554,9.28129747481817,55.4112938283573
697,856.225019097665,11.5336029493551,74.2374280489292
698,1016.98754809235,12.5055711530009,81.3227589247934
699,665.588439830414,9.97239513628431,66.743087366112
700,526.391986344262,5.35285830708932,98.3384868691759
701,1165.37448932601,13.5574032993663,85.9585322936053
702,678.216658066484,6.03441965993704,112.391364254829
703,912.726735088656,16.7536166219118,54.4793852985101
704,792.667262489475,5.47920861959291,144.668202567612
705,721.328206250743,12.0791791830949,59.7166575076771
706,1006.81905594603,12.3915983628614,81.2501362990865
707,632.417690190266,9.34202050912892,67.6960288807195
708,483.788170621505,10.9501869629789,44.1808137392656
709,1180.0578098656,13.7285572255609,85.9564330378784
710,1094.1049679917,15.3676364205005,71.1953964847945
711,983.484023434481,13.6133408935611,72.2441339803411
712,839.796815738163,11.5448865083627,72.7418857803274
713,498.163250755859,9.97608723036476,49.9357352489433
714,249.375683499672,7.12039923385834,35.0227108493946
715,648.673776919271,7.26446122115908,89.2941344404027
716,810.439719305663,11.9345457507437,67.9070436556129
717,664.880282833152,10.0297974914759,66.2904992247566
718,1040.49619508955,12.5067346097247,83.1948728072078
719,1142.49809814831,13.2634538580444,86.1388074611783
720,183.427577741298,5.35410391868285,34.2592487047623
721,647.524237020807,9.48317791459763,68.2813549268184
722,767.783152354092,15.4157246589555,49.8051936798222
723,558.192381813456,8.34300113227583,66.9054663859539
724,818.244915678415,12.2020865173458,67.057786757637
725,513.802585053426,8.24561295734112,62.3122365446446
726,748.129377662551,7.30540537197561,102.407647429459
727,930.797796519286,10.758070547087,86.5208861054851
728,684.647624065403,6.53243881740298,104.807353456024
729,219.996001887404,6.89876763679192,31.8891740481504
730,1011.95963548093,14.1637434443221,71.4471876350314
731,794.028616515608,11.6934844179409,67.9035083244611
732,467.282532768426,10.5413996205563,44.3283197287389
733,1069.25759805572,12.3138819711847,86.833510387533
734,931.874988870851,11.7146966276646,79.5475135625961
735,544.254437821785,6.57911621940854,82.724551394338
736,641.717463267959,6.84721712348697,93.7194559037384
737,1165.98758881702,14.3726582659049,81.1253956815349
738,817.687504453665,11.6642610757296,70.1019549498139
739,1072.7956761926,12.5500899317185,85.4811146397657
740,953.010948098821,9.80616027861587,97.1849246821955
741,849.048333348047,7.04443345838671,120.527553899628
742,638.561325896524,11.7403634326359,54.3902520190684
743,1101.80914542846,12.6688629024213,86.9698530890153
744,470.074441260341,9.60844842486718,48.9230331968857
745,1160.7361991702,15.0399324913235,77.1769554045421
746,963.431883446816,11.6698635341995,82.557253615126
747,866.168298826463,11.9108658142374,72.7208510561095
748,283.192328350644,6.99777269574747,40.4689235651709
749,671.166116811921,9.36767459394191,71.6470357804662
750,243.898551471721,5.16376699889754,47.2326794612911
751,1039.24436450975,11.8735873103561,87.5257272587976
752,698.067699980212,11.7439781437674,59.4404801707399
753,619.866164920823,8.94502909790454,69.2972776428455
754,579.504392641967,8.43386457506785,68.71160752985
755,1154.57758197929,14.7227889787993,78.4211186917012
756,520.387945916268,5.92915909710971,87.7675800890454
757,1101.42467261315,12.9027831382233,85.3633406695246
758,1068.15167862711,12.6774634176116,84.2559464335137
759,736.558970969195,7.74946966493633,95.0463712764589
760,841.498250114011,6.77387541283044,124.227004311317
761,1088.83706609367,12.5130781499799,87.0159247023818
762,614.669904182212,8.8314965952875,69.5997442279716
763,703.795711843656,9.59366796188559,73.3604409324719
764,898.560993838497,12.3903029527267,72.5213093874151
765,250.019721989229,6.70587832709485,37.2836651358605
766,1076.33731223984,12.7257417083584,84.5795346869951
767,578.379875701866,10.7292003975629,53.9070810750485
768,261.407844067136,4.7184385213743,55.4013457805949
769,1058.46047755996,12.2124361511469,86.6707071758619
770,828.635444204477,6.6411285157492,124.773288491466
771,258.596043228279,4.50864833802765,57.3555584380315
772,830.785979683635,12.1698673881974,68.2658202577743
773,1081.6329280676,12.6619858403694,85.4236406282411
774,737.43211989366,12.2982339197373,59.9624405184035
775,504.162201253966,8.52910332122512,59.1108094562921
776,750.254809125945,10.5382561854857,71.1934494588646
777,988.268425641431,11.0923022716663,89.0949778898305
778,953.815990154617,11.7455227842953,81.2067719480264
779,868.741963483235,14.9970331275942,57.9275884831362
780,715.504137445214,5.91340852723769,120.996906293475
781,1148.47685489369,15.2507520666055,75.3062439070471
782,657.222686080398,8.48056807240127,77.4974837144731
783,494.965452359725,9.33465604669027,53.0244981586891
784,557.261352455066,6.48964486203824,85.8693140074298
785,1102.54097434532,14.5966380448416,75.5338983509946
786,1166.32732004847,15.462439422886,75.4297099021897
787,1074.62700041157,12.1119445075925,88.7245643949184
788,854.61724157712,12.1195255219885,70.5157343021876
789,1351.62926970938,15.6313566227854,86.4690955703196
790,1047.1671153504,13.8854251449894,75.4148399790457
791,694.924970297679,10.0025129343851,69.4750384084757
792,828.658324291027,6.66632755694806,124.305071602332
793,583.586339299211,10.4698234527638,55.7398452736238
794,956.992678411413,11.6828737413573,81.9141505418879
795,630.877350374125,12.0692788351587,52.2713377485598
796,840.838421331531,12.0248152669618,69.9252672630852
797,1063.22014224949,12.30747225869,86.3881810904574
798,796.297391599454,6.81843950460076,116.785870295124
799,715.927689486895,12.0955555206104,59.1893186110367
800,261.285513892916,4.91297383766651,53.1827610987273
801,840.624134476516,11.6771365494834,71.9888930744503
802,873.391146435482,10.4420189462717,83.6419806293612
803,1031.80263140242,13.8283780093946,74.6148702835172
804,1154.10913902807,14.5350330376664,79.4018930701626
805,694.861207698147,9.12641869231584,76.137336136375
806,564.497626576878,9.34272991767625,60.4210580366731
807,1383.46235940519,15.9544062890717,86.7134968446186
808,673.43442131044,9.87093363123758,68.2239843229507
809,948.197174728681,11.1787327974004,84.8215260095658
810,208.623502843133,5.87867139309168,35.4882062447472
811,1057.66977184788,11.4024594819027,92.758038169445
812,593.651575758216,8.88640924298126,66.8044380498343
813,1396.12970397736,16.1702470049339,86.3394172984102
814,977.665387314612,10.2202827071039,95.6593291333373
815,944.894761745995,12.7459631263808,74.1328648433251
816,252.951492564745,6.67770871232343,37.8799830094316
817,784.156766770674,14.6060092617052,53.6872702680407
818,869.600167578196,10.7097773855746,81.1968481015763
819,710.005098724058,6.41370137998555,110.701302829546
820,867.109088620376,10.2892825674092,84.273036816668
821,996.9140740984,11.4019209494011,87.4338700051031
822,1126.36882497793,14.9074851831996,75.5572661073189
823,1003.32995882055,11.3542443975168,88.3660703163988
824,651.138598600569,9.73562967947112,66.8820220199606
825,844.515428048511,5.98701752035412,141.057784644425
826,576.106357758339,10.4385777074411,55.1901201394195
827,992.109951666725,11.2492691963588,88.1932803232991
828,644.278867143651,8.00804711636673,80.4539306252186
829,995.569189170372,11.3039144142068,88.0729588609707
830,888.341440629926,12.0606914462078,73.6559296448337
831,1359.79569761804,15.964247161231,85.1775648350205
832,717.403415146655,5.95653090350461,120.439804102176
833,282.673947745812,7.68724451446241,36.7718168992808
834,1172.80276287497,15.8512651413568,73.9879594730307
835,917.107055683623,12.1568748888935,75.4393759963337
836,816.923640135252,7.43174959813622,109.923461406736
837,464.807691998318,9.60299576582338,48.4023635262391
838,871.791737168063,10.7372566861238,81.1931541410119
839,1022.18824326786,11.5441856515216,88.5457211209283
840,517.664181967137,5.47770545575217,94.5038367157064
841,614.596857512926,11.6802574030262,52.6184343637574
842,866.811056971428,10.6713454621491,81.2279070194082
843,1385.64909866304,16.0484533853773,86.3415972485914
844,721.138910002951,10.2552095132917,70.3192761755173
845,766.459058456285,7.32088202522909,104.694906408125
846,704.343411540687,12.8386227793636,54.8612903147856
847,853.05006857076,7.40271906561222,115.234694307586
848,627.915550526086,12.0639301227306,52.0490042745674
849,1361.37466659606,15.7736340505921,86.3069767074351
850,264.582605698173,6.23665161349066,42.4238232460905
851,938.370400044133,14.331297257542,65.4770034548204
852,1126.48315768714,15.3155893680612,73.5514076941947
853,979.827315102371,11.1496633571678,87.8795425220145
854,505.472876614513,9.94057161638609,50.8494778893086
855,791.750397920969,7.07984674298352,111.831573007655
856,676.154932193,9.76865871148008,69.2167627269428
857,980.277431315768,11.1498515624586,87.9184288530217
858,734.001552531788,6.91946640133497,106.077768133996
859,976.72574024949,11.1102952281821,87.9117719367122
860,846.300973131295,10.6339697930105,79.5846696581322
861,838.113161688194,12.1445307858543,69.0115720785534
862,854.539016707292,10.5584234941992,80.9343380834057
863,961.92479533997,11.0177018279285,87.3072089227912
864,265.61340634876,4.53458498052921,58.5750200931864
865,894.324214970059,12.0540649219517,74.1927491481649
866,814.037656409623,10.0381801190468,81.094147221471
867,354.813887078032,7.72505270712298,45.9302868899357
868,537.911300179912,9.11912149544414,58.9871842861891
869,1027.66604448814,13.6348317833011,75.3706434242003
870,563.239265660982,8.85505508275784,63.6065230986192
871,1155.46921480469,13.9757498558867,82.6767240913371
872,679.536842775566,10.1246947295951,67.11677348545
873,796.368567195073,10.9719786350165,72.5820377241258
874,677.264357933236,13.1616190103945,51.457526418168
875,547.431218112839,5.18609286115114,105.557542598905
876,1031.71986009956,14.0127017072554,73.6274761037243
877,930.584545334349,10.5707124202295,88.0342315957305
878,843.986776560976,9.98868230958452,84.4943056954708
879,1293.52419141863,14.9290023694229,86.6450523223168
880,782.904081094442,6.32162269143334,123.845430091135
881,934.64249263278,10.5731451924578,88.3977733796272
882,623.226757624836,6.02597103649176,103.423457207267
883,970.418087129436,10.7009556814745,90.6851795311542
884,303.442999442797,6.3199351712473,48.0136253332659
885,577.747766711815,10.347002428363,55.8372118603262
886,846.511407749841,9.71042043598409,87.1755670447499
887,926.231749745451,10.4878600119323,88.3146560586865
888,993.086757584895,10.2961883342191,96.4518834882228
889,658.641755700138,9.41778067144426,69.935983718246
890,872.453537277444,11.8664057541292,73.5229820515663
891,797.358096929358,6.22655551264047,128.057654880078
892,666.490000569727,9.46788510460955,70.394812907609
893,721.157101755568,13.2415928434212,54.4615070319022
894,1122.95075245574,14.8140878555889,75.8028954197194
895,872.8020371521,11.7249774621278,74.4395492418889
896,540.599731505117,4.89819861233345,110.367050071002
897,706.755078699019,7.19602598129884,98.2146368753735
898,830.819157805731,9.538237199382,87.1040571165038
899,566.615005602821,10.9376843144555,51.8039275328113
900,271.187799297243,5.00800334410658,54.1508822306153
901,640.227831174316,11.1334131856856,57.5050813705059
902,868.025803785126,10.1954752233314,85.1383368377698
903,819.601359106328,12.2677854668567,66.8092347490592
904,643.576442058412,9.52283986859675,67.5824072376476
905,909.228848969586,11.9603536511526,76.0202311310391
906,1100.01551637581,13.9952655622476,78.5991170716411
907,807.99126506455,9.12432721766708,88.5535169650719
908,711.79127060755,10.1478317070558,70.1422029015952
909,669.293105264384,9.21853211111954,72.6030019960631
910,750.572267105405,6.59469089312305,113.814624410691
911,805.286978853394,9.11822569242237,88.3161928666254
912,796.653528995929,6.7968917341397,117.208506499297
913,906.049765633183,12.0587405277248,75.1363513917594
914,860.082070314086,10.1377241848454,84.8397583749421
915,528.897388614536,9.7995074691312,53.971833817218
916,725.916567325999,10.2365172475791,70.9144086576591
917,1171.23104351,14.5841705960142,80.3083751523105
918,271.115300648325,7.43354897075526,36.4718523702386
919,818.176466723655,9.19452215421848,88.9852080402322
920,706.895049202311,7.33150007179799,96.4188832134801
921,1129.85449184923,12.9119047393347,87.5048658318592
922,830.569449354848,9.79270081696203,84.8151561943167
923,1161.48155942179,15.8823349980177,73.130403027436
924,799.323463012984,6.72851806477515,118.796361296489
925,1026.06950758535,9.10148589413996,112.736482758929
926,867.636345570733,10.1714771254083,85.3009189199653
927,677.359690770258,9.34576719928527,72.47769779907
928,574.472527508353,7.79087332752137,73.736602221348
929,813.483449106188,9.28153116750552,87.6453932465561
930,531.893023362667,8.97655797494397,59.2535607576229
931,817.296013892808,8.58923766356211,95.1534985881228
932,713.33088051632,10.1348763014824,70.3837776897175
933,1128.85728471138,12.7480595858727,88.5513028164983
934,865.10116525594,10.0999867913503,85.653692735204
935,322.616153216964,7.04365980455733,45.8023473831357
936,720.972783584823,6.40657940074032,112.536306582185
937,778.06898147789,8.77099873569743,88.7092798578567
938,1225.72719274588,14.4865450945838,84.6114228577628
939,1168.23272198486,12.7923664230819,91.3226437820726
940,765.901421943323,11.0681493416525,69.1986888052752
941,873.780025960545,9.81362196282308,89.0374653996949
942,1112.44187725866,13.9940118115527,79.4941359375079
943,882.998832097523,14.7129395153593,60.0151201040235
944,575.434546744269,10.5362494283594,54.6147422436136
945,561.337326365201,6.2085486720141,90.413614520815
946,860.873094722788,11.425130482909,75.3490820967499
947,916.186682340258,10.2566081422312,89.3264780749394
948,1053.07552206902,14.0106655193398,75.1624197020044
949,1059.71160884098,14.0242522164272,75.5627888380166
950,885.428522146107,6.59681216332454,134.220666016339
951,1346.16794720647,15.1988767095621,88.5702261378009
952,276.925778486357,6.79832333641828,40.7344230014597
953,906.203977861731,10.2477904756026,88.4292062780919
954,612.51743960058,11.1308739358648,55.0286925474006
955,910.89966686315,11.9625574007379,76.1458972649912
956,697.293608862074,9.27926542620186,75.1453457612201
957,574.775710556546,8.70395072340958,66.0361861896422
958,856.841283734152,10.0915605073085,84.906718154602
959,1216.39447043105,15.5474109326009,78.237751333917
960,265.643639706113,4.8565969423728,54.6974852676012
961,574.173781708331,11.2096067795789,51.2215810062428
962,1030.97988591845,9.55824006444676,107.862941186561
963,655.361295957022,9.07116482269692,72.2466528573316
964,591.623032423643,8.48659674404501,69.7126363213595
965,921.532980372998,12.3337001236151,74.7166682452864
966,679.377025302583,7.54431012905152,90.0515771066261
967,758.56647143844,8.69041247485664,87.2877407871199
968,836.087844217789,7.41844479905353,112.703924726172
969,861.816646050012,8.4019538180492,102.573361472024
970,837.305406645717,11.3204901504305,73.9637061222015
971,773.056494583846,8.78607098496203,87.9865978668947
972,269.738705701556,6.62704775769219,40.7026953123225
973,1200.69158015954,15.5310222030823,77.3092436839892
974,780.18977261685,9.25097677369179,84.3359346480664
975,733.226488871681,6.39866736780117,114.59049935325
976,555.196730673397,10.1336700764893,54.7873304027811
977,857.108003346016,9.76860615050955,87.741074841195
978,952.428525591511,12.8190793171529,74.2977324679696
979,895.483515207574,11.7669703936674,76.1014505220047
980,691.721941873944,5.99011683327064,115.477203721962
981,726.616137700927,9.85560450821527,73.7261866682299
982,764.194888551527,8.87956745308178,86.0621750540678
983,915.523888569179,9.72038642794998,94.1859560167983
984,892.514888148552,10.4025671703356,85.7975606919112
985,1005.63589199243,12.1204429089736,82.970226380745
986,568.845855194287,9.3629118835911,60.7552289572663
987,745.562092716827,12.5703197600168,59.311306868126
988,1041.59114555383,6.55792929580222,158.829273475174
989,881.607367727917,13.9829244800238,63.0488542641703
990,794.837361604731,6.34580409233602,125.254002493502
991,865.27837268516,9.35182941580521,92.5250380661116
992,557.587178042882,7.93313035997205,70.2858963286778
993,1162.79627857404,12.4465651098103,93.4230663894191
994,1185.59999212125,15.1382818275886,78.3180023746531
995,942.413740908592,11.4352236014123,82.413232461165
996,934.298073132544,12.0010276283553,77.8515058931323
997,870.93256880831,9.42148193326358,92.4411440766432
998,812.641234560375,9.05903094941152,89.7050952909223
999,1002.54718922372,9.70188775425279,103.335269858616
1000,291.449573656779,5.22615687877689,55.7674751097385
1001,776.653452684421,6.72189965334394,115.540768642397
1002,951.175605458871,11.791863510869,80.6637224542279
1003,593.159494315019,9.81836586458936,60.413260464686
1004,728.070226435854,10.0195470168033,72.6649842767185
1005,1206.14720083557,13.2166752612423,91.2595018788552
1006,878.910059385352,9.35162039944264,93.9847878596243
1007,682.884348313215,11.4224020729859,59.7846533460981
1008,559.048888273261,5.77622376242654,96.7844929951967
1009,772.817533157271,8.26669685534572,93.4856505180207
1010,730.999061202589,9.23020994799408,79.1963633894862
1011,1131.82282383852,12.0698343957016,93.7728544346547
1012,709.310865376529,7.23650343447523,98.0184521156061
1013,806.677018536328,8.65826127210312,93.168477271001
1014,812.985332707849,7.26580460622784,111.891989499828
1015,613.07278843776,9.37687921441921,65.381325110279
1016,668.043216728699,9.25519473607615,72.1803523079542
1017,741.805247009802,9.64170168107456,76.9371705894896
1018,846.833273326224,9.46636440946155,89.4570752505388
1019,909.122842257941,9.82310144907675,92.5494709558748
1020,295.142025029424,6.2784343699835,47.0088572463966
1021,930.461123973853,9.97609491181568,93.2690729387323
1022,1030.02961536967,13.3379463215539,77.2255031275064
1023,559.605990143784,8.63626714021527,64.7972070639115
1024,319.068029697597,4.77922713782392,66.7614282594811
It appears that the empirical optimisation approach we’ve taken here has been quite successful. The “pre-release-3” tab above shows that for most input sizes in the range that we’re benchmarking, our code is around 10 times slower than FFTW, and never more than 20 times slower. In the previous article, we saw that, for the pre-release-2
code version, most input lengths were between 40 and 100 times slower than FFTW. The “Speed-up” tab also shows that we’ve significantly increased the range of input lengths getting 50-fold or better speedups compared to the original unoptimised code.
Most of the remaining slower cases can be put down to our implementation of Rader’s algorithm. When the input length $N$ is not of the form $2^m+1$, allocation is required of a zero-padded vector is required for the convolution in Rader’s algorithm. It ought to be possible to avoid this allocation and speed up the code a little, which ought to help with some of the slower cases (most of which are either prime lengths, or involve a comparatively large prime factor).
In the next (and penultimate) article in this series, we’ll clear up this issue a little, play with some compiler flags and catalogue the remaining opportunities for optimisation.