91
\$\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\$
12
  • 15
    \$\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
    Commented Feb 6, 2011 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
    Commented Feb 8, 2011 at 3:21
  • 8
    \$\begingroup\$ Completes in under a minute seems a very hardware-dependent requirement. Completes in under a minute on what hardware? \$\endgroup\$
    – sergiol
    Commented Aug 24, 2017 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\$ Commented Aug 24, 2017 at 21:20
  • 5
    \$\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
    Commented May 7, 2019 at 2:02

216 Answers 216

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

Hoon, 29 bytes

|=(@ (reel (gulf [1 +<]) mul)

Hoon's native number is a bignum, so it works fine with 125 (or even 2000). It also correctly gives 1 for 0.

It uses +< in order to access the sample of the gate. This is axis navigation syntax: It means to access the tail of the subject, and then the head, which is where the sample is stored in the binary tree model Hoon uses.

Urbit drops you into a shell and Hoon REPL when you start it, :dojo. To test this, simply enter %. 125 on one line and then the snippet for 125! Note there are two spaces between the dot and 1.

\$\endgroup\$
2
  • \$\begingroup\$ Hoon is a beautiful mystery. \$\endgroup\$
    – lynn
    Commented Mar 1, 2016 at 1:10
  • 1
    \$\begingroup\$ It's a surprisingly nice language to code in! It takes a little bit to learn all the runes, but you don't even need to internalize them to read it since they belong in "families" based on the first symbol. The fact it's strongly typed and has a novel type system is just icing on the cake. \$\endgroup\$ Commented Mar 1, 2016 at 1:36
1
\$\begingroup\$

Desmos, 18 bytes

a=1
\prod _{n=1}^an

Uses the formula for a! instead of a!

Formula

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

Joy, 13 bytes

[1][*]primrec

30 char requirement in codegolf?

\$\endgroup\$
2
  • \$\begingroup\$ @FryAmTheEggman To make a function you would actually have to write DEFINE f==[1][*]primerec.. I believe program arguments are thrown on the stack when the program starts, and that everything outside a define block is executed \$\endgroup\$
    – BlackCap
    Commented Jun 8, 2016 at 20:12
  • 1
    \$\begingroup\$ It'd be best if you knew for sure rather than just believing ;) Anyway, seems alright then, but you also wouldn't run in to that 30 character requirement if you gave some explanation of your code :P \$\endgroup\$ Commented Jun 8, 2016 at 20:16
1
\$\begingroup\$

Yup, 33 31 29 bytes

*{{:0e-}]~{~|~|0~--e~}~#\}0e#

Here's the github. Invoke like this:

node yup.js <location>.yup -n <input>

Or

node yup.js -l "*{{:0e-}]~{~|~|0~--e~}~#\}0e#" -n <input>

or Try it online!

Examples:

λ node yup.js -l "*{{:0e-}]~{~|~|0~--e~}~#\}0e#" -n 5
120
λ node yup.js examples\factorial.yup -n 0
1

Explanation

*{{:0e-}]~{~|~|0~--e~}~#\}0e#
*                              ` take input
 {                       }     ` while TOS -- if zero, we advance to the }
                          0e#  ` print number 1 (exp(0))
                               ` otherwise (nonzero)
  {    }                       ` while TOS is not zero
   :                           ` duplicate TOS
    0                          ` push 0
     e                         ` pop 0, push exp(0) = 1
      -                        ` subtract 1
                               ` we eventually are at zero.
        ]                      ` we move that zero to the bottom of the stack
         ~                     ` switch top two for looping offset
          {~        ~}         ` while STOS
            |~|0~--e           ` multiply two elements (see further down)
                      ~        ` switch the top zero with the result
                       #       ` print the result
                        \      ` exit program (so we don't print the final one)

Multiplication

In this program, I have multiplication defined as thus:

|~|0~--e

First, observe 0~--. This pushes a zero behind the TOS, and subtracts twice:

command | stack
        | a b
0       | a b 0
~       | a 0 b
-       | a (-b)
-       | a - (-b) = a + b

This performs addition. Let's replace 0~-- with + for clarity:

|~|+e

Now, | is ln. So watch the stack:

command | stack
        | a b
|       | a ln(b)
~       | ln(b) a
|       | ln(b) ln(a)
+       | (ln(b)+ln(a))
e       | exp(ln(b)+ln(a))

And, by the theorem of logarithms, this is multiplication.

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

Maple, 17 bytes

n->`*`(seq(1..n))

Usage:

> f:=n->`*`(seq(1..n));
> f(0);
  1
> f(5);
  120
> f(125);
  188267717688892609974376770249160085759540364871492425887598231508353156331613598866882932889495923133646405445930057740630161919341380597818883457558547055524326375565007131770880000000000000000000000000000000
\$\endgroup\$
1
\$\begingroup\$

Oasis, 3 bytes

Try it online

n*1

Explanation:

n*1
n    Push n
 *   Multiply the two items on the top of the stack
     Because there is only one item on the stack, A(n - 1) is pushed
     Implicit output
  1  Special case A(0) = 1
\$\endgroup\$
1
\$\begingroup\$

Alice, 13 bytes

/o
\i@/r.1~&*

Try it online!

Explanation

This is a basic framework for arithmetic programs to read and write integer I/O and process them in Cardinal mode:

/o
\i@/...

As for the actual computation:

r    Range: Replace the input N with 0, 1, 2, ..., N.
.    Duplicate N.
1~   Put a 1 underneath the copy to initialise the product correctly
     for N = 0.
&    Repeat the next command N times.
*    Multiply (N times, multiplying up the entire stack).
\$\endgroup\$
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\$
4
  • \$\begingroup\$ What's wrong with For(? \$\endgroup\$ Commented Sep 9, 2017 at 2:01
  • \$\begingroup\$ @lirtosiast I apologize for the poor quality of the previous edit, which I fixed. \$\endgroup\$
    – Timtech
    Commented Sep 9, 2017 at 13:33
  • \$\begingroup\$ @Scrooble Nothing, I just didn't understand TI-Basic as well in Apr '14. \$\endgroup\$
    – Timtech
    Commented Sep 9, 2017 at 13:34
  • \$\begingroup\$ 12 bytes: prod(seq(I,I,1,max(1,Ans or (some calculators) 9 bytes: prod(randIntNoRep(1,max(1,Ans \$\endgroup\$
    – Yousername
    Commented Apr 8, 2022 at 16:45
1
\$\begingroup\$

Pyth, 3 bytes

*FS

Try it here.

\$\endgroup\$
1
  • \$\begingroup\$ the S appears to no longer be necessary \$\endgroup\$
    – hakr14
    Commented Sep 12, 2018 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\$

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\$ Commented Feb 22, 2018 at 3:16
  • \$\begingroup\$ @WeijunZhou Ah yes, I will update, thank you \$\endgroup\$
    – qqq
    Commented Feb 22, 2018 at 14:55
  • 1
    \$\begingroup\$ @Weijun Zhou and downvoters, please retract, I have taken out the builtin \$\endgroup\$
    – qqq
    Commented Feb 22, 2018 at 15:01
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
    Commented May 3, 2019 at 6:47
  • \$\begingroup\$ @ASCII-only waiting for Dennis to pull the latest version \$\endgroup\$
    – Mayube
    Commented May 3, 2019 at 13:03
  • \$\begingroup\$ argh bad paste, was p|;B1Q1 or something \$\endgroup\$
    – ASCII-only
    Commented May 3, 2019 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
    Commented May 29, 2019 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\$
    – Wheat Wizard
    Commented May 29, 2019 at 2:29
  • \$\begingroup\$ Thanks for the prompt feedback - much appreciated! \$\endgroup\$
    – L Rettberg
    Commented May 30, 2019 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
    Commented Apr 20, 2021 at 15:19
1
4
5
6 7 8

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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