From:

Date:

October 8, 2001 06:54Subject:

[COMMIT] Arithmetic enhancements [was: Re: [PATCH] "Fix" mod op]Message ID:

1002549227.6157.149.camel@sarek.oh.focusresearch.comDan -- > >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

- [PATCH] "Fix" mod op by Gregor N. Purdy
- Re: [PATCH] "Fix" mod op by Gregor N. Purdy
- Re: [PATCH] "Fix" mod op by Gregor N. Purdy
- Re: [PATCH] "Fix" mod op by Dan Sugalski
**[COMMIT] Arithmetic enhancements [was: Re: [PATCH] "Fix" mod op]**by Gregor N. Purdy- Re: [COMMIT] Arithmetic enhancements [was: Re: [PATCH] "Fix"mod op] by Dan Sugalski
- Re: [COMMIT] Arithmetic enhancements [was: Re: [PATCH] "Fix" mod op] by Andy Dougherty

nntp.perl.org: Perl Programming lists via nntp and http.

Comments to Ask Bjørn Hansen at ask@perl.org | Group listing | About