81
\$\begingroup\$

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.

\$\endgroup\$
13
  • 13
    \$\begingroup\$ How many of the given answers can actually compute up to 125! without integer overflow? Wasn't that one of the requirements? Are results as exponential approximations acceptable (ie 125 ! = 1.88267718 × 10^209)? \$\endgroup\$
    – Ami
    Feb 6 '11 at 22:43
  • 7
    \$\begingroup\$ @SHiNKiROU, even golfscript can manage 125! less than 1/10th of a second and it's and interpreted interpreted language! \$\endgroup\$
    – gnibbler
    Feb 8 '11 at 3:21
  • 6
    \$\begingroup\$ @ugoren the two-character solution to the other question uses a built-in factorial function. That's not allowed in this version of the challenge. \$\endgroup\$ Jan 7 '14 at 3:18
  • 5
    \$\begingroup\$ Completes in under a minute seems a very hardware-dependent requirement. Completes in under a minute on what hardware? \$\endgroup\$
    – sergiol
    Aug 24 '17 at 18:05
  • 4
    \$\begingroup\$ @sergiol Incredibly that hasn't been an issue in the last 2 years, I suspect most languages can get it done in under a minute. \$\endgroup\$ Aug 24 '17 at 21:20

191 Answers 191

1
2
3 4 5
7
4
\$\begingroup\$

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:

{{} {<{}(<><<>()>{})>} [(<>()) ()]}
\$\endgroup\$
3
\$\begingroup\$

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-:#^_$>\:#^_$    .@
\$\endgroup\$
1
  • \$\begingroup\$ I know this is pretty old, but I think this is somewhat shorter and quicker : &:!#@_>:# 1# -# :# _$>\# :#* _$.@ (where & should be replaced by the input). It's 32 chars/bytes \$\endgroup\$
    – FliiFe
    Apr 7 '16 at 11:08
3
\$\begingroup\$

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!

\$\endgroup\$
3
\$\begingroup\$

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;}
\$\endgroup\$
1
  • \$\begingroup\$ +1 for the GCC "feature". I think GCC even allows a block return value (Can remember doing something like this) 0 == ({printf("Hello, world!"); 0;}); \$\endgroup\$
    – yyny
    Feb 6 '16 at 16:11
3
\$\begingroup\$

Haskell, 20

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

f n=foldl(*)1[1..n]
\$\endgroup\$
1
  • \$\begingroup\$ product is probably shorter \$\endgroup\$
    – univalence
    Aug 5 '19 at 18:15
3
\$\begingroup\$

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
\$\endgroup\$
2
  • \$\begingroup\$ You don't need a lot of this. K has currying, so the entire answer becomes */1.+!: 6 bytes. \$\endgroup\$ Jun 25 '15 at 14:43
  • \$\begingroup\$ @kirbyfan64sos: True & I'll edit it in. I think when I wrote this ~18 months ago, I was still stuck on everything must be callable (i.e., function). \$\endgroup\$
    – Kyle Kanos
    Jun 25 '15 at 15:00
3
\$\begingroup\$

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

\$\endgroup\$
3
  • \$\begingroup\$ Still impressive. \$\endgroup\$
    – Sainan
    Feb 5 '16 at 11:05
  • \$\begingroup\$ Take a look at esolangs.org/wiki/CompressedFuck. But code-golf is more about competing with other programs in the same language than it is about competing with the rest, and 125 characters for brainfuck is pretty impressive :) \$\endgroup\$
    – yyny
    Feb 6 '16 at 16:15
  • \$\begingroup\$ @YoYoYonnY thanks, I updated the answer \$\endgroup\$
    – KeksArmee
    Feb 8 '16 at 12:40
3
\$\begingroup\$

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.
\$\endgroup\$
4
  • 1
    \$\begingroup\$ L*F+1Sb is a bit shorter. \$\endgroup\$ Apr 9 '16 at 19:08
  • \$\begingroup\$ @FryAmTheEggman What kind of sorcery is this ? \$\endgroup\$
    – FliiFe
    Apr 9 '16 at 19:38
  • \$\begingroup\$ F is fold, basically a reduce over the list, it expands pretty much into what you did, but without the start at 1 thing. So I manually add a 1 to the list Sb creates, which of course won't change the product. \$\endgroup\$ Apr 9 '16 at 19:40
  • \$\begingroup\$ @FryAmTheEggman I still have a lot to learn... \$\endgroup\$
    – FliiFe
    Apr 9 '16 at 20:20
3
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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
\$\endgroup\$
2
  • 3
    \$\begingroup\$ I posted a shorter similar solution. No need to repeat it you don't have an extra insight. \$\endgroup\$
    – Alexandru
    Feb 7 '11 at 12:33
  • \$\begingroup\$ @Alexandru if he wrote this without referencing your answer, I don't see why he shouldn't be allowed to post it just because it's longer. All Runners in a race get to post their score regardless of being first or last. \$\endgroup\$
    – akozi
    Feb 20 '19 at 14:49
3
+100
\$\begingroup\$

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

\$\endgroup\$
2
  • 1
    \$\begingroup\$ No need to print the result inside your function -- you can let it return the result to the data stack instead. Here's a simpler input setup as well: Try it online! \$\endgroup\$
    – chunes
    Mar 26 at 9:45
  • 1
    \$\begingroup\$ Now consider there's already a word for a multiplying reduce -- product. And the math.unicode vocabulary can shorten product to Π. Try it online! \$\endgroup\$
    – chunes
    Mar 26 at 9:48
3
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ Why does the list in the range [1,N] for N=0 becomes [0].. I did know taking the product of [] becomes 1. Both seem to be the ideal situation for the 0 edge-case here.. xD \$\endgroup\$ Aug 9 '18 at 14:04
  • 1
    \$\begingroup\$ ݦP is one byte shorter. \$\endgroup\$
    – Grimmy
    May 29 '19 at 13:28
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

C#: 37

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

\$\endgroup\$
3
  • 2
    \$\begingroup\$ This function returns 1 always. \$\endgroup\$
    – Alexandru
    Jul 4 '11 at 11:15
  • \$\begingroup\$ whoopsies, you're right. \$\endgroup\$
    – Origamiguy
    Jul 10 '11 at 12:38
  • 3
    \$\begingroup\$ int is way too small to hold 125!, which is something like 1.88e+209. \$\endgroup\$ Jul 12 '11 at 19:05
2
\$\begingroup\$

Pico, 23

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

but Pico max out at 12:

>f(12)
479001600
\$\endgroup\$
2
  • \$\begingroup\$ Does it work with 125? \$\endgroup\$ Jan 11 '12 at 2:45
  • 1
    \$\begingroup\$ @userunknown No, it doesn't as Pico's number type has the same limits as C's int. and fixing it so that it could would require implementing big integer multiplication and that would require at least 500-4000 characters. \$\endgroup\$
    – Dan D.
    Jan 11 '12 at 9:55
2
\$\begingroup\$

Golfscript, 10 chars:

~,{)}%{*}*
\$\endgroup\$
2
\$\begingroup\$

Mathematica

f = If[# > 0, # f[# - 1], 1] &
f[125] = 188267.....
\$\endgroup\$
1
  • 1
    \$\begingroup\$ If[#>0,#0[#-1]#,1]& 19 bytes \$\endgroup\$
    – ZaMoC
    May 31 '20 at 8:37
2
\$\begingroup\$

Mathematica, 17

f = Times@@Range@#&

works more or less instantaneously for f[125].

\$\endgroup\$
1
  • 1
    \$\begingroup\$ 1##& is 1 byte shorter than Times \$\endgroup\$
    – LLlAMnYP
    Jan 19 '17 at 10:01
2
\$\begingroup\$

Ruby, 35 characters,

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

Test:

f(5)

=> 120

\$\endgroup\$
2
\$\begingroup\$

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)).

\$\endgroup\$
1
  • \$\begingroup\$ And it works fast enough even for ridiculously high n. For n=100,000 my old i5-2410 laptop needs only 10.3 seconds. Displaying the 456,574 digits of the result is kind of a problem, though ;) At first I didn’t see that there already was a Julia solution. I would have almost made a double post. \$\endgroup\$
    – M L
    Jun 28 '15 at 7:44
2
\$\begingroup\$

Bash+coreutils, 21 bytes

seq $1|paste -sd\*|bc
\$\endgroup\$
2
\$\begingroup\$

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)
\$\endgroup\$
3
  • 1
    \$\begingroup\$ Only the last will work entirely (i.e. give 1 for n=0). A shorter solution would be : ifelse((n=scan())>0,prod(1:n),1), with 32 bytes. \$\endgroup\$
    – Frédéric
    Aug 26 '16 at 16:11
  • \$\begingroup\$ @Frédéric or better yet "if"((n=scan())>0,prod(1:n),1) for 30 bytes. \$\endgroup\$
    – Giuseppe
    Aug 24 '17 at 17:34
  • 2
    \$\begingroup\$ @Giuseppe 0^(n=scan())+prod(1:n) is 22 bytes. \$\endgroup\$ Oct 31 '19 at 7:33
2
\$\begingroup\$

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
\$\endgroup\$
3
  • \$\begingroup\$ Why is it var f:Double->Double? Isn't that declaring the type twice? var seems to declare it to be of "variable" type, whereas Double->Double seems to declare it to be a function that accepts a double and returns a double. If this is not the case, can I get an explanation of the type signature for someone who doesn't know swift? \$\endgroup\$
    – Cyoce
    Feb 5 '16 at 6:21
  • \$\begingroup\$ @Cyoce If I was using let instead, the compiler would complain because I'm using the function itself in its definition without it being declared beforehand. By using var we can trick the compiler into thinking that f is declared already. \$\endgroup\$
    – Kametrixom
    Feb 5 '16 at 13:30
  • \$\begingroup\$ ok, thanks for the clarification \$\endgroup\$
    – Cyoce
    Feb 5 '16 at 15:56
2
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ You don't need parens around the argument. f=n=>… is fine. \$\endgroup\$
    – Cyoce
    Jan 27 '16 at 3:34
2
\$\begingroup\$

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
\$\endgroup\$
0
2
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ Does this account for 0!=1? \$\endgroup\$ Nov 23 '15 at 20:16
  • 1
    \$\begingroup\$ Yes, because pd (Product) is defined to be 1 for empty lists. \$\endgroup\$
    – mroman
    Nov 24 '15 at 9:37
2
\$\begingroup\$

Python - 33

f=lambda n:n*(n and f(n-1))+(n<1)
\$\endgroup\$
1
  • \$\begingroup\$ We already have this shorter answer using the same approach. \$\endgroup\$
    – lirtosiast
    Jan 24 '16 at 23:25
2
\$\begingroup\$

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

\$\endgroup\$
2
\$\begingroup\$

Python, 29 bytes

f=lambda x:x and x*f(x-1)or 1
\$\endgroup\$
2
\$\begingroup\$

JavaScript, 52 bytes

function f(m){n=1;for(i=1;i<=m;i++){n*=i;}return n;}
\$\endgroup\$
1
  • \$\begingroup\$ You can shorten that too function f(m){for(n=i=1;i<=m;)n*=i++;return n}. It's 6 character in less. \$\endgroup\$
    – HoLyVieR
    Feb 7 '11 at 3:57
1
2
3 4 5
7

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.