Factorisation of the factorial - an algorithm discovered by playing with transformations

E. A. Boiten

Technical Report 90-18, Dept. of Informatics, University of Nijmegen, November 1990.

Abstract

As an example of the transformational programming method, a previously unknown algorithm for calculating factorials is derived. The derivation is done by the unfold-fold strategy with transformation rules for changing the recursion structure of functions. These transformation rules (inverting the flow of computation and splitting recursion) are presented and explained. The derivation which proceeds from a system of linear recursive functions, via tail-recursive functions, to an efficient imperative program. The resulting program is, in our opinion, only intelligible by way of its derivation. It is also shown how a similar derivation leads to a version of the algorithm that may be executed on 2 processors.

Technical Report 90-18, Dept. of Informatics, University of Nijmegen, 1990, revised version as chapter 3 in my PhD thesis. A shorter version appeared in Periodica Polytechnica Ser. El. Eng., 35(2):77-99, 1992, Copies available on request by email.

Bibtex Record

@techreport{165,
author = {Boiten, E.A.},
title = {Factorisation of the Factorial -- an algorithm discovered by playing with transformations},
month = {November},
year = {1990},
pages = {31},
keywords = {transformational programming, factorial},
note = {},
url = {http://www.cs.kent.ac.uk/pubs/1990/165},
institution = {Dept. of Informatics, University of Nijmegen},
number = {90-18} }