Algorithms_in_C++ 1.0.0
Set of algorithms implemented in C++.
|
for IO operations More...
Typedefs | |
using | Point |
structure of points containing two numbers, x and y, such that 0 ≤ x ≤ 1 and 0 ≤ y ≤ 1. | |
Functions | |
uint64_t | aliquot_sum (const uint64_t num) |
to return the aliquot sum of a number | |
double | approximate_pi (const std::vector< Point > &pts) |
This function uses the points in a given vector 'pts' (drawn at random) to return an approximation of the number π. | |
template<typename T > | |
T | square_area (T length) |
area of a square (l * l) | |
template<typename T > | |
T | rect_area (T length, T width) |
area of a rectangle (l * w) | |
template<typename T > | |
T | triangle_area (T base, T height) |
area of a triangle (b * h / 2) | |
template<typename T > | |
T | circle_area (T radius) |
area of a circle (pi | |
template<typename T > | |
T | parallelogram_area (T base, T height) |
area of a parallelogram (b * h) | |
template<typename T > | |
T | cube_surface_area (T length) |
surface area of a cube ( 6 * (l | |
template<typename T > | |
T | sphere_surface_area (T radius) |
surface area of a sphere ( 4 * pi * r^2) | |
template<typename T > | |
T | cylinder_surface_area (T radius, T height) |
surface area of a cylinder (2 * pi * r * h + 2 * pi * r^2) | |
int | sum_of_divisor (int num) |
Function to calculate the sum of all the proper divisor of an integer. | |
bool | are_amicable (int x, int y) |
Function to check whether the pair is amicable or not. | |
bool | is_factorial (uint64_t n) |
Function to check if the given number is factorial of some number or not. | |
bool | is_prime (int64_t num) |
Function to check if the given number is prime or not. | |
void | sieve (std::vector< bool > *vec) |
Performs the sieve. | |
void | print_primes (std::vector< bool > const &primes) |
Prints all the indexes of true values in the passed std::vector. | |
uint64_t | phiFunction (uint64_t n) |
Function to calculate Euler's Totient. | |
uint64_t | factorial (uint8_t n) |
function to find factorial of given number | |
double | integral_approx (double lb, double ub, const std::function< double(double)> &func, double delta=.0001) |
Computes integral approximation. | |
void | test_eval (double approx, double expected, double threshold) |
Wrapper to evaluate if the approximated value is within .XX% threshold of the exact value. | |
uint64_t | iterativeFactorial (uint8_t n) |
Calculates the factorial iteratively. | |
uint64_t | largestPower (uint32_t n, const uint16_t &p) |
Function to calculate largest power. | |
uint64_t | lcmSum (const uint16_t &num) |
bool | magic_number (const uint64_t &n) |
uint64_t | power (uint64_t a, uint64_t b, uint64_t c) |
This function calculates a raised to exponent b under modulo c using modular exponentiation. | |
template<class T > | |
T | n_choose_r (T n, T r) |
This is the function implementation of \( \binom{n}{r} \). | |
template<typename T > | |
T | square_perimeter (T length) |
perimeter of a square (4 * l) | |
template<typename T > | |
T | rect_perimeter (T length, T width) |
perimeter of a rectangle ( 2(l + w) ) | |
template<typename T > | |
T | triangle_perimeter (T base, T height, T hypotenuse) |
perimeter of a triangle (a + b + c) | |
template<typename T > | |
T | circle_perimeter (T radius) |
perimeter of a circle (2 * pi * r) | |
template<typename T > | |
T | parallelogram_perimeter (T base, T height) |
perimeter of a parallelogram 2(b + h) | |
template<typename T > | |
T | cube_surface_perimeter (T length) |
surface perimeter of a cube ( 12 | |
template<typename T > | |
T | n_polygon_surface_perimeter (T sides, T length) |
surface perimeter of a n-polygon ( n * l) | |
template<typename T > | |
T | cylinder_surface_perimeter (T radius, T height) |
surface perimeter of a cylinder (2 * radius + 2 * height) | |
int | power_of_two (int n) |
This function finds whether a number is power of 2 or not. | |
std::array< std::complex< long double >, 2 > | quadraticEquation (long double a, long double b, long double c) |
Quadratic equation calculator. | |
uint64_t | binomialCoeffSum (uint64_t n) |
template<typename T > | |
T | cube_volume (T length) |
The volume of a cube | |
template<typename T > | |
T | rect_prism_volume (T length, T width, T height) |
The volume of a rectangular prism. | |
template<typename T > | |
T | cone_volume (T radius, T height, double PI=3.14) |
The volume of a cone | |
template<typename T > | |
T | triangle_prism_volume (T base, T height, T depth) |
The volume of a triangular prism. | |
template<typename T > | |
T | pyramid_volume (T length, T width, T height) |
The volume of a pyramid | |
template<typename T > | |
T | sphere_volume (T radius, double PI=3.14) |
The volume of a sphere | |
template<typename T > | |
T | cylinder_volume (T radius, T height, double PI=3.14) |
The volume of a cylinder | |
for IO operations
for io operations
Evaluate recurrence relation using matrix exponentiation.
Math algorithms.
Mathematical functions.
for I/O operations
Mathematical algorithms.
for cout
for M_PI definition and pow()
for std::vector
for assert
Mathematical algorithms
for assert for std::rand for IO operations
Mathematical algorithms
for assert for uint16_t datatype for IO operations
Mathematical algorithms
for assert for int32_t type for atoi
Mathematical algorithms
For assert For timing the sieve For IO operations For string handling For std::vector
for IO operations for assert
for assert for std::cin and std::cout
Mathematical algorithms
for assert for mathematical functions for passing in functions for IO operations
for math functions for fixed size data types for time to initialize rng for function pointers for std::cout for random number generation for std::vector
for assert for integral types for std::invalid_argument for std::cout
for std::cin and std::cout for assert
Given a recurrence relation; evaluate the value of nth term. For e.g., For fibonacci series, recurrence series is f(n) = f(n-1) + f(n-2)
where f(0) = 0
and f(1) = 1
. Note that the method used only demonstrates recurrence relation with one variable (n), unlike nCr
problem, since it has two (n, r)
This problem can be solved using matrix exponentiation method.
Mathematical algorithms
for assert for std::cout
Mathematical algorithms
for assert for M_PI definition and pow() for uint16_t datatype
Mathematical algorithms
std::array assert std::sqrt, std::trunc, std::pow std::complex std::invalid_argument std::setprecision
Mathematical algorithms
for assert for std::pow for std::uint32_t
Mathematical algorithms
using math::Point |
structure of points containing two numbers, x and y, such that 0 ≤ x ≤ 1 and 0 ≤ y ≤ 1.
uint64_t math::aliquot_sum | ( | const uint64_t | num | ) |
to return the aliquot sum of a number
num | The input number |
double math::approximate_pi | ( | const std::vector< Point > & | pts | ) |
This function uses the points in a given vector 'pts' (drawn at random) to return an approximation of the number π.
pts | Each item of pts contains a point. A point is represented by the point structure (coded above). |
bool math::are_amicable | ( | int | x, |
int | y ) |
Function to check whether the pair is amicable or not.
x | First number. |
y | Second number. |
true
if the pair is amicable false
if the pair is not amicable uint64_t math::binomialCoeffSum | ( | uint64_t | n | ) |
Function to calculate sum of binomial coefficients
n | number |
T math::circle_area | ( | T | radius | ) |
area of a circle (pi
radius | is the radius of the circle |
T math::circle_perimeter | ( | T | radius | ) |
perimeter of a circle (2 * pi * r)
radius | is the radius of the circle |
T math::cone_volume | ( | T | radius, |
T | height, | ||
double | PI = 3.14 ) |
The volume of a cone
radius | The radius of the base circle |
height | The height of the cone |
PI | The definition of the constant PI |
T math::cube_surface_area | ( | T | length | ) |
surface area of a cube ( 6 * (l
length | is the length of the cube |
T math::cube_surface_perimeter | ( | T | length | ) |
surface perimeter of a cube ( 12
length | is the length of the cube |
T math::cube_volume | ( | T | length | ) |
T math::cylinder_surface_area | ( | T | radius, |
T | height ) |
T math::cylinder_surface_perimeter | ( | T | radius, |
T | height ) |
T math::cylinder_volume | ( | T | radius, |
T | height, | ||
double | PI = 3.14 ) |
uint64_t math::factorial | ( | uint8_t | n | ) |
function to find factorial of given number
n | is the number which is to be factorialized |
double math::integral_approx | ( | double | lb, |
double | ub, | ||
const std::function< double(double)> & | func, | ||
double | delta = .0001 ) |
Computes integral approximation.
lb | lower bound |
ub | upper bound |
func | function passed in |
delta |
bool math::is_factorial | ( | uint64_t | n | ) |
Function to check if the given number is factorial of some number or not.
n | number to be checked. |
this loop is basically a reverse factorial calculation, where instead of multiplying we are dividing. We start at i = 2 since i = 1 has no impact division wise
if n was the sum of a factorial then it should be divided until it becomes 1
bool math::is_prime | ( | int64_t | num | ) |
Function to check if the given number is prime or not.
num | number to be checked. |
Reduce all possibilities of a number which cannot be prime with the first 3 if, else if conditionals. Example: Since no even number, except 2 can be a prime number and the next prime we find after our checks is 5, we will start the for loop with i = 5. then for each loop we increment i by +6 and check if i or i+2 is a factor of the number; if it's a factor then we will return false. otherwise, true will be returned after the loop terminates at the terminating condition which is i*i <= num
uint64_t math::iterativeFactorial | ( | uint8_t | n | ) |
Calculates the factorial iteratively.
n | Nth factorial. |
uint64_t math::largestPower | ( | uint32_t | n, |
const uint16_t & | p ) |
Function to calculate largest power.
n | number |
p | prime number |
uint64_t math::lcmSum | ( | const uint16_t & | num | ) |
Function to compute sum of euler totients in sumOfEulerTotient vector
num | input number |
bool math::magic_number | ( | const uint64_t & | n | ) |
Function to check if the given number is magic number or not.
n | number to be checked. |
T math::n_choose_r | ( | T | n, |
T | r ) |
This is the function implementation of \( \binom{n}{r} \).
We are calculating the ans with iterations instead of calculating three different factorials. Also, we are using the fact that \( \frac{n!}{r! (n-r)!} = \frac{(n - r + 1) \times \cdots \times n}{1 \times \cdots \times r} \)
T | Only for integer types such as long, int_64 etc |
n | \( n \) in \( \binom{n}{r} \) |
r | \( r \) in \( \binom{n}{r} \) |
T math::n_polygon_surface_perimeter | ( | T | sides, |
T | length ) |
surface perimeter of a n-polygon ( n * l)
length | is the length of the polygon |
sides | is the number of sides of the polygon |
T math::parallelogram_area | ( | T | base, |
T | height ) |
area of a parallelogram (b * h)
base | is the length of the bottom side of the parallelogram |
height | is the length of the tallest point in the parallelogram |
T math::parallelogram_perimeter | ( | T | base, |
T | height ) |
perimeter of a parallelogram 2(b + h)
base | is the length of the bottom side of the parallelogram |
height | is the length of the tallest point in the parallelogram |
uint64_t math::phiFunction | ( | uint64_t | n | ) |
Function to calculate Euler's Totient.
n | the number to find the Euler's Totient of |
uint64_t math::power | ( | uint64_t | a, |
uint64_t | b, | ||
uint64_t | c ) |
This function calculates a raised to exponent b under modulo c using modular exponentiation.
a | integer base |
b | unsigned integer exponent |
c | integer modulo |
Initialize the answer to be returned
Update a if it is more than or equal to c
In case a is divisible by c;
If b is odd, multiply a with answer
b must be even now
b = b/2
int math::power_of_two | ( | int | n | ) |
This function finds whether a number is power of 2 or not.
n | value for which we want to check prints the result, as "Yes, the number n is a power of 2" or "No, the number is not a power of 2" without quotes |
n
IS the power of 2 result stores the bitwise and of n and n-1
void math::print_primes | ( | std::vector< bool > const & | primes | ) |
Prints all the indexes of true values in the passed std::vector.
primes | The vector that has been passed through sieve(...) |
T math::pyramid_volume | ( | T | length, |
T | width, | ||
T | height ) |
The volume of a pyramid
length | The length of the base shape (or base for triangles) |
width | The width of the base shape (or height for triangles) |
height | The height of the pyramid |
std::array< std::complex< long double >, 2 > math::quadraticEquation | ( | long double | a, |
long double | b, | ||
long double | c ) |
Quadratic equation calculator.
a | quadratic coefficient. |
b | linear coefficient. |
c | constant |
T math::rect_area | ( | T | length, |
T | width ) |
area of a rectangle (l * w)
length | is the length of the rectangle |
width | is the width of the rectangle |
T math::rect_perimeter | ( | T | length, |
T | width ) |
perimeter of a rectangle ( 2(l + w) )
length | is the length of the rectangle |
width | is the width of the rectangle |
T math::rect_prism_volume | ( | T | length, |
T | width, | ||
T | height ) |
The volume of a rectangular prism.
length | The length of the base rectangle |
width | The width of the base rectangle |
height | The height of the rectangular prism |
void math::sieve | ( | std::vector< bool > * | vec | ) |
Performs the sieve.
vec | Array of bools, all initialised to true, where the number of elements is the highest number we wish to check for primeness |
T math::sphere_surface_area | ( | T | radius | ) |
surface area of a sphere ( 4 * pi * r^2)
radius | is the radius of the sphere |
T math::sphere_volume | ( | T | radius, |
double | PI = 3.14 ) |
T math::square_area | ( | T | length | ) |
area of a square (l * l)
length | is the length of the square |
T math::square_perimeter | ( | T | length | ) |
perimeter of a square (4 * l)
length | is the length of the square |
int math::sum_of_divisor | ( | int | num | ) |
Function to calculate the sum of all the proper divisor of an integer.
num | selected number. |
void math::test_eval | ( | double | approx, |
double | expected, | ||
double | threshold ) |
Wrapper to evaluate if the approximated value is within .XX%
threshold of the exact value.
approx | aprroximate value |
exact | expected value |
threshold | values from [0, 1) |
T math::triangle_area | ( | T | base, |
T | height ) |
T math::triangle_perimeter | ( | T | base, |
T | height, | ||
T | hypotenuse ) |
T math::triangle_prism_volume | ( | T | base, |
T | height, | ||
T | depth ) |
The volume of a triangular prism.
base | The length of the base triangle |
height | The height of the base triangles |
depth | The depth of the triangular prism (the height of the whole prism) |