Programming/Kdb/Factorial

The factorial

The factorial of a non-negative integer $n$, denoted by $n!$, is the product of all positive integers less than or equal to $n$:

$n!=n\cdot (n-1)\cdot (n-2)\cdot (n-3)\cdot \ldots \cdot 3\cdot 2\cdot 1.$

For example,

$5!=5\cdot 4\cdot 3\cdot 2\cdot 1=120.$

The value of $0!$ is 1, according to the convention for an empty product.

The factorial operation is encountered in many areas of mathematics, notably in combinatorics, algebra, and mathematical analysis. Its most basic use counts the number of distinct sequences—the permutations—of $n$ distinct objects: there are $n!$.

Implementing the factorial in q

A dummy implementation

We'll implement the factorial as a q function. That function will take a single parameter, x, and return the result.

We'll start with a dummy, incorrect implementation that always returns 1:

fact:{[x]1}

This defines a function, {...}, which takes a single argument, [x], which always (irrespective of the argument) returns 1. We assign, :, a name to that function, fact, so we can call it again and again, as required.

This is a function of a single argument, in other words, a monadic or unary function. We could have a dyadic (binary), triadic (ternary), etc. function. Here is an example of a dyadic function:

add:{[x;y]x+y}

Incidentally, it is possible to have a niladic (nullary) function. Such functions are not necessarily constant and may have useful side effects. The following function will print out the current time:

tm:{[].z.p}

When q encounters the variables named x, y, and z in the body of a function, it knows that these are the function's arguments. So we could skip [x;y] above:

add:{x+y}

We wouldn't be able to do this if we named the arguments differently:

add:{[a;b]a+b}

A recursive implementation using the conditional evaluation

The most basic implementation of a factorial is the recursive one.

In general, recursion is a method of solving a problem where the solution depends on the solutions to smaller instances of the same problem. Such problems can generally be solved by iteration, but this needs to identify and index the smaller instances at programming time. Recursion solves such recursive problems by using functions that call themselves from within their own code. The approach can be applied to many types of problems, and recursion is one of the central ideas of computer science.

The power of recursion evidently lies in the possibility of defining an infinite set of objects by a finite statement. In the same manner, an infinite number of computations can be described by a finite recursive program, even if this program contains no explicit repetitions.

—Niklaus Wirth, Algorithms + Data Structures = Programs, 1976.

Most computer programming languages support recursion by allowing a function to call itself from within its own code. Q is no exception:

fact:{$[x=0;1;x*fact x-1]}

We have just used the conditional evaluation, the ternary overload of $:

$[expr_cond; expr_true; expr_false]

Here expr_cond is an expression that evaluates to a boolean atom. The result of expr_cond can be any type whose underlying value is an integer. The result of the conditional is the evaluation of expr_true when expr_cond is not zero and expr_false if it is zero.

Notice that we don't need to have a boolean zero in expr_cond for expr_false to be evaluated; it could well be a long zero. Thus we can rewrite fact more tersely:

fact:{$[x;x*fact x-1;1]}

How would the function call itself if it weren't assigned the name fact? In q, there is a provision for that. The function can call itself using .z.s:

fact:{$[x;x*.z.s x-1;1]}

This works even if the function is anonymous, for example:

q){$[x;x*.z.s x-1;1]}[5]
120

Let's check the first few values:

q)fact[0]
1
q)fact[1]
1
q)fact[2]
2
q)fact[3]
6
q)fact[4]
24
q)fact[5]
120

Let us look at our recursive function again:

fact:{$[x;x*.z.s x-1;1]}

A recursive function definition has one or more base cases, meaning input(s) for which the function produces a result trivially (without recurring), and one or more recursive cases, meaning input(s) for which the program recurs (calls itself).

In our case the base case is $0!=1$. You can see it here:

fact:{$[x;...;1]}

Our recursive case is, for all $x>0$, $n!=n(n-1)!$. You can see it here:

fact:{$[...;x*.z.s x-1;...]}

Because the base case breaks the chain of recursion, it is sometimes also called the "terminating case".

A recursive implementation using the imperative if statement

Instead of the conditional evaluation we could have used the imperative if statement, which conditionally evaluates a sequence of expressions:

if[expr_cond;expr_1;...;expr_n]

The expr_cond is evaluated and, if it is nonzero, the expressions expr_1, ..., expr_n are evaluated in left-to-right order. As with other conditionals, the brackets do not create a lexical scope, so variables defined in the body exist in the same scope as the if.

Unlike $[...], there is no "else" to go with if.

Also unlike $[...], if[...] is not a function and does not return a value. Therefore we need to force the return using ::

fact1:{if[x>0;:x*.z.s x-1];1}

A problem with the recursive implementations

Recursive implementations tend to underperform their iterative peers.

In addition, they may run out of stack space:

q)fact 2001
'stack
  [1799fact:{$[x;x*.z.s x-1;1f]}
                   ^

This doesn't matter that much specifically for the factorial, because the factorial of 26 is already enormous and overflows the long:

q)fact 25
7034535277573963776
q)fact 26
-1569523520172457984

For many other recursive functions 'stack is a serious issue.

An iterative implementation using the imperative do statement

The imperative do statement allows repeated execution of a block of statements. It has the form,

do[expr_count;expr_1;...;expr_n]

where expr_count must evaluate to a nonnegative integer. The expressions expr_1, ..., expr_n are evaluated expr_count times in left-to-right order.

Note that do is a statement, not a function, and does not have an explicit result.

Here is a (rather awkward) implementation of a factorial using do:

fact2:{do[-1+f:r:x;r*:f-:1];r}

Here is another:

fact3:{r:1;do[x;r*:x;x-:1];r}

An iterative implementation using the imperative while statement

The imperative while statement is an iterator of the form

while[expr_cond;expr_1;...;expr_n]

where expr_cond is evaluated and the expressions expr_1, ..., expr_n are evaluated repeatedly in left-to-right order as long as expr_cond is nonzero.

The while statement is not a function, does not have an explicit result, and does not introduce a lexical scope.

Here is an iterative implementation of a factorial using while:

fact4:{r:1;while[x;r*:x;x-:1];r}

The following implementation is seemingly superior, as it is terser, but it fails at x = 0:

fact4a:{f:r:x;while[f-:1;r*:f];r}