Algorithms_in_C++ 1.0.0
Set of algorithms implemented in C++.
Loading...
Searching...
No Matches
double_factorial.cpp File Reference

Compute double factorial: \(n!!\). More...

#include <cassert>
#include <iostream>
Include dependency graph for double_factorial.cpp:

Functions

uint64_t double_factorial_iterative (uint64_t n)
 
uint64_t double_factorial_recursive (uint64_t n)
 
void test (uint64_t n, uint64_t expected)
 
void tests ()
 
int main ()
 

Detailed Description

Compute double factorial: \(n!!\).

Double factorial of a non-negative integer n, is defined as the product of all the integers from 1 to n that have the same parity (odd or even) as n.
It is also called as semifactorial of a number and is denoted by \(n!!\)

Function Documentation

◆ double_factorial_iterative()

uint64_t double_factorial_iterative ( uint64_t n)

Compute double factorial using iterative method

17 {
18 uint64_t res = 1;
19 for (uint64_t i = n;; i -= 2) {
20 if (i == 0 || i == 1)
21 return res;
22 res *= i;
23 }
24 return res;
25}

◆ double_factorial_recursive()

uint64_t double_factorial_recursive ( uint64_t n)

Compute double factorial using resursive method.
Recursion can be costly for large numbers.

30 {
31 if (n <= 1)
32 return 1;
33 return n * double_factorial_recursive(n - 2);
34}
uint64_t double_factorial_recursive(uint64_t n)
Definition double_factorial.cpp:30
Here is the call graph for this function:

◆ main()

int main ( void )

Main function

67 {
68 tests();
69 return 0;
70}
void tests()
Definition double_factorial.cpp:50
Here is the call graph for this function:

◆ test()

void test ( uint64_t n,
uint64_t expected )

Wrapper to run tests using both recursive and iterative implementations. The checks are only valid in debug builds due to the use of assert() statements.

Parameters
[in]nnumber to check double factorial for
[in]expectedexpected result
42 {
43 assert(double_factorial_iterative(n) == expected);
44 assert(double_factorial_recursive(n) == expected);
45}
uint64_t double_factorial_iterative(uint64_t n)
Definition double_factorial.cpp:17
Here is the call graph for this function:

◆ tests()

void tests ( )

Test implementations

50 {
51 std::cout << "Test 1:\t n=5\t...";
52 test(5, 15);
53 std::cout << "passed\n";
54
55 std::cout << "Test 2:\t n=15\t...";
56 test(15, 2027025);
57 std::cout << "passed\n";
58
59 std::cout << "Test 3:\t n=0\t...";
60 test(0, 1);
61 std::cout << "passed\n";
62}
static void test()
Self-test implementations.
Definition generate_parentheses.cpp:82
Here is the call graph for this function: