12

4

With the recent Python bashing, here's an attempt to show Python's strengths.
Your challenge is to write a program that calculates the factorial of as high a number `n`

as possible within 10 seconds.

Your score will be `(highest n for your program on your machine)/(highest n for my program on your machine)`

## Rules

- You must calculate an exact integer solution. Since the factorial would be much higher than what can fit in a 64 bit unsigned integer, you can use strings if your language does not support large integers
- Standard loopholes are forbidden. Particularly, you cannot use any external resources.
- Only the calculation part(this includes time for any workarounds using strings) adds to the total time which should be under 10 seconds on average.
- Single threaded programs only.
- You must store the output in an easily printable form (as printing takes time) (see my program below), string, variable, character array, etc.

EDIT:

- Your program must give the correct output for all
`n`

:`1 <= n <= (your highest n)`

EDIT2:

- I hate to say this explicitly but using your language's built-in factorial functions falls under the standard loopholes http://meta.codegolf.stackexchange.com/a/1078/8766 Sorry Mathematica and Sage

## My program

```
from __future__ import print_function
import time
def factorial( n ):
return reduce( ( lambda x , y : x * y ) , xrange( 1 , n + 1 ) , 1 )
start = time.clock()
answer = factorial( 90000 )
end = time.clock()
print ( answer )
print ( "Time:" , end - start , "sec" )
```

Highest score wins.
For the record, my code can manage `n = 90000`

in about `9.89`

seconds on a Pentium 4 3.0 GHz

**EDIT:** Can everyone please add the *score* rather than just the highest *n*. Just the highest `n`

has no meaning by itself as it depends on your hardware. It's impossible to have an objective winning criterion otherwise. ali0sha's anwer does this correctly.

We have a winner. I didn't accept the java answer https://codegolf.stackexchange.com/a/26974/8766 as it kind of skirts close to http://meta.codegolf.stackexchange.com/a/1080/8766

1You can use

`operator.mul`

instead of the lambda function – gnibbler – 2014-05-06T11:57:59.473You should probably add that

`print([1, 2, 6, 10, 50, 120, ...][n])`

is invalid. – Doorknob – 2014-05-06T12:09:26.4631Bit suprised this works, but assuming I read the rules correctly this MATLAB solution would be nice:

`factorial(Inf)`

, returns`Inf`

in a fraction of a second. – Dennis Jaheruddin – 2014-05-06T12:40:35.777Is my assumption that you are looking for an answer in [python] correct? – Justin – 2014-05-06T12:44:26.267

1@Doorknob That fits in the standard loopholes. – Justin – 2014-05-06T12:44:43.553

1@DennisJaheruddin, it's a bit of a stretch to refer to "Inf" as an "exact integer solution". – tobyink – 2014-05-06T13:12:27.833

How is bigint math a "strength" of Python? It doesn't even use GMP. – Niklas B. – 2014-05-06T13:35:47.197

1@Quincunx No, any language is allowed. – user80551 – 2014-05-06T17:22:51.027

@NiklasB. "It doesn't even use GMP."--I just used the simplest code so that others can make it more efficient – user80551 – 2014-05-06T17:37:50.833

@user80551 I was referring to your statement "here's an attempt to show Python's strengths", because this is clearly

nota task where Python can shine (unless you use bindings to non-standard libraries). Still a valid challenge, of course :) – Niklas B. – 2014-05-06T17:41:52.553@NiklasB. Hence the word

`attempt`

, Do you want me to change it to`lame attempt`

or something? – user80551 – 2014-05-06T17:50:26.350http://cs.stackexchange.com/questions/14456/factorial-algorithm-more-efficient-than-naive-multiplication – Guy Sirton – 2014-05-06T18:02:49.937

@NiklasB. C/C++ don't even

havea bigint class at all. In fact python's bigints are quite fast compared to other bigints implementations (I believe F# is about 3 times slower from a comment I receive some day ago...) If you want to include languages that can load/import a bigint implementation, so can python. In summary: I don't see the point of your comment. – Bakuriu – 2014-05-06T19:11:33.427@Bakuriu Sure, but Ruby, Haskell or other languages that use GMP by default will beat it hands down. Although I admit that my comment was lacking a proper point :) Nevermind – Niklas B. – 2014-05-06T19:12:32.033

1@NiklasB. Are you sure? Because on my machine Haskell is about tens of times slower at computing factorials... In fact I get a stackoverflow with the factorial of 1000000. Python's built-in

`math.factorial`

computes it without problems in about 12 seconds. – Bakuriu – 2014-05-06T19:28:47.8131@Bakuriu Interesting, I can reproduce that. Seems like Python 3 is about 10 times faster than Python 2.7, nice. I will definitely shut my mouth now :) Not sure why Haskell is so slow actually – Niklas B. – 2014-05-06T20:48:35.370

Oh god you seriously implemented this with a reduce and a lambda? Really really inefficient even for python. – Claudiu – 2014-05-07T02:53:18.897

@Claudiu See my previous comment to Niklas B. , I just used the simplest method that came to my mind and didn't bother optimizing. Optimizing the code is part of the challenge. – user80551 – 2014-05-07T05:23:03.897

Could the down-voter please explain what's wrong with the question? – user80551 – 2014-05-07T09:04:01.550

How can someone measure the correct score if they're using a much more powerful CPU than you? – phuclv – 2014-06-15T10:17:42.587

I really wished that someone would provide a creative solution with bitshifts and lots of recursion. – Simon Kuang – 2014-07-28T00:07:50.557