Factorial Algorithms in different languages
AlgorithmLanguage AgnosticAlgorithm Problem Overview
I want to see all the different ways you can come up with, for a factorial subroutine, or program. The hope is that anyone can come here and see if they might want to learn a new language.
Ideas:
- Procedural
- Functional
- Object Oriented
- One liners
- Obfuscated
- Oddball
- Bad Code
- Polyglot
Basically I want to see an example, of different ways of writing an algorithm, and what they would look like in different languages.
Please limit it to one example per entry. I will allow you to have more than one example per answer, if you are trying to highlight a specific style, language, or just a well thought out idea that lends itself to being in one post.
The only real requirement is it must find the factorial of a given argument, in all languages represented.
Be Creative!
Recommended Guideline:
Language Name: Optional Style type
- Optional bullet points
Code Goes Here
Other informational text goes here
I will ocasionally go along and edit any answer that does not have decent formatting.
Algorithm Solutions
Solution 1 - Algorithm
Polyglot: 5 languages, all using bignums
So, I wrote a polyglot which works in the three languages I often write in, as well as one from my other answer to this question and one I just learned today. It's a standalone program, which reads a single line containing a nonnegative integer and prints a single line containing its factorial. Bignums are used in all languages, so the maximum computable factorial depends only on your computer's resources.
- Perl: uses built-in bignum package. Run with
perl FILENAME
. - Haskell: uses built-in bignums. Run with
runhugs FILENAME
or your favorite compiler's equivalent. - C++: requires GMP for bignum support. To compile with g++, use
g++ -lgmpxx -lgmp -x c++ FILENAME
to link against the right libraries. After compiling, run./a.out
. Or use your favorite compiler's equivalent. - brainf*ck: I wrote some bignum support in https://stackoverflow.com/questions/23930/factorial-algorithms-in-different-languages/432010#432010">this post. Using Muller's"">http://aminet.net/package.php?package=dev/lang/brainfuck-2.lha">Muller's classic distribution, compile with
bf < FILENAME > EXECUTABLE
. Make the output executable and run it. Or use your favorite distribution. - Whitespace: uses built-in bignum support. Run with
wspace FILENAME
.
Edit: added Whitespace as a fifth language. Incidentally, do not wrap the code with <code>
tags; it breaks the Whitespace. Also, the code looks much nicer in fixed-width.
char //# b=0+0{- |0*/; #>>>>,----------[>>>>,-------- #define a/#--]>>>>++<<<<<<<<[>++++++[<------>-]<-<<< #Perl ><><><> <> <> <<]>>>>[[>>+<<-]>>[<<+>+>-]<-> #C++ --><><> <><><>< > < > < +<[>>>>+<<<-<[-]]>[-] #Haskell >>]>[-<<<<<[<<<<]>>>>[[>>+<<-]>>[<<+>+>-]>>] #Whitespace >>>>[-[>+<-]+>>>>]<<<<[<<<<]<<<<[<<<< #brainfck > < ]>>>>>[>>>[>>>>]>>>>[>>>>]<<<<[[>>>>/ exp; ;//;#+<<<<-]<<<<]>>>>+<<<<<<<[<<<<][.POLYGLOT^5. #include <gmpxx.h>//]>>>>-[>>>[>>>>]>>>>[>>>>]<<<<[>> #define eval int main()//>+<<<-]>>>[<<<+>>+>-> #include <iostream>//<]<-[>>+<<[-]]<<[<<<<]>>>>[>[>>> #define print std::cout << // > <+<-]>[<<+>+>-]<<[>>> #define z std::cin>>//<< +<<<-]>>>[<<<+>>+>-]<->+++++ #define c/++++[-<[-[>>>>+<<<<-]]>>>>[<<<<+>>>>-]<</ #define abs int $n //>< <]<[>>+<<<<[-]>>[<<+>>-]]>>]< #define uc mpz_class fact(int $n){/<<<[<<<<]<<<[<< use bignum;sub#<<]>>>>-]>>>>]>>>[>[-]>>>]<<<<[>>+<<-] z{$_[0+0]=readline(STDIN);}sub fact{my($n)=shift;#>> #[<<+>+>-]<->+<[>-<[-]]>[-<<-<<<<[>>+<<-]>>[<<+>+>+/ uc;if($n==0){return 1;}return $nfact($n-1); }//;# eval{abs;z($n);print fact($n);print("\n")/2;};#-]<-> '+<[>-<[-]]>]<<[<<<<]<<<<-[>>+<<-]>>[<<+>+>-]+<[>-+++ -}-- <[-]]>[-<<++++++++++<<<<-[>>+<<-]>>[<<+>+>-++ fact 0 = 1 -- ><><><>< > <><>< ]+<[>-<[-]]>]<<[<<+ + fact n=nfact(n-1){-<<]>>>>[[>>+<<-]>>[<<+>+++>+-} main=do{n<-readLn;print(fact n)}-- +>-]<->+<[>>>>+<<+ {-x<-<[-]]>[-]>>]>]>>>[>>>>]<<<<[>+++++++[<+++++++>-] <--.<<<<]+written+by+++A+Rex+++2009+.';#+++x-}--x/;}
Solution 2 - Algorithm
lolcode:
sorry I couldn't resist xD
HAI
CAN HAS STDIO?
I HAS A VAR
I HAS A INT
I HAS A CHEEZBURGER
I HAS A FACTORIALNUM
IM IN YR LOOP
UP VAR!!1
TIEMZD INT!![CHEEZBURGER]
UP FACTORIALNUM!!1
IZ VAR BIGGER THAN FACTORIALNUM? GTFO
IM OUTTA YR LOOP
U SEEZ INT
KTHXBYE
Solution 3 - Algorithm
This is one of the faster algorithms, up to 170!. It fails inexplicably beyond 170!, and it's relatively slow for small factorials, but for factorials between 80 and 170 it's blazingly fast compared to many algorithms.
curl http://www.google.com/search?q=170!
There's also an online interface, try it out now!
Let me know if you find a bug, or faster implementation for large factorials.
EDIT:
This algorithm is slightly slower, but gives results beyond 170:
curl http://www58.wolframalpha.com/input/?i=171!
It also simplifies them into various other representations.
Solution 4 - Algorithm
C++: Template Metaprogramming
Uses the classic enum hack.
template<unsigned int n>
struct factorial {
enum { result = n * factorial<n - 1>::result };
};
template<>
struct factorial<0> {
enum { result = 1 };
};
Usage.
const unsigned int x = factorial<4>::result;
Factorial is calculated completely at compile time based on the template parameter n. Therefore, factorial<4>::result is a constant once the compiler has done its work.
Solution 5 - Algorithm
Whitespace
. . . . . . . . . . . . . . . . . . . . . . . . . .It was hard to get it to show here properly, but now I tried copying it from the preview and it works. You need to input the number and press enter.
Solution 6 - Algorithm
I find the following implementations just hilarious:
The Evolution of a Haskell Programmer
Evolution of a Python programmer
Enjoy!
Solution 7 - Algorithm
C# Lookup:
Nothing to calculate really, just look it up. To extend it,add another 8 numbers to the table and 64 bit integers are at at their limit. Beyond that, a BigNum class is called for.
public static int Factorial(int f)
{
if (f<0 || f>12)
{
throw new ArgumentException("Out of range for integer factorial");
}
int [] fact={1,1,2,6,24,120,720,5040,40320,362880,3628800,
39916800,479001600};
return fact[f];
}
Solution 8 - Algorithm
http://homepages.cwi.nl/~tromp/cl/lazy-k.html">Lazy</a> http://esoteric.sange.fi/essie2/download/" title="download it">K
Your pure functional programming nightmares come true!
The only http://en.wikipedia.org/wiki/Esoteric_programming_language">Esoteric Turing-complete Programming Language that has:
- A purely functional foundation, core, and libraries---in fact, here's the complete API: http://en.wikipedia.org/wiki/SKI_combinator_calculus">S K I
- No http://en.wikipedia.org/wiki/Lambda_calculus">lambdas</a> even!
- No http://en.wikipedia.org/wiki/Church_encoding#Church_numerals">numbers</a> or lists needed or allowed
- No explicit recursion but yet, http://mvanier.livejournal.com/2897.html" title="Mike Vanier - Y Combinator (Slight Return">allows recursion
- A simple http://mitpress.mit.edu/sicp/full-text/sicp/book/node71.html">infinite lazy stream-based I/O mechanism
Here's the Factorial code in all its parenthetical glory:
K(SII(S(K(S(S(KS)(S(K(S(KS)))(S(K(S(KK)))(S(K(S(K(S(K(S(K(S(SI(K(S(K(S(S(KS)K)I))
(S(S(KS)K)(SII(S(S(KS)K)I))))))))K))))))(S(K(S(K(S(SI(K(S(K(S(SI(K(S(K(S(S(KS)K)I))
(S(S(KS)K)(SII(S(S(KS)K)I))(S(S(KS)K))(S(SII)I(S(S(KS)K)I))))))))K)))))))
(S(S(KS)K)(K(S(S(KS)K)))))))))(K(S(K(S(S(KS)K)))K))))(SII))II)
Features:
- No subtraction or conditionals
- Prints all factorials (if you wait long enough)
- Uses a second layer of Church numerals to convert the Nth factorial to N! asterisks followed by a newline
- Uses the http://en.wikipedia.org/wiki/Fixed_point_combinator#Y_combinator">Y combinator for recursion
In case you are interested in trying to understand it, here is the Scheme source code to run through the Lazier compiler:
(lazy-def '(fac input)
'((Y (lambda (f n a) ((lambda (b) ((cons 10) ((b (cons 42)) (f (1+ n) b))))
(* a n)))) 1 1))
(for suitable definitions of Y, cons, 1, 10, 42, 1+, and *).
EDIT:
Lazy K Factorial in Decimal
(http://www.updike.org/hazy/facdec.lazy">10KB of gibberish or else I would paste it). For example, at the Unix prompt:
$ echo "4" | ./lazy facdec.lazy 24 $ echo "5" | ./lazy facdec.lazy 120
Rather slow for numbers above, say, 5.
The code is sort of bloated because we have to include http://www.updike.org/hazy/factorialDecimal.hazy">library code for all of our own primitives (code written in http://www.updike.org/hazy/">Hazy</a>;, a lambda calculus interpreter and LC-to-Lazy K compiler written in Haskell).
Solution 9 - Algorithm
XSLT 1.0
The input file, factorial.xml:
<?xml version="1.0"?>
<?xml-stylesheet href="factorial.xsl" type="text/xsl" ?>
<n>
20
</n>
The XSLT file, factorial.xsl:
<?xml version="1.0"?>
<xsl:stylesheet version="1.0"
xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
xmlns:msxsl="urn:schemas-microsoft-com:xslt" >
<xsl:output method="text"/>
<!-- 0! = 1 -->
<xsl:template match="text()[. = 0]">
1
</xsl:template>
<!-- n! = (n-1)! * n-->
<xsl:template match="text()[. > 0]">
<xsl:variable name="x">
<xsl:apply-templates select="msxsl:node-set( . - 1 )/text()"/>
</xsl:variable>
<xsl:value-of select="$x * ."/>
</xsl:template>
<!-- Calculate n! -->
<xsl:template match="/n">
<xsl:apply-templates select="text()"/>
</xsl:template>
</xsl:stylesheet>
Save both files in the same directory and open factorial.xml in IE.
Solution 10 - Algorithm
Python: Functional, One-liner
factorial = lambda n: reduce(lambda x,y: x*y, range(1, n+1), 1)
NOTE:
- It supports big integers. Example:
print factorial(100)
93326215443944152681699238856266700490715968264381621468592963895217599993229915\
608941463976156518286253697920827223758251185210916864000000000000000000000000
- It does not work for n < 0.
Solution 11 - Algorithm
APL (oddball/one-liner):
×/⍳X
- ⍳X expands X into an array of the integers 1..X
- ×/ multiplies every element in the array
Or with the built-in operator:
!X
Source: http://www.webber-labs.com/mpl/lectures/ppt-slides/01.ppt
Solution 12 - Algorithm
Perl6
sub factorial ($n) { [*] 1..$n }
I hardly know about Perl6. But I guess this [*]
operator is same as Haskell's product
.
This code runs on Pugs, and maybe Parrot (I didn't check it.)
Edit
This code also works.
sub postfix:<!> ($n) { [*] 1..$n }
# This function(?) call like below ... It looks like mathematical notation.
say 10!;
Solution 13 - Algorithm
x86-64 Assembly: Procedural
You can call this from C (only tested with GCC on linux amd64). Assembly was assembled with nasm.
section .text
global factorial
; factorial in x86-64 - n is passed in via RDI register
; takes a 64-bit unsigned integer
; returns a 64-bit unsigned integer in RAX register
; C declaration in GCC:
; extern unsigned long long factorial(unsigned long long n);
factorial:
enter 0,0
; n is placed in rdi by caller
mov rax, 1 ; factorial = 1
mov rcx, 2 ; i = 2
loopstart:
cmp rcx, rdi
ja loopend
mul rcx ; factorial *= i
inc rcx
jmp loopstart
loopend:
leave
ret
Solution 14 - Algorithm
Recursively in Inform 7
(it reminds you of COBOL because it's for writing text adventures; proportional font is deliberate):
> To decide what number is the factorial of (n - a number):
> if n is zero, decide on one;
> otherwise decide on the factorial of (n minus one) times n.
If you want to actually call this function ("phrase") from a game you need to define an action and grammar rule:
> "The factorial game" [this must be the first line of the source]
>
> There is a room. [there has to be at least one!]
>
> Factorialing is an action applying to a number.
>
> Understand "factorial [a number]" as factorialing.
>
> Carry out factorialing:
> Let n be the factorial of the number understood;
> Say "It's [n]".
Solution 15 - Algorithm
Haskell:
ones = 1 : ones
integers = head ones : zipWith (+) integers (tail ones)
factorials = head integers : zipWith (*) factorials (tail integers)
Solution 16 - Algorithm
C#: LINQ
public static int factorial(int n)
{
return (Enumerable.Range(1, n).Aggregate(1, (previous, value) => previous * value));
}
Solution 17 - Algorithm
Erlang: tail recursive
fac(0) -> 1;
fac(N) when N > 0 -> fac(N, 1).
fac(1, R) -> R;
fac(N, R) -> fac(N - 1, R * N).
Solution 18 - Algorithm
Brainf*ck
+++++
>+<[[->>>>+<<<<]>>>>[-<<<<+>>+>>]<<<<>[->>+<<]<>>>[-<[->>+<<]>>[-<<+<+>>>]<]<[-]><<<-]
Written by Michael Reitzenstein.
Solution 19 - Algorithm
BASIC: old school
10 HOME
20 INPUT N
30 LET ANS = 1
40 FOR I = 1 TO N
50 ANS = ANS * I
60 NEXT I
70 PRINT ANS
Solution 20 - Algorithm
#F#: Functional
###Straight forward:
let rec fact x =
if x < 0 then failwith "Invalid value."
elif x = 0 then 1
else x * fact (x - 1)
###Getting fancy:
let fact x = [1 .. x] |> List.fold_left ( * ) 1
Solution 21 - Algorithm
Batch (NT):
@echo off
set n=%1
set result=1
for /l %%i in (%n%, -1, 1) do (
set /a result=result * %%i
)
echo %result%
Usage: C:>factorial.bat 15
Solution 22 - Algorithm
#Recursive Prolog
fac(0,1).
fac(N,X) :- N1 is N -1, fac(N1, T), X is N * T.
#Tail Recursive Prolog
fac(0,N,N).
fac(X,N,T) :- A is N * X, X1 is X - 1, fac(X1,A,T).
fac(N,T) :- fac(N,1,T).
Solution 23 - Algorithm
ruby recursive
(factorial=Hash.new{|h,k|k*h[k-1]})[1]=1
usage:
factorial[5]
=> 120
Solution 24 - Algorithm
Scheme
Here is a simple recursive definition:
(define (factorial x)
(if (= x 0) 1
(* x (factorial (- x 1)))))
In Scheme tail-recursive functions use constant stack space. Here is a version of factorial that is tail-recursive:
(define factorial
(letrec ((fact (lambda (x accum)
(if (= x 0) accum
(fact (- x 1) (* accum x))))))
(lambda (x)
(fact x 1))))
Solution 25 - Algorithm
D Templates: Functional
template factorial(int n : 1)
{
const factorial = 1;
}
template factorial(int n)
{
const factorial =
n * factorial!(n-1);
}
or
template factorial(int n)
{
static if(n == 1)
const factorial = 1;
else
const factorial =
n * factorial!(n-1);
}
Used like this:
factorial!(5)
Solution 26 - Algorithm
Oddball examples? What about using the gamma function! Since, Gamma n = (n-1)!
.
OCaml: Using Gamma
let rec gamma z =
let pi = 4.0 *. atan 1.0 in
if z < 0.5 then
pi /. ((sin (pi*.z)) *. (gamma (1.0 -. z)))
else
let consts = [| 0.99999999999980993; 676.5203681218851; -1259.1392167224028;
771.32342877765313; -176.61502916214059; 12.507343278686905;
-0.13857109526572012; 9.9843695780195716e-6; 1.5056327351493116e-7;
|]
in
let z = z -. 1.0 in
let results = Array.fold_right
(fun x y -> x +. y)
(Array.mapi
(fun i x -> if i = 0 then x else x /. (z+.(float i)))
consts
)
0.0
in
let x = z +. (float (Array.length consts)) -. 1.5 in
let final = (sqrt (2.0*.pi)) *.
(x ** (z+.0.5)) *.
(exp (-.x)) *. result
in
final
let factorial_gamma n = int_of_float (gamma (float (n+1)))
Solution 27 - Algorithm
Freshman Haskell programmer
fac n = if n == 0
then 1
else n * fac (n-1)
Sophomore Haskell programmer, at MIT (studied Scheme as a freshman)
fac = (\(n) ->
(if ((==) n 0)
then 1
else ((*) n (fac ((-) n 1)))))
Junior Haskell programmer (beginning Peano player)
fac 0 = 1
fac (n+1) = (n+1) * fac n
Another junior Haskell programmer (read that n+k patterns are “a disgusting part of Haskell” [1] and joined the “Ban n+k patterns”-movement [2])
fac 0 = 1
fac n = n * fac (n-1)
Senior Haskell programmer (voted for Nixon Buchanan Bush — “leans right”)
fac n = foldr (*) 1 [1..n]
Another senior Haskell programmer (voted for McGovern Biafra Nader — “leans left”)
fac n = foldl (*) 1 [1..n]
Yet another senior Haskell programmer (leaned so far right he came back left again!)
-- using foldr to simulate foldl
fac n = foldr (\x g n -> g (x*n)) id [1..n] 1
Memoizing Haskell programmer (takes Ginkgo Biloba daily)
facs = scanl (*) 1 [1..]
fac n = facs !! n
Pointless (ahem) “Points-free” Haskell programmer (studied at Oxford)
fac = foldr (*) 1 . enumFromTo 1
Iterative Haskell programmer (former Pascal programmer)
fac n = result (for init next done)
where init = (0,1)
next (i,m) = (i+1, m * (i+1))
done (i,_) = i==n
result (_,m) = m
for i n d = until d n i
Iterative one-liner Haskell programmer (former APL and C programmer)
fac n = snd (until ((>n) . fst) (\(i,m) -> (i+1, i*m)) (1,1))
Accumulating Haskell programmer (building up to a quick climax)
facAcc a 0 = a
facAcc a n = facAcc (n*a) (n-1)
fac = facAcc 1
Continuation-passing Haskell programmer (raised RABBITS in early years, then moved to New Jersey)
facCps k 0 = k 1
facCps k n = facCps (k . (n *)) (n-1)
fac = facCps id
Boy Scout Haskell programmer (likes tying knots; always “reverent,” he belongs to the Church of the Least Fixed-Point [8])
y f = f (y f)
fac = y (\f n -> if (n==0) then 1 else n * f (n-1))
Combinatory Haskell programmer (eschews variables, if not obfuscation; all this currying’s just a phase, though it seldom hinders)
s f g x = f x (g x)
k x y = x
b f g x = f (g x)
c f g x = f x g
y f = f (y f)
cond p f g x = if p x then f x else g x
fac = y (b (cond ((==) 0) (k 1)) (b (s (*)) (c b pred)))
List-encoding Haskell programmer (prefers to count in unary)
arb = () -- "undefined" is also a good RHS, as is "arb" :)
listenc n = replicate n arb
listprj f = length . f . listenc
listprod xs ys = [ i (x,y) | x<-xs, y<-ys ]
where i _ = arb
facl [] = listenc 1
facl n@(_:pred) = listprod n (facl pred)
fac = listprj facl
Interpretive Haskell programmer (never “met a language” he didn't like)
-- a dynamically-typed term language
data Term = Occ Var
| Use Prim
| Lit Integer
| App Term Term
| Abs Var Term
| Rec Var Term
type Var = String
type Prim = String
-- a domain of values, including functions
data Value = Num Integer
| Bool Bool
| Fun (Value -> Value)
instance Show Value where
show (Num n) = show n
show (Bool b) = show b
show (Fun _) = ""
prjFun (Fun f) = f
prjFun _ = error "bad function value"
prjNum (Num n) = n
prjNum _ = error "bad numeric value"
prjBool (Bool b) = b
prjBool _ = error "bad boolean value"
binOp inj f = Fun (\i -> (Fun (\j -> inj (f (prjNum i) (prjNum j)))))
-- environments mapping variables to values
type Env = [(Var, Value)]
getval x env = case lookup x env of
Just v -> v
Nothing -> error ("no value for " ++ x)
-- an environment-based evaluation function
eval env (Occ x) = getval x env
eval env (Use c) = getval c prims
eval env (Lit k) = Num k
eval env (App m n) = prjFun (eval env m) (eval env n)
eval env (Abs x m) = Fun (\v -> eval ((x,v) : env) m)
eval env (Rec x m) = f where f = eval ((x,f) : env) m
-- a (fixed) "environment" of language primitives
times = binOp Num (*)
minus = binOp Num (-)
equal = binOp Bool (==)
cond = Fun (\b -> Fun (\x -> Fun (\y -> if (prjBool b) then x else y)))
prims = [ ("*", times), ("-", minus), ("==", equal), ("if", cond) ]
-- a term representing factorial and a "wrapper" for evaluation
facTerm = Rec "f" (Abs "n"
(App (App (App (Use "if")
(App (App (Use "==") (Occ "n")) (Lit 0))) (Lit 1))
(App (App (Use "*") (Occ "n"))
(App (Occ "f")
(App (App (Use "-") (Occ "n")) (Lit 1))))))
fac n = prjNum (eval [] (App facTerm (Lit n)))
Static Haskell programmer (he does it with class, he’s got that fundep Jones! After Thomas Hallgren’s “Fun with Functional Dependencies” [7])
-- static Peano constructors and numerals
data Zero
data Succ n
type One = Succ Zero
type Two = Succ One
type Three = Succ Two
type Four = Succ Three
-- dynamic representatives for static Peanos
zero = undefined :: Zero
one = undefined :: One
two = undefined :: Two
three = undefined :: Three
four = undefined :: Four
-- addition, a la Prolog
class Add a b c | a b -> c where
add :: a -> b -> c
instance Add Zero b b
instance Add a b c => Add (Succ a) b (Succ c)
-- multiplication, a la Prolog
class Mul a b c | a b -> c where
mul :: a -> b -> c
instance Mul Zero b Zero
instance (Mul a b c, Add b c d) => Mul (Succ a) b d
-- factorial, a la Prolog
class Fac a b | a -> b where
fac :: a -> b
instance Fac Zero One
instance (Fac n k, Mul (Succ n) k m) => Fac (Succ n) m
-- try, for "instance" (sorry):
--
-- :t fac four
Beginning graduate Haskell programmer (graduate education tends to liberate one from petty concerns about, e.g., the efficiency of hardware-based integers)
-- the natural numbers, a la Peano
data Nat = Zero | Succ Nat
-- iteration and some applications
iter z s Zero = z
iter z s (Succ n) = s (iter z s n)
plus n = iter n Succ
mult n = iter Zero (plus n)
-- primitive recursion
primrec z s Zero = z
primrec z s (Succ n) = s n (primrec z s n)
-- two versions of factorial
fac = snd . iter (one, one) (\(a,b) -> (Succ a, mult a b))
fac' = primrec one (mult . Succ)
-- for convenience and testing (try e.g. "fac five")
int = iter 0 (1+)
instance Show Nat where
show = show . int
(zero : one : two : three : four : five : _) = iterate Succ Zero
Origamist Haskell programmer (always starts out with the “basic Bird fold”)
-- (curried, list) fold and an application
fold c n [] = n
fold c n (x:xs) = c x (fold c n xs)
prod = fold (*) 1
-- (curried, boolean-based, list) unfold and an application
unfold p f g x =
if p x
then []
else f x : unfold p f g (g x)
downfrom = unfold (==0) id pred
-- hylomorphisms, as-is or "unfolded" (ouch! sorry ...)
refold c n p f g = fold c n . unfold p f g
refold' c n p f g x =
if p x
then n
else c (f x) (refold' c n p f g (g x))
-- several versions of factorial, all (extensionally) equivalent
fac = prod . downfrom
fac' = refold (*) 1 (==0) id pred
fac'' = refold' (*) 1 (==0) id pred
Cartesianally-inclined Haskell programmer (prefers Greek food, avoids the spicy Indian stuff; inspired by Lex Augusteijn’s “Sorting Morphisms” [3])
-- (product-based, list) catamorphisms and an application
cata (n,c) [] = n
cata (n,c) (x:xs) = c (x, cata (n,c) xs)
mult = uncurry (*)
prod = cata (1, mult)
-- (co-product-based, list) anamorphisms and an application
ana f = either (const []) (cons . pair (id, ana f)) . f
cons = uncurry (:)
downfrom = ana uncount
uncount 0 = Left ()
uncount n = Right (n, n-1)
-- two variations on list hylomorphisms
hylo f g = cata g . ana f
hylo' f (n,c) = either (const n) (c . pair (id, hylo' f (c,n))) . f
pair (f,g) (x,y) = (f x, g y)
-- several versions of factorial, all (extensionally) equivalent
fac = prod . downfrom
fac' = hylo uncount (1, mult)
fac'' = hylo' uncount (1, mult)
Ph.D. Haskell programmer (ate so many bananas that his eyes bugged out, now he needs new lenses!)
-- explicit type recursion based on functors
newtype Mu f = Mu (f (Mu f)) deriving Show
in x = Mu x
out (Mu x) = x
-- cata- and ana-morphisms, now for *arbitrary* (regular) base functors
cata phi = phi . fmap (cata phi) . out
ana psi = in . fmap (ana psi) . psi
-- base functor and data type for natural numbers,
-- using a curried elimination operator
data N b = Zero | Succ b deriving Show
instance Functor N where
fmap f = nelim Zero (Succ . f)
nelim z s Zero = z
nelim z s (Succ n) = s n
type Nat = Mu N
-- conversion to internal numbers, conveniences and applications
int = cata (nelim 0 (1+))
instance Show Nat where
show = show . int
zero = in Zero
suck = in . Succ -- pardon my "French" (Prelude conflict)
plus n = cata (nelim n suck )
mult n = cata (nelim zero (plus n))
-- base functor and data type for lists
data L a b = Nil | Cons a b deriving Show
instance Functor (L a) where
fmap f = lelim Nil (\a b -> Cons a (f b))
lelim n c Nil = n
lelim n c (Cons a b) = c a b
type List a = Mu (L a)
-- conversion to internal lists, conveniences and applications
list = cata (lelim [] (:))
instance Show a => Show (List a) where
show = show . list
prod = cata (lelim (suck zero) mult)
upto = ana (nelim Nil (diag (Cons . suck)) . out)
diag f x = f x x
fac = prod . upto
Post-doc Haskell programmer (from Uustalu, Vene and Pardo’s “Recursion Schemes from Comonads” [4])
-- explicit type recursion with functors and catamorphisms
newtype Mu f = In (f (Mu f))
unIn (In x) = x
cata phi = phi . fmap (cata phi) . unIn
-- base functor and data type for natural numbers,
-- using locally-defined "eliminators"
data N c = Z | S c
instance Functor N where
fmap g Z = Z
fmap g (S x) = S (g x)
type Nat = Mu N
zero = In Z
suck n = In (S n)
add m = cata phi where
phi Z = m
phi (S f) = suck f
mult m = cata phi where
phi Z = zero
phi (S f) = add m f
-- explicit products and their functorial action
data Prod e c = Pair c e
outl (Pair x y) = x
outr (Pair x y) = y
fork f g x = Pair (f x) (g x)
instance Functor (Prod e) where
fmap g = fork (g . outl) outr
-- comonads, the categorical "opposite" of monads
class Functor n => Comonad n where
extr :: n a -> a
dupl :: n a -> n (n a)
instance Comonad (Prod e) where
extr = outl
dupl = fork id outr
-- generalized catamorphisms, zygomorphisms and paramorphisms
gcata :: (Functor f, Comonad n) =>
(forall a. f (n a) -> n (f a))
-> (f (n c) -> c) -> Mu f -> c
gcata dist phi = extr . cata (fmap phi . dist . fmap dupl)
zygo chi = gcata (fork (fmap outl) (chi . fmap outr))
para :: Functor f => (f (Prod (Mu f) c) -> c) -> Mu f -> c
para = zygo In
-- factorial, the *hard* way!
fac = para phi where
phi Z = suck zero
phi (S (Pair f n)) = mult f (suck n)
-- for convenience and testing
int = cata phi where
phi Z = 0
phi (S f) = 1 + f
instance Show (Mu N) where
show = show . int
Tenured professor (teaching Haskell to freshmen)
fac n = product [1..n]
Solution 28 - Algorithm
PowerShell
function factorial( [int] $n )
{
$result = 1;
if ( $n -gt 1 )
{
$result = $n * ( factorial ( $n - 1 ) )
}
$result
}
Here's a one-liner:
$n..1 | % {$result = 1}{$result *= $_}{$result}
Solution 29 - Algorithm
Java 1.6: recursive, memoized (for subsequent calls)
private static Map<BigInteger, BigInteger> _results = new HashMap()
public static BigInteger factorial(BigInteger n){
if (0 >= n.compareTo(BigInteger.ONE))
return BigInteger.ONE.max(n);
if (_results.containsKey(n))
return _results.get(n);
BigInteger result = factorial(n.subtract(BigInteger.ONE)).multiply(n);
_results.put(n, result);
return result;
}
Solution 30 - Algorithm
Bash: Recursive
In bash and recursive, but with the added advantage that it deals with each iteration in a new process. The max it can calculate is !20 before overflowing, but you can still run it for big numbers if you don't care about the answer and want your system to fall over ;)
#!/bin/bash
echo $(($1 * ( [[ $1 -gt 1 ]] && ./$0 $(($1 - 1)) ) || echo 1));
Solution 31 - Algorithm
C/C++: Procedural
unsigned long factorial(int n)
{
unsigned long factorial = 1;
int i;
for (i = 2; i <= n; i++)
factorial *= i;
return factorial;
}
PHP: Procedural
function factorial($n)
{
for ($factorial = 1, $i = 2; $i <= $n; $i++)
$factorial *= $i;
return $factorial;
}
@Niyaz: You didn't specify return type for the function
Solution 32 - Algorithm
The problem with most of the above is that they will run out of precision at about 25! (12! with 32 bit ints) or just overflow. Here's a c# implementation to break through these limits!
class Number
{
public Number ()
{
m_number = "0";
}
public Number (string value)
{
m_number = value;
}
public int this [int column]
{
get
{
return column < m_number.Length ? m_number [m_number.Length - column - 1] - '0' : 0;
}
}
public static implicit operator Number (string rhs)
{
return new Number (rhs);
}
public static bool operator == (Number lhs, Number rhs)
{
return lhs.m_number == rhs.m_number;
}
public static bool operator != (Number lhs, Number rhs)
{
return lhs.m_number != rhs.m_number;
}
public override bool Equals (object obj)
{
return this == (Number) obj;
}
public override int GetHashCode ()
{
return m_number.GetHashCode ();
}
public static Number operator + (Number lhs, Number rhs)
{
StringBuilder
result = new StringBuilder (new string ('0', lhs.m_number.Length + rhs.m_number.Length));
int
carry = 0;
for (int i = 0 ; i < result.Length ; ++i)
{
int
sum = carry + lhs [i] + rhs [i],
units = sum % 10;
carry = sum / 10;
result [result.Length - i - 1] = (char) ('0' + units);
}
return TrimLeadingZeros (result);
}
public static Number operator * (Number lhs, Number rhs)
{
StringBuilder
result = new StringBuilder (new string ('0', lhs.m_number.Length + rhs.m_number.Length));
for (int multiplier_index = rhs.m_number.Length - 1 ; multiplier_index >= 0 ; --multiplier_index)
{
int
multiplier = rhs.m_number [multiplier_index] - '0',
column = result.Length - rhs.m_number.Length + multiplier_index;
for (int i = lhs.m_number.Length - 1 ; i >= 0 ; --i, --column)
{
int
product = (lhs.m_number [i] - '0') * multiplier,
units = product % 10,
tens = product / 10,
hundreds = 0,
unit_sum = result [column] - '0' + units;
if (unit_sum > 9)
{
unit_sum -= 10;
++tens;
}
result [column] = (char) ('0' + unit_sum);
int
tens_sum = result [column - 1] - '0' + tens;
if (tens_sum > 9)
{
tens_sum -= 10;
++hundreds;
}
result [column - 1] = (char) ('0' + tens_sum);
if (hundreds > 0)
{
int
hundreds_sum = result [column - 2] - '0' + hundreds;
result [column - 2] = (char) ('0' + hundreds_sum);
}
}
}
return TrimLeadingZeros (result);
}
public override string ToString ()
{
return m_number;
}
static string TrimLeadingZeros (StringBuilder number)
{
while (number [0] == '0' && number.Length > 1)
{
number.Remove (0, 1);
}
return number.ToString ();
}
string
m_number;
}
static void Main (string [] args)
{
Number
a = new Number ("1"),
b = new Number (args [0]),
one = new Number ("1");
for (Number c = new Number ("1") ; c != b ; )
{
c = c + one;
a = a * c;
}
Console.WriteLine (string.Format ("{0}! = {1}", new object [] { b, a }));
}
FWIW: 10000! is over 35500 character long.
Skizz
Solution 33 - Algorithm
Lambda Calculus
Input and output are Church numerals (i.e. natural number k
is \f n. f^k n
; so 3 = \f n. f (f (f n)))
(\x. x x) (\y f. f (y y f)) (\y n. n (\x y z. z) (\x y. x) (\f n. f n) (\f. n (y (\f m. n (\g h. h (g f)) (\x. m) (\x. x)) f)))
Solution 34 - Algorithm
The code below is tongue in cheek, however when you consider that the return value is limited to n < 34 for uint32, <65 uint64 before we run out of space for the return value with a uint, hard coding 33 values isn't that crazy :)
public static int Factorial(int n)
{
switch (n)
{
case 1:
return 1;
case 2:
return 2;
case 3:
return 6;
case 4:
return 24;
default:
throw new Exception("Sorry, I can only count to 4");
}
}
Solution 35 - Algorithm
Ruby: functional
def factorial(n)
return 1 if n == 1
n * factorial(n -1)
end
Solution 36 - Algorithm
#Icon
##Recursive function
procedure factorial(n)
return (0
return (0<n) * factorial(n-1) | (n=0 & 1)
Then
write(factorial(3))
write(factorial(-1))
write(factorial(20))
prints
6
2432902008176640000
##Iterative generator procedure factorials() local f,n f := 1; n := 0 repeat suspend f *:= (n +:= 1) end Then
every write(factorials() \ 5)
prints
1
2
6
24
120
To understand this: evaluation is goal-directed and backtracks on failure. There is no boolean type, and binary operators which would return a boolean in other languages, either fail or return their second argument - with the exception of |, which in a single-value context returns its first argument if it succeeds, otherwise tries its second argument. (in a multiple-value context it returns its first argument then its second argument)
suspend
is like yield
in other languages, except that a generator is not explicitly called multiple times to return its results. Instead,
every
asks its argument for all values but doesn't return anything by default; it's useful with side-effects (in this case I/O).
\
limits the number of values returned by a generator, which in the case of factorials
would be infinite.
Solution 37 - Algorithm
Clojure
Tail-recursive
(defn fact
([n] (fact n 1))
([n acc] (if (= n 0)
acc
(recur (- n 1) (* acc n)))))
Short and simple
(defn fact [n] (apply * (range 1 (+ n 1))))
Solution 38 - Algorithm
Haskell
factorial n = product [1..n]
Solution 39 - Algorithm
Nothing is as fast as bash & bc:
function fac { seq $1 | paste -sd* | bc; }
$ fac 42
1405006117752879898543142606244511569936384000000000
$
Solution 40 - Algorithm
Mathematica : using pure recursive functions
(If[#>1,# #0[#-1],1])&
Solution 41 - Algorithm
Lua
function factorial (n)
if (n <= 1) then return 1 end
return n*factorial(n-1)
end
And here is a stack overflow caught in the wild:
> print (factorial(234132))
stdin:3: stack overflow
stack traceback:
stdin:3: in function 'factorial'
stdin:3: in function 'factorial'
stdin:3: in function 'factorial'
stdin:3: in function 'factorial'
stdin:3: in function 'factorial'
stdin:3: in function 'factorial'
stdin:3: in function 'factorial'
stdin:3: in function 'factorial'
stdin:3: in function 'factorial'
stdin:3: in function 'factorial'
...
stdin:3: in function 'factorial'
stdin:3: in function 'factorial'
stdin:3: in function 'factorial'
stdin:3: in function 'factorial'
stdin:3: in function 'factorial'
stdin:3: in function 'factorial'
stdin:3: in function 'factorial'
stdin:3: in function 'factorial'
stdin:1: in main chunk
[C]: ?
Solution 42 - Algorithm
Agda 2: Functional, dependently typed.
data Nat = zero | suc (m::Nat)
add (m::Nat) (n::Nat) :: Nat
= case m of
(zero ) -> n
(suc p) -> suc (add p n)
mul (m::Nat) (n::Nat)::Nat
= case m of
(zero ) -> zero
(suc p) -> add n (mul p n)
factorial (n::Nat)::Nat
= case n of
(zero ) -> suc zero
(suc p) -> mul n (factorial p)
Solution 43 - Algorithm
Delphi
facts: array[2..12] of integer;
function TForm1.calculate(f: integer): integer;
begin
if f = 1 then
Result := f
else if f > High(facts) then
Result := High(Integer)
else if (facts[f] > 0) then
Result := facts[f]
else begin
facts[f] := f * Calculate(f-1);
Result := facts[f];
end;
end;
initialize
for i := Low(facts) to High(facts) do
facts[i] := 0;
After the first time a factorial higher or equal to the desired value has been calculated, this algorithm just returns the factorial in constant time O(1).
It takes in account that int32 only can hold up to 12!
Solution 44 - Algorithm
Nemerle: Functional
def fact(n) {
| 0 => 1
| x => x * fact(x-1)
}
Solution 45 - Algorithm
#Language: T-SQL
#Style: Recursive, divide and conquer
Just for fun - in T-SQL using a divide and conquer recursive method. Yes, recursive - in SQL without stack overflow.
create function factorial(@b int=1, @e int) returns float as begin
return case when @b>=@e then @e else
convert(float,dbo.factorial(@b,convert(int,@b+(@e-@b)/2)))
* convert(float,dbo.factorial(convert(int,@b+1+(@e-@b)/2),@e)) end
end
call it like this:
print dbo.factorial(1,170) -- the 1 being the starting number
Solution 46 - Algorithm
PostScript: Tail Recursive
/fact0 { dup 2 lt { pop } { 2 copy mul 3 1 roll 1 sub exch pop fact0 } ifelse } def
/fact { 1 exch fact0 } def
Solution 47 - Algorithm
Forth (recursive):
: factorial ( n -- n ) dup 1 > if dup 1 - recurse * else drop 1 then ;
Solution 48 - Algorithm
Scala
The factorial can be defined functionally as:
def fact(n: Int): BigInt = 1 to n reduceLeft(_*_)
or more traditionally as
def fact(n: Int): BigInt = if (n == 0) 1 else fact(n-1) * n
and we can make ! a valid method on Ints:
object extendBuiltins extends Application {
class Factorizer(n: Int) {
def ! = 1 to n reduceLeft(_*_)
}
implicit def int2fact(n: Int) = new Factorizer(n)
println("10! = " + (10!))
}
Solution 49 - Algorithm
Compile time in C++
template<unsigned i>
struct factorial
{ static const unsigned value = i * factorial<i-1>::value; };
template<>
struct factorial<0>
{ static const unsigned value = 1; };
Use in code as:
Factorial<5>::value
Solution 50 - Algorithm
Java Script: Creative method using "interview question" counting bits fnc.
function nu(x)
{
var r=0
while( x ) {
x &= x-1
r++
}
return r
}
function fac(n)
{
var r= Math.pow(2,n-nu(n))
for ( var i=3 ; i <= n ; i+= 2 )
r *= Math.pow(i,Math.floor(Math.log(n/i)/Math.LN2)+1)
return r
}
Works up to 21! then Chrome switches to scientific notation. Inspiration thanks lack of sleep and Knuth, et al's "concrete mathematics".
Solution 51 - Algorithm
Brainfuck: with bignum support!
Accepts as input a non-negative integer followed by newline, and outputs the corresponding factorial followed by newline.
>>>>,----------[>>>>,----------]>>>>++<<<<<<<<[>++++++[<------>-]<-<<<<]>>>>[[>>+<<-]>>[<<+>+>-]<->+<[>>>>+<<<-<[-]]>[-]
>>]>[-<<<<<[<<<<]>>>>[[>>+<<-]>>[<<+>+>-]>>]>>>>[-[>+<-]+>>>
>]<<<<[<<<<]<<<<[<<<<]>>>>>[>>>[>>>>]>>>>[>>>>]<<<<[[>>>>+<<<<-]<<<<]>>>>+<<<<<<<[<<<<]>>>>-[>>>[>>>>]>>>>[>>>>]<<<<[>>>+<<<-]>>>[<<<+>>+>-]<-[>>+<<[-]]<<[<<<<]>>>>[>[>+<-]>[<<+>+>-]<<[>>>+<<<-]>>>[<<<+>>+>-]<->+++++++++[-<[-[>>>>+<<<<-]]>>
>>[<<<<+>>>>-]<<<]<[>>+<<<<[-]>>[<<+>>-]]>>]<<<<[<<<<]<<<[<<<<]>>>>-]>>>>]>>>[>[-]>>>]<<<<[>>+<<-]>>[<<+>+>-]<->+<[>-<[-]]>[-<<-<<<<[>>+<<-]>>[<<+>+>-]<->+<[>-<[-]]>]<<[<<<<]<<<<-[>>+<<-]>>[<<+>+>-]+<[>-<[-]]>[-<<++++++++++<<<<-[>>+<<-]>>[<<+>+>-]+<[>-<[-]]>]<<[<<<<]>>>>[[>>+<<-]>>[<<+>+>-]<->+<[>>>>+<<<-<[-]]>[-]>>]>]>>>[>>>>]<<<<[>+++++++[<+++++++>-]<--.<<
<<]++++++++++.
Unlike the brainf*ck answer posted earlier, this does not overflow any memory locations. (That implementation put n! in a single memory location, effectively limiting it to n less than 6 under standard bf rules.) This program will output n! for any value of n, limited only by time and memory (or bf implementation). For example, using Urban Muller's compiler on my machine, it takes 12 seconds to compute 1000! I think that's pretty good, considering the program can only move left/right and increment/decrement by one.
Believe it or not, this is the first bf program I've written; it took about 10 hours, which were mostly spent debugging. Unfortunately, I later found out that Daniel B Cristofani has written a factorial generator, which just outputs ever-larger factorials, never terminating:
>++++++++++>>>+>+[>>>+[-[<<<<<[+<<<<<]>>[[-]>[<<+>+>-]<[>+<-]<[>+<-[>+<-[>+<-[>+<-[>+<-[>+<-[>+<-[>+<-[>+<-[>[-]>>>>+>+<
<<<<<-[>+<-]]]]]]]]]]]>[<+>-]+>>>>>]<<<<<[<<<<<]>>>>>>>[>>>>>]++[-<<<<<]>>>>>>-]+>>>>>]<[>++<-]<<<<[<[>+<-]<<<<]>>[->[-]
++++++[<++++++++>-]>>>>]<<<<<[<[>+>+<<-]>.<<<<<]>.>>>>]
His program is much shorter, but he's practically a professional bf golfer.
Solution 52 - Algorithm
Agda2
It is Agda2, using the very nice Agda2 syntax.
module fac where
data Nat : Set where -- Peano numbers
zero : Nat
suc : Nat -> Nat
{-# BUILTIN NATURAL Nat #-}
{-# BUILTIN SUC suc #-}
{-# BUILTIN ZERO zero #-}
infixl 10 _+_ -- Addition over Peano numbers
_+_ : Nat -> Nat -> Nat
zero + n = n
(suc n) + m = suc (n + m)
infixl 20 _*_ -- Multiplication over Peano numbers
_*_ : Nat -> Nat -> Nat
zero * n = zero
n * zero = zero
(suc n) * (suc m) = suc n + (suc n * m)
_! : Nat -> Nat -- Factorial function, syntax: "x !"
zero ! = suc zero
(suc n) ! = (suc n) * (n !)
Solution 53 - Algorithm
Python: functional, recursive one-liner using short circuit boolean evaluation.
factorial = lambda n: ((n <= 1) and 1) or factorial(n-1) * n
Solution 54 - Algorithm
#Perl 6: Functional# multi factorial ( Int $n where { $n <= 0 } ){ return 1; } multi factorial ( Int $n ){ return $n * factorial( $n-1 ); }
This will also work:
multi factorial(0) { 1 }
multi factorial(Int $n) { $n * factorial($n - 1) }
Check Jonathan Worthington's journal on use.perl.org, for more information about the last example.
Solution 55 - Algorithm
Perl 6:Procedural
sub factorial ( int $n ){
my $result = 1;
loop ( ; $n > 0; $n-- ){
$result *= $n;
}
return $result;
}
Solution 56 - Algorithm
C:
Edit: Actually C++ I guess, because of the variable declaration in the for loop.
int factorial(int x) {
int product = 1;
for (int i = x; i > 0; i--) {
product *= i;
}
return product;
}
Solution 57 - Algorithm
Javascript:
factorial = function( n )
{
return n > 0 ? n * factorial( n - 1 ) : 1;
}
I'm not sure what a Factorial is but that does what the other programs do in javascript.
Solution 58 - Algorithm
Python:
Recursive
def fact(x):
return (1 if x==0 else x * fact(x-1))
Using iterator
import operator
def fact(x):
return reduce(operator.mul, xrange(1, x+1))
Solution 59 - Algorithm
two of many Mathematica solutions (although ! is built-in and efficient):
(* returns pure function *)
(FixedPoint[(If[#[[2]]>1,{#[[1]]*#[[2]],#[[2]]-1},#])&,{1,n}][[1]])&
(* not using built-in, returns pure function, don't use: might build 1..n list *)
(Times @@ Range[#])&
Solution 60 - Algorithm
Visual Basic: Linq
<Extension()> _
Public Function Product(ByVal xs As IEnumerable(Of Integer)) As Integer
Return xs.Aggregate(1, Function(a, b) a * b)
End Function
Public Function Fact(ByVal n As Integer) As Integer
Return Aggregate x In Enumerable.Range(1, n) Into Product()
End Function
This shows how to use the Aggregate
keyword in VB. C# can't do this (although C# can of course call the extension method directly).
Solution 61 - Algorithm
Scheme : Functional - Tail Recursive
(define (factorial n)
(define (fac-times n acc)
(if (= n 0)
acc
(fac-times (- n 1) (* acc n))))
(if (< n 0)
(display "Wrong argument!")
(fac-times n 1)))
Solution 62 - Algorithm
#Ruby: Iterative
def factorial(n)
(1 .. n).inject{|a, b| a*b}
end
#Ruby: Recursive
def factorial(n)
n == 1 ? 1 : n * factorial(n-1)
end
Solution 63 - Algorithm
#Language: T-SQL
#Style: Big Numbers
Here's another T-SQL solution -- supports big numbers in a most Rube Goldbergian manner. Lots of set-based ops. Tried to keep it uniquely SQL. Horrible performance (400! took 33 seconds on a Dell Latitude D830)
create function bigfact(@x varchar(max)) returns varchar(max) as begin
declare @c int
declare @n table(n int,e int)
declare @f table(n int,e int)
set @c=0
while @c<len(@x) begin
set @c=@c+1
insert @n(n,e) values(convert(int,substring(@x,@c,1)),len(@x)-@c)
end
-- our current factorial
insert @f(n,e) select 1,0
while 1=1 begin
declare @p table(n int,e int)
delete @p
-- product
insert @p(n,e) select sum(f.n*n.n), f.e+n.e from @f f cross join @n n group by f.e+n.e
-- normalize
while 1=1 begin
delete @f
insert @f(n,e) select sum(n),e from (
select (n % 10) as n,e from @p union all
select (n/10) % 10,e+1 from @p union all
select (n/100) %10,e+2 from @p union all
select (n/1000)%10,e+3 from @p union all
select (n/10000) % 10,e+4 from @p union all
select (n/100000)% 10,e+5 from @p union all
select (n/1000000)%10,e+6 from @p union all
select (n/10000000) % 10,e+7 from @p union all
select (n/100000000)% 10,e+8 from @p union all
select (n/1000000000)%10,e+9 from @p
) f group by e having sum(n)>0
set @c=0
select @c=count(*) from @f where n>9
if @c=0 break
delete @p
insert @p(n,e) select n,e from @f
end
-- decrement
update @n set n=n-1 where e=0
-- normalize
while 1=1 begin
declare @e table(e int)
delete @e
insert @e(e) select e from @n where n<0
if @@rowcount=0 break
update @n set n=n+10 where e in (select e from @e)
update @n set n=n-1 where e in (select e+1 from @e)
end
set @c=0
select @c=count(*) from @n where n>0
if @c=0 break
end
select @c=max(e) from @f
set @x=''
declare @l varchar(max)
while @c>=0 begin
set @l='0'
select @l=convert(varchar(max),n) from @f where e=@c
set @x=@x+@l
set @c=@c-1
end
return @x
end
Example:
print dbo.bigfact('69')
returns:
171122452428141311372468338881272839092270544893520369393648040923257279754140647424000000000000000
Solution 64 - Algorithm
ChucK
Language Name:Moog moog => dac;
4.0 => moog.gain;
for (0 => int i; i < 8; i++) {
<<< factorial(i) >>>;
}
fun int factorial(int n) {
1 => int result;
if (n != 0) {
n * factorial(n - 1) => result;
}
Std.mtof(result % 128) => moog.freq;
0.25::second => now;
return result;
}
And it sounds like this. Not terribly interesting, but, hey, it's just a factorial function!
Solution 65 - Algorithm
Simple solutions are the best:
#include <stdexcept>;
long fact(long f)
{
static long fact [] = { 1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600, 1932053504, 1278945280, 2004310016, 2004189184 };
static long max = sizeof(fact)/sizeof(long);
if ((f < 0) || (f >= max))
{ throw std::range_error("Factorial Range Error");
}
return fact[f];
}
Solution 66 - Algorithm
Common Lisp: Lisp as God intended it to be used (that is, with LOOP)
(defun fact (n)
(loop for i from 1 to n
for acc = 1 then (* acc i)
finally (return acc)))
Now, if someone can come up with a version based on FORMAT...
Solution 67 - Algorithm
Common Lisp: FORMAT (obfuscated)
Okay, so I'll give it a try myself.
(defun format-fact (stream arg colonp atsignp &rest args)
(destructuring-bind (n acc) arg
(format stream
"~[~A~:;~*~/format-fact/~]"
(1- n)
acc
(list (1- n) (* acc n)))))
(defun fact (n)
(parse-integer (format nil "~/format-fact/" (list n 1))))
There has to be a nicer, even more obscure FORMAT-based implementation. This one is pretty straight-forward and boring, simply using FORMAT as an IF replacement. Obviously, I'm not a FORMAT expert.
Solution 68 - Algorithm
AWK
#!/usr/bin/awk -f
{
result=1;
for(i=$1;i>0;i--){
result=result*i;
}
print result;
}
Solution 69 - Algorithm
#Language: T-SQL, C#
#Style: Custom Aggregate
Another crazy way would be to create a custom aggregate and apply it over a temporary table of the integers 1..n.
/* ProductAggregate.cs */
using System;
using System.Data.SqlTypes;
using Microsoft.SqlServer.Server;
[Serializable]
[SqlUserDefinedAggregate(Format.Native)]
public struct product {
private SqlDouble accum;
public void Init() { accum = 1; }
public void Accumulate(SqlDouble value) { accum *= value; }
public void Merge(product value) { Accumulate(value.Terminate()); }
public SqlDouble Terminate() { return accum; }
}
add this to sql
create assembly ProductAggregate from 'ProductAggregate.dll' with permission_set=safe -- mod path to point to actual dll location on disk.
create aggregate product(@a float) returns float external name ProductAggregate.product
create the table (there should be a built-in way to do this in SQL -- hmm. a question for SO?)
select 1 as n into #n union select 2 union select 3 union select 4 union select 5
then finally
select dbo.product(n) from #n
Solution 70 - Algorithm
Haskell:
factorial n = product [1..n]
Solution 71 - Algorithm
Eiffel
class
APPLICATION
inherit
ARGUMENTS
create
make
feature -- Initialization
make is
-- Run application.
local
l_fact: NATURAL_64
do
l_fact := factorial(argument(1).to_natural_64)
print("Result is: " + l_fact.out)
end
factorial(n: NATURAL_64): NATURAL_64 is
--
require
positive_n: n >= 0
do
if n = 0 then
Result := 1
else
Result := n * factorial(n-1)
end
end
end -- class APPLICATION
end -- class APPLICATION
Solution 72 - Algorithm
befunge-93
v
>v"Please enter a number (1-16) : "0<
,: >$*99g1-:99p#v_.25*,@
^_&:1-99p>:1-:!|10 <
^ <
An esoteric language by Chris Pressey of Cat's Eye Technologies.
Solution 73 - Algorithm
Perl (Y-combinator/Functional)
print sub {
my $f = shift;
sub {
my $f1 = shift;
$f->( sub { $f1->( $f1 )->( @_ ) } )
}->( sub {
my $f2 = shift;
$f->( sub { $f2->( $f2 )->( @_ ) } )
} )
}->( sub {
my $h = shift;
sub {
my $n = shift;
return 1 if $n <=1;
return $n * $h->($n-1);
}
})->(5);
Everything after 'print' and before the '->(5)' represents the subroutine. The factorial part is in the final "sub {...}". Everything else is to implement the Y-combinator.
Solution 74 - Algorithm
J
fact=. verb define
*/ >:@i. y
)
Solution 75 - Algorithm
Smalltalk, using a closure
fac := [ :x | x = 0 ifTrue: [ 1 ] ifFalse: [ x * (fac value: x -1) ]].
Transcript show: (fac value: 24) "-> 620448401733239439360000"
NB does not work in Squeak, requires full closures.
Solution 76 - Algorithm
Smalltalk, memoized
Define a method on Dictionary
Dictionary >> fac: x
^self at: x ifAbsentPut: [ x * (self fac: x - 1) ]
usage
d := Dictionary new.
d at: 0 put: 1.
d fac: 24
Solution 77 - Algorithm
Smalltalk, 1-Liner
(1 to: 24) inject: 1 into: [ :a :b | a * b ]
Solution 78 - Algorithm
Mathematica: non-recursive
fact[n_] := Times @@ Range[n]
Which is syntactic sugar for Apply[Times, Range[n]]
. I think that's the best way to do it, not counting the built-in n!
, of course. Note that that automatically uses bignums.
Solution 79 - Algorithm
Common Lisp version:
(defun ! (n) (reduce #'* (loop for i from 2 below (+ n 1) collect i)))
Seems to be quite fast.
* (! 42)
1405006117752879898543142606244511569936384000000000
Solution 80 - Algorithm
Delphi iterative
While recursion can be the only decent solution to a problem, for factorials it is not. To describe it, yes. To program it, no. Iteration is cheapest.
This function calculates factorials for somewhat larger arguments.
function Factorial(aNumber: Int64): String;
var
F: Double;
begin
F := 0;
while aNumber > 1 do begin
F := F + log10(aNumber);
dec(aNumber);
end;
Result := FloatToStr(Power(10, Frac(F))) + ' * 10^' + IntToStr(Trunc(F));
end;
1000000! = 8.2639327850046 * 10^5565708
Solution 81 - Algorithm
Logo
? to factorial :n
> ifelse :n = 0 [output 1] [output :n * factorial :n - 1]
> end
And to invoke:
? print factorial 5
120
This is using the UCBLogo dialect of logo.
Solution 82 - Algorithm
Perl, pessimal:
# Because there are just so many other ways to get programs wrong...
use strict;
use warnings;
sub factorial {
my ($x)=@_;
for(my $f=1;;$f++) {
my $tmp=$f;
foreach my $g (1..$x) {
$tmp/=$g;
}
return $f if $tmp == 1;
}
}
I trust I get extra points for not using the '*' operator...
Solution 83 - Algorithm
*NIX Shell
Linux version:
seq -s'*' 42 | bc
BSD version:
jot -s'*' 42 | bc
Solution 84 - Algorithm
FORTH, iterative 1 liner
: FACT 1 SWAP 1 + 1 DO I * LOOP ;
Solution 85 - Algorithm
Scheme evolution
Regular Scheme program:
(define factorial
(lambda (n)
(if (= n 0)
1
(* n (factorial (- n 1))))))
Should work, but notice that calling this function on large numbers will extend the stack on every recursion, which is bad in languages like C and Java.
Continuation-passing style
(define factorial
(lambda (n)
(factorial_cps n (lambda (k) k))))
(define factorial_cps
(lambda (n k)
(if (zero? n)
(k 1)
(factorial (- n 1) (lambda (v)
(k (* n v)))))))
Ah, this way, we don't grow our stack every recursion because we can extend a continuation instead. However, C doesn't have continuations.
Representation-independent CPS
(define factorial
(lambda (n)
(factorial_cps n (k_))))
(define factorial_cps
(lambda (n k)
(if (zero? n)
(apply_k 1)
(factorial (- n 1) (k_extend n k))))
(define apply_k
(lambda (ko v)
(ko v)))
(define kt_empty
(lambda ()
(lambda (v) v)))
(define kt_extend
(lambda ()
(lambda (v)
(apply_k k (* n v)))))
Notice that responsibility for representation of the continuations used in the original CPS program has been shifted to the kt_
helper procedures.
Representation-independent CPS using ParentheC unions
Since representation of the continuations is in the helper procedures, we can switch to using ParentheC instead, with kt_
being a type designator.
(define factorial
(lambda (n)
(factorial_cps n (kt_empty))))
(define factorial_cps
(lambda (n k)
(if (zero? n)
(apply_k 1)
(factorial (- n 1) (kt_extend n k))))
(define-union kt
(empty)
(extend n k))
(define apply_k
(lambda ()
(union-case kh kt
[(empty) v]
[(extend n k) (begin (set! kh k) (set! v (* n v)) (apply_k))])))
Trampolined, registerized ParentheC program
That's not enough. We now replace all function calls by instead setting global variables and a program counter. Procedures are now labels suitable for GOTO statements.
(define-registers n k kh v)
(define-program-counter pc)
(define-label main
(begin
(set! n 5) ; what is the factorial of 5??
(set! pc factorial_cps)
(mount-trampoline kt_empty k pc)
(printf "Factorial of 5: ~d\n" v)))
(define-label factorial_cps
(if (zero? n)
(begin
(set! kh k)
(set! v 1)
(set! pc apply_k))
(begin
(set! k (kt_extend n k))
(set! n (- n 1))
(set! pc factorial_cps))))
(define-union kt
(empty dismount) ; get off the trampoline!
(extend n k))
(define-label apply_k
(union-case kh kt
[(empty dismount) (dismount-trampoline dismount)]
[(extend n k) (begin
(set! kh k)
(set! v (* n v))
(set! pc apply_k))]))
Oh look, we have a main
procedure now too. Now all that's left to do is save this file as fact5.pc
and run it through ParentheC's pc2c:
> (load "pc2c.ss")
> (pc2c "fact5.pc" "fact5.c" "fact5.h")
Could it be? We got fact5.c
and fact5.h
. Let's see...
$ gcc fact5.c -o fact5
$ ./fact5
Factorial of 5: 120
Success! We have converted a recursive Scheme program into a non-recursive C program! And it only took several hours and many forehead-shaped impressions in the wall to do it! For convenience, fact5.c and and fact5.h.
Solution 86 - Algorithm
C++
factorial(int n)
{
for(int i=1, f = 1; i<=n; i++)
f *= i;
return f;
}
Solution 87 - Algorithm
Java: functional
int factorial(int x) {
return x == 0 ? 1 : x * factorial(x-1);
}
Solution 88 - Algorithm
Haskell: Functional
fact 0 = 1
fact n = n * fact (n-1)
Solution 89 - Algorithm
This one not only calculates n!, it is also O(n!). It may have problems if you want to calculate anything "big" though.
long f(long n)
{
long r=1;
for (long i=1; i<n; i++)
r=r*i;
return r;
}
long factorial(long n)
{
// iterative implementation should be efficient
long result;
for (long i=0; i<f(n); i++)
result=result+1;
return result;
}
Solution 90 - Algorithm
Bourne Shell: Functional
factorial() {
if [ $1 -eq 0 ]
then
echo 1
return
fi
a=`expr $1 - 1`
expr $1 \* `factorial $a`
}
Also works for Korn Shell and Bourne Again Shell. :-)
Solution 91 - Algorithm
Lisp recursive:
(defun factorial (x)
(if (<= x 1)
1
(* x (factorial (- x 1)))))
Solution 92 - Algorithm
JavaScript Using anonymous functions:
var f = function(n){
if(n>1){
return arguments.callee(n-1)*n;
}
return 1;
}
Solution 93 - Algorithm
C: One liner, procedural
int f(int n) { for (int i = n - 1; i > 0; n *= i, i--); return n ? n : 1; }
I used int's for brevity; use other types to support larger numbers.
Solution 94 - Algorithm
Python, C/C++ (weave): Multi-Language, Procedural
Four implementations:
- [weave]
- [python]
- [psyco]
- [list]
Code:
#!/usr/bin/env python
""" weave_factorial.py
"""
# [weave] factorial() as extension module in C++
from scipy.weave import ext_tools
def build_factorial_ext():
func = ext_tools.ext_function(
'factorial',
r"""
unsigned long long i = 1;
for ( ; n > 1; --n)
i *= n;
PyObject *o = PyLong_FromUnsignedLongLong(i);
return_val = o;
Py_XDECREF(o);
""",
['n'],
{'n': 1}, # effective type declaration
{})
mod = ext_tools.ext_module('factorial_ext')
mod.add_function(func)
mod.compile()
try: from factorial_ext import factorial as factorial_weave
except ImportError:
build_factorial_ext()
from factorial_ext import factorial as factorial_weave
# [python] pure python procedural factorial()
def factorial_python(n):
i = 1
while n > 1:
i *= n
n -= 1
return i
# [psyco] factorial() psyco-optimized
try:
import psyco
factorial_psyco = psyco.proxy(factorial_python)
except ImportError:
pass
# [list] list-lookup factorial()
factorials = map(factorial_python, range(21))
factorial_list = lambda n: factorials[n]
Measure relative performance:
$ python -mtimeit \
-s "from weave_factorial import factorial_$label as f" "f($n)"
-
n = 12
- [weave] 0.70 µsec (2)
- [python] 3.8 µsec (9)
- [psyco] 1.2 µsec (3)
- [list] 0.43 µsec (1)
-
n = 20
- [weave] 0.85 µsec (2)
- [python] 9.2 µsec (21)
- [psyco] 4.3 µsec (10)
- [list] 0.43 µsec (1)
µsec stands for microseconds.
Solution 95 - Algorithm
Here is an interesting Ruby version. On my laptop it will find 30000! in under a second. (It takes longer for Ruby to format it for printing than to calculate it.) This is significantly faster than the naive solution of just multiplying the numbers in order.
def factorial (n)
return multiply_range(1, n)
end
def multiply_range(n, m)
if (m < n)
return 1
elsif (n == m)
return m
else
i = (n + m) / 2
return multiply_range(n, i) * multiply_range(i+1, m)
end
end
Solution 96 - Algorithm
Scala: Recursive
- Should compile to being tail recursive. Should!
.
def factorial( value: BigInt ): BigInt = value match {
case 0 => 1
case _ => value * factorial( value - 1 )
}
Solution 97 - Algorithm
Occam-pi
PROC subprocess(MOBILE CHAN INT parent.out!,parent.in?)
INT value:
SEQ
parent.in ? value
IF
value = 1
SEQ
parent.out ! value
OTHERWISE
INITIAL MOBILE CHAN INT child.in IS MOBILE CHAN INT:
INITIAL MOBILE CHAN INT child.out IS MOBILE CHAN INT:
FORKING
INT newvalue:
SEQ
FORK subprocess(child.in!,child.out?)
child.out ! (value-1)
child.in ? newvalue
parent.out ! (newalue*value)
:
PROC main(CHAN BYTE in?,src!,kyb?)
INITIAL INT value IS 0:
INITIAL MOBILE CHAN INT child.out is MOBILE CHAN INT
INITIAL MOBILE CHAN INT child.in is MOBILE CHAN INT
SEQ
WHILE TRUE
SEQ
subprocess(child.in!,child.out?)
child.out ! value
child.in ? value
src ! value:
value := value + 1
:
Solution 98 - Algorithm
OCaml
Lest anyone believe OCaml and oddball go hand-in-hand, I thought I would provide a sane implementation of factorial.
# let rec factorial n =
if n=0 then 1 else n * factorial(n - 1);;
I don't think I made my case very well...
Solution 99 - Algorithm
Genuinely functional Java:
public final class Factorial {
public static void main(String[] args) {
final int n = Integer.valueOf(args[0]);
System.out.println("Factorial of " + n + " is " + create(n).apply());
}
private static Function create(final int n) {
return n == 0 ? new ZeroFactorialFunction() : new NFactorialFunction(n);
}
interface Function {
int apply();
}
private static class NFactorialFunction implements Function {
private final int n;
public NFactorialFunction(final int n) {
this.n = n;
}
@Override
public int apply() {
return n * Factorial.create(n - 1).apply();
}
}
private static class ZeroFactorialFunction implements Function {
@Override
public int apply() {
return 1;
}
}
}
Solution 100 - Algorithm
C# factorial using recursion in a single line
private static int factorial(int n){ if (n == 0)return 1;else return n * factorial(n - 1); }