#include <iostream>
#include <ctime>
#include <NTL/ZZ.h>

#define PRINT_NUMBER 0

using namespace NTL;
typedef ZZ BigInt;

template <typename Function>
void testFactorial(BigInt number, const char* name, Function testFunction);
BigInt iterativeFactorial(BigInt number);
BigInt recursiveFactorial(BigInt number);
BigInt tailRecursiveFactorial(BigInt number);

int main()
{
	BigInt number{0};
	std::cout << std::fixed;

	while ( std::cin >> number )
	{
		testFactorial(number, "Iterative factorial     ", iterativeFactorial);
		testFactorial(number, "Tail recursive factorial", tailRecursiveFactorial);
		testFactorial(number, "Pure recursive factorial", recursiveFactorial);
		std::cout << "\n";
	}
}

template <typename Function>
void testFactorial(BigInt number, const char* name, Function testFunction)
{
	clock_t start = clock();
	BigInt factorial = testFunction( number );
	double duration = double(clock() - start) / CLOCKS_PER_SEC;
	std::cout << name << ": ";
  #if PRINT_NUMBER
	std::cout << factorial;
  #endif
	std::cout << " (" << duration << "s)\n";
}

BigInt iterativeFactorial(BigInt number)
{
	BigInt result{1};

	for ( BigInt current{1}; current <= number; ++current )
		result = result * current;

	return result;
}

BigInt recursiveFactorial(BigInt number)
{
	if ( number <= 0 )
		return BigInt{1};
	else
		return number * recursiveFactorial(number - 1);
}

BigInt tailRecursiveFactorial(BigInt number, BigInt accumulator)
{
	if ( number <= 0 )
		return accumulator;
	else
		return tailRecursiveFactorial( number - 1, accumulator * number );
}

inline BigInt tailRecursiveFactorial(BigInt number)
{
	return tailRecursiveFactorial(number, ZZ{1});
}