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]1f}

This defines a function, {...}, which takes a single argument, [x], which always (irrespective of the argument) returns 1f. 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}

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=0f;1f;x*fact x-1]}

Here we have 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;1f]}

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

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

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

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]

Unlike $[...], it 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]}
                   ^

It doesn't matter so 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

An iterative implementation

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