In this post, I’d like to demonstrate a few ways of computing factorials using the Raku programming language.
1 — reduction
Let me start with the basic and the most effective (non necessarily the most efficient) form of computing the factorial of a given integer number:
say [*] 1..10; # 3628800
In the below examples, we mostly will be dealing with the factorial of 10, so remember the result. But to make the programs more versatile, let us read the number from the command line:
unit sub MAIN($n); say [*] 1..$n;
To run the program, pass the number:
$ raku 00-cmd.raku 10 3628800
The program uses the reduction meta-operator [ ] with the main operator * in it.
You can also start with 2 (you can even compute 0! and 1! this way).
unit sub MAIN($n); say [*] 2..$n;
2 — for
The second solution is using a postfix for loop to multiply the numbers in the range:
unit sub MAIN($n); my $f = 1; $f *= $_ for 2..$n; say $f;
This solution is not that expressive but still demonstrates quite a clear code.
3 — map
You can also use map that is applied to a range:
unit sub MAIN($n); my $f = 1; (2..$n).map: $f *= *; say $f;
Refer to my article All the stars of Perl 6, or * ** * to learn more about how to read *= *.
4 — recursion
Let’s implement a recursive solution.
unit sub MAIN($n);
sub factorial($n) {
if $n < 2 {
return 1;
}
else {
return $n * factorial($n - 1);
}
}
say factorial(n);
There are two branches, one of which terminates recursion.
5 — better recursion
The previous program can be rewritten to make a code with less punctuation:
unit sub MAIN($n);
sub factorial($n) {
return 1 if $n < 2;
return $n * factorial($n - 1);
}
say factorial($n);
Here, the first return is managed by a postfix if, and the second return can only be reached if the condition in if is false. So, neither an additional Boolean test nor else is needed.
6 — big numbers
What if you need to compute a factorial of a relatively big number? No worries, Raku will just do it:
say [*] 1..500;
The speed is more than acceptable for any practical application:
raku 06-long-factorial.raku 0.14s user 0.02s system 124% cpu 0.127 total
7 — small numbers
Let’s try something opposite and compute a factorial, which can fit a native integer:
unit sub MAIN($n); my int $f = 1; $f *= $_ for 2..$n; say $f;
I am using a for loop here, but notice that the type of $f is a native integer (thus, 4 bytes). This program works with the numbers up to 20:
$ raku 07-int-factorial.raku 20 2432902008176640000
8 — sequence
The fun fact is that you can add a dot to the first program 🙂
unit sub MAIN($n); say [*] 1 ... $n;
Now, 1 ... $n is a sequence. You can start it with 2 if you are not planning to compute a factorials of 0 and 1.
9 — reversed sequence
Unlike the solution with a range, it is possible to swap the ends of the sequence:
unit sub MAIN($n); say [*] $n ... 1;
10 — sequence with definition
Nothing stops us from defining the elements of the sequence with a code block. The next program shows how you do it:
unit sub MAIN($n); my @f = 1, * * ++$ ... *; say @f[$n];
This time, the program generates a sequence of factorials from 1! to $n!, and to print the only one we need, we take the value from the array as @f[$n]. Notice that the sequence itself is lazy and its right end is undefined, so you can’t use @f[*-1], for example.
The rule here is * * ++$ (multiply the last computed value by the incremented index); it is using the built-in state variable $.
11 — multi functions
The idea of the solutions 4 and 5 with two branches can be further transformed to using multi-functions:
unit sub MAIN($n);
multi sub factorial(1) { 1 }
multi sub factorial($n) { $n * factorial($n - 1) }
say factorial($n);
For the numbers above 1, Raku calls the second variant of the function. When the number comes down to 1, recursion stops, because the first variant is called. Notice how easily you can create a variant of a function that only reacts to the given value.
12 — where
The previous program loops infinitely if you try to set $n to 0. One of the simplest solution is to add a where clause to catch that case too.
unit sub MAIN($n);
multi sub factorial($n where $n < 2) { 1 }
multi sub factorial($n) { $n * factorial($n - 1) }
say factorial($n);
13 — operator
Here’s another classical Raku solution: modifying its grammar to allow mathematical notation $n!.
unit sub MAIN($n);
sub postfix:<!>($n) {
[*] 1..$n
}
say $n!;
14 — methodop
A rarely seen Raku’s feature called methodop (method operator) that allows you to call a function as it if was a method:
unit sub MAIN($n);
sub factorial($n) {
[*] 1..$n
}
say $n.&factorial;
15 — cached
Recursive solutions are perfect subjects for result caching. The following program demonstrates this approach.
unit sub MAIN($n);
use experimental :cached;
sub f($n) is cached {
say "Called f($n)";
return 1 if $n < 2;
return $n * f($n - 1);
}
say f($n div 2);
say f(10);
This program first computes a factorial of the half of the input number, and then of the number itself. The program logs all the calls of the function. You can clearly see that, say, the factorial of 10 is using the results that were already computed for the factorial of 5:
$ raku 15-cached-factorial.raku 10 Called f(5) Called f(4) Called f(3) Called f(2) Called f(1) 120 Called f(10) Called f(9) Called f(8) Called f(7) Called f(6) 3628800
Note that the feature is experimental.
16 — triangular reduction
The reduction operator that we already used has a special variant [\ ] that allows to keep all the intermediate results. This is somewhat similar to using a sequence in the example 10.
unit sub MAIN($n); my @f = [\*] 1..$n; say @f[$n - 1];
17 — division of factorials
Now a few programs that go beyond the factorials themselves. The first program computes the value of the expression a! / b!, where both a and b are integer numbers, and a is not less than b.
The idea is to optimise the solution to skip the overlapping parts of the multiplication sequences. For example, 10! / 5! is 6 * 7 * 8 * 9 * 10.
To have more fun, let us modify Raku’s grammar so that it really parses the above expression.
unit sub MAIN($a, $b where $a >= $b);
class F {
has $.n;
}
sub postfix:<!>(Int $n) {
F.new(n => $n)
}
sub infix:</>(F $a, F $b) {
[*] $b.n ^.. $a.n
}
say $a! / $b!;
We already have seen the postfix:<!> operator. To catch division, another operator is defined, but to prevent catching the division of data of other types, a proxy class F is introduced.
To keep proper processing of expression such as 4 / 5, define another / operator that catches things which are not F. Don’t forget to add multi to both options. The callsame built-in routine dispatches control to built-in operator definitions.
. . .
multi sub infix:</>(F $a, F $b) {
[*] $b.n ^.. $a.n
}
multi sub infix:</>($a, $b) {
callsame
}
say $a! / $b!;
say 4 / 5;
18 — optimisation
Let’s try to reduce the number of multiplications. Take a factorial of 10:
10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1
Now, take one number from each end, multiply them, and repeat the procedure:
10 * 1 = 10 9 * 2 = 18 8 * 3 = 24 7 * 4 = 28 6 * 5 = 30
You can see that every such result is bigger than the previous one by 8, 6, 4, and 2. In other words, the difference reduces by 2 on each iteration, starting from 10, which is the input number.
The whole program that implements this algorithm is shown below:
unit sub MAIN(
$n is copy where $n %% 2 #= Even numbers only
);
my $f = $n;
my $d = $n - 2;
my $m = $n + $d;
while $d > 0 {
$f *= $m;
$d -= 2;
$m += $d;
}
say $f;
It only works for even input numbers, so it contains a restriction reflected in the where clause of the MAIN function. As homework, modify the program to accept odd numbers too.
19 — integral
Before wrapping up, let’s look at a couple of exotic methods, which, however, can be used to compute factorials of non-integer numbers (or, to be stricter, to compute what can be called extended definition of it).
The proper way would be to use the Gamma function, but let me illustrate the method with a simpler formula:
An integral is a sum by definition, so let’s make a straightforward loop:
unit sub MAIN($n);
my num $f = 0E0;
my num $dx = 1E-6;
loop (my $x = $dx; $x <= 1; $x += $dx) {
$f += (-log($x)) ** $n;
}
say $f * $dx;
With the given step of 1E-6, the result is not that exact:
$ raku 19-integral-factorial.raku 10 3086830.6595557937
But you can compute a ‘factorial’ of a floating-point number. For example, 5! is 120 and 6! is 720, but what is 5.5!?
$ raku 19-integral-factorial.raku 5.5 285.948286477563
20 — another formula
And finally, the Stirling’s formula for the rescue. The bigger the n, the more correct is the result.
The implementation can be as simple as this:
unit sub MAIN($n); # τ = 2 * π say (τ * $n).sqrt * ($n / e) ** $n;
But you can make it a bit more outstanding if you have a fixed $n:
say sqrt(τ * 10) * (10 / e)¹⁰;
* * *
And that’s it for now. You can find the source code of all the programs shown here in the GitHub repository github.com/ash/factorial.
my @fac = lazy gather { my $f = 1; take $f; take $f *= $_ for 1..*; }