© University of Kent - Contact | Feedback | Legal | FOI | Cookies
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 = {182-196},
keywords = {determinacy analysis, Craig interpolants},
note = {},
doi = {},
url = {http://www.cs.kent.ac.uk/pubs/1990/165},
institution = {Dept. of Informatics, University of Nijmegen},
number = {90-18},
}