Download or view BinarySplittingFactorial.frink in plain text format
/** This demonstrates using a binary splitting algorithm to calculate very
large factorials. This can be faster than using the naive calculation.
Frink caches factorials up to a certain size (currently the largest is
10000!) and returns them directly from a cache. When building this cache,
all factorials smaller than that factorial are calculated and stored.
http://www.oocities.org/hjsmithh/Numbers/BinSplit.html
This file is no longer necessary as Frink now uses a binary splitting
algorithm to calculate giant factorials that are too big to fit into its
cache. Its algorithm, though, follows this very closely.
This function actually calculates a! / b! so it can be used to calculate
ratios of factorials, or the factorial n! by calling p[n, 0]
*/
p[a,b] :=
{
diff = a-b
// println["$a $b $diff"]
if diff > 3
{
m = (a+b) div 2
return p[a, m] * p[m,b]
}
if diff == 0
return 1
if diff == 1
return a
// The following cases are not strictly necessary but they reduce the
// amount of recursion necessary.
if diff == 2
return a(a-1)
if diff == 3
return a(a-1)(a-2)
return 0
}
// Calculate the factorial n! using a binary splitting algorithm. p[a,b]
// is equal to a! / b! so we can use it to calculate a! by setting b to 0.
factorialSplit[n] := p[n,0]
// Attempt to calculate binomial coefficents, that is
// m! / ((m-n)! n!)
// Which we can maybe do faster using binary spliting because p[a,b] calculates
// a! / b! so we've done a lot of dividing out already (by never dividing at
// all; there are just multiplications in calculating a! / b! )
//
// This implementation is no longer necessary. As of the 2017-04-04 release
// of Frink, binomial coefficients are calculated using binary splitting.
// However, Frink's implementation follows this closely.
binomialSplit[m,n] :=
{
if m < n
return 0
// Since binomial[m, n] == binomial[m, m-n], use the one that will give
// the larger divisor b! and thus the smaller initial value that needs to
// be divided later.
if n < (m-n)
n = m - n
inter = p[m,n]
// println["Inter is $inter"]
divisor = (m-n)!
// println["Dividing by " + (m-n) + "! = $divisor"]
return inter / divisor
}
/* Timing and tests */
/*
bss = 0 s
bs = 0 s
for i = 1 to 20000
{
m = random[0,15000]
n = random[0,m]
s = now[]
a = binomialSplit[m,n]
e = now[]
bss = bss + (e-s)
s = now[]
b = binomial[m,n]
e = now[]
bs = bs + (e-s)
if b != m!/((m-n)! n!)
println["$m $n"]
}
println["Time in binomialSplit: " + bss]
println["Time in binomial: " + bs]
*/
Download or view BinarySplittingFactorial.frink in plain text format
This is a program written in the programming language Frink.
For more information, view the Frink
Documentation or see More Sample Frink Programs.
Alan Eliasen was born 20217 days, 15 hours, 43 minutes ago.