1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
|
// Copyright Madhur Chauhan 2020.
// Use, modification and distribution are subject to the
// Boost Software License, Version 1.0. (See accompanying file
// LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
#include <boost/math/policies/error_handling.hpp>
#include <boost/math/special_functions/fibonacci.hpp>
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/test/tools/old/interface.hpp>
#include <cstdint>
#include <exception>
#define BOOST_TEST_MODULE Fibonacci_Test_Module
#include <boost/test/included/unit_test.hpp>
using boost::math::fibonacci;
using boost::math::unchecked_fibonacci;
using namespace boost::multiprecision;
typedef cpp_int BST;
typedef number<backends::cpp_int_backend<2048, 2048, unsigned_magnitude, unchecked>> BST_2048;
// Some sanity checks using OEIS A000045
BOOST_AUTO_TEST_CASE(sanity_checks) {
BOOST_TEST(fibonacci<char>(0) == 0); // Base case
BOOST_TEST(fibonacci<int>(1) == 1); // Base case
BOOST_TEST(fibonacci<int16_t>(2) == 1); // Base Case
BOOST_TEST(fibonacci<int16_t>(3) == 2); // First computation
BOOST_TEST(fibonacci<int16_t>(10) == 55);
BOOST_TEST(fibonacci<int16_t>(15) == 610);
BOOST_TEST(fibonacci<int16_t>(18) == 2584);
BOOST_TEST(fibonacci<int32_t>(40) == 102334155);
}
// Tests unchecked_fibonacci by computing naively
BOOST_AUTO_TEST_CASE(big_integer_check) {
// GMP is used as type for fibonacci and cpp_int is for naive computation
BST val = 0, a = 0, b = 1;
for (int i = 0; i <= 1e4; ++i) {
BOOST_TEST(fibonacci<BST>(i) == a);
val = b, b += a, a = val;
}
}
// Check for overflow throw using magic constants
BOOST_AUTO_TEST_CASE(overflow_check) {
// 1. check for unsigned integer overflow
BOOST_CHECK_NO_THROW(fibonacci<uint64_t>(93));
BOOST_CHECK_THROW(fibonacci<uint64_t>(94), std::exception);
BOOST_CHECK_NO_THROW(unchecked_fibonacci<uint64_t>(94));
// 2. check for signed integer overflow
BOOST_CHECK_NO_THROW(fibonacci<int64_t>(91));
// BOOST_CHECK_THROW(fibonacci<int64_t>(92), std::exception); // this should be the correct value but imprecisions
BOOST_CHECK_THROW(fibonacci<int64_t>(93), std::exception);
// In UBSAN this will error out, but it is expected
BOOST_CHECK_NO_THROW(unchecked_fibonacci<int64_t>(93));
// 3. check for floating point (double)
BOOST_CHECK_NO_THROW(fibonacci<double>(78));
BOOST_CHECK_THROW(fibonacci<double>(79), std::exception);
BOOST_CHECK_NO_THROW(unchecked_fibonacci<double>(79));
// 4. check using boost's multiprecision unchecked integer
BOOST_CHECK_NO_THROW(fibonacci<BST_2048>(2950));
// BOOST_CHECK_THROW(fibonacci<T>(2951), std::exception); // this should be the correct value but imprecisions
BOOST_CHECK_THROW(fibonacci<BST_2048>(2952), std::exception);
BOOST_CHECK_NO_THROW(unchecked_fibonacci<BST_2048>(2952));
}
BOOST_AUTO_TEST_CASE(generator_check) {
// first 5 values
boost::math::fibonacci_generator<BST_2048> gen;
for (int i : {0, 1, 1, 2, 3, 5, 8, 13, 21}) {
BOOST_TEST(gen() == i);
}
// test whether the generator is set correctly to the given index --- next
const int next = 1000; // next <=2950 (checked from test above)
gen.set(next);
BST_2048 a = fibonacci<BST_2048>(next), b = fibonacci<BST_2048>(next + 1);
for (int i = next; i < next + 50; ++i) {
BOOST_TEST(gen() == a);
swap(a, b);
b += a;
}
// shift the generator back to next and check again
a = fibonacci<BST_2048>(next), b = fibonacci<BST_2048>(next + 1);
gen.set(next);
for (int i = next; i < next + 50; ++i) {
BOOST_TEST(gen() == a);
swap(a, b);
b += a;
}
}
#ifndef BOOST_NO_CXX14_CONSTEXPR
BOOST_AUTO_TEST_CASE(constexpr_check) {
constexpr int x = boost::math::unchecked_fibonacci<int>(32);
static_assert(x == 2178309, "constexpr check 1");
constexpr double y = boost::math::unchecked_fibonacci<double>(40);
static_assert(y == 102334155.0, "constexpr check 2");
constexpr int xx = boost::math::fibonacci<int>(32);
static_assert(xx == 2178309, "constexpr check 3");
constexpr double yy = boost::math::fibonacci<double>(40);
static_assert(yy == 102334155.0, "constexpr check 4");
}
#endif
|
