82
\$\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
  • 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
  • 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
  • 3
    \$\begingroup\$ Why aren't built-ins allowed? You haven't specified what built-ins are, and if you said that it was up to a "reasonable person" to decide (which is completely subjective, but ignoring that), you still say that any form of eval is a built-in for the factorial, even though it evaluates code, not the factorial of a given number. \$\endgroup\$
    – MilkyWay90
    May 7 '19 at 2:02

191 Answers 191

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

Powershell, 38 bytes

filter f{((1..$_-join'*'|iex),1)[!$_]}

I used some of the other answers here for inspiration, but I'm not lower than @Joey. Although, I'm not sure how their code knows to stop subtracting once it hits 0...

PS C:\> 0|f
1
PS C:\> 4|f
24
PS C:\> 125|f
1.88267717688893E+209
\$\endgroup\$
1
\$\begingroup\$

Pyth, 15

K1FNr1hQ=K*KN;K

Try it here!

If you only need one variable, it’s better to use K or J which don’t need an equals sign to be assigned to on their first use

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

Pyth, 7 Bytes

u*GhHQ1

Try it online!

This is pretty much simple. Pyth is a good choise for code golfing.

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

TI-BASIC, 65 14 bytes

For(I,0,Ans:IAns+not(Ans:End

Tricky tricky... +not(Ans and loop starting from zero should handle the special case. seq( isn't as viable of an option for that reason. TI-Basic only supports up to 10^100 which makes 70! and above fail, but it's easy to see that this solution would extend indefinitely.

\$\endgroup\$
3
  • \$\begingroup\$ What's wrong with For(? \$\endgroup\$ Sep 9 '17 at 2:01
  • \$\begingroup\$ @lirtosiast I apologize for the poor quality of the previous edit, which I fixed. \$\endgroup\$
    – Timtech
    Sep 9 '17 at 13:33
  • \$\begingroup\$ @Scrooble Nothing, I just didn't understand TI-Basic as well in Apr '14. \$\endgroup\$
    – Timtech
    Sep 9 '17 at 13:34
1
\$\begingroup\$

Pyth, 3 bytes

*FS

Try it here.

\$\endgroup\$
1
  • \$\begingroup\$ the S appears to no longer be necessary \$\endgroup\$
    – hakr14
    Sep 12 '18 at 18:20
1
\$\begingroup\$

K (oK), 5 bytes

Solution:

*/1+!

Try it online!

Explanation:

Interpretted right-to-left:

*/1+!   / solution
    !   / til, performs range, 0..n
  1+    / adds 1 (vectorised)
*/      / multiply-over elements in list

Notes:

Unlike the K/Kona/Q implementations, the input is treated as a float:

oK)@5
-9
q)type 5
-7h
\$\endgroup\$
1
\$\begingroup\$

><>, 17 16 bytes

1v;n
$<*}-1.!?::

-1 byte thanks to Jo King.

Since the question asks for a function as opposed to a full program, I allowed myself to accept the input from the stack without counting an additional 3 bytes for using the -v option.

This manages to be shorter than the other ><> answer because it jumps to the end-of-iteration code without having to hardcode the jump destination address : the current iteration counter (duplicated) is used as an address.
The iteration stops when the counter is 0, and jumping to (0, 0) while the direction pointer points to the right will execute the n; code that is otherwise unreachable, displaying the result and stopping the execution.

It handles 0! correctly and executes in 10*(n+1) ticks for n > 0 or 9 ticks for n = 0.

You can try it online.

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

Pyt, 1 2 bytes

řΠ

Try it online!

Implicit input
ř creates a range from 1 to input, taking care of the 0 edge case
Π multiplies everything together
Implicit output
\$\endgroup\$
3
  • \$\begingroup\$ Builtin is not allowed. \$\endgroup\$ Feb 22 '18 at 3:16
  • \$\begingroup\$ @WeijunZhou Ah yes, I will update, thank you \$\endgroup\$ Feb 22 '18 at 14:55
  • 1
    \$\begingroup\$ @Weijun Zhou and downvoters, please retract, I have taken out the builtin \$\endgroup\$ Feb 22 '18 at 15:01
1
\$\begingroup\$

Python - 74

Python without any library calls. Not the shortest but calculate factorial of 125 in a flash (< 1 sec)

def factorial(n):
 if n < 1:
  return 1
 else:
  return n * factorial(n-1)

Output of 125 factorial

188267717688892609974376770249160085759540364871492425887598231508353156331613598866882932889495923133646405445930057740630161919341380597818883457558547055524326375565007131770880000000000000000000000000000000
\$\endgroup\$
15
  • \$\begingroup\$ For some reason my indentation is not getting preserved. \$\endgroup\$
    – Ricardo A
    Jun 6 '14 at 3:59
  • \$\begingroup\$ Someone indented it for you, and then I reduced the indentation to only a single space per indent. I also added a character count. \$\endgroup\$
    – Rainbolt
    Jun 6 '14 at 21:45
  • 1
    \$\begingroup\$ You can save characters with def factorial(n):return 1 if n<1 else n*factorial(n-1) \$\endgroup\$
    – Rainbolt
    Jun 6 '14 at 21:46
  • \$\begingroup\$ Also, in Python, 0 is equivalent to false when used as a condition, so you could literally say if n: instead of if n < 1: \$\endgroup\$
    – Rainbolt
    Jun 6 '14 at 21:49
  • 1
    \$\begingroup\$ You seem to have missed the point of the challenge, as this does not seem the least bit golfed, i.e., written such that the code has as few characters as possible. \$\endgroup\$
    – Wrzlprmft
    Jun 6 '14 at 22:11
1
\$\begingroup\$

Flobnar, 19 bytes

|\@<:
1&::
<>-*
  1

Try it online!

An interesting sibling to Befunge. This uses the -d flag to enable decimal input.

Explanation:

This is basically equivalent to the recursive function:

def f(x):
  if x == 0:
    return 1
  else:
    return x*f(x-1)

The program starts from the @, and evaluates to its left. The \ evaluates underneath itself and stores that in the call stack. Underneath it is the &, which gives decimal input. If EOF has been reached, it evaluates underneath itself. Underneath, the > pushes the pointer right and returns the top value of the call stack minus 1.

That's this section:

 \@
 &:
 >-
  1

The \ basically counts down from the input and stores the latest version in the call stack.

After that, it hits the |, which evaluates further along, and returns either the value above it if the evaluated value is non-zero, else the value below it. The : returns the top of the call stack, so if it is zero, the | goes down and returns 1, else it goes up and wraps around the field. It hits the < which wraps it around again, and then multiplies the top of the call stack by the next iteration of the function.

|  <:
1  :
<  *
\$\endgroup\$
1
  • \$\begingroup\$ You beat me to this answer and probably outgolfed any attempt I might have made! Looks like the -d flag is misdocumented as -e - that should be fixed soon. \$\endgroup\$ Aug 7 '18 at 20:41
1
\$\begingroup\$

dc, 23 22 bytes

1r[dk*K1-d0<a]dsax_1*+

Try it online or verify 0-125!

Explanation

1r[dk*K1-d0<a]dsax_1*+  # input on stack, eg:     4
1                       # push 1:                 1 4
 r                      # reverse top two:        4 1
  [dk*K1-d0<a]          # push [string]:          [string] 4 1
              dsa       # copy top to register a: [string] 4 1
                 x      # exec top*               0 24
                  _1    # push -1:                -1 0 24
                    *   # multiply:               0 24
                     +  # add:                    24

# first exec of [string]:

  [dk*K1-d0<a]  # stack:                4 1
   d            # duplicate top:        4 4 1
    k           # pop & set precision:  4 1
     *          # multiply              4
      K         # push precision        4 4
       1        # push 1                1 4 4
        -       # subtract              3 4
         d0<a   # if top > 0 exec content of register a, namely [string]
                # output on stack:      24

In case of 0 after the exec part (*), the stack will be -1 0:

x       # exec top*               -1 0
 _1     # push -1:                -1 -1 0
   *    # multiply:               1 0
    +   # add:                    1
\$\endgroup\$
1
\$\begingroup\$

µ6, 14 bytes

#+[#.[#/0[+/1]/1/2][+/0]/1]

Try it online!

Explanation

#                            -- primitive recursion with
 +                           -- | base case: successor (of 0)
  [                          -- | compose
   #.[#/0[+/1]/1/2]          -- | | multiplication
                   [+/0]     -- | | successor of first argument
                        /1   -- | | second argument
                          ]  -- | : f n * f (n-1)
\$\endgroup\$
1
\$\begingroup\$

AsciiDots, 80 57 53 49 48 47 43 bytes

/{*}<$#&
\<^\*#1\
 \1#~*{-}-\
/#1/\*.>#?)
.

Outgolfs the sample by 34 57 61 65 66 67 71 bytes. Try it online!

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

Powershell, 21 byte

1..$_-ge1-join'*'|iex

Test script:

$f = {
1..$_-ge1-join'*'|iex
}

@(
    0,1,2,3,4,5,6,125
) | % {
    &$f $_
}

Output:

1
1
2
6
24
120
720
1.88267717688893E+209

Explanation

  1. 1..$_ generates a sequence of integer from 1 to argument (sequence=(1,0) if argument equal to 0)
  2. -ge1 leaves in the sequence numbers great or equal to 1
  3. -join'*' converts the sequence to string with '*' between elements
  4. |iex evaluates string as powershell expression
\$\endgroup\$
1
\$\begingroup\$

Symbolic Python, 36 bytes

__('__=_==_'+';__*=_;_=~-_'*_)
_=+__

Try it online!

Can compute 125! with ease.

Works using an 'exec' pseudo-loop:

  • First, we set __ to True, which is equivalent to 1.
  • We multiply this by _ (the input), and then decrement _.
  • The second step is repeated _ (input) times using string multiplication in the __ (exec) function's argument.
\$\endgroup\$
1
\$\begingroup\$

CJam, 10 bytes

qi1{_(j*}j

Explanation:

qi1{_(j*}j
qi            e# Read input as integer
   {    }j    e# Define a recursive function
  1           e# Where the value for f(0) = 1
    _         e# For f(i), duplicate i
     (        e# Then subtract 1
      j       e# Run the function for this number (i-1)
       *      e# Multiply i and f(i-1) together
              e# Implicit output

Try it online!

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

MathGolf, 3 bytes

╒ε*

Try it online!

Explanation

╒    create 1-based range [1, ..., input]
 ε*  Reduce by multiplication
\$\endgroup\$
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\$
3
  • \$\begingroup\$ get it on tio or GH pages pls. also 7: p;#qB1Q. alternatively, p;#>q0B1Q \$\endgroup\$
    – ASCII-only
    May 3 '19 at 6:47
  • \$\begingroup\$ @ASCII-only waiting for Dennis to pull the latest version \$\endgroup\$
    – Mayube
    May 3 '19 at 13:03
  • \$\begingroup\$ argh bad paste, was p|;B1Q1 or something \$\endgroup\$
    – ASCII-only
    May 3 '19 at 13:09
1
\$\begingroup\$

><>, 14 bytes

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

Try it online!

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

Excel Formula, 41 bytes

The following should be entered as an array formula (Ctrl+Shift+Enter):

=IFERROR(PRODUCT(ROW(OFFSET(A1,,,A1))),0)

Where A1 contains the value for n.

The IFERROR is just there to handle n=0.

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

Python 2, 52 bytes

I'm posting this purely because it uses reduce :)

f=lambda x:x<1or reduce(lambda a,b:a*b,range(1,x+1))

Try it online

Note: returns True for n<1. I assume this is ok because True == 1

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

NuStack, 55 bytes

f(n:int):int{r:int=n;while(n>1){n=n-1;r=r*n;}return r;}

Naive while-based approach

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

Swift - 53 Characters

func f(_ x:Double)->(Double){return(x<2 ?1:x*f(x-1))}

I'm sure it can be improved using closures...still investigating.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ Welcome to PPCG. There is already a Swift answer in 43 bytes. (It doesn't mean you can't post. But you may want to have a look at the existing answers in the same language first.) \$\endgroup\$
    – jimmy23013
    May 29 '19 at 0:10
  • \$\begingroup\$ Welcome to the site! Since you are golfing in Swift you might want to check out our tips for golfing in swift question. There is one of these for most other languages as well. \$\endgroup\$
    – Grain Ghost
    May 29 '19 at 2:29
  • \$\begingroup\$ Thanks for the prompt feedback - much appreciated! \$\endgroup\$
    – L Rettberg
    May 30 '19 at 18:07
1
\$\begingroup\$

Pepe, 60 bytes

rrEERREeeeeeeeErEeREeEreEREErEEEEErEEEeeReererRrEEEEEEeEreEE

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\$

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\$ by overloading !, you can shave of a few bytes: 12 bytes: !n=prod(1:n) and recursive in 15 bytes: !n=n<1||!(n-1)n \$\endgroup\$
    – MarcMush
    Apr 20 at 15:19
1
\$\begingroup\$

C, 37 bytes

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

This program accepts one number from stdin and then prints the answer in floating point form.

\$\endgroup\$
8
  • \$\begingroup\$ Hello, and welcome to Code Golf! This is a great answer, but to reduce the byte count even more, why not remove the extra spaces? \$\endgroup\$ Aug 3 '19 at 22:23
  • \$\begingroup\$ Oh, so you only want the nonmain function. Alright. I will keep that in mind for next time. \$\endgroup\$
    – T. Salim
    Aug 3 '19 at 22:33
  • \$\begingroup\$ You are right Jo, I fixed it. \$\endgroup\$
    – T. Salim
    Aug 4 '19 at 0:05
  • \$\begingroup\$ Thank you A__, I removed the parentheses. \$\endgroup\$
    – T. Salim
    Aug 4 '19 at 2:41
  • \$\begingroup\$ No, I tried to simply use long but the computer outputted 0 due to overflow, so I kept it as long double. \$\endgroup\$
    – T. Salim
    Aug 4 '19 at 2:45
1
\$\begingroup\$

Pip, 13 bytes

Fi,a{o*:i+1}o

Try it online!

Recursive factorial is given in Pip documentation, so I did iterative. Also, it couldn't handle up to 125! anyway.

\$\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\$

Keg, 9 5 4 bytes

Ï⑨∑*

Try it online!

-1 byte thanks to @A̲̲

Answer History

5 Bytes

Ï_1∑*

Try it online!

This:

  • Takes the (Ï)ota of the implicit input (pushes input, input - 1, input - 2 ... 0)
  • Pops the bottom 0
  • Pushes an extra 1 (so that the 0 case works)
  • Multiplies the entire stack together
\$\endgroup\$
1
1
3 4
5
6 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.