mirror of
https://github.com/boostorg/math.git
synced 2026-01-19 16:32:10 +00:00
71 lines
2.9 KiB
C++
71 lines
2.9 KiB
C++
// 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 <benchmark/benchmark.h>
|
|
#include <boost/math/special_functions/fibonacci.hpp>
|
|
#include <boost/multiprecision/gmp.hpp>
|
|
#include <utility>
|
|
|
|
using T = boost::multiprecision::mpz_int;
|
|
|
|
auto fib_rec(unsigned long long n) -> std::pair<T, T> {
|
|
if (n == 0) return {0, 1};
|
|
auto p = fib_rec(n >> 1);
|
|
T c = p.first * (2 * p.second - p.first);
|
|
T d = p.first * p.first + p.second * p.second;
|
|
return (n & 1) ? std::make_pair(d, c + d) : std::make_pair(c, d);
|
|
}
|
|
|
|
static void recursive_slow(benchmark::State &state) {
|
|
for (auto _ : state)
|
|
benchmark::DoNotOptimize(fib_rec(state.range(0)).first);
|
|
state.SetComplexityN(state.range(0));
|
|
}
|
|
constexpr int bm_start = 1 << 3, bm_end = 1 << 22;
|
|
BENCHMARK(recursive_slow)->Range(bm_start, bm_end)->Complexity();
|
|
|
|
static void iterative_fast(benchmark::State &state) {
|
|
for (auto _ : state)
|
|
benchmark::DoNotOptimize(boost::math::fibonacci<T>(state.range(0)));
|
|
state.SetComplexityN(state.range(0));
|
|
}
|
|
BENCHMARK(iterative_fast)->Range(bm_start, bm_end)->Complexity();
|
|
|
|
BENCHMARK_MAIN();
|
|
|
|
/*
|
|
Expected output:
|
|
|
|
CPU Caches:
|
|
L1 Data 32K (x4)
|
|
L1 Instruction 32K (x4)
|
|
L2 Unified 256K (x4)
|
|
L3 Unified 8192K (x4)
|
|
Load Average: 0.96, 0.80, 0.74
|
|
-----------------------------------------------------------------
|
|
Benchmark Time CPU Iterations
|
|
-----------------------------------------------------------------
|
|
recursive_slow/8 3669 ns 3594 ns 190414
|
|
recursive_slow/64 6213 ns 6199 ns 116423
|
|
recursive_slow/512 8999 ns 8990 ns 78773
|
|
recursive_slow/4096 14529 ns 13984 ns 51206
|
|
recursive_slow/32768 74183 ns 73039 ns 8539
|
|
recursive_slow/262144 1297806 ns 1291304 ns 569
|
|
recursive_slow/2097152 23166565 ns 22751898 ns 30
|
|
recursive_slow/4194304 47038831 ns 46546938 ns 16
|
|
recursive_slow_BigO 0.51 NlgN 0.51 NlgN
|
|
recursive_slow_RMS 5 % 5 %
|
|
iterative_fast/8 1413 ns 1399 ns 493692
|
|
iterative_fast/64 2408 ns 2394 ns 298417
|
|
iterative_fast/512 4181 ns 4132 ns 170957
|
|
iterative_fast/4096 7627 ns 7558 ns 93554
|
|
iterative_fast/32768 65080 ns 64791 ns 11289
|
|
iterative_fast/262144 1207873 ns 1200725 ns 557
|
|
iterative_fast/2097152 19627331 ns 19510132 ns 36
|
|
iterative_fast/4194304 42351871 ns 42240620 ns 17
|
|
iterative_fast_BigO 0.46 NlgN 0.45 NlgN
|
|
iterative_fast_RMS 5 % 5 %
|
|
*/
|