Haskell FFT 12: Optimisation Part 2

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:

1. We could have a specialised straight line transform for $N=16$ say, which would make the $16 \times 16$ factorisation more attractive;

2. 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;

3. 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”);

4. 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:

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:

1. Try the largest few base transforms that are available;

2. 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$:

1. Find the largest index $k$ such that $a_k < a_{k+1}$. If no such index exists, the permutation is the last permutation.

2. Find the largest index $l$ such that $a_k < a_l$.

3. Swap the value of $a_k$ with that of $a_l$.

4. 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:

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):

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:

1. 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).

2. 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).

3. Limit the number of generated plans to around 50 so that the benchmarking step doesn’t take too long.

4. 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.