Modulus and Remainder operations (Was Re: Help with a bit of C code)

Modulus and Remainder operations (Was Re: Help with a bit of C code)

[David A. Cobb]

X-In-Reply-To: Mon, 26 Sep 1994 14:35:11 EDT <bruce@AIS.COM>

<quote>
    Strictly speaking, the % operator in C is a REMAINDER operator, not a
    MODULUS operator.  This often seems to be a confusing point for a lot
    of people, but the results are different for negative numbers (Try it
    with, eg, PL/I, which uses the modulus function rather than the remainder
    function).  For example, these 3 languages give the following results:
</quote>

Ada, the language everyone loves to hate, has both but has the
decency to give both clear definitions.  I assume the designers
talked to a mathamagician:

<quote>
    A = (A/B)*B + (A rem B) where (A rem B) <e>has the sign of A</e>
and an absolute value less than B. ....

    A = B*N + (A mod B), for some signed integer N, where (A mod B)
<e>has the sign of B</e> and an absolute value less than the
absolute value of B.
</quote>

Thus:
<pre>
    A        B        A/B      A rem B   A mod B
    12        5         2         2         2
   -12        5        -2        -2         3
    12       -5        -2         2        -3
   -12       -5        -2        -2        -2
</pre>

Re: Modulus and Remainder operations (Was Re: Help with a bit of C code)

[Robert Dewar]

In traditional C, the result of applying / or % to negative integers is
implementation dependent and hence undefined at the language level. Likely
it will be remainder type semantics rather than modulus type semantics
because most machines do things that way by default, but on the ICL1900
series C gave modular semantics, since that's the way the machine was.

I think this is unchanged in the ANSI C standard, can someone confirm this?

Re: Modulus and Remainder operations (Was Re: Help with a bit of C code)

[Christopher Costello]

Robert Dewar (dewar@cs.nyu.edu) wrote:
: In traditional C, the result of applying / or % to negative integers is
: implementation dependent and hence undefined at the language level. Likely
: it will be remainder type semantics rather than modulus type semantics
: because most machines do things that way by default, but on the ICL1900
: series C gave modular semantics, since that's the way the machine was.

: I think this is unchanged in the ANSI C standard, can someone confirm this?

In the ANSI standard, section 3.3.5 it says:

"... If either operand is negative, whether the result of the / operator
is the largest integer less than or equal to the algebraic quotient or 
the smallest integer greater than or equal to the algebraic quotient is
implementation defined, as is the sign of the result of the % operator."

I'd rather bite my tongue off than engage in language wars. Maybe.
--
+--------------------------------------------------------------------------+
| SIEMENS   Christopher Costello   Tel:    +49 89 636 40367                | 
| =======   SNI BU BA NM 123       Fax:    +49 89 636 45860                | 
| NIXDORF   Muenchen, Germany      E-mail: Christopher.Costello@mch.sni.de |
+--------------------------------------------------------------------------+

Re: Modulus and Remainder operations (Was Re: Help with a bit of C code)

[Norman H. Cohen]

In article <36bsmq$5p@gnat.cs.nyu.edu>, dewar@cs.nyu.edu (Robert Dewar) writes: 

|> In traditional C, the result of applying / or % to negative integers is
|> implementation dependent and hence undefined at the language level. Likely
|> it will be remainder type semantics rather than modulus type semantics
|> because most machines do things that way by default, but on the ICL1900
|> series C gave modular semantics, since that's the way the machine was.
|>
|> I think this is unchanged in the ANSI C standard, can someone confirm this?

Yes, it's implementation-defined, within certain constraints, of course.
Section 3.3.5 of the ANSI C standard contains the following paragraph
(page 47, lines 25-30): 

      When integers are divided and the division is inexact, if both
   operands are positive the result of the / operator is the largest
   integer less than the algebraic quotient and the result of the %
   operator is positive.  If either operand is negative, whether the
   result of the / operator is the largest integer less than or equal to
   the algebraic quotient or the smallest integer greater than or equal
   to the algebraic quotient is implementation-defined, as is the sign of
   the result of the % operator.  If the quotient a/b is representable,
   the expression (a/b)*b + a%b shall equal a.

(Boy, the Ada RM with its paragraph numbers sure is easier to cite, and
it's nice that the citations are not bound by page number and line
number to one particular printed version!)

Thus, it is implementation-defined in C whether (-11)/5 and 11/(-5) round
towards zero as in Ada, yielding -2, or towards negative infinity,
yielding -3.  More surprisingly, even though 11/5 must yield 2, it is
implementation-defined in C whether (-11)/(-5) yields 2 or 3.  The last
sentence of the paragraph in effect defines a%b to be a - (a/b)*b, the
same formula given in RM83-4.5.5(3) for a rem b, so we have: 

       | Rounding towards 0 | Rounding away from 0 |
       +------------+-------+-----------+----------+
 a | b |    a/b     |  a%b  |    a/b    |   a%b    | a rem b | a mod b |
---+---+------------+-------+-----------+----------+---------+---------+
 11|  5|     2      |   1   |      not allowed     |    1    |    1    |
---+---+------------+-------+-----------+----------+---------+---------+
-11|  5|    -2      |  -1   |     -3    |    4     |   -1    |    4    |
---+---+------------+-------+-----------+----------+---------+---------+
 11| -5|    -2      |   1   |     -3    |   -4     |    1    |   -4    |
---+---+------------+-------+-----------+----------+---------+---------+
-11| -5|     2      |  -1   |      3    |    4     |   -1    |   -1    |
---+---+------------+-------+-----------+----------+---------+---------+

When negative quotients a/b are rounded toward zero a%b = a rem b
and when negative quotients a/b are rounded towards negative infinity
a%b = a mod b.  In the case where a and b are both negative, if the
quotient is rounded towards zero we get a%b = a rem b = a mod b.  If the
quotient is rounded away from zero, we get a%b = a rem b + b =
a mod b + b.

--
Norman H. Cohen    ncohen@watson.ibm.com

Re: Modulus and Remainder operations (Was Re: Help with a bit of C code)

[Norman H. Cohen]

In article <37cigq$6e0@felix.seas.gwu.edu>, mfeldman@seas.gwu.edu (Michael Feldman) writes: 
|> In article <37bof4$ljl@gnat.cs.nyu.edu>, Robert Dewar <dewar@cs.nyu.edu> wrote: 
|>
|> >Indeed one can even argue that it promotes portability for a compiler to
|> >deliberately behave in the worst possible manner when given freedom (I
|> >believe that Tuck mentioned that the Intermetrics compiler has two
|> >options, nice and nasty, for choosing order of elaboration, which seems
|> >a good idea, one which we have had on the GNAT todo list for some
|> >time!)
|>
|> Yes, I agree. Indeed, I would love to see an implementer make a random
|> selection among implementation-dependent possibilities (expression
|> evaluation order, etc.) just to discourage side-effect-y code. 0.5 :-)

Indeed, this is the reasoning behind the following implementation advice
in the Safety and Security Annex:  "Whenever possible, the implicit
initial value for a scalar subtype should be an invalid representation."
The idea is to smoke out uses of uninitialized scalar variables by
increasing the likelihood that their use will raise Constraint_Error.

This approach provides no guarantees, of course, but it does tip the odds
a little bit in favor of the tester (who gets paid by the bug :-) ).

--
Norman H. Cohen    ncohen@watson.ibm.com

Re: Modulus and Remainder operations (Was Re: Help with a bit of C code)

[Norman H. Cohen]

In article <1994Oct11.161048.1058@nosc.mil>, sampson@nosc.mil
(Charles H. Sampson) writes: 

|> In article <hbakerCxFK2p.4wp@netcom.com>,
|> Henry G. Baker <hbaker@netcom.com> wrote: 
...
|> >Sounds a bit like Ada's uncertainty about INOUT parameter passing
|> >being 'by-reference' or 'by-copyin-copyout'.  I don't think that Ada83
|> >even required that a particular subprogram do it the same way for
|> >every call.
|>
|>      All true, but at least the Ada definition acknowledges the indetermin-
|> ism and says that any program that relies on a particular choice of imple-
|> mentation is erroneous.  I doubt that the C standard declares erroneous any
|> program that relies on the division operator!

Let's be fair: 

1. The issue here is not "reliance on the division operator", but
   reliance on the direction in which a nonintegral quotient is rounded
   when the divisor or dividend is negative.

2. The ANSI C standard recognizes the equivalent of what the Ada standard
   calls "erroneous execution."  The ANSI C standard calls it "undefined
   behavior".  Like erroneous execution in the Ada standard, undefined
   behavior in the ANSI C standard arises in specific, precisely
   enumerated circumstances.  (As you might guess, there are many more
   such circumstances in C than in Ada.)

3. The ANSI C standard does not say that dependence on the direction of
   rounding the quotient makes the behavior undefined, only that the
   direction of rounding is "implementation-defined".  That gives the
   implementation much less freedom.  It may round up or it may round
   down, but it may not overwrite a return address on the stack, for
   example.

4. In Ada 9X, the parameter-passing mechanism is mandated in many cases
   where Ada 83 leaves it up to the implementation.  In the cases where
   it is still up to the implementation, the crime of "relying" on a
   particular mechanism has been more precisely defined and its severity
   has been reduced from "erroneous execution" (a captial offense) to
   "bounded error" (a noncapital felony).  If a formal parameter has more
   than one "access path" (i.e., it is "aliased" in the pre-Ada-9X sense)
   and it is updated by one name, then examined by the other name, the
   possible outcomes are that the examination will yield the old value,
   that the examination will yield the new value, or (science fiction)
   that your very clever compiler will catch this error and raise the
   exception Program_Error.  See RM9X-6.2(12) for the details.

--
Norman H. Cohen    ncohen@watson.ibm.com

Re: Modulus and Remainder operations (Was Re: Help with a bit of C code)

[Henry G. Baker]

In article <37er8t$oh0@watnews1.watson.ibm.com> ncohen@watson.ibm.com writes:
>4. In Ada 9X, the parameter-passing mechanism is mandated in many cases
>   where Ada 83 leaves it up to the implementation.  In the cases where
>   it is still up to the implementation, the crime of "relying" on a
>   particular mechanism has been more precisely defined and its severity
>   has been reduced from "erroneous execution" (a captial offense) to
>   "bounded error" (a noncapital felony).  If a formal parameter has more
>   than one "access path" (i.e., it is "aliased" in the pre-Ada-9X sense)
>   and it is updated by one name, then examined by the other name, the
>   possible outcomes are that the examination will yield the old value,
>   that the examination will yield the new value, or (science fiction)
>   that your very clever compiler will catch this error and raise the
>   exception Program_Error.  See RM9X-6.2(12) for the details.

So I've been told.  But this policy is still a crock, especially for
Ada 'limited' types, because the definer of the type has lost control
of the type.  The 'textbook' definitions of prototypical limited types
such as 'bank accounts' are no longer safe in the presence of such
equivocation.

See "How to Steal from a Limited Private Account--Why Mode INOUT
Parameters for Limited Types MUST be Passed by Reference".  Ada
Letters XIII, 3 (May/June 1993), 91-95.  This paper is also in my ftp
directory.

      Henry Baker
      Read ftp.netcom.com:/pub/hbaker/README for info on ftp-able papers.

Re: Modulus and Remainder operations (Was Re: Help with a bit of C code)

[Magnus Kempe]

hbaker@netcom.com (Henry G. Baker) writes:
: 
: ...  the definer of [a limited] type has lost control of the type.
: The 'textbook' definitions of prototypical limited types such as 'bank
: accounts' are no longer safe in the presence of such equivocation.

Henry, please read RM9X 6.2(4-10).  The following declaration ensures that
parameters of type T will always be passed by reference:

package P is
  type T is limited private;
private
  type T is limited record ... end record; -- NOTE: "limited"
end P;

Also, parameters of tagged types are always passed by reference.


: See "How to Steal from a Limited Private Account--Why Mode INOUT
: Parameters for Limited Types MUST be Passed by Reference".  Ada
: Letters XIII, 3 (May/June 1993), 91-95.

Your problem is SOLVED In Ada 9X.

-- 
Magnus Kempe		"I know not what course others may take, but as for me,
Magnus.Kempe@di.epfl.ch  Give me Liberty... or give me Death!" -- Patrick Henry

Re: Modulus and Remainder operations (Was Re: Help with a bit of C code)

[Robert Dewar]

I might add to Magus' comment about the limited type issue being solved in
Ada 9X is that this is not some accident, but rather an important consequence
of a quite deliberate review of the status of limited objects in Ada, no
doubt informed by useful contributions from Henry and others :-)

Re: Modulus and Remainder operations (Was Re: Help with a bit of C code)

[Henry G. Baker]

In article <1994Oct13.092135@di.epfl.ch> Magnus.Kempe@di.epfl.ch (Magnus Kempe) writes:
>hbaker@netcom.com (Henry G. Baker) writes:
>: 
>: ...  the definer of [a limited] type has lost control of the type.
>: The 'textbook' definitions of prototypical limited types such as 'bank
>: accounts' are no longer safe in the presence of such equivocation.
>
>Henry, please read RM9X 6.2(4-10).  The following declaration ensures that
>parameters of type T will always be passed by reference:
>
>package P is
>  type T is limited private;
>private
>  type T is limited record ... end record; -- NOTE: "limited"
>end P;
>
>Also, parameters of tagged types are always passed by reference.
>
>: See "How to Steal from a Limited Private Account--Why Mode INOUT
>: Parameters for Limited Types MUST be Passed by Reference".  Ada
>: Letters XIII, 3 (May/June 1993), 91-95.
>
>Your problem is SOLVED In Ada 9X.

For _most_, but not _all_, limited types.  So we have yet another rule
to learn, and another 'relief act' for the language lawyers.  I can't
wait for ANSI/ISO Committee meetings to start showing up on CSPAN...  :-)

      Henry Baker
      Read ftp.netcom.com:/pub/hbaker/README for info on ftp-able papers.

Re: Modulus and Remainder operations (Was Re: Help with a bit of C code)

[Robert Dewar]

Well Henry, of course anyone can play the part of "completely bamboozled by
yet another incomprehensible Ada rule from those language lawyers", but
*really* the rule on limited types is quite easy to understand, and the
design and motivation behind the rule seems quite clear.

Re: Modulus and Remainder operations (Was Re: Help with a bit of C code)

[Tucker Taft]

In article <hbakerCxo6GM.KLs@netcom.com>,
Henry G. Baker <hbaker@netcom.com> wrote:

> ...  the definer of [a limited] type has lost control of the type.

>In article <1994Oct13.092135@di.epfl.ch> 
>Magnus.Kempe@di.epfl.ch (Magnus Kempe) writes:
>>Henry, please read RM9X 6.2(4-10).  The following declaration ensures that
>>parameters of type T will always be passed by reference:
>>
>>package P is
>>  type T is limited private;
>>private
>>  type T is limited record ... end record; -- NOTE: "limited"
>>end P;
>> ...
>>Your problem is SOLVED In Ada 9X.
>
>For _most_, but not _all_, limited types.   ...

Not all limited types are used for the same purpose.  
In Ada 9X, the programmer decides whether pass-by-copy, 
pass-by-reference, or pass-by-most-efficient-route is appropriate.

That is what programmers are supposed to do.  It seems inappropriate
for the language designer to make these decisions for the programmer.
The language should provide the building blocks.  The programmer gets
to stack them up ;-).

>      Henry Baker

-Tucker Taft  stt@inmet.com

Re: Modulus and Remainder operations (Was Re: Help with a bit of C code)

[Tucker Taft]

In article <hbakerCxL95y.8L3@netcom.com>,
Henry G. Baker <hbaker@netcom.com> wrote:

>In article <37er8t$oh0@watnews1.watson.ibm.com> ncohen@watson.ibm.com writes:

>>4. In Ada 9X, the parameter-passing mechanism is mandated in many cases
>>   where Ada 83 leaves it up to the implementation.   ...

>So I've been told.  But this policy is still a crock, especially for
>Ada 'limited' types, because the definer of the type has lost control
>of the type.  The 'textbook' definitions of prototypical limited types
>such as 'bank accounts' are no longer safe in the presence of such
>equivocation.

The "definer" of a limited type can decide whether to require
pass-by-reference, so they have not lost control of the type.
If you want to ensure pass-by-reference, then just declare
your limited (full) type as:

    type T is limited record
       ... -- whatever
    end T;

All objects of such a type are always passed by reference.

On the other hand, if the full type of a limited private type is in fact
nonlimited, then the definer has "lost control" over the parameter
passing, though clearly, in Ada 9X, they had the choice not to.

There are good reasons for this flexibility.  Being able to pass by copy
is essential in certain circumstances, such as extracting from a bit-packed
data structure, or in a distributed system.  The Ada rules give
flexiblity here, but as you have noted there is a price.  In Ada 9X,
the definer of a type can choose whether they want the flexibility,
or the control, by whether they make the full type nonlimited (might
be passed by copy), or limited (will be passed by reference).

>See "How to Steal from a Limited Private Account--Why Mode INOUT
>Parameters for Limited Types MUST be Passed by Reference".  Ada
>Letters XIII, 3 (May/June 1993), 91-95.  This paper is also in my ftp
>directory.

In Ada 9X, these attempts at theft can be prevented by the definer
of the type, by simply making the full type itself limited.

>      Henry Baker
>      Read ftp.netcom.com:/pub/hbaker/README for info on ftp-able papers.

S. Tucker Taft   stt@inmet.com
Ada 9X Mapping/Revision Team
Intermetrics, Inc.
Cambridge, MA  02138

Re: Modulus and Remainder operations (Was Re: Help with a bit of C code)

[Norman H. Cohen]

In article <hbakerCxL95y.8L3@netcom.com>, hbaker@netcom.com (Henry G. Baker)
says of the bounded error that results from aliasing subprogram
variables: 

|>                     But this policy is still a crock, especially for
|> Ada 'limited' types, because the definer of the type has lost control
|> of the type.  The 'textbook' definitions of prototypical limited types
|> such as 'bank accounts' are no longer safe in the presence of such
|> equivocation.
|>
|> See "How to Steal from a Limited Private Account--Why Mode INOUT
|> Parameters for Limited Types MUST be Passed by Reference".  Ada
|> Letters XIII, 3 (May/June 1993), 91-95.  This paper is also in my ftp
|> directory.

Henry, you seem to be envisioning some sort of adversarial relationship
between the writer of a limited private type and the client who uses the
type.  It makes more sense to think of the limited private type as an
appliance that is used by the client.  If you use it properly, it is
guaranteed to work; if you abuse it, you void the warranty.  The client
who uses the limited private type in a way that violates the rules of Ada
is the one responsible for the fact that the properties of the
limited-private type are violated, and it is his program that breaks.

If your point is simply that a "bounded error" can have consequences more
wide-ranging than one might suspect from the innocuous-looking lists of
possible outcomes (use the old parameter value, use the new parameter
value, or raise Program_Error), then your point is well taken.

It's still a step forward from Ada 83, where the same rule violation is
considered erroneous, which means in effect that the underlying abstract
machine is broken and NOTHING is guaranteed.

--
Norman H. Cohen    ncohen@watson.ibm.com

Re: Modulus and Remainder operations (Was Re: Help with a bit of C code)

[Henry G. Baker]

In article <37k951$153e@watnews1.watson.ibm.com> ncohen@watson.ibm.com writes:
>In article <hbakerCxL95y.8L3@netcom.com>, hbaker@netcom.com (Henry G. Baker)
>says of the bounded error that results from aliasing subprogram
>variables: 
>
>|>                     But this policy is still a crock, especially for
>|> Ada 'limited' types, because the definer of the type has lost control
>|> of the type.  The 'textbook' definitions of prototypical limited types
>|> such as 'bank accounts' are no longer safe in the presence of such
>|> equivocation.
>|>
>|> See "How to Steal from a Limited Private Account--Why Mode INOUT
>|> Parameters for Limited Types MUST be Passed by Reference".  Ada
>|> Letters XIII, 3 (May/June 1993), 91-95.  This paper is also in my ftp
>|> directory.
>
>Henry, you seem to be envisioning some sort of adversarial relationship
>between the writer of a limited private type and the client who uses the
>type.

In short, yes.  We'll never reach the nirvana of being able to
more-or-less painlessly put together large systems from smaller
components without some strong guarantees that clients of
encapsulations cannot screw up the objects exported by the
encapsulations.  The more of these 'contractual' issues that can be
put _into_ the language and type system so that they can be enforced,
the easier it will be to construct these systems by composition.

Static type systems and 'packages' were deemed important for precisely
these reasons.  However, Ada83 & Ada9X have heretofore refused to close
this loophole in the strong typing model.

>It's still a step forward from Ada 83, where the same rule violation is
>considered erroneous, which means in effect that the underlying abstract
>machine is broken and NOTHING is guaranteed.

I agree that it is a step forward, in much the same vein that a square
wheel is an improvement on a triangular one.  Still makes for one heck
of a bumpy ride, though.  :-)

      Henry Baker
      Read ftp.netcom.com:/pub/hbaker/README for info on ftp-able papers.

Re: Modulus and Remainder operations (Was Re: Help with a bit of C code)

[David Weller]

In article <hbakerCxo659.H6w@netcom.com>,
Henry G. Baker <hbaker@netcom.com> wrote:
>
>I agree that it is a step forward, in much the same vein that a square
>wheel is an improvement on a triangular one.  Still makes for one heck
>of a bumpy ride, though.  :-)
>

Sir, I respectfully disagree.  In my seminal work, "Kittens: Cats of
the Future?", I mathematically prove the converse of your statement,
that Triangular wheels are an improvement over square ones.  I won't
go into all the mathematical mumbo-jumbo, but the central theme,
stressed repeatedly in the paper, focuses on the "Bump Factor".
While this formula still requires more study (a topic of my doctoral
research at Slimy Stone on the Green River University of Improbable
Studies, Hatfordhanoverschestershire, West Sufferfolk, England), let
me present a rough sketch:

	+---+					/\
	|   |				       /  \
	+---+ Square = 4 sides                /____\ Triangle = 3 sides

Let us take into consideration the consumer-oriented view, that each
individual bump contributes to the overall discomfort, we will use
the variable Bd (Bumpiness discomfort).  When we permit squares and
triangles of equal sides (s), we find that the mathematical derivations
(see seminal work mentioned above) simplifies to: Bd = n * s.

Thus, one can see that, for a square wheel, Bd(square)= 4s.  While
for a triangular wheel, Bd(triangle)= 3s.  Thus, triangular wheels
are less bumpy than square wheels.

My research is now extending this theory to two-sided and one-sided
wheels.  While the one-sided wheels are somewhat problematic, given
the physical challenge of milling a wheel that is a point, the
two-sided wheel variation is progressing nicely.  At this point, the
current limitation we seem to have is getting the vehicle to propel
itself properly.  However, we're currently modifying a Yugo to hold a
'78 Trans-Am 6.6 Litre engine.  My engineering assistant assures me
this will work spectacularly.

I will publish a report next year, "Puppies: Dogs of the Future?"
which will bring to completion this theory.  I look forward to a
well-received publication, and invite you to be a distinguished
reviewer.

I apologize for moving off-topic, but such blasphemous statements
simply cannot go unanswered.


-- 
Proud (and vocal) member of Team Ada! (and Team OS/2)        ||This is not your
   	      Ada -- Very Cool.  Doesn't Suck.               ||  father's Ada 
For all sorts of interesting Ada tidbits, run the command:   ||________________
"finger dweller@starbase.neosoft.com | more" (or e-mail with "finger" as subj.)
   ObNitPick: Spelling Ada as ADA is like spelling C++ as CPLUSPLUS. :-) 

Re: Modulus and Remainder operations (Was Re: Help with a bit of C code)

[Henry G. Baker]

In article <37n2bo$boo@Starbase.NeoSoft.COM> dweller@Starbase.NeoSoft.COM (David Weller) writes:
>In article <hbakerCxo659.H6w@netcom.com>,
>Henry G. Baker <hbaker@netcom.com> wrote:
>>
>>I agree that it is a step forward, in much the same vein that a square
>>wheel is an improvement on a triangular one.  Still makes for one heck
>>of a bumpy ride, though.  :-)
>
>Sir, I respectfully disagree.  In my seminal work, "Kittens: Cats of
>the Future?", I mathematically prove the converse of your statement,
>that Triangular wheels are an improvement over square ones.  I won't
>go into all the mathematical mumbo-jumbo, but the central theme,
>stressed repeatedly in the paper, focuses on the "Bump Factor".
>While this formula still requires more study (a topic of my doctoral
>research at Slimy Stone on the Green River University of Improbable
>Studies, Hatfordhanoverschestershire, West Sufferfolk, England), let
>me present a rough sketch:
>
>	+---+					/\
>	|   |				       /  \
>	+---+ Square = 4 sides                /____\ Triangle = 3 sides
>
>Let us take into consideration the consumer-oriented view, that each
>individual bump contributes to the overall discomfort, we will use
>the variable Bd (Bumpiness discomfort).  When we permit squares and
>triangles of equal sides (s), we find that the mathematical derivations
>(see seminal work mentioned above) simplifies to: Bd = n * s.
>
>Thus, one can see that, for a square wheel, Bd(square)= 4s.  While
>for a triangular wheel, Bd(triangle)= 3s.  Thus, triangular wheels
>are less bumpy than square wheels.
>
>My research is now extending this theory to two-sided and one-sided
>wheels.  While the one-sided wheels are somewhat problematic, given
>the physical challenge of milling a wheel that is a point, the
>two-sided wheel variation is progressing nicely.  At this point, the
>current limitation we seem to have is getting the vehicle to propel
>itself properly.  However, we're currently modifying a Yugo to hold a
>'78 Trans-Am 6.6 Litre engine.  My engineering assistant assures me
>this will work spectacularly.
>
>I will publish a report next year, "Puppies: Dogs of the Future?"
>which will bring to completion this theory.  I look forward to a
>well-received publication, and invite you to be a distinguished
>reviewer.

You might consider studying wheels with a _negative_ number of sides
-- presumably you drive around _inside_ the wheel.  Also non-integral
numbers of sides -- e.g., rational, irrational & transcendental
wheels.

-----

I don't know if you've seen the bicycle chainwheels which are
elliptical instead of round.  They seem to transmit power from the leg
in a slightly more uniform manner, and should be slightly more
efficient.  It drives the derailleur a bit crazy, though.

      Henry Baker
      Read ftp.netcom.com:/pub/hbaker/README for info on ftp-able papers.

Re: Modulus and Remainder operations (Was Re: Help with a bit of C code)

[Charles H. Sampson]

In article <37er8t$oh0@watnews1.watson.ibm.com> ncohen@watson.ibm.com writes:
>In article <1994Oct11.161048.1058@nosc.mil>, sampson@nosc.mil (me) writes: 
>
>|> In article <hbakerCxFK2p.4wp@netcom.com>,
>|> Henry G. Baker <hbaker@netcom.com> wrote: 
>...
>|> >Sounds a bit like Ada's uncertainty about INOUT parameter passing
>|> >being 'by-reference' or 'by-copyin-copyout'.  I don't think that Ada83
>|> >even required that a particular subprogram do it the same way for
>|> >every call.
>|>
>|>      All true, but at least the Ada definition acknowledges the indetermin-
>|> ism and says that any program that relies on a particular choice of imple-
>|> mentation is erroneous.  I doubt that the C standard declares erroneous any
>|> program that relies on the division operator!
>
>Let's be fair: 
>
>1. The issue here is not "reliance on the division operator", but
>   reliance on the direction in which a nonintegral quotient is rounded
>   when the divisor or dividend is negative.
>
     I was using "reliance on" in the same sense as the LRM use of "depends
on" in LRM 6.2(7).  If there's any essential difference between the two
phrases, it is escaping me.  I also don't see any difference between "reli-
ance on an operator" and "reliance on the result obtained when the operator
is applied".

     My point is that the C standard says that the integer division opera-
tor can give one of two possible results.  Any C programmer who relies on
getting a particular one of those results will find that he has the same
portability problem as the Ada programmer who (for whatever reason) creates
an erroneous program that relies on a parameter passing mechanism.  They
both must also face the small possibility that their programs will blow up
on the next release of their compilers.

>2. [What Ada calls "erroneous execution" the ANSI C standard calls
>   "undefined behavior".]

>3. The ANSI C standard does not say that dependence on the direction of
>   rounding the quotient makes the behavior undefined, only that the
>   direction of rounding is "implementation-defined".  That gives the
>   implementation much less freedom.  It may round up or it may round
>   down, but it may not overwrite a return address on the stack, for
>   example.

     Fair enough.  The behavior is defined, being limited to a finite set
(namely two) of possible outcomes.  It still looks to me like the careful C
programmer has the same problem with division as the Ada programmer does
with rounding.

>4. In Ada 9X, the parameter-passing mechanism is mandated in many cases
>   where Ada 83 leaves it up to the implementation.  In the cases where
>   it is still up to the implementation, the crime of "relying" on a
>   particular mechanism has been more precisely defined and its severity
>   has been reduced from "erroneous execution" (a captial offense) to
>   "bounded error" (a noncapital felony).  If a formal parameter has more
>   than one "access path" (i.e., it is "aliased" in the pre-Ada-9X sense)
>   and it is updated by one name, then examined by the other name, the
>   possible outcomes are that the examination will yield the old value,
>   that the examination will yield the new value, or (science fiction)
>   that your very clever compiler will catch this error and raise the
>   exception Program_Error.  See RM9X-6.2(12) for the details.

     This discussion has caused me to reread, once again, the definition of
"erroneous execution" in LRM 1.6(7).  The gist is that there are certain
Ada rules that might not be caught by a compiler/runtime and if one of
these rules is violated the effect of execution is unpredictable.  The
interesting point to me is that the effect of executing a program that
relies on a particular choice of a compiler-dependent feature is also un-
predictable.  Does anyone know why programs that rely on an implementation
of a compiler-dependent feature were not also classified as erroneous?

                                   Charlie

Re: Modulus and Remainder operations (Was Re: Help with a bit of C code)

[Robert I. Eachus]

In article <1994Oct13.181350.10997@nosc.mil> sampson@nosc.mil (Charles H. Sampson) writes:

 >   This discussion has caused me to reread, once again, the definition of
 > "erroneous execution" in LRM 1.6(7).  The gist is that there are certain
 > Ada rules that might not be caught by a compiler/runtime and if one of
 > these rules is violated the effect of execution is unpredictable.  The
 > interesting point to me is that the effect of executing a program that
 > relies on a particular choice of a compiler-dependent feature is also un-
 > predictable.  Does anyone know why programs that rely on an implementation
 > of a compiler-dependent feature were not also classified as erroneous?

    Because it is the difference between undefined and not defined in
this standard.  The value of an (integer say)  variable which has
never been assigned to is undefined.  The value of INTEGER'SIZE is
implementation dependent.  You certainly don't want to declare that
any program which depends on INTEGER'SIZE is erroneous.

    Basically 1.1.1(16) says that the effect of executing a program
which depends on implementation dependent features is one from the set
of all possible legal effects.  (Knowing the implementation
characteristics can help you narrow that down. ;-)
--

					Robert I. Eachus

with Standard_Disclaimer;
use  Standard_Disclaimer;
function Message (Text: in Clever_Ideas) return Better_Ideas is...

Re: Modulus and Remainder operations (Was Re: Help with a bit of C code)

[Robert Dewar]

There is a big difference between the different kinds of "errors", and chief
among them is that some of them are not considered errors.

Implementation dependent means that the effect is a function of the
implementation, but the implementation is not required to document
what it does. It is not in any sense an error to write such code,
but its effect is non-deterministic, and so it would be wrong in
some sense to "rely" on a particular behavior, whatever that means.
The fact that it is impossible to formally characterize is why we
have abandoned statements like "relying on xxx is erronoues", such
statements are semantically vacuous.

Implementation defined means that the effect must be defined by the
implementation. The effect is entirely deterministic for a given
implementation, and there is nothing WHATSOEVER wrong in relying on
the documented behavior. Of course the code is potentially non-portable,
but there are many ways to write non-portable code, and many situations
in which it is quite legitimate to write non-portable code (e.g. in
device drivers). Writing non-portable code when you should be writing
portable code is a mistake, but is not somehow "wrong" at the language
level.

Erroneous means that the compiler is free to do anything at all, and
we definitely intend to imply that erroneous execution is an error in the
general sense, to be avoided. While it can be quite legitimate to write
a program that exploits an implementation dependent or implentation
defined feature, it is never legitimate to write an erroneous program,
and the compiler is free to for example raise program error (or worse)
if it detects the error (or if it doesn't).

A bounded error is a special case of erroneousness where the possible
things the compiler can do are limited. IN purely formal terms it is
no different from a non-deterministic behavior. However, the 
non-formalizable, but very important difference, is that it is definitely
considered an error, essentially as bad as writing erroneous programs,
to write programs containing bounded errors. The reason we go to the trouble
of limiting the damage is to (a) make programs easier to debug and (b) attempt
to limit the damage that occurs if a program accidentally runs into a bounded
error.

Re: Modulus and Remainder operations (Was Re: Help with a bit of C code)

[Bob Duff]

In article <1994Oct13.181350.10997@nosc.mil>,
Charles H. Sampson <sampson@nosc.mil> wrote:

> ...Does anyone know why programs that rely on an implementation
>of a compiler-dependent feature were not also classified as erroneous?
>
>                                   Charlie

Depending on an implementation-dependent feature makes your program
nonportable.  Erroneous execution is much worse: your program might do
anything, including delete all the files on your disk, crash the system,
and set your keyboard on fire.  Therefore, erroneousness is reserved for
situations where we really can't predict what might happen.  (A good
operating system will minimize the probability of trashing the disk, but
I know of case where an erroneous Ada program running under MS-DOS
actually destroyed the root directory.)

In Ada 9X, we have reduced the number of erroneous situations.  For
example, in Ada 83, reading an uninitialized variable was considered
erroneous.  In Ada 9X, this is defined as a "Bounded Error", which is
not quite as bad as being erroneous, since you have *some* knowledge of
what the program might do.  Either way, you shouldn't read an
uninitialized variable.  But if you do (presumably by accident), then in
Ada 9X, the damage is a bit less -- it can't trash your disk, for
example.

In general, "not portable" is not considered to be an error,
and certainly should not always be classified as "erroneous".

- Bob
-- 
Bob Duff                                bobduff@inmet.com
Oak Tree Software, Inc.
Ada 9X Mapping/Revision Team (Intermetrics, Inc.)