Original-Via: uk.ac.st-and.cs; Wed, 30 Oct 91 17:05:34 GMT

It seems to me that some of the most useful arithmetic divide and
conquer algorithms express a function of an integer n in terms of
the same function applied to n `div` 2. Has any thought been given to
generalising n+k patterns to c*n+k patterns? If these were allowed we
would be able to express, for instance, the well known algorithm for
raising numbers to an integer power by:

x^0       = 1
x^(2*n)   = xn*xn where xn = x^n
x^(2*n+1) = x * x^(2*n)

and a very fast implementation of Fibonacci numbers would be

fib 1       = 1
fib 2       = 1
fib (2*n)   = (fib(n+1))^2 - (fib(n-1))^2
fib (2*n+1) = (fib(n+1))^2 + (fib n   )^2

There are many more 'real world' examples.

Tony Davie

Reply via email to