👨💻 about me home CV/Resume 🖊️ Contact Github LinkedIn I’m a Haskeller 📝 Blog Freedom, privacy, tutorials… 🏆 Best of Fizzbuzz makex LuaX Calculadoira panda upp Haskell todo pwd TPG Nextcloud Git
11 June 2022
This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version.
This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
You should have received a copy of the GNU General Public License along with this program. If not, see http://www.gnu.org/licenses/.
The Fibonacci sequence is a classical hello-world application for functional programming. The challenge here is to get a fast implementation. We will first show two classical implementations: the trivial recursive definition that is very slow and the iterative version that is slightly faster.
And a third one that is blazing fast.
The Fibonacci sequence is defined recursively:
\[ \begin{align} F_0 &= 1 \\ F_1 &= 1 \\ F_n &= F_{n-1} + F_{n-2} \end{align} \]
\(n\) | \(F_n\) | \(F_n = F_{n-1} + F_{n-2}\) |
---|---|---|
0 | 1 | |
1 | 1 | |
2 | 2 | \(F_{2} = F_{1} + F_{0}\) |
3 | 3 | \(F_{3} = F_{2} + F_{1}\) |
4 | 5 | \(F_{4} = F_{3} + F_{2}\) |
5 | 8 | \(F_{5} = F_{4} + F_{3}\) |
6 | 13 | \(F_{6} = F_{5} + F_{4}\) |
7 | 21 | \(F_{7} = F_{6} + F_{5}\) |
8 | 34 | \(F_{8} = F_{7} + F_{6}\) |
9 | 55 | \(F_{9} = F_{8} + F_{7}\) |
10 | 89 | \(F_{10} = F_{9} + F_{8}\) |
A trivial implementation of this sequence in Haskell is:
recursiveFib :: Int -> Integer
0 = 1
recursiveFib 1 = 1
recursiveFib = recursiveFib (n-1) + recursiveFib (n-2) recursiveFib n
The objective here is to compare implementations for large values of
\(n\). For such values \(F_n\) can not be coded by machine integers.
\(F_n\) can be an arbitrary large
integer (Integer
type
in Haskell).
This function is very simple but also very slow. Its complexity is \(\mathcal{O}(F_n)\) and \(F_n\) increases very fast since \(F_n \sim \frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^n\).
\(F_n\) can also be constructed iteratively from \(F_0\) to \(F_n\):
\[ \begin{align} F_0 &= 1 \\ F_1 &= 1 \\ F_2 &= F_1 + F_0 \\ F_3 &= F_2 + F_1 \\ ... \\ F_n &= F_{n-1} + F_{n-2} \\ \end{align} \]
iterativeFib :: Int -> Integer
= loop n 1 1
iterativeFib n where
0 a b = b
loop = loop (n-1) (a+b) a loop n a b
This function is faster since it avoids computing Fibonacci terms several times. Its complexity is \(\mathcal{O}(n)\).
We can exploit some properties of the Fibonacci sequence to improve its computation.
Let’s try to apply the definition several times to compute several steps at once:
\[ \begin{align} F_n &= F_{n-1} &+ F_{n-2} \\ &= F_{n-2} + F_{n-3} &+ F_{n-2} \\ &= 2 F_{n-2} &+ F_{n-3} \\ &= 2 \left( F_{n-3} + F_{n-4} \right) &+ F_{n-3} \\ &= 3 F_{n-3} &+ 2 F_{n-4} \\ &= 3 \left( F_{n-4} + F_{n-5} \right) &+ 2 F_{n-4} \\ &= 5 F_{n-4} &+ 3 F_{n-5} \\ \end{align} \]
The coefficients seem to be Fibonacci numbers.
Let’s prove by induction (over \(k\)) that:
\[ F_n = F_k F_{n-k} + F_{k-1} F_{n-k-1} \]
The property is obviously true for \(k = 1\):
\[ \begin{align} F_n &= F_1 F_{n-1} &+ F_{1-1} F_{n-1-1} \\ &= F_1 F_{n-1} &+ F_0 F_{n-2 } \\ &= 1 F_{n-1} &+ 1 F_{n-2 } \\ &= F_{n-1} &+ F_{n-2 } \\ \end{align} \]
Lets prove that \(F_n = F_k F_{n-k} + F_{k-1} F_{n-k-1} \implies F_n = F_{k+1} F_{n-k-1} + F_k F_{n-k-2}\).
\[ \begin{align} F_{k+1} F_{n-k-1} + F_k F_{n-k-2} &= \left( F_k + F_{k-1} \right) F_{n-k-1} + F_k F_{n-k-2} \\ &= F_k \left( F_{n-k-1} + F_{n-k-2} \right) + F_{k-1} F_{n-k-1} \\ &= F_k F_{n-k} + F_{k-1} F_{n-k-1} \\ \end{align} \]
The Fibonacci sequence can then be defined by:
\[ \begin{align} F_0 &= 1 \\ F_1 &= 1 \\ F_n &= F_k F_{n-k} + F_{k-1} F_{n-k-1}, \forall n \ge 2, \forall k \in [1, n-1] \end{align} \]
The trivial implementation is slow because of the double recursivity. We now have four recursions but:
Intuitively if \(k\) is close to \(n-k\) then subtrees will be close too. If \(k = n-k\) (i.e. \(k = \frac{n}{2}\)) then the first term of \(F_n\) is a square (\(F_k = F_{n-k}\)).
First case: n is even (\(n = 2k\))
\[ \begin{align} F_n &= F_k F_{n-k} &+ F_{k-1} F_{n-k-1} \\ &= F_k F_k &+ F_{k-1} F_{k-1} &&(n-k-1 = 2k-k-1 = k-1) \\ &= F_k^2 &+ F_{k-1}^2 \\ \end{align} \]
Second case: n is odd (\(n = 2k+1\))
\[ \begin{align} F_n &= F_k F_{n-k} &+ F_{k-1} F_{n-k-1} \\ &= F_k F_{k+1} &+ F_{k-1} F_{n-k-1} && (n-k = 2k+1-k = k+1) \\ &= F_k F_{k+1} &+ F_{k-1} F_{k} && (n-k-1 = k) \\ &= F_k \left( F_k + F_{k-1} \right) &+ F_{k-1} F_{k} \\ &= F_k^2 + 2 F_k F_{k-1} \\ &= F_k \left(F_k + 2 F_{k-1} \right) \\ \end{align} \]
This definition can be easily implemented in Haskell:
fastFib :: Int -> Integer
0 = 1
fastFib 1 = 1
fastFib =
fastFib n case r of
0 -> fk^2 + fk1^2
1 -> fk * (fk + 2*fk1)
where
= n `divMod` 2
(k, r) = fastFib k
fk = fastFib (pred k) fk1
This function is way faster than the previous ones and can deal with very large numbers. Its complexity is \(\mathcal{O}(F_{\log_2 n})\) (I have no proof yet, just an intuition because the depth of the tree is divided by two every steps and there is still a double recursion).
The three functions shall return the same values:
= [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597]
fibs
testFib :: String -> (Int -> Integer) -> IO ()
= do
testFib name f zip3 [0..] fibs (map f [0..])) $ \(i, ref, fi) ->
forM_ (/= ref) $
when (fi error ("ERROR: "++name++" "++show i++" = "++show fi++" (should be "++show ref++")")
putStrLn $ " - "++name++": OK"
= do
unitTests putStrLn "* Unit tests:"
putStrLn ""
"recursiveFib" recursiveFib
testFib "iterativeFib" iterativeFib
testFib "fastFib" fastFib
testFib putStrLn ""
Lets compare the performances of the three function:
= do
perfTests putStrLn "* Performance tests:"
putStrLn ""
putStrLn " n | recursiveFib | iterativeFib | fastFib "
putStrLn " ---:|-------------:|-------------:|--------:"
20..40] $ \i -> do
forM_ [<- fmtTime <$> profile recursiveFib i
t1 <- fmtTime <$> profile iterativeFib i
t2 <- fmtTime <$> profile fastFib i
t3 putStrLn $ show i++" | "++t1++" | "++t2++" | "++t3
20000, 40000 .. 300000] $ \i -> do
forM_ [let t1 = ""
<- fmtTime <$> profile iterativeFib i
t2 <- fmtTime <$> profile fastFib i
t3 putStrLn $ show i++" | "++t1++" | "++t2++" | "++t3
2500000, 5000000 .. 40000000] $ \i -> do
forM_ [let t1 = ""
let t2 = ""
<- fmtTime <$> profile fastFib i
t3 putStrLn $ show i++" | "++t1++" | "++t2++" | "++t3
putStrLn ""
profile :: (Int -> Integer) -> Int -> IO (Double, Integer)
= timeItT $ do
profile f n let fn = f n
`deepseq` (return ())
fn return fn
fmtTime :: (Double, Integer) -> String
| t < 1e-6 = show (round (t*1e9)) ++ " ns"
fmtTime (t, f) | t < 1e-3 = show (round (t*1e6)) ++ " µs"
fmtTime (t, f) | t < 1e-0 = show (round (t*1e3)) ++ " ms"
fmtTime (t, f) = show (round t) ++ " s" fmtTime (t, f)
= do
largeFibValue let n = 100*1000
let fn = fastFib n
let fn' = fmt fn
let nbDigits = length (filter (/=' ') fn')
putStr "* Large number example: "
putStrLn $ "fastFib "++fmt (fromIntegral n)++" = "++fn'++" ("++fmt (fromIntegral nbDigits)++" digits)"
fmt :: Integer -> String
= intercalate " " . reverse . map reverse . chunksOf 3 . reverse . show fmt
Tests made on a Intel(R) Core(TM) i7-9700 CPU @ 3.00GHz
powered by Fedora Linux 37
and
The Glorious Glasgow Haskell Compilation System, version 9.2.5
.
Unit tests:
Performance tests:
n | recursiveFib | iterativeFib | fastFib |
---|---|---|---|
20 | 113 µs | 397 ns | 650 ns |
21 | 186 µs | 370 ns | 679 ns |
22 | 347 µs | 471 ns | 1 µs |
23 | 513 µs | 410 ns | 631 ns |
24 | 816 µs | 2 µs | 733 ns |
25 | 1 ms | 488 ns | 967 ns |
26 | 2 ms | 613 ns | 1 µs |
27 | 3 ms | 549 ns | 1 µs |
28 | 4 ms | 857 ns | 995 ns |
29 | 6 ms | 538 ns | 877 ns |
30 | 10 ms | 632 ns | 1 µs |
31 | 16 ms | 774 ns | 993 ns |
32 | 26 ms | 5 µs | 1 µs |
33 | 42 ms | 1 µs | 1 µs |
34 | 68 ms | 682 ns | 1 µs |
35 | 112 ms | 883 ns | 1 µs |
36 | 178 ms | 922 ns | 1 µs |
37 | 288 ms | 861 ns | 1 µs |
38 | 461 ms | 760 ns | 2 µs |
39 | 752 ms | 746 ns | 2 µs |
40 | 1 s | 759 ns | 2 µs |
20000 | 4 ms | 517 µs | |
40000 | 26 ms | 789 µs | |
60000 | 56 ms | 1 ms | |
80000 | 113 ms | 2 ms | |
100000 | 148 ms | 2 ms | |
120000 | 182 ms | 3 ms | |
140000 | 215 ms | 3 ms | |
160000 | 269 ms | 3 ms | |
180000 | 309 ms | 4 ms | |
200000 | 421 ms | 4 ms | |
220000 | 506 ms | 5 ms | |
240000 | 600 ms | 5 ms | |
260000 | 736 ms | 6 ms | |
280000 | 864 ms | 6 ms | |
300000 | 1 s | 7 ms | |
2500000 | 63 ms | ||
5000000 | 131 ms | ||
7500000 | 206 ms | ||
10000000 | 286 ms | ||
12500000 | 376 ms | ||
15000000 | 433 ms | ||
17500000 | 516 ms | ||
20000000 | 584 ms | ||
22500000 | 658 ms | ||
25000000 | 785 ms | ||
27500000 | 854 ms | ||
30000000 | 930 ms | ||
32500000 | 1 s | ||
35000000 | 1 s | ||
37500000 | 1 s | ||
40000000 | 1 s |
Large number example: fastFib 100 000 = 4 202 692 702 995 154 386 319 005 101 293 915 131 773 915 702 632 234 503 304 716 087 198 335 731 457 276 226 633 938 477 267 013 660 962 533 661 702 858 329 186 641 162 298 822 215 333 733 574 147 268 614 522 205 177 960 360 216 576 292 096 795 530 656 502 537 998 314 495 026 330 500 620 719 088 898 984 643 619 599 926 476 236 108 318 505 023 749 864 703 859 491 024 686 621 241 730 682 736 115 723 551 647 724 257 547 502 352 412 468 746 074 851 053 353 923 438 703 547 870 019 701 586 274 514 903 943 581 778 012 410 826 464 461 823 272 924 826 749 362 282 954 004 235 923 662 667 858 166 740 323 769 532 233 540 810 434 266 661 679 738 865 959 304 652 017 245 761 094 495 566 071 167 054 301 690 895 714 604 884 013 679 491 394 566 493 844 646 298 912 078 940 644 595 782 507 997 928 878 739 392 985 610 180 101 343 882 600 283 820 398 139 200 927 163 512 122 969 924 839 839 463 533 622 369 599 880 593 624 548 314 955 919 982 731 440 664 606 860 389 674 767 846 630 714 238 798 520 061 220 948 360 195 842 828 694 894 114 956 887 994 407 533 188 621 624 706 043 127 847 588 617 179 645 038 305 434 988 777 154 546 903 665 027 721 615 391 983 839 969 917 881 343 981 419 443 688 092 501 114 818 197 984 022 611 661 046 073 180 322 923 553 766 037 586 498 499 974 540 204 693 791 793 047 963 222 486 139 060 147 413 637 230 339 253 443 256 608 485 701 564 784 891 053 397 926 289 664 177 821 919 706 286 664 135 844 377 802 876 352 562 122 389 353 466 102 826 235 289 263 234 488 363 199 404 159 286 560 829 728 598 821 205 147 493 568 392 160 744 064 818 153 706 709 889 719 108 606 083 648 795 534 004 972 817 295 465 584 196 082 602 156 304 071 901 493 325 048 737 897 039 612 705 399 999 458 459 884 586 324 576 356 850 465 902 800 682 163 360 223 018 811 383 011 208 727 253 121 314 804 106 183 630 746 333 917 234 788 155 584 199 422 004 369 734 794 567 464 293 731 590 299 016 321 476 910 276 047 953 145 737 133 530 620 933 370 013 274 962 876 666 024 092 378 144 462 247 911 861 242 773 628 847 211 726 253 860 103 658 427 961 076 487 163 331 347 200 528 488 644 744 897 867 222 184 279 861 410 512 996 912 357 518 380 420 226 522 996 351 489 992 015 929 613 369 585 992 284 921 472 840 596 751 824 858 206 083 370 375 175 870 696 347 451 742 484 480 895 089 618 955 310 799 475 473 330 332 388 074 551 229 896 105 111 703 918 074 819 309 463 129 676 526 583 523 254 006 198 015 481 044 159 254 418 528 609 134 434 118 408 385 912 583 154 979 720 111 735 082 542 883 519 942 050 207 089 706 291 319 323 705 936 118 699 708 767 405 215 366 496 845 718 246 640 603 638 302 177 053 284 851 442 532 497 454 630 999 497 577 583 104 521 012 195 115 814 606 785 903 295 807 850 171 689 359 081 326 188 293 931 649 613 908 497 264 994 236 206 250 488 864 434 829 436 295 195 232 851 838 550 923 528 889 484 987 751 381 022 320 088 255 160 033 641 645 914 092 823 188 828 485 453 780 754 751 793 048 907 600 025 512 141 470 637 066 402 501 872 547 952 277 141 425 050 621 431 726 133 512 376 491 993 264 368 219 026 824 677 798 278 050 012 296 677 681 338 164 667 973 991 346 578 705 512 745 343 946 944 045 970 777 191 879 954 073 954 276 059 158 130 792 852 127 416 568 328 282 956 215 993 174 690 589 582 184 622 213 311 123 743 528 370 969 527 697 376 659 264 209 701 430 460 262 628 089 511 749 784 920 754 475 292 453 555 824 485 037 081 169 662 961 361 437 456 685 569 229 108 353 804 447 871 639 780 202 320 840 236 093 709 222 541 404 770 096 912 820 491 605 767 773 669 730 366 536 498 834 923 648 247 283 567 638 754 132 943 595 918 097 552 972 633 716 970 745 724 835 609 042 802 322 527 268 722 270 064 679 384 555 006 784 008 088 065 427 716 480 324 882 491 803 961 614 497 071 569 285 030 997 191 355 977 454 006 784 666 563 982 465 863 641 444 396 717 248 234 018 026 243 961 781 706 483 360 371 717 605 953 991 771 045 496 130 564 628 772 749 130 877 955 433 893 243 191 369 395 281 413 812 395 013 590 807 898 227 658 488 263 250 802 618 524 850 762 756 185 439 484 575 939 335 126 157 545 942 937 679 620 715 509 540 065 149 312 865 564 443 708 655 439 771 673 542 181 054 558 453 697 618 966 155 551 804 171 330 106 742 714 737 433 118 616 111 666 800 134 742 357 715 495 644 208 822 055 262 531 207 630 247 540 274 901 297 665 161 330 833 084 658 587 180 009 012 735 858 860 387 323 290 477 368 590 430 709 381 480 698 925 172 403 629 520 614 399 575 937 151 757 870 535 045 340 264 867 187 154 085 515 769 299 670 425 865 012 093 497 499 458 084 071 483 820 091 588 806 573 538 923 913 704 024 350 619 657 151 098 348 052 986 098 255 110 975 492 885 336 115 545 257 393 042 442 696 791 158 576 341 900 753 200 960 006 019 671 663 122 779 964 553 274 124 613 827 002 842 207 651 443 127 215 907 411 334 080 034 890 407 625 849 192 846 588 580 412 869 163 865 154 796 429 776 325 124 265 243 357 090 373 279 994 090 608 028 914 324 200 216 278 403 137 569 688 793 319 327 179 281 513 651 857 484 816 495 100 553 151 506 872 893 457 040 698 364 864 908 926 339 042 055 054 701 374 510 871 324 934 497 999 408 637 497 701 279 716 028 106 056 465 342 577 613 367 511 844 757 858 239 618 765 128 089 472 486 851 278 975 083 193 508 109 837 771 994 103 670 102 484 129 663 885 788 768 053 596 123 033 251 579 123 980 971 589 651 437 698 106 274 532 939 294 318 318 049 638 382 537 268 302 829 198 532 880 152 940 714 337 232 086 321 104 061 644 358 354 382 664 864 917 218 438 210 293 517 424 553 745 505 758 090 753 355 882 025 205 602 453 784 317 543 553 853 199 425 081 002 171 431 279 765 462 841 928 691 038 739 447 760 277 789 370 517 385 306 279 744 047 722 489 086 714 748 028 855 582 994 177 874 607 142 469 064 610 509 456 252 022 128 258 329 950 255 642 602 299 905 929 046 841 595 791 167 921 512 858 860 328 296 849 951 271 553 446 508 878 296 327 611 803 906 735 633 266 224 123 093 687 573 746 634 252 135 170 679 694 981 289 617 944 100 773 168 818 654 945 023 743 438 512 318 640 838 968 116 604 957 523 873 700 674 044 602 618 648 483 425 343 480 172 570 393 405 927 238 389 192 205 890 319 989 061 851 984 210 383 082 164 165 286 102 068 738 694 744 762 282 270 671 562 080 897 567 280 776 109 321 283 700 776 536 592 362 521 370 175 610 492 010 490 647 926 435 022 313 362 357 037 672 820 456 385 127 428 485 063 107 497 131 400 081 807 697 966 418 670 920 862 707 517 582 909 049 383 024 204 603 334 049 254 656 583 584 442 952 963 370 887 765 452 655 876 066 062 446 937 832 610 287 823 426 705 006 187 125 841 909 320 161 763 987 566 513 486 927 154 010 085 083 647 269 535 513 915 816 758 710 288 791 204 561 224 527 095 476 616 464 634 423 436 358 506 846 144 301 437 379 657 717 790 829 502 874 496 253 094 716 740 270 948 624 055 817 414 650 104 670 627 976 517 803 754 955 899 088 266 937 466 501 789 934 094 158 017 587 793 129 776 426 891 242 809 581 667 986 926 232 813 625 576 760 050 205 090 619 888 399 123 409 239 688 442 164 270 550 778 132 287 725 184 933 490 420 599 495 679 264 605 659 110 257 760 825 014 193 077 871 965 880 962 249 652 458 201 556 815 237 466 699 463 967 549 092 715 904 279 567 434 739 404 713 888 403 457 003 339 771 465 555 694 947 195 071 035 775 250 811 866 532 575 065 892 797 554 153 301 608 090 613 307 672 021 657 715 401 873 436 452 152 566 925 919 864 525 536 834 568 235 530 705 981 621 300 855 049 045 749 462 125 005 586 100 312 191 552 245 274 122 445 172 305 460 076 489 568 744 037 811 637 120 488 942 481 442 457 383 881 221 646 993 921 230 130 822 937 656 219 514 811 987 478 059 283 006 119 165 854 697 271 444 230 766 548 407 257 874 820 601 218 362 249 866 393 721 509 747 526 537 539 677 353 958 519 844 769 577 322 142 446 097 980 810 172 948 625 060 754 655 647 850 574 348 574 673 760 923 656 634 582 655 495 694 500 804 946 625 600 683 003 303 969 791 972 728 978 548 772 898 691 700 233 344 838 111 143 624 421 997 248 348 373 393 817 914 540 838 366 741 137 930 672 543 630 607 318 584 213 889 310 473 297 461 294 643 309 134 066 151 220 872 533 746 202 317 748 637 999 040 114 037 035 041 286 112 690 264 736 393 397 273 817 924 315 745 503 107 186 029 046 465 168 489 664 991 484 955 836 275 210 278 398 095 989 067 353 453 771 747 035 442 365 355 445 747 127 447 923 214 040 603 969 451 728 451 202 645 051 877 393 660 878 207 404 279 794 929 371 571 338 262 325 793 789 167 979 461 085 931 415 095 683 486 296 162 401 875 755 894 130 120 407 378 671 712 437 729 188 487 520 121 912 910 810 326 749 154 096 040 648 754 248 927 534 521 962 074 102 425 291 913 766 944 369 032 132 103 550 933 382 245 399 558 387 757 904 745 511 758 965 088 027 854 937 299 536 471 846 566 637 636 919 001 351 398 679 746 388 509 468 405 284 549 140 756 479 486 056 457 920 649 429 617 829 741 961 946 109 703 629 304 530 913 466 716 238 442 148 820 189 449 581 503 029 766 353 579 703 388 699 920 365 905 324 047 373 120 549 655 643 341 862 622 777 074 389 646 423 179 579 674 577 956 341 322 830 784 916 026 813 548 454 623 362 949 055 914 885 337 880 398 436 974 918 071 336 089 580 020 123 110 991 614 556 127 897 128 629 528 458 209 067 952 194 326 976 896 997 752 127 042 336 429 246 818 734 853 834 742 889 330 980 560 103 357 922 288 676 566 480 206 614 652 444 443 461 774 011 721 264 398 205 623 102 431 248 408 168 327 688 547 753 045 794 176 361 665 903 058 552 581 366 119 249 019 699 162 802 496 454 086 053 321 275 062 840 623 398 173 054 019 398 759 351 215 711 987 306 636 178 410 283 089 779 146 732 418 239 902 330 676 994 111 916 249 584 184 821 290 161 741 884 890 744 574 259 103 285 106 768 945 456 293 864 755 738 899 456 354 943 259 853 902 533 118 320 431 113 938 205 766 012 422 223 175 295 440 659 963 277 854 864 852 984 742 083 179 611 314 290 857 560 405 710 728 212 958 906 402 305 931 907 418 946 110 255 773 607 562 277 250 486 349 227 222 087 557 966 804 673 075 308 805 002 278 223 894 683 614 028 706 639 026 079 344 344 434 686 294 556 396 103 123 818 136 981 228 794 370 785 368 388 506 599 135 026 980 613 330 934 094 961 793 563 094 627 199 853 201 613 193 153 865 108 452 721 786 814 140 586 572 232 010 017 459 153 962 501 788 701 203 805 098 164 119 780 148 853 692 024 087 086 122 573 636 233 064 502 251 961 233 974 992 366 640 735 451 891 044 862 799 462 188 815 582 042 386 580 030 801 106 890 097 238 687 055 452 552 110 829 965 059 161 245 343 415 161 008 354 431 626 917 063 844 116 549 102 496 993 880 762 448 490 819 042 269 804 160 074 405 392 450 174 036 209 847 483 710 949 092 804 116 773 547 479 425 117 696 723 576 173 189 547 660 596 984 813 143 044 906 939 144 736 572 025 112 530 913 402 350 316 579 592 727 107 140 204 745 792 181 312 643 267 980 166 276 213 539 787 318 686 784 516 646 409 043 739 461 341 058 341 866 130 194 515 206 728 071 388 017 201 750 465 345 177 683 567 166 246 451 096 874 716 792 230 890 148 549 731 651 715 426 719 134 701 779 009 646 503 713 855 713 690 614 979 894 889 941 888 457 297 282 875 954 463 903 599 095 148 708 206 058 572 338 514 158 627 674 241 149 795 154 024 155 999 938 386 472 330 121 596 245 377 182 900 950 030 617 269 384 713 599 791 193 454 044 355 416 529 598 060 101 173 170 994 161 856 361 550 265 787 123 369 355 532 596 323 286 384 309 305 409 145 251 652 049 876 541 298 945 371 331 714 297 379 550 668 239 431 873 282 678 293 074 955 266 864 563 208 743 768 540 095 516 367 311 985 558 520 002 873 697 087 726 788 222 240 830 142 818 294 228 089 082 545 681 401 285 437 906 803 150 262 330 031 355 435 708 411 061 568 390 519 438 584 930 325 978 406 002 583 613 274 547 851 416 495 855 586 226 252 253 360 321 674 766 981 620 421 827 339 385 206 593 739 096 885 252 787 145 406 142 672 658 262 177 573 655 048 328 267 368 597 269 217 457 845 651 924 361 951 505 134 294 767 813 855 422 501 312 640 796 469 744 649 758 696 322 680 162 740 933 123 199 953 154 087 011 991 048 812 393 111 727 123 352 964 379 020 421 420 583 756 994 849 612 766 818 894 376 697 073 240 511 064 803 717 146 258 228 885 676 833 210 858 702 603 529 846 510 370 844 972 539 194 851 074 168 242 379 857 338 076 991 793 231 848 897 846 533 495 471 513 960 873 594 311 483 932 323 174 971 369 007 675 150 619 831 918 752 629 632 940 698 780 673 005 828 943 186 361 408 536 433 545 182 513 621 733 366 469 934 325 860 335 901 609 292 835 044 356 195 560 151 952 535 903 838 669 632 931 421 195 319 086 416 029 491 768 186 604 338 108 617 856 893 658 652 762 599 159 576 463 089 057 484 057 012 421 874 561 183 369 156 744 400 271 989 993 859 435 242 606 882 312 306 519 905 393 345 015 702 439 093 202 555 708 305 829 478 488 168 303 432 296 270 227 178 110 341 320 372 986 862 855 706 153 836 192 552 748 513 974 514 717 282 608 166 467 373 122 237 687 789 655 395 096 239 211 535 388 318 181 125 900 905 930 703 765 521 017 233 830 956 585 103 471 622 343 721 470 945 239 512 383 177 898 180 368 057 660 537 081 723 959 944 939 544 511 007 394 960 086 606 314 007 369 726 809 860 353 148 028 035 639 179 259 295 514 035 556 750 901 346 225 565 651 200 500 040 388 964 695 765 286 839 375 894 326 641 359 638 758 981 952 190 977 233 092 636 192 929 286 884 271 506 009 538 217 214 933 792 744 247 421 149 897 522 229 185 157 042 978 227 719 340 975 109 319 968 827 282 928 000 446 381 475 380 613 389 725 119 957 350 959 904 451 122 273 439 971 539 673 040 298 002 820 751 768 235 827 912 095 052 102 735 663 217 352 194 962 362 184 727 464 644 960 226 149 981 751 908 352 203 306 342 021 592 050 720 598 795 035 239 228 195 869 165 158 542 449 929 474 548 106 605 050 117 625 206 972 350 963 702 019 752 601 985 260 677 384 221 896 524 605 299 854 929 995 338 755 313 295 340 940 138 314 907 468 467 139 499 677 720 572 636 120 372 107 374 342 868 057 717 426 582 051 294 080 969 959 563 531 911 282 739 990 097 960 539 607 984 437 523 116 507 734 719 777 809 570 433 883 645 270 239 644 294 309 466 315 623 904 013 251 732 165 782 921 533 830 102 558 013 937 152 598 856 329 347 755 255 719 232 808 344 589 151 922 043 864 806 081 186 297 548 489 573 356 845 798 244 178 775 602 686 253 784 216 073 315 926 315 117 006 546 664 792 964 827 288 742 401 180 295 584 471 128 695 425 297 779 253 841 606 405 927 427 313 508 860 836 696 395 679 355 243 026 261 886 885 752 006 481 760 497 725 961 130 073 922 590 764 478 449 738 830 065 772 275 665 777 414 636 443 696 093 953 753 681 025 203 011 970 464 541 713 411 933 975 735 103 788 738 392 769 375 565 506 845 210 536 678 318 283 945 400 401 975 534 721 292 450 383 336 003 817 385 678 921 281 713 802 749 790 225 543 274 326 172 443 844 383 519 165 927 950 001 713 682 536 758 546 723 469 033 733 698 464 059 513 247 716 076 530 428 565 235 979 898 018 682 260 049 948 150 428 797 107 476 676 459 294 460 386 409 882 046 653 439 741 904 221 084 760 506 651 625 666 078 950 470 073 700 364 878 268 487 810 943 704 123 780 820 867 203 211 027 983 637 336 090 586 543 818 602 974 928 781 155 484 266 146 415 144 583 159 391 700 957 591 524 192 858 746 462 325 799 289 808 212 663 991 897 979 203 096 513 770 030 043 332 559 965 757 095 804 880 516 280 318 291 317 892 283 539 611 806 096 480 760 588 324 398 833 851 927 871 266 308 437 436 655 196 451 140 800 936 247 852 263 042 630 333 253 021 422 636 233 953 558 646 545 567 952 000 386 740 056 413 841 503 316 500 443 196 882 791 862 089 512 040 487 190 834 318 318 720 805 613 880 482 722 099 504 496 769 830 259 462 446 643 387 340 087 559 348 080 783 121 714 848 722 685 337 702 205 260 808 038 256 129 653 712 130 928 142 868 326 732 024 547 341 918 409 543 265 770 751 846 027 970 701 058 154 304 742 603 541 295 214 529 990 635 988 000 113 171 975 043 316 669 542 398 374 118 000 586 212 749 941 657 916 328 896 392 364 001 183 403 234 069 404 287 388 451 847 652 826 410 122 033 605 624 323 121 635 568 975 986 369 749 647 596 502 871 188 585 784 355 101 687 504 624 636 539 324 552 490 154 032 140 569 865 547 304 245 954 636 331 164 655 521 637 183 906 414 415 309 758 712 816 906 121 425 865 963 519 572 977 922 422 193 998 635 333 872 816 316 775 329 382 888 285 388 337 632 233 238 036 645 089 499 874 738 060 057 408 898 360 753 928 123 721 929 221 887 935 357 828 140 069 065 634 778 202 887 507 881 813 240 782 624 394 992 260 288 324 899 145 727 374 030 782 190 991 736 334 686 587 324 734 925 180 822 573 968 054 570 812 461 164 995 383 965 527 453 691 487 340 952 630 177 567 364 936 503 105 040 012 083 733 323 507 697 152 712 523 147 323 433 715 982 381 154 982 902 092 524 326 981 085 372 148 717 838 722 362 846 968 085 831 693 638 384 498 765 389 697 888 945 985 515 666 277 324 765 372 113 023 407 091 352 370 001 332 816 569 293 276 900 781 471 078 643 097 906 578 447 793 178 960 543 143 205 024 459 597 894 087 211 433 825 957 259 050 676 114 083 777 577 666 949 879 034 498 423 616 833 565 457 642 039 910 618 453 618 935 750 101 710 017 725 620 355 769 563 378 953 758 665 795 785 319 349 166 712 506 777 600 201 116 719 824 482 067 962 138 213 637 479 996 078 388 947 476 976 854 371 179 482 021 389 349 861 181 740 828 990 847 397 711 566 219 575 730 166 769 531 616 390 028 616 437 744 333 987 950 465 924 649 624 221 361 582 556 979 790 545 498 220 365 919 158 604 912 020 715 635 631 040 315 538 986 628 041 330 966 376 721 410 914 045 182 032 024 057 167 118 820 434 464 793 928 749 803 819 352 938 145 054 343 275 764 367 252 195 300 947 748 256 245 931 417 922 605 137 017 689 402 364 247 601 489 831 981 249 881 815 659 363 767 625 500 657 693 805 874 763 140 615 448 155 779 212 535 276 526 235 730 433 689 192 685 254 054 526 262 411 911 016 156 357 795 666 960 065 908 532 277 002 703 275 187 121 877 171 252 803 456 126 830 235 101 667 545 124 754 877 133 773 716 679 551 420 426 703 467 351 042 791 173 384 629 237 801 027 761 041 683 371 686 184 253 726 562 037 513 732 843 533 633 565 163 220 145 118 782 869 823 125 951 421 106 201 364 541 930 300 041 723 532 889 519 178 318 955 856 530 899 618 414 036 372 766 242 613 462 981 832 366 718 516 227 612 929 064 474 842 642 670 720 228 351 684 614 265 920 516 762 231 207 830 828 736 495 674 753 147 731 828 095 679 250 957 455 183 208 640 720 034 073 280 476 977 250 429 065 166 775 862 662 137 940 822 216 639 672 500 136 596 904 942 830 895 605 490 951 255 968 987 922 101 774 658 817 948 774 345 231 590 358 526 032 183 309 667 099 112 583 393 485 448 487 247 848 989 986 555 106 163 389 286 689 996 700 225 455 725 201 192 468 963 399 245 341 930 568 628 287 266 154 554 977 591 171 677 234 870 273 109 994 284 553 066 290 629 230 944 606 505 961 324 859 550 418 277 938 672 668 519 564 635 104 078 617 839 799 413 872 033 532 827 843 195 645 709 007 893 008 947 027 923 548 105 184 401 821 727 997 576 067 980 745 684 603 001 508 138 923 452 502 105 044 934 874 146 471 722 564 995 367 164 821 236 866 037 139 904 194 334 377 622 398 866 638 519 217 567 726 283 183 853 832 672 567 439 807 319 989 466 480 664 493 203 325 667 248 130 169 442 386 260 260 938 595 262 185 473 829 829 655 664 167 239 056 097 352 374 183 107 195 265 095 683 795 670 742 646 740 683 849 734 475 169 685 935 789 219 642 416 124 979 114 398 039 590 666 990 374 976 005 078 576 331 036 100 207 225 998 255 550 662 603 112 543 323 693 395 536 358 218 289 831 122 170 914 531 594 780 311 067 952 757 440 640 496 806 878 780 414 499 789 323 112 454 004 235 627 907 950 496 053 532 320 798 797 946 603 624 816 863 361 484 297 838 295 038 330 096 430 888 224 575 734 937 428 832 687 311 310 335 645 328 966 004 829 358 961 398 637 161 232 521 561 088 632 564 699 206 653 873 837 378 293 823 902 017 672 262 403 793 232 643 723 649 636 576 550 174 442 401 991 112 661 121 854 039 511 616 612 290 979 354 350 942 496 682 148 176 886 761 519 933 539 302 375 974 268 295 207 970 549 690 201 597 108 189 357 323 757 477 303 432 824 688 714 733 897 849 865 805 712 867 879 245 604 618 677 327 572 104 101 392 804 594 601 734 946 451 198 976 706 954 026 926 325 977 085 411 919 015 691 045 995 552 207 351 293 138 187 161 405 499 084 909 554 845 419 434 931 917 344 430 522 376 469 392 263 403 392 646 510 051 744 603 644 570 754 463 847 534 733 966 705 557 908 398 431 759 668 907 930 084 657 438 598 561 912 663 124 717 703 955 390 006 624 505 825 330 361 779 064 559 334 274 155 743 297 547 382 435 851 687 558 291 288 934 724 053 570 713 445 458 222 971 933 730 758 205 897 144 472 889 089 781 340 754 148 110 731 186 122 936 859 973 310 507 122 731 462 503 393 873 897 738 479 354 688 284 953 678 332 216 656 064 611 036 606 566 593 132 311 955 013 694 851 138 439 291 211 561 574 498 547 816 003 618 955 409 622 344 616 927 979 949 484 656 636 148 330 699 173 829 550 144 656 063 429 037 359 575 915 469 558 527 253 860 731 802 499 652 816 768 425 443 425 889 739 073 884 352 974 610 591 022 393 415 807 247 569 583 300 801 154 557 691 634 376 230 748 190 087 515 083 604 267 146 590 376 806 793 177 153 184 509 444 555 078 218 804 371 479 017 254 048 737 590 623 414 381 181 091 777 995 894 452 851 110 954 312 451 007 661 884 236 739 962 192 456 077 969 511 122 779 364 407 990 415 119 514 440 661 546 965 008 576 217 977 093 190 909 583 132 987 787 434 522 165 255 034 445 404 702 763 169 714 368 762 469 620 043 258 522 003 356 436 848 692 882 916 179 287 819 142 433 475 654 756 287 226 124 351 664 343 691 962 489 756 968 151 414 727 888 765 534 977 698 006 480 871 154 761 766 945 959 111 922 927 429 454 384 882 497 333 914 219 571 616 022 292 224 906 364 296 597 972 099 547 195 800 025 036 746 754 894 650 280 064 556 031 370 644 217 419 634 227 831 878 046 942 804 047 499 799 250 678 440 344 926 170 781 018 652 689 185 600 559 289 478 435 620 230 506 562 090 798 332 784 054 409 933 754 325 466 268 996 342 381 853 087 817 159 138 132 409 688 240 004 900 823 384 875 229 448 700 461 035 381 883 418 217 015 178 779 468 503 346 298 941 683 080 899 357 908 203 402 596 981 571 019 152 124 322 599 142 297 993 961 017 488 797 887 830 281 192 191 238 727 922 353 623 295 034 097 047 026 384 576 950 518 160 676 657 044 486 620 981 891 268 715 888 390 683 926 816 266 566 045 504 069 411 325 517 726 301 593 005 468 118 625 314 041 176 546 254 147 484 954 209 655 218 329 262 550 835 896 721 811 635 441 831 388 710 685 040 170 614 684 768 874 135 589 248 534 951 236 185 901 475 459 798 978 133 816 784 134 989 257 021 373 591 925 918 938 505 117 120 958 353 354 468 195 902 418 584 460 471 378 852 709 468 342 796 348 047 587 156 573 415 690 896 444 525 395 795 251 837 597 314 216 029 681 638 412 088 153 036 099 966 996 188 639 795 041 806 972 170 297 532 612 770 372 422 177 442 399 757 860 752 244 275 767 990 624 899 121 340 496 474 889 285 918 528 422 833 247 118 694 861 120 447 658 840 271 122 911 279 114 792 252 504 327 153 033 684 366 578 150 172 821 878 605 530 320 299 879 588 079 217 379 263 325 468 352 926 442 085 153 146 379 821 322 093 120 797 035 112 094 626 071 007 302 778 912 072 566 743 084 284 949 202 405 450 391 750 643 121 078 577 065 441 187 219 944 044 713 259 661 653 295 743 027 549 410 956 701 543 326 099 389 775 148 130 009 541 828 402 651 298 935 227 760 199 983 004 106 141 718 321 080 195 789 503 790 459 326 081 276 788 138 994 738 324 227 512 564 849 341 286 531 071 052 868 689 648 644 035 294 619 832 639 219 517 599 262 158 567 853 308 180 854 622 517 432 057 724 041 779 265 437 756 658 172 231 185 312 218 755 767 693 801 703 046 218 276 691 467 762 250 144 758 754 615 144 514 318 255 923 066 943 062 603 732 646 568 363 555 326 160 331 715 437 535 324 349 374 224 250 967 669 972 209 569 182 920 399 221 779 749 244 067 926 548 005 910 615 674 789 500 542 998 017 635 444 037 775 787 063 172 034 013 555 643 683 051 468 017 023 738 859 881 563 516 237 835 944 674 355 662 760 135 149 674 301 440 420 415 171 928 872 374 647 867 382 781 971 827 035 983 886 036 616 187 357 262 700 493 342 349 286 117 240 506 228 275 121 275 481 554 264 228 471 521 735 497 145 802 473 814 776 450 360 970 418 983 518 376 319 628 772 221 549 149 786 891 339 743 058 279 126 510 663 209 664 415 284 380 540 087 275 689 926 332 447 230 094 477 529 152 928 444 134 842 867 829 072 123 694 329 242 420 883 604 363 950 605 506 758 772 124 314 102 728 605 283 875 613 848 102 406 526 257 247 712 999 775 694 643 500 056 233 401 552 208 865 282 718 695 548 243 000 376 564 479 084 893 901 000 536 841 057 522 363 280 370 838 897 496 675 493 411 119 896 288 413 437 648 165 762 755 516 249 385 819 799 876 190 593 410 596 588 772 953 750 592 135 480 282 406 384 799 725 149 946 020 648 503 742 074 502 433 099 373 164 782 711 911 703 171 878 502 492 156 281 762 509 092 095 744 129 027 049 665 089 185 824 440 951 849 086 836 244 861 302 746 209 634 753 793 226 318 816 715 261 107 812 607 328 110 620 115 344 977 658 157 304 987 786 773 827 545 017 316 589 662 732 722 171 023 102 044 468 910 200 415 948 303 526 753 908 200 009 932 370 035 916 020 269 727 358 967 287 596 800 092 431 351 089 975 959 771 739 670 737 705 545 635 339 787 762 830 709 652 643 567 870 591 839 666 401 171 540 256 204 228 281 060 067 944 109 179 653 941 685 365 005 272 724 324 536 997 345 115 516 175 842 141 599 701 909 755 483 073 424 634 942 570 911 097 725 362 896 370 051 831 044 608 670 285 904 915 489 785 451 861 640 485 967 121 832 187 912 603 224 446 865 674 572 002 909 630 090 732 796 419 381 087 368 300 577 008 488 549 876 326 424 201 225 775 611 351 792 112 069 706 098 584 806 375 300 143 303 206 297 900 856 011 317 453 460 216 898 549 935 534 481 242 900 706 196 770 703 583 346 771 718 929 609 650 046 081 906 453 813 744 649 270 388 930 650 195 618 060 462 577 300 950 622 064 469 234 834 931 163 196 871 839 460 688 231 399 405 614 992 896 889 553 688 544 426 015 978 917 594 885 221 304 833 320 378 882 656 155 887 963 824 087 690 654 293 193 046 677 769 081 072 048 908 640 193 133 809 524 389 871 737 237 253 005 521 747 524 415 947 922 113 766 652 805 888 438 396 054 147 567 486 987 337 167 355 166 104 543 042 899 131 993 430 820 991 650 159 647 656 208 456 324 363 081 781 712 602 217 016 347 775 564 111 441 803 592 193 088 471 289 255 795 393 642 877 824 453 654 048 165 950 323 223 788 178 060 285 905 582 700 086 738 684 883 750 337 714 980 917 164 444 693 060 308 390 225 962 379 946 272 713 289 768 929 936 724 536 553 233 482 465 794 212 734 027 070 565 388 511 936 215 762 656 298 864 684 435 370 823 571 848 084 247 138 397 525 778 310 128 785 553 445 708 026 765 901 738 206 081 873 519 050 998 499 630 965 910 793 432 366 813 853 970 202 821 394 949 406 134 489 952 453 908 830 903 545 787 795 663 963 353 463 066 176 422 602 202 105 775 621 923 781 957 494 629 716 436 815 349 210 857 072 706 316 427 328 453 577 498 513 994 637 159 418 953 720 826 767 147 133 205 092 570 099 335 672 952 611 163 628 000 805 824 409 754 601 708 517 576 411 444 079 395 720 215 248 444 116 421 555 957 828 748 745 424 226 011 844 865 906 715 664 110 802 868 290 518 210 612 860 404 454 750 511 438 922 544 439 143 868 194 881 337 928 254 493 717 003 965 533 900 634 644 833 101 037 271 446 752 357 724 260 351 165 699 515 773 967 642 913 572 637 535 873 501 670 470 613 312 527 450 847 505 213 359 793 783 861 950 188 821 929 180 325 547 521 785 176 580 032 177 426 333 023 524 832 481 849 348 447 808 439 788 218 713 542 427 529 133 485 690 077 625 718 966 956 228 062 966 168 347 006 680 212 942 597 861 705 301 218 647 978 947 398 135 250 300 005 080 179 027 045 518 797 793 505 294 699 210 802 788 329 649 160 385 012 184 940 049 568 696 199 707 027 524 548 531 041 667 993 720 684 674 742 262 714 439 058 761 479 088 895 841 824 160 373 748 908 700 112 817 860 631 624 151 944 290 572 786 670 975 635 303 518 603 594 047 587 697 599 520 048 169 851 304 461 861 034 981 185 133 385 903 366 316 421 187 501 308 774 815 870 676 228 749 311 300 865 732 973 446 153 743 975 659 991 079 304 994 892 588 234 011 350 360 387 511 421 993 302 025 047 776 808 575 499 810 068 887 160 787 732 953 050 111 241 465 547 976 334 636 931 551 115 834 357 110 038 285 979 669 707 537 501 (20 899 digits)