Factorial calculation

[akeub]

you illiterate theologists!
here is the problem ..
you have to calculate n!
that is an integer, for those who haven't noticed
the calculation will complete after n steps
so time is not an issue (at least for n=73)
what apears to be our problem is
that in a language like c
no default arithmetic variable type is "large enough"
to handle the results' storage

after a little search:
http://www.google.com/search?hl=en&ie=U ... gle+Search
http://primes.utm.edu/links/programs/large_arithmetic/

using malloc, realloc for the implementation scheme is piece of cake
the hard biscuit would be to condact a multiplication
if memory serves correctly,
in digital circuits design a multiplication between two numbers in binary form, is farely trivial
since you either multiply with one (copy paste)
or zero (nullify the entire line)
perhaps some more ram might be needed
but unlikely you can find a faster algorithm
(i wonder what those arithmetic coprocessors are for)

now in regard with fibonacci,
which idiot would ever use top down recursion to solve it ??
after the first time you try,
you wont attempt another!
or you will be dead long before it ever finish ..


combinatorics! what a fabulous word, it makes a rhyme i think
you may have order, or disorder
element duplication, or clone elimination
for instance, when you wish to print the possible permutations of n objects to k boxes:

void foo(int n, int k, int p[], int i) {

int j;

if (i==k) { //permutation complete
printt(p,k); //p[] is an array of k boxes
return;
}

for (j=0; j<n; j++) { //n possible values..
p= j;
foo(n,k,p,i+1); //recursion!!
}
}

as you may have noticed, the easiest case (above) is the one
where you might run into printouts like 75667333333
or where 8254 is distinct from 4528
if on the other hand, are attempting to implement a set,
chaos mechanics rule:

void goo(int n, int k, int p[], int i, int j) {

if (i==k) {
...
}

for ( ; j<n; j++) {
p= j;
goo(n,k,p,i+1,p); //most amusing..
}
}

in the rare occasion when you dont wish for a value to be repeated, you must explicitly say so:

#define FREE 38745
#define TAKEN -845

void hoo(int n, int k, int p[], int i, int q[]) {

int j;

if (i==k) {
...
}

for (j=0; j<n; j++) {
if (q[j]==FREE) { //q[] is a log table of size n
q[j]= TAKEN;
p= j;
hoo(n,k,p,i+1,q);
q[j]= FREE; //dont forget!
}
}
} //q[] should have been initialized to FREE (u careless punks..)

the last case, of a set with no dublicates, is gracefully left as an exercise .. (usually n>=k, but you may find an exception)

naturally, the question still remains .. what do you want n! for ?!?

[Eero Ränik]

akeub, would you please consider using less line breaks? Otherwise, it's a bit hard to read your posts...

[Schol-R-LEA]

It seems that in the whole discussion, an important fact has been lost: the original poster almost certainly was a student trying to Tom Sawyer his way of doing his own homework. I was perfectly willing to give hints on how to solve the problem, or even explaining that it was a trick question (one can be pretty sure that the teacher did not intend for his students to actually write a bignum library just to solve it), but I have no intention on doing it for him - especially since the assignment is surely just a memory now.

Oh, and I would like to recommend to our poetic friend that he sign in and create an account with the forum. Prosaic as it is, it does help if the person you are communicating with sticks to a single user name...

[aejhg]

u wish!

(-

[Therx]

I suspect this could get nasty!

Also don't think that by using random guest names you are completely anon. clicking the IP at the bottom of your posts tells anyone who wants to know exactly where you are.

Pete

[Schol-R-LEA]

Now, let's not pressure him; if he (or she) doesn't want to sign in, that's his choice. No point in getting argumentative.

OTOH, it's hard to take someone seriously if they play games like that. Which is a shame, since it does sound like he's got something to say.

[Therx]

I don't think they've got to sign up just they should use the same name each time. Just so that everyone else knows who it is.

Pete