Front page | perl.perl6.internals |
Postings from October 2001
[COMMIT] Arithmetic enhancements [was: Re: [PATCH] "Fix" mod op]
Thread Previous
|
Thread Next
From:
Gregor N. Purdy
Date:
October 8, 2001 06:54
Subject:
[COMMIT] Arithmetic enhancements [was: Re: [PATCH] "Fix" mod op]
Message ID:
1002549227.6157.149.camel@sarek.oh.focusresearch.com
Dan --
> >Fortunately, there is a perfectly rational definition of the mod(x,y)
> >function over the full domains of x and y, and even for x and y that
> >are not integral. This can be found in the book Concrete Mathematics,
> >Second Edition by Graham, Knuth and Patashnik (Section 3.4, pages
> >81-85.
>
> Keen, I'd forgotten that was in there. I'd say toss the other mods and go
> with this as our sole modulus operator, assuming that it behaves the same
> as C's % for positive integers.
For now, I've kept C's built-in mod as cmod_i, and the math library's
floating point mod (fmod) as cmod_n. Especially in the case of the
former, I'd hate to be the cause of someone's speed woes if they have
mod in an inner loop and they can guarantee all positive arguments.
We can revisit the plurality of mod operators in the future.
The thing that's making my brain itch right now is div. We cannot afford
to do complicated things to the standard integer division, but you will
have noticed that the nicer mod is based on floor-div (where C does
truncate-div). Having floor-div (and maybe even ceiling-div) around to
build other things out of would be nice (but maybe not nice enough to
allocate more builtin ops to -- maybe we could have our first oplib
contain an expanded set of numerical ops. I'd like to start thinking
and talking about oplibs soon).
> Once the feature freeze is over this can go in.
Its in. Here's the log entry:
* Renamed existing mod_i as cmod_i and added "corrected" mod_i:
NOTE: This "uncorrected mod" algorithm uses the C language's
built-in mod operator (x % y), which is
... the remainder when x is divided by y, and thus is zero
when y divides x exactly.
...
The direction of truncation for / and the sign of the result
for % are machine-dependent for negative operands, as is the
action taken on overflow or underlfow.
-- [1], page 41
Also:
... if the second operand is 0, the result is undefined.
Otherwise, it is always true that (a/b)*b + a%b is equal to z.
If both operands are non-negative, then teh remainder is
non-negative and smaller than the divisor; if not, it is
guaranteed only that the absolute value of the
remainder is smaller than the absolute value of the divisor.
-- [1], page 205
This op is provided for those who need it (such as speed-sensitive
applications with heavy use of mod, but using it only with
positive arguments), but a more mathematically useful numeric mod
based on floor(x/y) and defined with y == 0 is provided by the
mod_i op.
[1] Brian W. Kernighan and Dennis M. Ritchie, *The C Programming
Language*, Second Edition. Prentice Hall, 1988.
* Added "corrected" mod_i:
NOTE: This "corrected mod" algorithm is based on the C code on
page 70 of [1]. Assuming correct behavior of C's built-in mod
operator (%) with positive arguments, this algorithm implements a
mathematically convenient version of mod, defined thus:
x mod y = x - y * floor(x / y)
For more information on this definition of mod, see section 3.4 of
[2], pages 81-85.
References:
[1] Donald E. Knuth, *MMIXware: A RISC Computer for the Third
Millennium* Springer, 1999.
[2] Ronald L. Graham, Donald E. Knuth and Oren Patashnik,
*Concrete Mathematics*, Second Edition. Addison-Wesley,
1994.
* Added mod_n, using the same formula as above, but with FLOATVAL
arguments.
* Added cmod_n, using the C math library's fmod() function:
NOTE: This "uncorrected mod" algorithm uses the built-in C math
library's fmod() function, which computes
... the remainder of dividing x by y. The return value is
x - n * y, where n is the quotient of x / y, rounded towards
zero to an integer.
-- fmod() manpage on RedHat Linux 7.0
In addition, fmod() returns
the remainder, unless y is zero, when the function fails and
errno is set.
According to page 251 of [1], the result when y is zero is
implementation-defined.
This op is provided for those who need it, but a more
mathematically useful numeric mod based on floor(x/y) instead of
truncate(x/y) and defined with y == 0 is provided by the mod_n op.
[1] Brian W. Kernighan and Dennis M. Ritchie, *The C Programming
Language*, Second Edition. Prentice Hall, 1988.
* Added and modified tests as appropropriate for the above.
Regards,
-- Gregor
_____________________________________________________________________
/ perl -e 'srand(-2091643526); print chr rand 90 for (0..4)' \
Gregor N. Purdy gregor@focusresearch.com
Focus Research, Inc. http://www.focusresearch.com/
8080 Beckett Center Drive #203 513-860-3570 vox
West Chester, OH 45069 513-860-3579 fax
\_____________________________________________________________________/
Thread Previous
|
Thread Next