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
