Code Golf: Factorials

Question

Since the palindrome code golf was a big hit, here is one that doesn't rely on built in functions.

What is the shortest (in characters) way to write a factorial function?

Answer 1

My attempt, using C#:

int f(int v){return v<2?1:v*f(v-1);}

38 Characters, counting whitespace.

For those who don't understand the ? operator, it works like this:

  (Condition) ? (Return this if true) : (Return this if false)

So, in my case, it collapses this:

if (v<2)
{
    return 1;
}
else
{
    return v*f(v-1);
}

Answer 2

Haskell:

\n->product[1..n]

17 characters, 20 with reasonable whitespace. As a named function:

fac n = product [1..n]

22 characters. Without using product:

fac n = foldr (*) 1 [1..n]

26 characters

These (largely equivalent) implementations have no stack overflow or integer overflow errors. Compiled with ghc, this calculates and prints all 35661 digits of 10000! in 0.11s and all 456575 digits of 100000! in 11.145s on my two year old laptop. Of course, there are doubtless faster algorithms, but that's not bad performance for a naive solution.

Answer 3

I tried to get creative with using a lambda instead of a regular function to make it smaller.

However, you can't recurse on an anonymous type, so I get this:

Func<int,int>f=null;f=v=>v<2?1:v*f(v-1);

41 characters.

Answer 4

40 in python without trying too hard.

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

EDIT: Make that 38 . I guess I didn't need the extra parens above..

Answer 5

It's only 2 characters in APL, where most math functions are intrinsic:

?!

Explanation: The question mark operator requests user input, and the monadic exclamation point applies the factorial function. Since the result isn't assigned to any variable or used in further calculations, it gets printed.

APL isn't as popular as it used to be, but one of my customers still has some production APL applications.

Answer 6

34 in python:

def f(n):return n and n*f(n-1)or 1

34 in C:

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

Answer 7

Ruby, 19 characters + the length of the number to be computed (in this case, 1 character for the variable n)

(1..n).inject(1,&:*)

Answer 8

Java:

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

Identical to C.

Answer 9

9 bytes of i386 machine-code. Input is EAX, output is EAX.

#AT&T syntax
mov %eax, %ebx
again:
    dec %ebx
    .byte 0x74, 4    #jz (short) done
    mul %ebx
    .byte 0xEB, -7   #jmp (short) again
done:

PS: Anyone know why as won't genetrate short jumps for me?

Answer 10

66 characters of Windows cmd.exe batch language (Win2K or later only):

set r=1
for /l %%i in (1,1,%1) do call set/a r=%%r%%*%%i
echo %r%

The recursive version was shaping up to be much larger.

Answer 11

22 characters of Standard ML:

fun f 0=1|f n=n*f(n-1)

Answer 12

OCaml:

let rec f n = if n=0 then 1 else n*f(n-1);;

Answer 13

Perl, 32 characters

sub f{$_[0]?$_[0]*f($_[0]-1):1;}

Answer 14

Probably the longest entry here, but brainf*ck is special in any case... :)

So, here goes my entry at 93 characters:

,>++++++[<-------->-]<[->+>+<<]>>->>+<<<[>[<[->[-<<+>>>+<]>[-<+>]<<]<[->+<]>>-]<.>>>-]>>>[.-]

Commented and indented:

, 
>++++++ Put 6 in next cell
[<-------->-] Subtract 8 six times to subtract 48
<
[->+>+<<]  Move (0) to (1) and (2)
>>-  Decrement one from (2) as we want to multiply n * n minus 1
>>+  Store 1 in (4) to allow distinguishing 0 separately
<<< Go to (1)
[   A makeshift if($_ != 0)
  >[   While (2) 
    <[   While(1)
      - Subtract one from (1) for multiplication by repeated addition
      >[-<<+>>>+<] Add (2) to (0) and (3)
      >[-<+>] Move data from (3) to (2)
      <<
    ]  
    <[->+<] Copy (0) to (1) for next round of multiplication
    >>- Decrement (2) to go to n minus 2 and so on
  ]
  <.>>>-  Print output from (1) and make (4) = 0 to stop the if
]
>>>[.-]  If we're at (4) (and it is nonzero) we have a 0 as input; so print 1 and stop;

EDIT: Seeing the other language codes do not include input code and just take the number as an argument, I too removed the input part and assumed the number was contained as argument in (0). Now it's reduced to 71 characters:

[->+>+<<]>>->>+<<<[>[<[->[-<<+>>>+<]>[-<+>]<<]<[->+<]>>-]<.>>>-]>>>[.-]

The outputting algorithm is non trivial so I decided not to remove it.

Answer 15

30 characters in Python, an improvement of 8 over the other python.

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

Answer 16

def f(n): return reduce(lambda x,y: x*y,range(1,n+1))

Answer 17

28 characters in C:

F(n){return n>1?n*F(n-1):1;}

Note that this uses the old-style default-int convention.

Answer 18

Perl 6:

19 characters.

sub f($n){[*]1..$n}

16 characters

sub f{[*]1..$^n}

If you wanted to call it like '5!'
30 characters.

sub postfix:<!>($n){[*]1..$n}

Or for an anonymous code block
11 characters.

{[*]1..$^n}

say {[*]1..$^n}(5) # 120

Answer 19

Language: dc, Char count:23

23 chars version:

dc -e'?d[1-dsa*lad1<b]dsbxszp' <<<1000

Edit: More readable (24 chars) version by Hudson

dc -e'?[q]sQ[d1=Qd1-lFx*]dsFxp' <<<1000

I should mention that dc is arbitrary precision calculator.

Answer 20

Language: Golfscript, Char count: 10

My first script in golfscript at all:

 ,{1+}%{*}*

Answer 21

Not the shortest, but certainly the least appropriate technique: C++ templates to compute factorial as part of the type signature of the class:

#include <iostream>

template <int N>
struct Factorial
{
    enum { value = N * Factorial<N - 1>::value };
};

template <>
struct Factorial<0>
{
    enum { value = 1 };
};

int main()
{
        std::cout << "4!=" << Factorial<4>::value << std::endl;
}

This will fail to produce valid answers for even moderate values of N.

Answer 22

New python record: 28 chars

f=lambda x:+(x<2)or x*f(x-1)

Answer 23

25 characters in groovy: def f(n){n<=2?n:n*f(n-1)}

Answer 24

F#:

let f n = [1..n] |> Seq.fold ( * ) 1

With spaces: 36 chars. Spaces removed, 30 chars.

Answer 25

Someone posted dc. I'm going to post bc, paste & seq:

20 characters

seq $n|paste -sd*|bc

Answer 26

Scala:

def f(n:Int)=(1/:(1 to n))(_*_)

Answer 27

C#:

Slightly longer than the previous poster, but more useful as it is not as limited as with an int output, can resolve up to 28! instead of only 13!

Also, v > 1 is easier on the eye than v < 2

decimal f(int v) { return v > 1 ? v * f(v - 1) : 1; }

Answer 28

In the J programming language, factorial is built-in, so:

fact=:!

but that's boring, so let's do it manually:

fact=:*/@:(1+i.)

I guess this little-known language looks pretty unreadable, but here's the equivalent Haskell definition:

fact = foldr1 (*) . \n -> [1..n]

Answer 29

R5RS w/ blatant whitespace abuse:

(define(f x)(if(= x 0)1(* x(f(- x 1)))))

Answer 30

Smalltalk-80

f||self=0 ifTrue:[^1].^self*f self-1.

Answer 31

The most brief version in AS3 at 37 characters:

function f(i){return i<1?1:i*f(i-1);}

Which is the stripped down version of the more readable:

function factorial(i:Number):Number{return (i<1) ? 1 : i * factorial(i-1);}

Answer 32

Skipping the obvious n! in Mathematica, we can do it recursively, like so:

If[#1<=#2,#1,#0[#1,2#2]#0[#1-#2,2#2]]&[#,1]&

for a total of 44 characters. This is a more efficient algorithm than the freshman year recursion example, which weights in at a mere 28 characters.

If[#1<1,1,#1#0[#1-1]]&[#,0]&

Of course, a list-based solution is even shorter (15 characters).

Times@@Range@#&

When golfing in Mathematica, you can save a lot of strokes by (ab)using its very terse syntax for pure functions and function application.

Answer 33

Clojure - 36 chars

I'm learning Clojure right now (a dialect of Lisp), so I thought I'd do one in that.

(defn ![n](apply *(range 1(inc n))))

To be called like so: (! n)

* throws errors for ranges and lazy seqs, which is why apply was added.

Two characters can be shaved off by binding an anonymous function to !:

(def ! #(apply *(range 1(inc %))))

Answer 34

C# 41:

Func<int,int> f=null;f=x=>x<2?1:x*f(x-1);

C# 49, decimal

Func<decimal,decimal> f=null;f=x=>x<2?1:x*f(x-1);

C# int formatted:

Func<int,int> f = null;
f = (x) => (x < 2) ? 1 : x * f(x-1);

Answer 35

66 bytes of ARM assembly (thumb2). Not as short as many, but produces a bignum result. I'm sure that a few more bytes could be saved with some care.

// uint32_t factorial(uint32_t n, uint32_t *result, uint32_t length);
// 
// stores n! in the buffer result as a little-endian bignum.  length is
// size of the buffer in (32-bit) words.  It is the caller's responsibility
// to allocate and free the result buffer.  If the buffer is not large
// enough to contain n!, 0 is returned.  On successful exit, the return
// value is the number of (32-bit) words of the buffer that were used to
// store the result.

_factorial:
    push   {r4-r7}
    tst     r2,     r2
    beq     Lerror
    movs    r3,     #1
    str     r3,    [r1]
    tst     r0,     r0
    beq     Ldone
Lloop:
    eors    r6,     r6
    movs    r7,     r3
Lmultiply:
    movs    r5,     r6
    eors    r6,     r6
    ldr     r4,    [r1]
    umlal   r5, r6, r0, r4
    str     r5,    [r1], #4
    subs    r7,     $1
    bne     Lmultiply
    tst     r6,     r6
    beq     LnoOverflow
    adds    r3,     $1
    cmp     r3,     r2
    bhi     Lerror
    str     r6,    [r1], #4
LnoOverflow:
    sub     r1, r1, r3, lsl #2
    subs    r0,     $1
    bne     Lloop
Ldone:
    mov     r0,     r3
Lexit:
    pop    {r4-r7}
    bx      lr
Lerror:
    eors    r0,     r0
    b       Lexit

Answer 36

Lua

45 chars

Since Lua wasn't on here already.

function f(i)return i>0 and i*f(i-1)or 1 end

Answer 37

PHP - 59 chars

function f($n){return array_reduce(range(1,$n),'bcmul',1);}

Answer 38

Repent - 3 chars

Repent is a esoteric stack based language of my own, use this interpreter (language reference). Put the arguments in the "command line args" textbox.

1.∏

Explanation:

1 `Push a one to the stack`
. `Make a list from the argument to 1 (e.g. [6,5,4,3,2,1])`
∏ `N-Ary-Product - multiply all the values in the list together`