Find the Factorial!

Question

Create the shortest program or function that finds the factorial of a non-negative integer.

The factorial, represented with ! is defined as such

$$n!:=\begin{cases}1 & n=0\\n\cdot(n-1)!&n>0\end{cases}$$

In plain English the factorial of 0 is 1 and the factorial of n, where n is larger than 0 is n times the factorial of one less than n.

Your code should perform input and output using a standard methods.

Requirements:

• Does not use any built-in libraries that can calculate the factorial (this includes any form of eval)
• Can calculate factorials for numbers up to 125
• Can calculate the factorial for the number 0 (equal to 1)
• Completes in under a minute for numbers up to 125

The shortest submission wins, in the case of a tie the answer with the most votes at the time wins.

Answer 1

Python, 25 bytes

f=lambda x:x<2or x*f(x-1)

Try it online!

This is a recursive lambda. It returns True if the factorial is 1 (inputs 1 and 0), but that's allowed by meta.

Answer 2

Python 2, 45 bytes

lambda n:reduce(long.__mul__,range(1,n+1),1L)

Try it online! Not the shortest Python solution but I thought it would be interesting to post a solution with reduce and long.__mul__.

Answer 3

Flurry, 32 bytes

{{}{<{}(<><<>()>{})>}[(<>())()]}

This is an anonymous function that takes an argument as a Church numeral and returns a Church numeral as output.

You can test it with the interpreter as follows:

$ ./Flurry -nin -c '{{}{<{}(<><<>()>{})>}[(<>())()]}{}' 9
362880

While the function itself returns quickly for N=125, the resulting Church numeral is too large to be practically useful for any purpose, including being converted into an integer and displayed by the interpreter.

Explanation

As with my Fibonacci answer, we're iterating a function \$n\$ times and storing an additional variable using the stack. In this case, the variable on the stack is the counter, so the step function looks like this:

next = λn. n * push(1 + pop())

This admits a straightforward translation that uses function composition for multiplication and <><<>()> for the successor function:

{<{} (<> <<> ()> {})>}

The main function is responsible for setting up initial values and calling next the appropriate number of times. It looks like this:

main = λn. push(0); n (next) (1)

The Church numeral representation of zero is λab. b; in other words, a constant function that ignores its argument and returns the identity function. By coincidence, the Church numeral representation of one is λab. ab, which is itself the identity function. Thus we can rewrite it as:

main = λn. n (next) (push(0) (arbitrary value))

This can again be translated directly:

{{} {<{}(<><<>()>{})>} [(<>()) ()]}

Answer 4

V (vim), 33 bytes

S<C-r>=r<Tab>1,<C-r>"<BS>)
<C-o>:%s/\n/*/g
<C-o>C<C-r>=<C-r>"<BS><BS>

Try it online!

Explanation:

S<C-r>=r<Tab>1,<C-r>"<BS>)  # Replace N with [1, ..., N]
<C-o>:%s/\n/*/g             # Merge all lines with *
<C-o>C<C-r>=<C-r>"<BS><BS>  # Remove trailing * and evaluate.

Overflows for any N greater than 49, but would work properly otherwise.

Answer 5

05AB1E, 4 bytes

Code:

L0KP

Explanation:

L     # Create the list [1, ..., input]
 0K   # Remove all occurencies of zero
   P  # Calculate the product

I have no idea why this works for 0, but it does.

Answer 6

Befunge - 2x20 = 40 characters

0\:#v_# 1#<\$v *\<
    >:1-:#^_$>\:#^_$

This is a function in that it is a standalone block of code not utilising the wraparound. You have to place the argument on the top of the stack then enter from the top-left going right, the function will exit from the bottom-right going right with the result on the top of the stack.

E.g. to calculate the factorial of 125

555**   0\:#v_# 1#<\$v *\<
            >:1-:#^_$>\:#^_$    .@

Testing 0

0   0\:#v_# 1#<\$v *\<
        >:1-:#^_$>\:#^_$    .@

Answer 7

J - 6 characters

*/>:i.

Does this count? I know it is very similar to the earlier J example, but it is a little shorter :)

I'm a beginner with J, but it's a lot of fun so far!

Answer 8

In C (23 Characters)

This abuses the GCC "feature" that makes the last assignment count as a return if no return is specified.

f(a){a=a>0?f(a-1)*a:1;}

In proper C, 28 characters

f(a){return a>0?f(a-1)*a:1;}

Answer 9

Haskell, 20

Gee, I sure hope folds don't count as built in functions...

f n=foldl(*)1[1..n]

Answer 10

Kona (11 6)

*/1.+!

K works right-to-left (for the most part), so we enumerate x (make a list/array of numbers from 0 to x-1), add 1 to it (list ranges 0 to x), then multiply all numbers together. If it weren't a requirement to compute 125!, I could save 1 more byte by eliminating . next to the 1. In any event, 125! is computed in mere milliseconds:

  */1.+!125.
1.882677e+209

Answer 11

BrainFuck, 125 / CompressedFuck, 47

,[>+>+>>>+<<<<<-]>>-<[[>[->+>+<<]>>[-<<+>>]<<<-]>>>>[<<<<+>>>>-]<<<<->[-]>[<+>-]<<[>>>>+>+<<<<<-]>>>>>[<<<<<+>>>>>-]<<<<<-]>.

In 8-bit text encodings the program had 1000 bits.

However, any BrainFuck program could be stored with a 3-bit encoding. 125*3=375

375 bits / 8 = 47 bytes

EDIT: In the CompressedFuck format it has 47 bytes :)

Also I forgot to mention that this program only works with infinite-sized cells

Answer 12

Pyth, 8 bytes

It's a shame that, 5 years after the challenge has been posted, there is no pyth answer. So I'm doing it now, even if it's ridiculous :). BTW, this is non-competiting, since the language is newer than the challenge...

Lu*GHSb1

You call it with yx, where x is a number. Test it here !

Explanation

Lu*GHSb1
L          Defines a lambda 'y' with argument 'b'
     Sb    Create a range from one to 'b' (function argument)  
  *GH      Lambda function that takes two arguments and multiply them
 u     1   Reduce the range with the above lambda.

Answer 13

Python, 35 bytes

def f(n):return n and n*f(n-1) or 1

or

def f(n):return n*f(n-1) if n else 1

Answer 14

Factor, 24 bytes

[ [1,b] 1 [ * ] reduce ]

Try it online!

Computes 125 factorial very quickly

-2 bytes thanks to @chunes

Factor, 12 bytes

[ [1,b] Π ]

Try it online!

Thanks to @chunes

Answer 15

Julia - 14 characters (19 with non-arbitrary-precision input)

f(n)=prod(1:n)

If you want it to work all the way up to n=125, precision becomes an issue. If requiring the input value to be "big" to match the output is unacceptable, then an extra 5 characters can be used to overcome the problem:

g(n)=prod(1:big(n))

big(n) converts n to an arbitrary precision integer, and the code remains in arbitrary precision from there. The alternative is, with the 14 character code above, making the input arbitrary precision - for instance, calling f(big(125)).

Edit: Note that the above was from 2014, and was for Julia 0.2. There are some tricks to squeeze the code down in modern Julia - for example, in Julia 1.8.5, !n=prod(1:n) is 12 characters, and can be used as !125, for example. Original answer kept as the "real" one for posterity.

Answer 16

PowerShell, 34

{($p=1)..$_-ge1|%{$p*=$_};$p}

Creates a list of numbers from one to the argument, selects those greater than or equal to one and multiplies those. For 0 the list 1, 0 will be created where then only 1 remains, yielding the correct answer.

To test:

> &{($p=1).."$args"-ge1|%{$p*=$_};$p} 125
1,88267717688893E+209

It's just a scriptblock; i.e. a function without a name.

Answer 17

Pico, 23

f(x):if(x=0,1,x*f(x-1))

but Pico max out at 12:

>f(12)
479001600

Answer 18

Golfscript, 10 chars:

~,{)}%{*}*

Answer 19

Ruby, 19

[1,*2..n].inject :*

The extra hardcoded 1 at the beginning makes it work for when n=0.
Ruby auto-converts to BigInt after a certain point, so it has 100% accuracy.

Answer 20

Mathematica

f = If[# > 0, # f[# - 1], 1] &
f[125] = 188267.....

Answer 21

Mathematica, 17

f = Times@@Range@#&

works more or less instantaneously for f[125].

Answer 22

Ruby, 35 characters,

def f(x);p 1.upto(x).inject(:*);end

Test:

f(5)

=> 120

Answer 23

Mathematica – 46 characters

f[x_]:=Integrate[(x+1)^(t-1)Exp[-x-1],{t,0,∞}]

This is using the integral definition of the Gamma Function.

Answer 24

R, 22 (9 w/o function def; 35 w/ recursion)

Simply

f=function(n)prod(1:n)

Or, without defining a function:

prod(1:n)

Or, recursive:

f=function(n)if(n<2)1 else n*f(n-1)

Answer 25

Swift: 43

var f:Double->Double;f={$0<1 ?0:f($0-1)*$0}

Swift is definitely not made for conciseness, but I though let's give it a try anyways. This solution is obviously recursive.

There's also the more native Swift way to do it which is a bit longer (57 characters):

let f={stride(from:1,through:$0,by:1.0).reduce(1){$0*$1}}

If it would be allowed to add an additional rule for very typey languages:

• You may add functions with the same behaviour as functions in the standard library for the purpose of shorter names

Then I would declare these two:

func ...(lhs: Double, rhs: Double) -> StrideThrough<Double> {
    return stride(from: lhs, through: rhs, by: 1)
}

extension SequenceType {
    func r<T>(initial: T, @noescape _ combine: (T, Self.Generator.Element) -> T) -> T {
        return reduce(initial, combine: combine)
    }
}

which redeclares stride(from: a, through: b, to:1.0) to a...b which I even think should be in the standard library, and reduce(a, combine: f) becomes r(a, f). This would one enable to do this:

let f={(1...$0).r(1,*)}

which would be 23 characters.

I'm even thinking about creating a Code Golf Swift extension, which just redeclares all the standard methods to something more concise.

Any of those can be called like:

f(0) // 0
f(120) // 6.689502913449124e+198
f(170) // 7.257415615307994e+306

All of them can go up to 170, where the result will be Double.infinity when above.

The times are as follows (for input 170):

recursive (43 chars): 0.00000101 s
native (rule-bend)  : 0.00000027 s
native              : 0.00000027 s

Answer 26

JavaScript ES6 21 chars

Note: I'm just extending Casey Chu's answer using ES6 with minor change

f=(n)=>n<2?1:n*f(n-1)

fiddle: Factorial

1) Does not use any built-in functions

2) Calculates factorial up to 170

3) Calculates factorial for 0 too

4) Execution time is less than a millisecond

Note: It will work only in browsers that supports ES6. FF(22+) and Chrome(45+) supports arrow functions as per MDN at the time of writing this answer.

Answer 27

Simplex v.0.5, 12 bytes

(The Docs page may be outdated; mainly, the * also increments the pointer and the J being the max of two elements.)

h*M{*LTRpM}]

This defines a macro that performs the factorial function on the current byte. It maintains the structure of the strip, but inserts an extra 0 at the next byte. You can delete this by adding another command p before the function ends.

This one works for inputs on a strip whose sole member is the input. I.e., a strip which looks like [N,/,/,...] (/ is the empty or null bit.) It clocks in at…

11 Bytes!!

This beats the GolfScript entry, FYI.

h{*M}pwT1J]

This is what it does:

h{*M}pwT1J]
h         ] ~~ define new macro
 {  }       ~~ repeat inside until zero met
  *         ~~ copy the current byte and increment pointer
   M        ~~ decrement byte
     p      ~~ remove trailing zero
      wT    ~~ spreads T (multiplication) across strip backwards; sets pointer to after the result
        1J  ~~ Takes the maximum of 1 and the current byte

---

Here the non-destructive version being used in an example code:

h*M{*LTRpM}p]ih0o

This defines the macro, asks for numeric input (i), calls the first macro (h0) and outputs the byte as a number (o).

Here is the pseudo-code I used:

Function factorial(N)
    A = N - 1
    While A > 1
        N = A * N
        A = A - 1
    End While
    Return N
End Function

This is the expanded explanation.

h    ~~ open macro, implicit [
 *   ~~ A=N [N,A]
 M   ~~ A=N-1 [N,A-1]
 {   ~~ Loop until current byte is zero
  *  ~~ [N,A-1,A-1]
  LT ~~ [N*(A-1),0,A-1]
  Rp ~~ [N*(A-1),A-1]
  M  ~~ [N*(A-1),A-2]
 }
 p   ~~ [N!]
]    ~~ close macro

Answer 28

Burlesque, 4 bytes

Burlesque has a built-in ?! to do that, but since that is forbidden by the rules we can just use ropd (runs in less than a fraction of a second):

blsq ) 125ropd
188267717688892609974376770249160085759540364871492425887598231508353156331613598866882932889495923133646405445930057740630161919341380597818883457558547055524326375565007131770880000000000000000000000000000000
blsq ) 5ropd
120
blsq ) 125?!
188267717688892609974376770249160085759540364871492425887598231508353156331613598866882932889495923133646405445930057740630161919341380597818883457558547055524326375565007131770880000000000000000000000000000000

Basically factorial is just the product of a list [1..N] and ro creates [1..N] and pd is the product of a list. Simple as that.

Answer 29

Python - 33

f=lambda n:n*(n and f(n-1))+(n<1)

Answer 30

JacobFck, noncompeting

43 bytes. This answer is noncompeting, because the language was invented after the challenge was posted.

Might be a bit late but this is too good to pass up.

<^0|=_s~$t$c:m^1^c|=_e-$c^t*$t_m:e^t>!:s^1>

Here is the commented and expanded: here