69
\$\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\$
  • 9
    \$\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
  • 3
    \$\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
  • 3
    \$\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

173 Answers 173

1
\$\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\$
  • \$\begingroup\$ L*F+1Sb is a bit shorter. \$\endgroup\$ – FryAmTheEggman 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\$ – FryAmTheEggman Apr 9 '16 at 19:40
  • \$\begingroup\$ @FryAmTheEggman I still have a lot to learn... \$\endgroup\$ – FliiFe Apr 9 '16 at 20:20
1
\$\begingroup\$

Racket, 29

(λ(x)(apply * x(range 1 x)))
\$\endgroup\$
  • \$\begingroup\$ Can you explain how this solution works? Not everyone is familiar with Racket. \$\endgroup\$ – overactor Sep 9 '14 at 10:15
1
\$\begingroup\$

Java (non-competing), 191 bytes

This is a show-off that calculates the factorial without recursion and returns results up to 22147483647-1, rather than a serious contender (I'd use doubles if I tried to get the shortest program). That's why I decided to make it non-competing.

import java.math.BigInteger;class a{BigInteger A(BigInteger b){BigInteger B=b,c=BigInteger.ONE;if(b.compareTo(c)<1)return c;for(;;){b=b.subtract(c);B=B.multiply(b);if(b.equals(c))return B;}}}

Ungolfed:

import java.math.BigInteger;

class a {
    BigInteger A(BigInteger b) {
        BigInteger B = b, c = BigInteger.ONE;
        if (b.compareTo(c) < 1)
            return c;
        for(;;) {
            b = b.subtract(c);
            B = B.multiply(b);
            if (b.equals(c))
                return B;
        }
    }
}

Test:

public static void main(String[] args){
    for(int i = 0; i <= 125; i++)
        System.out.println(i + ": " + new a().A(BigInteger.valueOf(i)));
}
\$\endgroup\$
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\$
  • \$\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 Jun 8 '16 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\$ – FryAmTheEggman Jun 8 '16 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\$

Fourier, 18 bytes

Non-competing: Fourier is newer than the challenge

1~NI(i^~iN*i~Ni)No

Try it online!

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

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\$
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\$
  • \$\begingroup\$ What's wrong with For(? \$\endgroup\$ – Khuldraeseth na'Barya 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\$
  • \$\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\$
  • \$\begingroup\$ If you run the bottom line to the left so that the pointer is moving left when it is transported, You remove the need for the second line. -1 byte 1v;n \n $<*}-1.!?:: \$\endgroup\$ – Jo King Dec 20 '17 at 5:41
  • \$\begingroup\$ Don’t forget you can remove the ; as well! \$\endgroup\$ – Jo King Dec 21 '17 at 12:41
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\$
  • \$\begingroup\$ Builtin is not allowed. \$\endgroup\$ – Weijun Zhou Feb 22 '18 at 3:16
  • \$\begingroup\$ @WeijunZhou Ah yes, I will update, thank you \$\endgroup\$ – FantaC Feb 22 '18 at 14:55
  • 1
    \$\begingroup\$ @Weijun Zhou and downvoters, please retract, I have taken out the builtin \$\endgroup\$ – FantaC 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\$
  • \$\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\$
  • \$\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\$ – Esolanging Fruit 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\$

Muriel, 128 bytes

C:"\";@%(B+\");B:\\\"\"+B+\"*\"+$a+\"\\\";a:\"+$(a-1)+\";C:\\\"\"+|C+C),(a>0)*(&B+2),a*999+&B+2";@"B:\".$(1\";a:"+~+";C:\""+|C+C

Try it online!

This is a difficult for a number of reasons. First is Muriel itself, where the only way to do loops is to create a quine and eval it, passing a condition into the code. Next is that large numbers lose precision over time (so the output for \$125!\$ is 1.88267717688893e+209), but the program can't handle that format inside the program itself, so you can't pass large numbers to the next iteration of code. The last problem is that numbers will eventually be so large, the program just renders them as Inf, but thankfully that's far beyond \$125!\$, so we don't have to worry about that.

Explanation:

The first iteration doesn't have to be a complete quine, but can take shortcuts in constructing the actual loop.

C:"\";@%(B+\");B:\\\"\"+B+\"*\"+$a+\"\\\";a:\"+$(a-1)+\";C:\\\"\"+|C+C),(a>0)*(&B+2),a*999+&B+2";

This creates an string version of the loop. This string persists across all iterations of the loop.

@                   # Evaluate the next strings as a new program
 "B:\".$(1\";       # Initialise B as the string ".$(1"
 a:"+~              # Initialise a as the inputted number
 +"C:\""+|C         # Initialise C as the persistent string C
 +C                 # And add the executing part of the program

The resulting program with input 125 looks like (newlines added for clarity)

B:".$(1";
a:125;
C:"\";@%(B+\");B:\\\"\"+B+\"*\"+$a+\"\\\";a:\"+$(a-1)+\";C:\\\"\"+|C+C),(a>0)*(&B+2),a*999+&B+2";
@%(B+");B:\""+B+"*"+$a+"\";a:"+$(a-1)+";C:\""+|C+C),(a>0)*(&B+2),a*999+&B+2

The eval then executes

@                   # Evaluate
 %(     ...     ),(a>0)*(&B+2),a*999+&B+2   # The substring
   B+");                                    # If a is 0, evaluate B
                                            # Otherwise
   B:\""+B+"*"+$a+"\";                      # Concatonate "*a" to the end of B
   a:"+$(a-1)+";                            # Decrement a
   C:\""+|C                                 # Set C to C
   +C                                       # And add the executing part of the program

Eventually, a will reach 0, and B will be evaluated. B will look like:

.                         # Print
 $(       ...         )   # The string form of
   1*125*124*123*...*1    # The factorial
\$\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\$
  • \$\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\$

Julia 1.0, 12 bytes

n->prod(1:n)

Try it online!

\$\endgroup\$

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.