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

                                                {
    uint64_t res = 1;
    for (uint64_t i = n;; i -= 2) {
        if (i == 0 || i == 1)
            return res;
        res *= i;
    }
    return res;
}

double_factorial_recursive()

uint64_t double_factorial_recursive

(

uint64_t

n

)

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

                                                {
    if (n <= 1)
        return 1;
    return n * double_factorial_recursive(n - 2);
}

Here is the call graph for this function:

main()

int main

(

void

)

Main function

           {
    tests();
    return 0;
}

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]	n	number to check double factorial for
[in]	expected	expected result

                                         {
    assert(double_factorial_iterative(n) == expected);
    assert(double_factorial_recursive(n) == expected);
}

Here is the call graph for this function:

tests()

void tests

(

)

Test implementations

             {
    std::cout << "Test 1:\t n=5\t...";
    test(5, 15);
    std::cout << "passed\n";
 
    std::cout << "Test 2:\t n=15\t...";
    test(15, 2027025);
    std::cout << "passed\n";
 
    std::cout << "Test 3:\t n=0\t...";
    test(0, 1);
    std::cout << "passed\n";
}

Here is the call graph for this function: