[Scheme-reports] Centered Division

[Noah Lavine <noah.b.lavine@x>]

Hello,

John Cowan <cowan@x> Mar 02 01:31PM -0500

> Taylor Campbell scripsit:

>> I think if the small language's division operators are to be pruned,
>> at least the euclidean one should be kept; and if floor is kept, then
>> ceiling should be kept too.

> Which amounts to saying that all, except possibly centered (which was not
> part of DivisionRiastradh) should be kept.

I would like to also put in a plea for the centered operator. The
reason is that you can implement the GCD algorithm faster with that
than with standard division.

The standard GCD algorithm is this:

(define (gcd a a-next)
 (if (= a-next 0)
    a
    (gcd a-next (remainder a a-next))))


Let a_1, a_2, ..., a_n be the sequence of a's generated by the
function, where a_1 is the first and a_n is the GCD.

Its worst-case performance is the situation where the remainder only
strips off one multiple of a-next, so (remainder a a-next) = (- a
a-next). In sequence notation, a_{i+1} = a_{i-1} - a_i, or
equivalently, a_{i-1} = a_i + a_{i+1}. This is the Fibonacci sequence.

However, the following algorithm is faster:

(define (gcd a a-next)
 (if (= a-next 0)
    a
    (gcd a-next (centered-remainder a a-next))))

Again let a_1, a_2, ..., a_n be the sequence of numbers it produces.

The worst case is when the centered-remainder does as little as
possible. But now for all elements of the sequence except the first,
|a-next| <= |a|/2 by the centered division property, so we are going
to take off at least two multiples of a-next. The worst-case is that
we only do this, so (centered-remainder a a-next) = (- a (* 2
a-next)). That means that a_{i+1} = a_{i-1} - 2*a_i, or a_{i-1} =
a_{i+1} + 2*a_i.

This is a sequence that grows faster than the Fibonacci sequence.
Equivalently, any two integers will be at least as far down the
Fibonacci sequence as this second one, so it will take at least as
long to find the GCD with the first algorithm as with the second, and
for most pairs of integers, the second one will be faster.

Thank you,
Noah Lavine

_______________________________________________
Scheme-reports mailing list
Scheme-reports@x
http://lists.scheme-reports.org/cgi-bin/mailman/listinfo/scheme-reports