Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Factorial functions I wrote during 42’s entrance exam
/* ************************************************************************** */
/* */
/* ::: :::::::: */
/* ft_iterative_factorial.c :+: :+: :+: */
/* +:+ +:+ +:+ */
/* By: dtortera <42@diti.me> +#+ +:+ +#+ */
/* +#+#+#+#+#+ +#+ */
/* Created: 2013/07/22 09:46:40 by dtortera #+# #+# */
/* Updated: 2013/07/22 16:28:46 by dtortera ### ########.fr */
/* */
/* ************************************************************************** */
/*
** Iteratively computes a factorial. When computation fails (like when input
** number `nb` is negative, or when an overflow occurs), return 0. Else returns
** the computed factorial (also, 0! = 1). Overflow detection uses XOR comparison
** (bitwise operator ^). Say, we want to multiply 4-bit signed numbers (i.e.
** sign on left bit, and 2^3-1 = 7 values), like 6 * 5 = 30. In binary form:
** 0110 * 0101 = 11110. Notice how the 4th bit changed during the overflow? We
** ^ ^ ^ check that at each operation: result_old ^ result. If
** the XOR operation returns a negative number (leftmost
** bit set to 1), we know an overflow occured, and we exit with error code 0.
*/
int ft_iterative_factorial(int nb)
{
int result;
int result_old;
result = 1;
if (nb < 0)
return 0;
else
{
while (nb != 0)
{
result_old = result;
result = nb * result;
if ((result_old ^ result) < 0)
return 0;
else
nb--;
}
return result;
}
}
/* ************************************************************************** */
/* */
/* ::: :::::::: */
/* ft_recursive_factorial.c :+: :+: :+: */
/* +:+ +:+ +:+ */
/* By: dtortera <42@diti.me> +#+ +:+ +#+ */
/* +#+#+#+#+#+ +#+ */
/* Created: 2013/07/22 16:37:53 by dtortera #+# #+# */
/* Updated: 2013/07/22 21:12:52 by dtortera ### ########.fr */
/* */
/* ************************************************************************** */
/*
** Recursively computes a factorial. When computation fails (like when input
** number `nb` is negative, or when an overflow occurs), return 0. Else returns
** the computed factorial (also, 0! = 1). Overflow detection uses XOR comparison
** (bitwise operator ^), which means it detects sign changes (equivalent to a
** `if (result_old + result < 0)` check), and only sign changes. Insofar as
** this function is not iterative, we cannot perform iteration-by-iteration
** checks. As a result: this function will only start to detect the overflow
** for 17!, not 14! like it should be.
*/
int ft_recursive_factorial(int nb)
{
int result;
int signed_int_max;
signed_int_max = (int) (~0U >> 1);
if (nb < 0)
return 0;
else if (nb == 0)
return 1;
else
{
result = nb * ft_recursive_factorial(nb - 1);
return ((~signed_int_max ^ result) < 0) ? result : 0;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.