Check out this paper (PDF link) by Richard Fateman. The code samples are in Lisp, in but in any event, much of the secret boils down to minimizing the number of bignum (arbitrary precision integer) calculations you have to do. Naturally, if you don’t need/have bignums, it’s trivial; either a lookup table or a simple … Read more
This will work for the factorial (although a very small subset) of positive integers: unsigned long factorial(unsigned long f) { if ( f == 0 ) return 1; return(f * factorial(f – 1)); } printf(“%i”, factorial(5)); Due to the nature of your problem (and level that you have admitted), this solution is based more in … Read more
Python 2 uses the naive factorial algorithm: 1121 for (i=1 ; i<=x ; i++) { 1122 iobj = (PyObject *)PyInt_FromLong(i); 1123 if (iobj == NULL) 1124 goto error; 1125 newresult = PyNumber_Multiply(result, iobj); 1126 Py_DECREF(iobj); 1127 if (newresult == NULL) 1128 goto error; 1129 Py_DECREF(result); 1130 result = newresult; 1131 } Python 3 uses the … Read more
If you take multiplication as O(1), then yes, O(N) is correct. However, note that multiplying two numbers of arbitrary length x is not O(1) on finite hardware — as x tends to infinity, the time needed for multiplication grows (e.g. if you use Karatsuba multiplication, it’s O(x ** 1.585)). You can theoretically do better for … Read more
Here, a!! is defined as (a!)!. 123!!!!!! is absolutely gigantic. I think you’d need more particles than there are in the universe if you were to write it down in ink. You can’t therefore compare the numbers directly. I conject that there is not a number class that can do this. What you can do, … Read more
Even though it is commonly used for examples, the factorial function isn’t all that useful in practice. The numbers grow very quickly, and most problems that include the factorial function can (and should) be computed in more efficient ways. A trivial example is computing binomial coefficients. While it is possible to define them as choose … Read more
The main problem is that you never initialize result (to 1), so this: result=$(($result * $input)) is equivalent to this: result=$(( * $input)) which is not a valid arithmetic expression.
Factorials get large real fast: >>> math.factorial(170) 7257415615307998967396728211129263114716991681296451376543577798900561843401706157852350749242617459511490991237838520776666022565442753025328900773207510902400430280058295603966612599658257104398558294257568966313439612262571094946806711205568880457193340212661452800000000000000000000000000000000000000000L Note the L; the factorial of 170 is still convertable to a float: >>> float(math.factorial(170)) 7.257415615307999e+306 but the next factorial is too large: >>> float(math.factorial(171)) Traceback (most recent call last): File “<stdin>”, line 1, in <module> OverflowError: long int too large to convert to float You could … Read more
Here is my version, which works purely in integers (the division by k always produces an integer quotient) and is fast at O(k): function choose(n, k) if k == 0 return 1 return (n * choose(n – 1, k – 1)) / k I wrote it recursively because it’s so simple and pretty, but you … Read more
n can be arbitrarily large Well, n can’t be arbitrarily large – if n >= m, then n! ≡ 0 (mod m) (because m is one of the factors, by the definition of factorial). Assuming n << m and you need an exact value, your algorithm can’t get any faster, to my knowledge. However, if … Read more