Some remarks on rational.cpp

From: Christoph Koegl (yahoo_at_[hidden])
Date: 2001-05-29 10:57:56

Hi.

First, I duly pay credit to all Boost contributors out there; you make my programming
life so much more enjoyable every day, thank you very much for that.

I have some remarks regarding the Rational Number library.

1. The employed algorithms for addition and for multiplication of rationals (which
   incidentally work for any quotient field of an integral domain) are attributed
   to Nickolay Mladenov by the author (Paul Moore). To give credit where credit is
   due, it should be noted that the exact same algorithm was published by Peter
   Henrici (Author of some well known higher calculus textbooks) in 1956. The exact
   reference is (in an abbreviated style):
   Henrici, P. (1956): A subroutine for computations with rational numbers. J. ACM
   3(1): 6-9.
   I think a related note should be added to the source code. The above paper is the
   earliest article (to my knowledge) on explicitly representing rationals (or rather
   quotient fields) in software.
2. Interface/Utility functions:
   The documentation of the gcd and lcm functions fail to exactly define their
   semantics. Rather than stating that "the" greatest common divisor resp.
   "the" least common multiple of n and m are computed it should state which one
   of the possible GCDs/LCMs is chosen. Note that, e.g., for 12 and -32 (taken to be
   integers) 4 and -4 are greatest common divisors ("greatest" in this respect has
   nothing to do with -4 < 4 in the canonical ordering of the integers). As given,
   the gcd function requires an ordering < on the underlying integer type and uses it
   in some way to single out one of the GCDs. To be really useful the documentation
   needs to state something along the lines of "we employ the canonical Euclidean
   algorithm for GCD computation" and "GCDs computed by gcd are never less than zero
   (wrt. < and 0 of the underlying integer type)".
   The documentation also fails to mention its behavior in the important singular
   cases gcd(0,0) and lcm(0,0). It wisely chooses the somewhat standard conventions
   of gcd(0,0) = 0 and lcm(0,0) = 0. But note that 0 and 0 neither have a greatest
   common divisor nor a least common multiple according to the mathematical defini-
   tions of these notions.
3. Some of the informal descriptions of the performance characteristics of the various
   operations can be made more precise without being chattier. The documentation could
   state performance bounds in terms of operation counts of the underlying integer
   type. Paul Moore notes that his remarks are based on the current implementation
   and therefore subject to change, but for many of the operations he chose a
   (sometimes obvious, sometimes rather nonobvious) optimal implementation in terms
   of operations of the underlying integer type. So I propose the following changes
   (or perhaps clarifying additions?) to the documentation:
   (*) Increment and decrement operations are essentially as cheap as addition
       and subtraction on the underlying integer type.
       ==>
       Increment and decrement operations perform at most one addition resp.
       subtraction of the underlying integer type.
   (*) (In)equality comparison is essentially as cheap as the same operation on
       the underlying integer type.
       ==>
       (In)equality comparisons perform at most two (in)equality comparisons of the
       underlying integer type.
       [Yes, I know that in fact inequality is reduced to equality.]
   (*) The gcd operation is essentially a repeated modulus operation. The only
       other significant operations are construction, assignment, and comparison
       against zero of IntType values. These latter operations are assumed to be
       trivial in comparison with the modulus operation.
       ==>
       The gcd operation performs never more than 5 * log[10]( k ) + 1 modulo
       operations of the underlying integer type, where k is the maximum of the
       absolute values of the arguments (assuming not both are 0, in which case no
       modulo operations are performed).
       [The above is a crude adaption of a well known bound on the number of
       divisions performed by the Euclidean algorithm, see e.g. D. Knuth, TAoCP/2.]
   (*) The lcm operation is essentially a gcd, plus a couple of multiplications and
       divisions.
       ==>
       The lcm operation performs exactly as many modulo operations as the gcd
       operation on the same arguments plus at most one division and one multiplica-
       tion of the underlying integer type.
   (*) The addition and subtraction operations are complex. They will require
       approximately two gcd operations, 3 divisions, 3 multiplications and an
       addition on the underlying integer type.
       ==>
       The addition and subtraction operations are performed using Henrici's algo-
       rithm. They therefore use (at most) two gcd operations, four divisions, three
       multiplications, and one addition resp. subtraction of the underlying integer
       type.
       [Note: I wrote "at most" because one could take advantage of some special cases
       in the implementation, such when arguments or intermediate results are 0 or
       gcd's are 1. But explicit treatment of these special cases would possibly
       slow down the typical cases (by way of additional comparisons) so benefits are
       unlikely to result from this "overall".]
   Note that as written the documentation of the comparison operations also talks
   about (in)equality comparisons which are already mentioned earlier.
   The comparison operations, as implemented and as documented, make use of special
   cases by investing some comparisons against IntType(0). This could also be done
   with addition/subtraction and multiplication/division, as stated above. Paul, do
   you have any measurements or usage profiles that suggested your choices of
   not making use of special cases in the field operations?

That's all for now, and (again) thanks for some incredibly brilliant libraries!

Cheers, Christoph
-- 
================================================================================
Christoph Koegl, Dept. of Computer Science, University of Kaiserslautern
E-Mail: christoph_at_[hidden]             WWW: http://www.familie-koegl.de/
--------------------------------------------------------------------------------
There are no stupid questions, but there are a LOT of inquisitive idiots.
--------------------------------------------------------------------------------