75
\$\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\$
  • 11
    \$\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
  • 6
    \$\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
  • 5
    \$\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\$ – Michael Stern Jan 7 '14 at 3:18
  • 4
    \$\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\$ – Kevin Brown Aug 24 '17 at 21:20

180 Answers 180

1
\$\begingroup\$

Clam, 9 7 bytes

p;#qB1Q

-2 bytes thanks to ASCII-only

Explanation

p;#qB1Q - Implicit Q = first input
p       - Print...
 ;      - Product of...
    B1Q - Range(1...Q) OR Range(Q...1) if (Q < 1)
  #q    - Where (q => q) ie (q != 0)
\$\endgroup\$
  • \$\begingroup\$ get it on tio or GH pages pls. also 7: p;#qB1Q. alternatively, p;#>q0B1Q \$\endgroup\$ – ASCII-only May 3 at 6:47
  • \$\begingroup\$ @ASCII-only waiting for Dennis to pull the latest version \$\endgroup\$ – Skidsdev May 3 at 13:03
  • \$\begingroup\$ argh bad paste, was p|;B1Q1 or something \$\endgroup\$ – ASCII-only May 3 at 13:09
1
\$\begingroup\$

><>, 14 bytes

1$:@?!n$:1-@*!

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Julia 1.0, 12 bytes

n->prod(1:n)

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Dreaderef, 47 bytes

"??"-14"?"-1"?"*-1" "-1" "

Try it online! Takes input from command-line arguments.

This file contains unprintables. A hexdump is provided below:

00000000: 2201 1604 043f 0703 3f22 2d31 3422 0b02  "....?..?"-14"..
00000010: 3f1c 222d 3122 0116 1303 013f 1202 222a  ?."-1".....?.."*
00000020: 2d31 2216 0120 222d 3122 0112 2005 22    -1".. "-1".. ."

Ungolfed, the program looks like this:

; Jump to 28 if N = 0
0.   deref 22 4
3.   bool  ?  7
6.   mul   ?  -14 11
10.  add   ?  28  -1

; R = R * N
14.  deref 22 19
17.  mul   1  ?   18

; N = N - 1
21.  add   *  -1  22

; Jump to start
25.  deref 32 -1

; Print R
28.  deref 18 32
31.  numo  ?

There are two variables: N, which is located at position 22 and initialized to the input integer, and R, which is located at position 18 and initialized to 1.

\$\endgroup\$
1
\$\begingroup\$

8088 / 8087 machine code, 37 36 34 bytes

Unassembled:

8B F4           MOV  SI, SP             ; save stack position to load into FPU next
50              PUSH AX                 ; save N to top of stack 
9B              FWAIT                   ; synchronize CPU and FPU 
DF 04           FILD WORD PTR[SI]       ; load N into ST(0) 
50              PUSH BX                 ; push return address of 0000 to stack              
            FACT PROC                   ; fall through to start recursion 
55              PUSH BP                 ; save BP 
8B EC           MOV  BP, SP             ; point BP to top of stack 
8B 46 04        MOV  AX, [BP+4]         ; AX = N 
48              DEC  AX                 ; decrement N 
75 06           JNZ  NEXT               ; if N > 1, continue recursion 
D9 E8           FLD1                    ; otherwise, return 1 
EB 09           JMP  DONE               ; end recursion 
            NEXT: 
50              PUSH AX                 ; save N on stack 
E8 0109         CALL FACT               ; recursive call 
9B              FWAIT                   ; synchronize CPU and FPU
DE 4E 04        FIMUL WORD PTR[BP+4]    ; accumulate result in ST(0) * N 
            DONE: 
5D              POP  BP                 ; restore BP 
C2 0002         RET  2                  ; remove N from stack and return 
            FACT ENDP 

A recursive solution (at the machine code level) using only the 8088 CPU, and the 8087 FPU to calculate the factorial sum at 80-bit double-extended precision.

Input \$n\$ is in AX, output \${n!}\$ is in ST(0). Test output displayed using Borland Turbo Debugger 3:

n = 1:

enter image description here

n = 15:

enter image description here

n = 50:

enter image description here

n = 125:

enter image description here

Notes:

  • Calculates \${125!}\$ in an imperceptible amount of time (difficult to accurately profile in DOS)
  • Specifically targeted to 8088 CPU (even includes FWAITs) to run on an original IBM PC (with FPU installed)
  • Language is not newer than the challenge
\$\endgroup\$
1
\$\begingroup\$

Julia, 14 characters

f(n)=prod(1:n)

although I think recursive implementations are more interesting for this challenge. The best I could do there was 18 characters:

f(n)=n<1||n*f(n-1)

for n = 125, note that one has to use a BigInt like this:

julia> f(big(125))
188267717688892609974376770249160085759540364871492425887598231508353156331613598866882932889495923133646405445930057740630161919341380597818883457558547055524326375565007131770880000000000000000000000000000000

Both complete in much less than a second.

\$\endgroup\$
1
\$\begingroup\$

Wren, 34 bytes

Generate range from a to 1 and then reduce it with product of this whole sequence.

Fn.new{|a|(a..1).reduce{|a,b|a*b}}

Try it online!

\$\endgroup\$
1
\$\begingroup\$

@, 8 bytes

#*¨1^ň

Explanation

     ň Input a single number from STDIN
    ^  Increment this number
  ¨1   Exclusive range from 1 to this number
#*     Fold multiplication over this vector
\$\endgroup\$
0
\$\begingroup\$

PHP, 13

Might sound like cheating, but in PHP it's just:

gmp_fact($n);

Will get you 100% precision, but it won't always be fast, especially for larger numbers.

\$\endgroup\$
  • \$\begingroup\$ Does not use any built-in libraries that can calculate the factorial \$\endgroup\$ – user unknown Jan 11 '12 at 2:44
  • 3
    \$\begingroup\$ Ah, so it is cheating. \$\endgroup\$ – Mr. Llama Jan 11 '12 at 15:13
0
\$\begingroup\$

F# based on cfern's 63 36 characters

His didn't work on 125 for me. Adapted to use BigInteger

let f n:BigInteger=Seq.fold(*)BigInteger.One{BigInteger.One..n}

Edit: I just realized that double works too.

let f n:double=Seq.fold(*)1.{1.0..n}
\$\endgroup\$
0
\$\begingroup\$

MuPAD – 7

`*`($n)

Computes n!, no recursion.

\$\endgroup\$
0
\$\begingroup\$

Clojure, 29

#(reduce * (range 1 (inc %)))
\$\endgroup\$
0
\$\begingroup\$

Python 3 - 52 characters

r=n=int(input())
for i in range(1,n):r=r*i
print(r)

This is my best try. My C++ solution (not posted) was over 100 characters even without #includes and whitespace!

\$\endgroup\$
  • \$\begingroup\$ You may discard prompt string in input \$\endgroup\$ – AMK Jan 7 '14 at 0:23
  • 2
    \$\begingroup\$ Can't you do r*=i instead of r=r*i ? \$\endgroup\$ – Cyoce Jan 21 '16 at 7:05
0
\$\begingroup\$

Python (31 29 character)

f=lambda n:n and n*f(n-1)or 1

28 characters

f=lambda n:+(n<2)or n*f(n-1)
\$\endgroup\$
  • \$\begingroup\$ As I see no Python solution present \$\endgroup\$ – AMK Nov 24 '12 at 13:49
  • \$\begingroup\$ The first page has a Python solution with only 28 characters. \$\endgroup\$ – Kevin Brown Nov 24 '12 at 15:36
0
\$\begingroup\$

C 20 characters

x(){while(n)f*=n--;}

Assuming f and n are global variables. Here is the entire program :

double n=5,f=1;

x(){while(n)f*=n--;}

main(){
x();
printf("%f",f);
}
\$\endgroup\$
0
\$\begingroup\$

C 37 characters

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

This returns the value but is slightly longer than my
previous answer which used global variables.

\$\endgroup\$
0
\$\begingroup\$

the minimum solutions is already given using C# lamada. But just try to this another way.

        var seq = Enumerable.Range(1, 5).ToList();
        int O=1;    //O will contain Factorial or ouput
        seq.ForEach(x=>O*=x); 
\$\endgroup\$
0
\$\begingroup\$

C#, just the relevant code, 59

(assuming the argument variable is called a)

Enumerable.Range(1,int.Parse(a[0])).Aggregate(1,(x,y)=>x*y)

With boilerplate, 122

using System.Linq;class A{static int Main(string[] a){return Enumerable.Range(1,int.Parse(a[0])).Aggregate(1,(x,y)=>x*y);}

(note that this solution returns the result)

\$\endgroup\$
0
\$\begingroup\$

C#, 30

double a=1;while(p>0){a*=p--;}

With spaces for ease of reading:

double a = 1;
        while(p > 0)
        {
            a *= p--;
        }

a is the factorial result, while p is the number for which factorial is computed.

\$\endgroup\$
  • \$\begingroup\$ Couldn't you just say "while(p)statement;" instead of "while(p>0){statement;}"? Unless C# behaves differently from C, it should work. \$\endgroup\$ – Glenn Randers-Pehrson Apr 1 '14 at 18:59
  • \$\begingroup\$ if p is bool, it would. Here I need to continue checking p with 0... \$\endgroup\$ – s3l1n Apr 2 '14 at 5:20
0
\$\begingroup\$

Python 2.7.5 - 29 characters

f=lambda n:n and n*f(n-1)or 1

29 characters. It's still mathematically sound for a negative input value, since (-n)! = ∞ and therefore the program gives a Runtime Error maximum recursion depth exceeded.

\$\endgroup\$
0
\$\begingroup\$

Simplefunge, 87 chars including whitespace

v

     v  *&<
     >   &V
     `    &
 v     <  o
     ^H^  @
v>>!1-^
>iV    
  >1o@

I don't actually have time to test this right now, but it should work. If it doesn't work, I'll fix it tomorrow.

\$\endgroup\$
0
\$\begingroup\$

Scala, 28 (39 w/ recursion)

Solution:

def f(n:Int)=(1 to n)product

Recursive solution:

def f(n:Int):Int=if(n<2)1 else n*f(n-1)
\$\endgroup\$
0
\$\begingroup\$

R - 33

function(x) ifelse(x,prod(1:x),1)

> (function(x) ifelse(x,prod(1:x),1))(0)
[1] 1
> (function(x) ifelse(x,prod(1:x),1))(5)
[1] 120
> (function(x) ifelse(x,prod(1:x),1))(120)
[1] 6.689503e+198
\$\endgroup\$
0
\$\begingroup\$

Python, 43 38

import math
f=lambda n:math.gamma(n+1)

Explanation: The gamma function is a very quickly-growing complex function which, at integer values, is equal to the factorial of one less than the number. So we add one to n and take the gamma function of it.

I hope this isn't considered cheating, since the gamma function is not technically able to directly calculate the factorial.

\$\endgroup\$
  • 1
    \$\begingroup\$ To quote Wikipedia, "In mathematics, the gamma function is an extension of the factorial function, with its argument shifted down by 1, to real and complex numbers". Some would say it's "close enough" to a factorial function that it shouldn't count, I personally don't care because it's longer than the other Python answers. \$\endgroup\$ – Kevin Brown Oct 14 '15 at 17:49
0
\$\begingroup\$

Clojure/ClojureScript, 26 bytes

#(apply *(range 1(inc %)))
\$\endgroup\$
0
\$\begingroup\$

R 27 Bytes

function(n)prod(seq_len(n))
\$\endgroup\$
0
\$\begingroup\$

Y, 10 bytes

Try it here!

jC:t:tF|*p

A three-link program. Ungolfed:

j C :t :t F |* p

j takes numeric input, C begins a new link, :t duplicates and decrements to [n n-1]; the :t:t becomes [n n-1 n-2]; the last n-2 is popped for a zero-check by the F node; once a zero is found, we continue. |* folds the stack over multiplication, and p prints it.

\$\endgroup\$
0
\$\begingroup\$

ForceLang, 83 bytes

Noncompeting, language postdates the challenge

set a io.readnum()
set b 1
label l
set b b.mult a
set a a+-1
if a
goto l
io.write b
\$\endgroup\$
0
\$\begingroup\$

Perl 5, 31 bytes

$s=1;map{$s*=$_}(2..<>);print$s

Prints the result in scientific notation, and takes care of the 0 value as well.

Another way to do it, but without the 0 case, for 26 bytes :

print eval join'*',(1..<>)
\$\endgroup\$
  • \$\begingroup\$ 26 bytes: $\=1;map$\*=$_,2..<>;print. Or 21 + 3 (flag -l61): map$\*=$_,2..<>;print. \$\endgroup\$ – Denis Ibaev Nov 10 '16 at 20:29
  • \$\begingroup\$ 21 bytes: map$.*=$_,2..<>;say$. \$\endgroup\$ – Xcali Nov 15 '17 at 23:15
0
\$\begingroup\$

Befunge-93, 24 22

0\0>-#1:_$> #\:#*_$:!+

As with the other Befunge answer(s?), this is a function in that you enter with your input on the top of the stack, start on the top-left with your pointer facing right, and exit still facing right with the result on top of the stack.

The difference is that this one is shorter, and only one row. And it still doesn't use wraparound or self-modification.

You can test it here. Testing six factorial:

6    0\0>-#1:_$> #\:#*_$:!+    .@

Outputs 720.

Testing zero:

0    0\0>-#1:_$> #\:#*_$:!+    .@

Outputs 1. The :!+ (formerly :0`!+) does at the end does nothing but check for zeroes.

EDIT: A suggestion golfed two characters off. Thanks!

\$\endgroup\$
  • 1
    \$\begingroup\$ You don't need the 0` part, ! will return the correct result directly. So instead your implementation should look like that 0\0>-#1:_$> #\:#*_$:!+ \$\endgroup\$ – FliiFe Apr 7 '16 at 11:14
  • \$\begingroup\$ Ah! Thank you. I'll change that now. \$\endgroup\$ – Kasran Apr 9 '16 at 17:10

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.