From: Christoph Koegl (yahoo_at_[hidden])
Date: 2001-05-29 10:57:56
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
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( 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
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
[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!
-- ================================================================================ 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. --------------------------------------------------------------------------------
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk