Primary module interface unit for module base. More...

#include <algorithm>
#include <array>
#include <bit>
#include <cassert>
#include <climits>
#include <cmath>
#include <cstdint>
#include <functional>
#include <ranges>
#include <type_traits>
import base:concepts;

Include dependency graph for base.cpp:

Functions
template<Integer T>
constexpr bool	ntlib::is_odd (T n) noexcept
	Checks whether a given number is odd.
template<Integer T>
constexpr bool	ntlib::is_even (T n) noexcept
	Checks whether a given number is even.
template<AdditiveGroup T>
constexpr T	ntlib::abs (T n) noexcept
	Computes the absolute value of a given number.
template<AdditiveGroup T>
constexpr T	ntlib::difference (T a, T b) noexcept
	Computes the difference between two numbers.
template<std::totally_ordered T>
constexpr int	ntlib::sgn (T n) noexcept
	Computes the sign of a given number.
template<Integer T>
constexpr std::pair< T, T >	ntlib::odd_part (T n) noexcept
	Given a number n, computes a pair (e, o), such that n=2^e*o.
template<Integer T>
constexpr T	ntlib::gcd (T a, T b) noexcept
	Computes the greatest common divisor of two numbers using the Euclidean algorithm.
template<Integer T>
constexpr T	ntlib::gcd (std::initializer_list< T > list) noexcept
	Computes the greatest common divisor of a list of numbers.
template<Integer T>
constexpr T	ntlib::lcm (T a, T b) noexcept
	Computes the least common multiple of two numbers.
template<Integer T>
constexpr T	ntlib::lcm (std::initializer_list< T > list) noexcept
	Computes the least common multiple of a list of numbers.
template<Integer T>
constexpr std::tuple< T, T, T >	ntlib::extended_euclid (T a, T b) noexcept
	Extended Euclidean algorithm.
template<MultiplicativeMonoid A, Integer B>
constexpr A	ntlib::pow (A a, B b) noexcept
	Binary exponentation.
template<Integer T>
constexpr T	ntlib::ilog2 (T n) noexcept
	Computes the integer part of the binary logarithm of a given number.
template<Integer T>
constexpr T	ntlib::isqrt (T n) noexcept
	Computes the integer square root of a given number.
template<Integer T>
constexpr bool	ntlib::is_square (T n) noexcept
	Tests, if a given number is a perfect square.
template<Integer T>
constexpr T	ntlib::factorial (T n) noexcept
	Computes the factorial of a given number.

Variables
template<Integer T>
constexpr auto	ntlib::SMALL_PRIMES
	A list with all prime numbers up to ntlib::SMALL_PRIMES_BIGGEST.
template<Integer T>
constexpr T	ntlib::SMALL_PRIMES_BIGGEST
	Helper constant to get the biggest among the small primes in ntlib::SMALL_PRIMES.

Detailed Description

Primary module interface unit for module base.

Function Documentation

◆ abs()

template<AdditiveGroup T>

T ntlib::abs ( T n )

nodiscardconstexprexportnoexcept

Computes the absolute value of a given number.

Template Parameters

T	An additive group.

Parameters

n	The given number.

Returns: The absolute value of n.

◆ difference()

template<AdditiveGroup T>

T ntlib::difference	(	T	a,
		T	b )

nodiscardconstexprexportnoexcept

Computes the difference between two numbers.

Template Parameters

T	An additive group.

Parameters

a	The first number.
b	The second number.

Returns: The difference, i.e., \(\lvert a-b \rvert\).

◆ extended_euclid()

template<Integer T>

std::tuple< T, T, T > ntlib::extended_euclid	(	T	a,
		T	b )

nodiscardconstexprexportnoexcept

Extended Euclidean algorithm.

Given two integers \(a\) and \(b\), finds whole number solutions for \(a \cdot x + b \cdot y = \text{gcd}(a,b)\).

Template Parameters

T	An integer-like type.

Parameters

a	The first number.
b	The second number.

Returns: Tuple \((\mathrm{gcd}(a,b), x, y)\).

◆ factorial()

template<Integer T>

T ntlib::factorial ( T n )

nodiscardconstexprexportnoexcept

Computes the factorial of a given number.

Template Parameters

T	An integer-like type.

Parameters

n	The given number.

Returns: The factorial of \(n\), i.e, \(n! = 1 \cdot 2 \cdot \ldots \cdot n\).

◆ gcd() [1/2]

template<Integer T>

T ntlib::gcd ( std::initializer_list< T > list )

nodiscardconstexprexportnoexcept

Computes the greatest common divisor of a list of numbers.

Template Parameters

T	An integer-like type.

Parameters

list	The list of numbers. Must not be empty.

Returns: The greatest common divisor of the numbers in the list.

◆ gcd() [2/2]

template<Integer T>

T ntlib::gcd	(	T	a,
		T	b )

nodiscardconstexprexportnoexcept

Computes the greatest common divisor of two numbers using the Euclidean algorithm.

The greatest common divisor of two numbers a and b (not both zero) is the smallest positive number that divides both a and b.

Complexity: \(O(\log a + \log b)\)

Template Parameters

T	An integer-like type.

Parameters

a	The first number.
b	The second number.

Returns: The greatest common divisor of a and b.

◆ ilog2()

template<Integer T>

T ntlib::ilog2 ( T n )

nodiscardconstexprexportnoexcept

Computes the integer part of the binary logarithm of a given number.

Template Parameters

T	An integer-like type.

Parameters

n	The given number.

Returns: The integer part of the binary logarithm of \(n\), i.e., \(\lfloor\log_2(n)\rfloor\).

◆ is_even()

template<Integer T>

bool ntlib::is_even ( T n )

nodiscardconstexprexportnoexcept

Checks whether a given number is even.

Template Parameters

T	An integer-like type.

Parameters

n	The given number.

Returns: Whether n is even.

◆ is_odd()

template<Integer T>

bool ntlib::is_odd ( T n )

nodiscardconstexprexportnoexcept

Checks whether a given number is odd.

Template Parameters

T	An integer-like type.

Parameters

n	The given number.

Returns: Whether n is odd.

◆ is_square()

template<Integer T>

bool ntlib::is_square ( T n )

nodiscardconstexprexportnoexcept

Tests, if a given number is a perfect square.

Uses ideas from this site: https://math.stackexchange.com/questions/131330/detecting-perfect-squares-faster-than-by-extracting-square-root/712818#712818

Complexity: \(O(\log n)\)

Template Parameters

T	An integer-like type.

Parameters

n	The given number.

Returns: Whether n is a perfect square.

◆ isqrt()

template<Integer T>

T ntlib::isqrt ( T n )

nodiscardconstexprexportnoexcept

Computes the integer square root of a given number.

Template Parameters

T	An integer-like type.

Parameters

n	The given number. Must be non-negative.

Returns: The integer square root of \(n\), i.e., \(\lfloor(\sqrt{n})\rfloor\).

◆ lcm() [1/2]

template<Integer T>

T ntlib::lcm ( std::initializer_list< T > list )

nodiscardconstexprexportnoexcept

Computes the least common multiple of a list of numbers.

Template Parameters

T	An integer-like type.

Parameters

list	The list of numbers. Must not be empty.

Returns: The least common multiple of the numbers in the list.

◆ lcm() [2/2]

template<Integer T>

T ntlib::lcm	(	T	a,
		T	b )

nodiscardconstexprexportnoexcept

Computes the least common multiple of two numbers.

The least common multiple of two non-zero integers a and b is the smallest positive integer that can be divided by both a and b.

Complexity: \(O(\log a + \log b)\)

Template Parameters

T	An integer-like type.

Parameters

a	The first number.
b	The second number.

Returns: The least common multiple of a and b.

◆ odd_part()

template<Integer T>

std::pair< T, T > ntlib::odd_part ( T n )

nodiscardconstexprexportnoexcept

Given a number n, computes a pair (e, o), such that n=2^e*o.

Template Parameters

T	An integer-like type.

Parameters

n	The number n to decompose.

Returns: A pair with e and o as its first and second element, respectively.

◆ pow()

template<MultiplicativeMonoid A, Integer B>

A ntlib::pow	(	A	a,
		B	b )

nodiscardconstexprexportnoexcept

Binary exponentation.

Complexity: \(O(\log b)\)

Template Parameters

A	A multiplicative monoid.
B	An integer-like type.

Parameters

a	The base.
b	The exponent, non-negative.

Returns: The power \(a^b\).

◆ sgn()

template<std::totally_ordered T>

int ntlib::sgn ( T n )

nodiscardconstexprexportnoexcept

Computes the sign of a given number.

Template Parameters

T	An integer-like type.

Parameters

n	The given number.

Returns: The sign. One of -1, 0 or +1.

Variable Documentation

◆ SMALL_PRIMES

template<Integer T>

auto ntlib::SMALL_PRIMES

constexprexport

Initial value:

                        = std::to_array<T>({
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151,
157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233,
239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317,
331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419,
421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503,
509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607,
613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701,
709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811,
821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911,
919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1'009})

A list with all prime numbers up to ntlib::SMALL_PRIMES_BIGGEST.

Can be used for trial division in primality tests and prime factorizations.

Template Parameters

T	An integer-like type.

◆ SMALL_PRIMES_BIGGEST

template<Integer T>

T ntlib::SMALL_PRIMES_BIGGEST

constexprexport

Initial value:

=

*std::ranges::max_element(SMALL_PRIMES<T>)

ntlib::SMALL_PRIMES

constexpr auto SMALL_PRIMES

A list with all prime numbers up to ntlib::SMALL_PRIMES_BIGGEST.

Definition base.cpp:39

Helper constant to get the biggest among the small primes in ntlib::SMALL_PRIMES.

Template Parameters

T	An integer-like type.

Functions

Variables

Detailed Description

Function Documentation

◆ abs()

◆ difference()

◆ extended_euclid()

◆ factorial()

◆ gcd() [1/2]

◆ gcd() [2/2]

◆ ilog2()

◆ is_even()

◆ is_odd()

◆ is_square()

◆ isqrt()

◆ lcm() [1/2]

◆ lcm() [2/2]

◆ odd_part()

◆ pow()

◆ sgn()

Variable Documentation

◆ SMALL_PRIMES

◆ SMALL_PRIMES_BIGGEST