Difference between revisions of "Programming/Kdb/Factorial"

From Thalesians Wiki
Line 23: Line 23:
We'll start with a dummy, incorrect implementation that always returns <tt>1</tt>:
We'll start with a dummy, incorrect implementation that always returns <tt>1</tt>:
<pre>
<pre>
fact:{[x]1f}
fact:{[x]1}
</pre>
</pre>
This defines a function, <tt>{...}</tt>, which takes a single argument, <tt>[x]</tt>, which always (irrespective of the argument) returns <tt>1f</tt>. We assign, <tt>:</tt>, a name to that function, <tt>fact</tt>, so we can call it again and again, as required.
This defines a function, <tt>{...}</tt>, which takes a single argument, <tt>[x]</tt>, which always (irrespective of the argument) returns <tt>1</tt>. We assign, <tt>:</tt>, a name to that function, <tt>fact</tt>, 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:
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:
<pre>
<pre>
add:{[x;y]x+y}
add:{[x;y]x+y}
</pre>
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:
<pre>
tm:{[].z.p}
</pre>
</pre>


Line 50: Line 55:
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.
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.
</blockquote>
</blockquote>
<p style="text-align:right">&mdash;Niklaus Wirth, ''Algorithms + Data Structures = Programs'', 1976.
<p style="text-align:right">&mdash;Niklaus Wirth, ''Algorithms + Data Structures = Programs'', 1976.</p>


Most computer programming languages support recursion by allowing a function to call itself from within its own code. Q is no exception:
Most computer programming languages support recursion by allowing a function to call itself from within its own code. Q is no exception:
<pre>
<pre>
fact:{$[x=0f;1f;x*fact x-1]}
fact:{$[x=0;1;x*fact x-1]}
</pre>
</pre>


Here we have used the '''conditional evaluation''', the ternary overload of $:
We have just used the '''conditional evaluation''', the ternary overload of $:
<pre>
<pre>
$[expr_cond; expr_true; expr_false]
$[expr_cond; expr_true; expr_false]
Line 65: Line 70:
Notice that we don't need to have a ''boolean'' zero in <tt>expr_cond</tt> for <tt>expr_false</tt> to be evaluated; it could well be a long zero. Thus we can rewrite <tt>fact</tt> more tersely:
Notice that we don't need to have a ''boolean'' zero in <tt>expr_cond</tt> for <tt>expr_false</tt> to be evaluated; it could well be a long zero. Thus we can rewrite <tt>fact</tt> more tersely:
<pre>
<pre>
fact:{$[x;x*fact x-1;1f]}
fact:{$[x;x*fact x-1;1]}
</pre>
</pre>


How would the function call itself if it weren't assigned to the variable <tt>fact</tt>? In q, there is a provision for that. The function can call itself using <tt>.z.s</tt> even if it is anonymous:
How would the function call itself if it weren't assigned the name <tt>fact</tt>? In q, there is a provision for that. The function can call itself using <tt>.z.s</tt>:
<pre>
<pre>
fact:{$[x;x*.z.s x-1;1]}
fact:{$[x;x*.z.s x-1;1]}
</pre>
This works even if the function is anonymous, for example:
<pre>
q){$[x;x*.z.s x-1;1]}[5]
120
</pre>
</pre>


Line 88: Line 98:
120
120
</pre>
</pre>
Let us look at our recursive function again:
<pre>
fact:{$[x;x*.z.s x-1;1]}
</pre>
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 <math>0! = 1</math>. You can see it here:
<pre>
fact:{$[x;...;1]}
</pre>
Our recursive case is, for all <math>x > 0</math>, <math>n! = n(n - 1)!</math>. You can see it here:
<pre>
fact:{$[...;x*.z.s x-1;...]}
</pre>
Because the base case breaks the chain of recursion, it is sometimes also called the "terminating case".


==A recursive implementation using the imperative <tt>if</tt> statement==
==A recursive implementation using the imperative <tt>if</tt> statement==

Revision as of 06:15, 1 July 2021

The factorial

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

For example,

The value of 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 distinct objects: there are .

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 . You can see it here:

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

Our recursive case is, for all , . 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]

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}