based

Opinionated utility library
git clone git://git.dimitrijedobrota.com/based.git
Log | Files | Refs | README | HACKING | CONTRIBUTING | CODE_OF_CONDUCT | BUILDING
commit81c55b179c512909f1c786dbabe411898fb0a93e
parent4cbf30905bd2424e402532141b72ff0d6fc1e8f7
authorDimitrije Dobrota <mail@dimitrijedobrota.com>
dateThu, 27 Mar 2025 16:31:36 +0100

Fast exsponentiation function

Diffstat:
Mexample/functional.cpp|+++++++++++
Minclude/based/functional.hpp|++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Minclude/based/type_traits.hpp|+++++++++++++

3 files changed, 102 insertions(+), 0 deletions(-)

diff --git a/example/functional.cpp b/example/functional.cpp

@@ -21,5 +21,16 @@ int main()

std::cout << based::circular_nonterminating_orbit(1, func) << '\n';
std::cout << based::connection_point_nonterminating_orbit(1, func) << '\n';
std::cout << '\n';
std::cout << based::power(3, 0, std::multiplies<int> {}, 1) << '\n';
for (std::size_t i = 1; i < 8; i++) {
std::cout << based::power(3, i, std::multiplies<int> {}) << '\n';
}
std::cout << '\n';
for (std::size_t i = 0; i < 8; i++) {
std::cout << based::fibonacci(i) << '\n';
}
return 0;
}

diff --git a/include/based/functional.hpp b/include/based/functional.hpp

@@ -1,5 +1,7 @@

#pragma once
#include <cassert>
#include "based/type_traits.hpp"
namespace based

@@ -141,4 +143,80 @@ codomain_t<F> power_unary(codomain_t<F> x, N n, F f)

return x;
}
template<Integer I, BinaryOperation Op>
codomain_t<Op> power_left_associated(codomain_t<Op> a, I n, Op op)
{
assert(n > 0);
return one(n) ? a : op(power_left_associated(a, predecesor(n), op), a);
}
template<Integer I, BinaryOperation Op>
codomain_t<Op> power_right_associated(codomain_t<Op> a, I n, Op op)
{
assert(n > 0);
return one(n) ? a : op(a, power_right_associated(a, predecesor(n), op));
}
template<Integer I, AssociativeBinaryOperation Op>
codomain_t<Op> power_accumulate_positive(codomain_t<Op> r,
codomain_t<Op> a,
I n,
Op op)
{
assert(n > 0);
while (true) {
if (odd(n)) {
r = op(r, a);
if (one(n)) {
return r;
}
}
a = op(a, a);
n = half(n);
}
}
template<Integer I, AssociativeBinaryOperation Op>
codomain_t<Op> power_accumulate(codomain_t<Op> r, codomain_t<Op> a, I n, Op op)
{
assert(n >= 0);
return zero(n) ? r : power_accumulate_positive(r, a, n, op);
}
template<Integer I, AssociativeBinaryOperation Op>
codomain_t<Op> power(codomain_t<Op> a, I n, Op op)
{
assert(n > 0);
while (even(n)) {
a = op(a, a);
n = half(n);
}
n = half(n);
return zero(n) ? a : power_accumulate_positive(a, op(a, a), n, op);
}
template<Integer I, AssociativeBinaryOperation Op>
codomain_t<Op> power(codomain_t<Op> a, I n, Op op, codomain_t<Op> id)
{
assert(n >= 0);
return !zero(n) ? power(a, n, op) : id;
}
template<Integer I>
std::pair<I, I> fibonacci_matrix_multiply(const std::pair<I, I>& x,
const std::pair<I, I>& y)
{
return {(x.first * (y.first + y.second)) + (x.second * y.first),
(x.first * y.first) + (x.second * y.second)};
}
template<Integer I>
I fibonacci(I n)
{
assert(n >= 0);
return !zero(n) ? power({I {1}, I {0}}, n, fibonacci_matrix_multiply<I>).first
: I {0};
}
} // namespace based

diff --git a/include/based/type_traits.hpp b/include/based/type_traits.hpp

@@ -275,4 +275,17 @@ concept Transformation = requires {

requires(UnaryFunction<P>);
};
template<typename P>
concept BinaryOperation = requires {
requires(Operation<P>);
requires(arity_v<P> == 2);
};
template<typename P>
concept AssociativeBinaryOperation = requires {
requires(Operation<P>);
requires(arity_v<P> == 2);
// requires(P is associative)
};
} // namespace based