Confused by Bignum#remainder

Help a guy out who got B’s and C’s in math classes in college:

Ruby 1.8.4 on Solaris 10:

irb(main):013:0> -1234567890987654321.remainder(13731)
=> -6966
irb(main):014:0> -1234567890987654321.remainder(13731.24)
=> -9906.22531493148
irb(main):015:0> -1234567890987654321.modulo(13731)
=> 6765
irb(main):016:0> -1234567890987654321.modulo(13731.24)
=> 3825.01468506852

Basically, I’m trying to figure out the nuances of Bignum#remainder vs
Bignum#modulo. To confuse myself even further K&R (2nd ed, p. 41) says
you
can’t do modulus on double or long, and that the sign result is machine
dependent for negative operands.

Can someone explain the subtleties of this to me (or point me to a link
that
does)? An archive search didn’t reveal anything obvious.

Perhaps the documentation in bignum.c needs further exposition? Or
should I
just know this?

Thanks,

Dan

PS - I did try to read over the bigdivrem() private function in bignum.c
but,
like, whoa.

This communication is the property of Qwest and may contain confidential
or
privileged information. Unauthorized use of this communication is
strictly
prohibited and may be unlawful. If you have received this communication
in error, please immediately notify the sender by reply e-mail and
destroy
all copies of the communication and any attachments.

On 8/10/06, Daniel B. [email protected] wrote:

irb(main):016:0> -1234567890987654321.modulo(13731.24)
Perhaps the documentation in bignum.c needs further exposition? Or should I
just know this?

Well perhaps the c code isn’t the best place to understand ruby
semantics. I’d look at the class library documentation
http://www.ruby-doc.org is a good online resource for that.
If we look at the Numeric class (from which all the standard numeric
classes descend:
http://www.ruby-doc.org/core/classes/Numeric.html

And poke around at the modulo and remainder method definitions, we
find that remainder is defined in terms of modulo, so that
dividend.remainder(divisor) is divendend.modulo(divisor) if dividend
and divisor have the same sign, and dividend.mod(divisor)-divisor
otherwise.

And if we look at mod we find that it’s implemented as if it called
divmod in whose specification we find a nice table showing how modulo
and remainder are related under various conditions.
http://www.ruby-doc.org/core/classes/Numeric.html#M000032

As for the K&R restrictions and caveats, those have to do with C whose
operations are defined on machine-dependent representations, where
integers have a small fixed number of bits. Since ruby automatically
converts to Bignums when integers can’t be represented by Fixnums, it
doesn’t run into the boundary conditions on representational overflow.


Rick DeNatale

IPMS/USA Region 12 Coordinator
http://ipmsr12.denhaven2.com/

Visit the Project Mercury Wiki Site
http://www.mercuryspacecraft.com/

Rick DeNatale wrote:

=> 6765
link that
classes descend:
http://www.ruby-doc.org/core/classes/Numeric.html

And poke around at the modulo and remainder method definitions, we
find that remainder is defined in terms of modulo, so that
dividend.remainder(divisor) is divendend.modulo(divisor) if dividend
and divisor have the same sign, and dividend.mod(divisor)-divisor
otherwise.

Ah, hah! I get it now.

And if we look at mod we find that it’s implemented as if it called
divmod in whose specification we find a nice table showing how modulo
and remainder are related under various conditions.
http://www.ruby-doc.org/core/classes/Numeric.html#M000032

Yep, that cleared it right up. I should have looked.

Many thanks,

Dan

This communication is the property of Qwest and may contain confidential
or
privileged information. Unauthorized use of this communication is
strictly
prohibited and may be unlawful. If you have received this communication
in error, please immediately notify the sender by reply e-mail and
destroy
all copies of the communication and any attachments.

On Aug 10, 2006, at 2:53 PM, Daniel B. wrote:

irb(main):016:0> -1234567890987654321.modulo(13731.24)
=> 3825.01468506852

Basically, I’m trying to figure out the nuances of Bignum#remainder
vs Bignum#modulo. To confuse myself even further K&R (2nd ed, p.
41) says you can’t do modulus on double or long, and that the sign
result is machine dependent for negative operands.

Can someone explain the subtleties of this to me (or point me to a
link that does)? An archive search didn’t reveal anything obvious.

A couple of years ago I took a discrete math course and was very
surprised to find division defined as:

"Let a be an integer and d a positive integer. Then there are
unique integers q and r, with 0 .le. r .le d, such that a = dq + r.
Apparently my elementary school teacher had lied to me by saying that
division was even defined for a non-positive divisor. Furthermore, an
examination of the above definition will show that my calculator has
always lied to me for negative dividends since the remainder must by
definition be non-negative. This led me to examine how various
languages implemented the mod function for integers and reals of
various sizes and, sure enough, it’s inconsistent from one language
to the next.

The entry at:
http://en.wikipedia.org/wiki/Modulo_operation
is OK but it could be a bit more in-depth.

Chris G. wrote:

–snip–

definition be non-negative.
–snip–

You do not understand the difference between a theorem and a definition.
The statement you quote is a theorem. It does not define division but
states a property of the integers. This property as stated holds if the
assumptions of the theorem (d is a positive integer) hold. This theorem
then can be used to define the modulo function.


Michael U.
R&D Team
ISIS Information Systems Austria
tel: +43 2236 27551-219, fax: +43 2236 21081
e-mail: [email protected]
Visit our Website: www.isis-papyrus.com

Chris G. wrote:

unique integers q and r, with 0 .le. r .le d, such that a = dq +

a modulo function but not one which will serve to answer the original
question which was about the case where the assumption that d is
positive does not hold. My, rather trivial, point was that language
implementors do what feels right to them in this case and who can blame
them?

The more interesting case is when the dividend is negative. Here Ruby
does the ‘right thing’ but many languages do not.

OK. I understand now. What I took to be an attack on mathematics as it
was
taught to you was just an ellipse to get to the main point. Sorry for
the
misunderstanding. And I do agree with your main point, except that I
do
blame the language implementors and designers. As you pointed out, Ruby
does it right. If other languages do it wrong I do hold it against them.

Best regards,

Michael


Michael U.
R&D Team
ISIS Information Systems Austria
tel: +43 2236 27551-219, fax: +43 2236 21081
e-mail: [email protected]
Visit our Website: www.isis-papyrus.com

On Aug 11, 2006, at 2:16 AM, Michael U. wrote:

that my calculator has always lied to me for negative dividends
since the remainder must by definition be non-negative.
–snip–

You do not understand the difference between a theorem and a
definition.

Actually, i do. I was just trying to state the so called “division
algorithm”.

The statement you quote is a theorem. It does not define division but
states a property of the integers. This property as stated holds if
the
assumptions of the theorem (d is a positive integer) hold. This
theorem
then can be used to define the modulo function.

I think you may be missing the point. The theorem can be used to
define a modulo function but not one which will serve to answer the
original question which was about the case where the assumption that
d is positive does not hold. My, rather trivial, point was that
language implementors do what feels right to them in this case and
who can blame them?

The more interesting case is when the dividend is negative. Here Ruby
does the ‘right thing’ but many languages do not.

On 8/11/06, Chris G. [email protected] wrote:

I’m afraid I was a little arch and i confused you. I apologize. Let
me try to be very straightforward. I’m not that old but discrete
math has evolved in my lifetime.

Hey, when I was a kid, we thought that negative numbers didn’t have
square roots.

When my dad was a kid, there were no such things as negative numbers.

When my granddad was a kid the integers were I, II, III, IV, V, …

On Aug 11, 2006, at 7:17 AM, Michael U. wrote:

OK. I understand now. What I took to be an attack on mathematics as
it was
taught to you was just an ellipse to get to the main point. Sorry
for the
misunderstanding. And I do agree with your main point, except that
I do
blame the language implementors and designers. As you pointed out,
Ruby
does it right. If other languages do it wrong I do hold it against
them.

I’m afraid I was a little arch and i confused you. I apologize. Let
me try to be very straightforward. I’m not that old but discrete
math has evolved in my lifetime. This was brought home to me
dramatically when I took the aforementioned math class. The age
distribution in the class was bimodal and it turned out that the ‘old
folks’ had a fundamentally different notion of what a remainder was,
what was meant by set equivalency, and some other things that escape
me at the moment. The instructor found this both fascinating and funny.

She did a little research and gave a lecture on the subject. From
memory, she told us that originally mathematicians had though that,
for example, {a, b, c} and {a, b, b, c} were distinct sets. But this
approach had left them unable to prove some theorems in set theory
that they though they should be able to prove. So in fairly recent
times they went back to the drawing board and decided that those two
sets were equivalent after all. Since set theory underlies so much of
discrete math this change had repercussions.

The point of all this is that the modulus functions in C and FORTRAN
don’t work the way they do because their original implementers were
sloppy. They simply embody the then contemporary notion of modulus.

In article [email protected],
“Daniel B.” [email protected] wrote:

Basically, I’m trying to figure out the nuances of Bignum#remainder vs
Bignum#modulo. To confuse myself even further K&R (2nd ed, p. 41) says you

Well, one difference seems to be how they handle negative numbers (and
it seems to work the same way for regular sized number, not just
Bignums). Consider dividing -12 by 5.

A mathematician would see this as -12 = 5 * (-3) + 3, so would say that
-12/5 is -3 with a remainder of 3, and would also say that (-12)%5 is 3.

For some reason, the people who design processor instruction sets seem
to think that -12/5 should be -2, not -3. I think their reasoning is
that (-a)/b should equal -(a/b). To make that work, they need to use
round-toward-zero, and that means they see -12 as 5 * (-2) + (-2), so
-12/5 is -2 with a remainder of -2, and (-12)%5 is -2.

Languages like C tend to do whatever the processor does, so in C you get
(-12)%5 coming out -2.

Perl, Ruby (and I think Python) go with the mathematician’s view for %.
Ruby goes the other way for remainder, which is an interesting choice.
I suppose it kind of makes sense, because otherwise, why have a separate
remainder method?

I haven’t checked to see what any of these do when the divisor, rather
than or in addition to the dividend is negative.