Best Answer

This is a non-recursive implementation of n factorial that supports arbitrary length decimal arithmetic. For very large values of n, you may need to tell your linker to increase the size of the run-time stack.

#include <stdlib.h>

#include <stdio.h>

/* Portable arbitrary length decimal iterative */

/* one node of a linked list of digits, the first node being low-order */

struct _decimal {

int digit;

struct _decimal *next;

};

typedef struct _decimal decimal;

/* Portable arbitrary length decimal iterative */

/* Initialize the list - necessary on second pass, if main recoded */

void decimal_initialize (decimal *d, int n) {

decimal *next, *nextsave;

d->digit = n;

nextsave = d->next;

d->next = NULL;

next = nextsave;

while (next != NULL) {

nextsave = next->next;

free (next);

next = nextsave;

}

return;

}

/* Portable arbitrary length decimal iterative */

/* Append a digit at the high order position */

void decimal_add_digit (decimal *d, int n) {

decimal *new_digit = (decimal*) malloc (sizeof (decimal));

while (d->next != NULL) d = d->next;

new_digit->digit = n;

new_digit->next = NULL;

d->next = new_digit;

return;

}

/* Portable arbitrary length decimal iterative */

/* Print the digits in reverse order - recursive */

void decimal_print_digits (decimal *d, int last_digit) {

if (d->next != NULL) decimal_print_digits (d->next, false);

printf ("%d", d->digit);

if (last_digit) printf("\n");

return;

}

/* Portable arbitrary length decimal iterative */

/* multiply the list by N */

void decimal_multiply (decimal *d, int N) {

int carry = 0;

while (d != NULL) {

d->digit = d->digit * N + carry;

carry = d->digit / 10;

d->digit %= 10;

if (carry != 0 && d->next 2) {

decimal_initialize (d, 2);

return;

}

while (N > 2) {

decimal_multiply (d, N);

N--;

}

return;

}

/* Generates all variations to show differences in results */

int main (int argc, char *argv[]) {

int N;

decimal Decimal = {2, NULL};

if (argc < 2) {

printf ("Enter N (or use command line) : ");

scanf ("%d", &N);

} else {

N = atoi (argv[1]);

}

printf ("Arbitrary: %u! = ", N);

decimal_NFactIterative (&Decimal, N);

decimal_print_digits (&Decimal, true);

return 0;

}

Study guides

☆

Q: Designing a non-recursive algorithm for factorial problem?

Write your answer...

Submit

Still have questions?

Related questions

While designing an algorithm as a solution to a given problem, we must take care of the following five important characteristics of an algorithm.

Recursion uses the output of an algorithm as input to the same algorithm, gradually reducing a complex problem to a simple problem that can easily be solved. For instance, given the positive value n, we can calculate the factorial of n with the following function: unsigned factorial (unsigned n) { return n * factorial (n-1); } This is the essence of recursion; a function that calls itself. However, as it stands, this function will call itself infinitely (or until the stack is full at least). Therefore we need to define an endpoint. That endpoint is always the simplest case, the point at which the problem is small enough to be solved. In this case, the problem is solved when n is less than 2: unsigned factorial (unsigned n) { if (n<2) return n; // else return n * factorial (n-1); } Thus if n is 0 or 1, the return value is 0 or 1 respectively. If n is 2, the return value is 2 * factorial (1), which is 2*1=2. Factorial 3 is therefore 3 * factorial(2) which becomes 3*2*1 = 6. And so on.

An algorithm is the numbers to be calculated to get an answer to a problem. It is the word problem in its basic numerical form.

An algorithm is a set of code that is used to solve a problem.

An algorithm is the process by which you solve a problem

algorithm is a step by step outline or flowchart how to solve a problem. program is an implemented coding of a solution to a problem based on the algorithm.

An algorithm is the statement of the methodology used to solve a problem. A program is the implementation of that algorithm.

This is the definition of an algorithm - a list of orders of how to solve a given programming problem.

An algorithm is a statement of how a particular problem will be solved. Coding is the implementation of that algorithm in a particular language.

An algorithm defines the specific steps required to solve a problem. A computer program is the implementation of an algorithm.

An algorithm is a set of steps used to solve a specific problem. So in order to make one, you need to identify a problem and figure out a solution to that problem. Write down the solution in a step-by-step manner and you have yourself an algorithm.

algorithm is a way to solve your problem

People also asked