[COMMIT] Arithmetic enhancements [was: Re: [PATCH] "Fix" mod op] (original) (raw)

develooper Front page | perl.perl6.internals |Postings from October 2001 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