[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

*To*: scheme-reports@x*Subject*: [Scheme-reports] Centered Division*From*: Noah Lavine <noah.b.lavine@x>*Date*: Sun, 4 Mar 2012 21:22:10 -0500

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

- Prev by Date:
**Re: [Scheme-reports] Query - Pairs and Lists** - Next by Date:
**Re: [Scheme-reports] Comments on draft 6 about call/cc** - Previous by thread:
**Re: [Scheme-reports] [scheme-reports-wg1] Equality of records** - Next by thread:
**[Scheme-reports] Formal Comment: The epoch of current-second should be 1970-01-01 00:00:00 TAI.** - Index(es):