Confused by Bignum#remainder

ruby-talk
1

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.

2

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:
class Numeric - RDoc Documentation

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.

···

On 8/10/06, Daniel Berger <Daniel.Berger@qwest.com> wrote:

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?

--
Rick DeNatale

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

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

3

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&gt;
is OK but it could be a bit more in-depth.

···

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

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.

--
In America, anybody can be president. That's one of the risks you take.
-Adlai Stevenson, statesman (1900-1965)

4

In article <44DBA9B0.8060601@qwest.com>,

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.

···

"Daniel Berger" <Daniel.Berger@qwest.com> wrote:

--
--Tim Smith

5

Rick DeNatale wrote:

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?

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:
class Numeric - RDoc Documentation

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.
class Numeric - RDoc Documentation

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 8/10/06, Daniel Berger <Daniel.Berger@qwest.com> wrote:

6

Chris Gehlker wrote:

--snip--

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.

--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 Ulm
R&D Team
ISIS Information Systems Austria
tel: +43 2236 27551-219, fax: +43 2236 21081
e-mail: michael.ulm@isis-papyrus.com
Visit our Website: www.isis-papyrus.com

---------------------------------------------------------------
This e-mail is only intended for the recipient and not legally
binding. Unauthorised use, publication, reproduction or
disclosure of the content of this e-mail is not permitted.
This email has been checked for known viruses, but ISIS accepts
no responsibility for malicious or inappropriate content.
---------------------------------------------------------------

7

Chris Gehlker wrote:

--snip--

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.

--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 Aug 11, 2006, at 2:16 AM, Michael Ulm wrote:

--
A young idea is a beautiful and a fragile thing. Attack people, not ideas.

8

Chris Gehlker wrote:

Chris Gehlker wrote:

--snip--

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.

--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.

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

···

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

--
Michael Ulm
R&D Team
ISIS Information Systems Austria
tel: +43 2236 27551-219, fax: +43 2236 21081
e-mail: michael.ulm@isis-papyrus.com
Visit our Website: www.isis-papyrus.com

---------------------------------------------------------------
This e-mail is only intended for the recipient and not legally
binding. Unauthorised use, publication, reproduction or
disclosure of the content of this e-mail is not permitted.
This email has been checked for known viruses, but ISIS accepts
no responsibility for malicious or inappropriate content.
---------------------------------------------------------------

9

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.

···

On Aug 11, 2006, at 7:17 AM, Michael Ulm 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.

--
Egotism is the anesthetic that dulls the pain of stupidity.
-Frank William Leahy, football coach (1908-1973)

10

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, ...

<G>

···

On 8/11/06, Chris Gehlker <canyonrat@mac.com> 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.

--
Rick DeNatale