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

Boiten, Eerke (1990) Factorisation of the Factorial -- an algorithm discovered by playing with transformations. Technical report. (The full text of this publication is not available from this repository)

The full text of this publication is not available from this repository. (Contact us about this Publication)

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 ( inv.html 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 mailto:E.A.Boiten@ukc.ac.uk.

Item Type: Monograph (Technical report)
Uncontrolled keywords: transformational programming, factorial
Subjects: Q Science > QA Mathematics (inc Computing science) > QA 76 Software, computer programming,
Divisions: Faculties > Science Technology and Medical Studies > School of Computing > Theoretical Computing Group
Depositing User: Mark Wheadon
Date Deposited: 30 Jul 2009 20:24
Last Modified: 13 May 2014 08:38
Resource URI: http://kar.kent.ac.uk/id/eprint/20962 (The current URI for this page, for reference purposes)
  • Depositors only (login required):