Find the Factorial!

Question

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.

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)? — Ami, Commented Feb 6, 2011 at 22:43
@SHiNKiROU, even golfscript can manage 125! less than 1/10th of a second and it's and interpreted interpreted language! — gnibbler, Commented Feb 8, 2011 at 3:21
Completes in under a minute seems a very hardware-dependent requirement. Completes in under a minute on what hardware? — sergiol, Commented Aug 24, 2017 at 18:05
@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. — Kevin Brown-Silva, Commented Aug 24, 2017 at 21:20
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. — MilkyWay90, Commented May 7, 2019 at 2:02

Mama Fun Roll · Accepted Answer · 2016-02-14 02:32:43Z

1

DUP, 19 bytes

[$[$1-a;!*][%1]?]a:

Try it here!

A recursive lambda that leaves result on the stack. Usage:

6[$[$1-a;!*][%1]?]a:a;!

Explanation

[               ]a: {set a to lambda}
 $                  {check if top of stack >0}
  [       ][  ]?    {conditional}
   $1-a;!*          {if so, top of stack *a(top of stack -1)}
            %1      {otherwise, replace top of stack with 1}

answered Feb 14, 2016 at 2:32

Mama Fun Roll

9,9281 gold badge36 silver badges46 bronze badges

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

1

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.

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Feb 29, 2016 at 1:13

RenderSettings

6905 silver badges8 bronze badges

\$\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\$
– RenderSettings
Commented Mar 1, 2016 at 1:36

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

1

Desmos, 18 bytes

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

Uses the formula for a! instead of a!

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Jun 7, 2016 at 17:38

weatherman115

8557 silver badges7 bronze badges

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

1

Joy, 13 bytes

[1][*]primrec

30 char requirement in codegolf?

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Jun 8, 2016 at 19:52

BlackCap

3,93816 silver badges33 bronze badges

\$\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\$
– FryAmTheEggman
Commented Jun 8, 2016 at 20:16

Add a comment |

Conor O'Brien · Accepted Answer · 2016-06-08 23:21:42Z

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.

Community · Accepted Answer · 2020-06-17 09:04:33Z

1

Maple, 17 bytes

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

Usage:

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

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Aug 19, 2016 at 18:40

DSkoog

5803 silver badges9 bronze badges

Add a comment |

TuxCrafting · Accepted Answer · 2016-11-10 18:52:57Z

1

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

edited Nov 10, 2016 at 18:52

answered Nov 10, 2016 at 18:47

TuxCrafting

4,8373 gold badges33 silver badges46 bronze badges

Add a comment |

Martin Ender · Accepted Answer · 2017-04-12 12:51:45Z

1

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

answered Apr 12, 2017 at 12:51

Martin Ender

197k67 gold badges447 silver badges975 bronze badges

Add a comment |

Sinusoid · Accepted Answer · 2017-04-12 15:28:48Z

1

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

answered Apr 12, 2017 at 15:28

Sinusoid

4513 silver badges8 bronze badges

Add a comment |

Cóemgein · Accepted Answer · 2017-08-24 17:02:42Z

1

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

answered Aug 24, 2017 at 17:02

Cóemgein

111 bronze badge

Add a comment |

Kevin Halley · Accepted Answer · 2017-08-25 19:40:50Z

1

Pyth, 7 Bytes

u*GhHQ1

Try it online!

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

answered Aug 25, 2017 at 19:40

Kevin Halley

3153 silver badges4 bronze badges

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

1

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.

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Apr 1, 2014 at 15:30

Timtech

12.6k2 gold badges45 silver badges61 bronze badges

\$\begingroup\$ What's wrong with For(? \$\endgroup\$
– Khuldraeseth na'Barya
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

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

1

Pyth, 3 bytes

*FS

Try it here.

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Sep 12, 2017 at 15:24

Mr. Xcoder

42.5k9 gold badges81 silver badges214 bronze badges

\$\begingroup\$ the S appears to no longer be necessary \$\endgroup\$
– hakr14
Commented Sep 12, 2018 at 18:20

Add a comment |

mkst · Accepted Answer · 2017-09-13 07:51:16Z

1

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

answered Sep 13, 2017 at 7:51

mkst

5,22512 silver badges19 bronze badges

Add a comment |

qqq · Accepted Answer · 2018-02-22 15:01:05Z

1

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

edited Feb 22, 2018 at 15:01

answered Feb 21, 2018 at 23:58

qqq

1,6262 gold badges18 silver badges41 bronze badges

\$\begingroup\$ Builtin is not allowed. \$\endgroup\$
– Weijun Zhou
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

Add a comment |

ბიმო · Accepted Answer · 2018-08-07 18:25:04Z

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

ბიმო · Accepted Answer · 2018-08-08 12:13:20Z

1

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

edited Aug 8, 2018 at 12:13

answered Aug 7, 2018 at 19:25

ბიმო

16.9k2 gold badges41 silver badges104 bronze badges

Add a comment |

Alion · Accepted Answer · 2018-08-13 21:45:45Z

1

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!

edited Aug 13, 2018 at 21:45

answered Aug 3, 2018 at 22:02

Alion

1,3201 gold badge12 silver badges13 bronze badges

Add a comment |

mazzy · Accepted Answer · 2018-09-14 13:43:27Z

1

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..$_ generates a sequence of integer from 1 to argument (sequence=(1,0) if argument equal to 0)
-ge1 leaves in the sequence numbers great or equal to 1
-join'*' converts the sequence to string with '*' between elements
|iex evaluates string as powershell expression

answered Sep 14, 2018 at 13:43

mazzy

7,1652 gold badges12 silver badges22 bronze badges

Add a comment |

FlipTack · Accepted Answer · 2018-12-14 23:14:43Z

1

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.

edited Dec 14, 2018 at 23:14

answered Dec 14, 2018 at 23:01

FlipTack

14.7k3 gold badges54 silver badges101 bronze badges

Add a comment |

lolad · Accepted Answer · 2019-02-19 14:47:57Z

1

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!

answered Feb 19, 2019 at 14:47

lolad

8427 silver badges17 bronze badges

Add a comment |

maxb · Accepted Answer · 2019-03-08 11:52:06Z

1

MathGolf, 3 bytes

╒ε*

Try it online!

Explanation

╒    create 1-based range [1, ..., input]
 ε*  Reduce by multiplication

answered Mar 8, 2019 at 11:52

maxb

6,9473 gold badges32 silver badges41 bronze badges

Add a comment |

Mayube · Accepted Answer · 2019-05-03 13:05:08Z

1

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)

edited May 3, 2019 at 13:05

answered May 2, 2019 at 19:04

Mayube

11.7k2 gold badges48 silver badges93 bronze badges

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

Add a comment |

Emigna · Accepted Answer · 2019-05-03 13:52:28Z

1

><>, 14 bytes

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

Try it online!

answered May 3, 2019 at 13:52

Emigna

53k5 gold badges43 silver badges162 bronze badges

Add a comment |

i_saw_drones · Accepted Answer · 2019-05-03 19:43:27Z

1

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.

answered May 3, 2019 at 19:43

i_saw_drones

4832 silver badges7 bronze badges

Add a comment |

Benjamin Urquhart · Accepted Answer · 2019-05-03 20:42:31Z

1

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

answered May 3, 2019 at 20:42

Benjamin Urquhart

1,5248 silver badges25 bronze badges

Add a comment |

Mayube · Accepted Answer · 2019-05-28 17:12:45Z

1

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

answered May 28, 2019 at 17:12

Mayube

11.7k2 gold badges48 silver badges93 bronze badges

Add a comment |

L Rettberg · Accepted Answer · 2019-05-28 23:23:39Z

1

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.

answered May 28, 2019 at 23:23

L Rettberg

112 bronze badges

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

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

1

Pepe, 60 bytes

rrEERREeeeeeeeErEeREeEreEREErEEEEErEEEeeReererRrEEEEEEeEreEE

Try it online!

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered May 29, 2019 at 11:14

u-ndefined

2,32311 silver badges21 bronze badges

Add a comment |

Esolanging Fruit · Accepted Answer · 2019-06-05 21:57:39Z

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.

Find the Factorial!

217 Answers 217

DUP, 19 bytes

Explanation

Hoon, 29 bytes

Desmos, 18 bytes

Joy, 13 bytes

Yup, 33 31 29 bytes

Explanation

Multiplication

Maple, 17 bytes

Oasis, 3 bytes

Alice, 13 bytes

Explanation

Powershell, 38 bytes

TI-BASIC, 65 14 bytes

Pyth, 3 bytes

K (oK), 5 bytes

Pyt, 1 2 bytes

dc, 23 22 bytes

Explanation

µ6, 14 bytes

Explanation

AsciiDots, 80 57 53 49 48 47 43 bytes

Powershell, 21 byte

Explanation

Symbolic Python, 36 bytes

CJam, 10 bytes

MathGolf, 3 bytes

Explanation

Clam, 9 7 bytes

Explanation

><>, 14 bytes

Excel Formula, 41 bytes

Python 2, 52 bytes

NuStack, 55 bytes

Swift - 53 Characters

Pepe, 60 bytes

Dreaderef, 47 bytes

Your Answer

Sign up or log in

Post as a guest

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

Linked

Related

Hot Network Questions

Not the answer you're looking for? Browse other questions tagged
code-golf
arithmetic
restricted-time
factorial
or ask your own question.