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 currently available from this repository. You may be able to access a copy if URLs are provided)

The full text of this publication is not currently available from this repository. You may be able to access a copy if URLs are provided. (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: https://kar.kent.ac.uk/id/eprint/20962 (The current URI for this page, for reference purposes)
  • Depositors only (login required):