kuyper@wizard.net wrote:
 > Greg Herlihy wrote:
 >> Seungbeom Kim wrote:
 >>> Greg Herlihy wrote:
 >>>>     (p - q) + (q - array);

 >>>> Next we take advantage of the fact that the additive
 >>>> operators are associative for built-in types to transform
 >>>> the above calculation into:

 >>>>     p + (-q + q) - array;
 >>> Additive operators are associative? Not true in general.

 >> Additive operators are associative for all real numbers. And
 >> I would consider the set of all reals, a pretty "general"
 >> case.

 > There's key differences between mathematical operators acting
 > on real numbers, and C++ operators acting on representations
 > of arithmetic types. The C++ operators operations are not, in
 > general, either associative nor commutative. They have finite
 > upper and lower limits, and for floating point numbers they
 > have a finite precision that varies depending upon the value
 > being represented. They are associated and commutative, when
 > the values involved in the operations allow them to be, as
 > accurately as those values allow them to be, but it's not
 > possible for them to be associative for all sets of values,
 > and for floating point values they can't be exactly
 > associative even for some sets of values where it's possible
 > for them to be approximately associative.

 > Pointer arithmetic is another matter entirely. It's connected
 > to math only because it's defined in terms of positions in an
 > array. That connection means it's closely realited to integer
 > arithmetic. However, that definition only applies to pointers
 > to positions within the array, and by dint of special rules,
 > it has been extended to include positions one past the end of
 > the array.

And it isn't always defined then.  Given two pointers, p and q,
the results of p-q are defined only if they can be represented
in a ptrdiff_t.  And on most machines, this isn't at all
guaranteed.

Still, of course, you've hit the nail on the head.  Mathematics
doesn't deal with pointer arithmetic, because mathematics
doesn't know what a pointer is.  All we have to go on with
regards to pointer arithmetic is what the standard says.

     [...]
 >>> See 1.9/15; it says certain restrictions apply for
 >>> associativity or commutativity to hold, but it's basically a
 >>> rephrase of the as-if rule, and we may just as well say that
 >>> operators are not associative or commutative.

 >> Only if there is a risk of overflow. Given the following
 >> relation:

 >>     array < q <  p;

 >> there is no chance that measuring the distance between array
 >> and q or between p and q would overflow if the distance from
 >> p to array does not overflow.

Define overflow for pointer arithmetic.  (And of course, there
isn't the slightest guarantee that p - array will not overflow,
so your if doesn't hold.)

--
James Kanze                                    kanze.james@neuf.fr
Conseils en informatique orient   e objet/
                   Beratung in objektorientierter Datenverarbeitung
9 place S   mard, 78210 St.-Cyr-l'   cole, France +33 (0)1 30 23 00 34

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

Greg Herlihy wrote:
 > Seungbeom Kim wrote:
 >> Greg Herlihy wrote:
 >>>     (p - q) + (q - array);

 >>> Next we take advantage of the fact that the additive
 >>> operators are associative for built-in types to transform
 >>> the above calculation into:

 >>>     p + (-q + q) - array;
 >> Additive operators are associative? Not true in general.

 > Additive operators are associative for all real numbers. And I
 > would consider the set of all reals, a pretty "general" case.

We're talking about programming languages here, and particularly
C++.  And no programming language supports the set of all reals.
Additive operators are NOT associative in C++, except for
unsigned integral types.

 > Now the sets of numbers particular to C++ they are certainly
 > associative in this example

 >> See 1.9/15; it says certain restrictions apply for
 >> associativity or commutativity to hold, but it's basically a
 >> rephrase of the as-if rule, and we may just as well say that
 >> operators are not associative or commutative.

 > Only if there is a risk of overflow.

Nonsense.  That's only true for integral types, not for all
arithmetic types.  And of course, we don't even know what
overflow means when applied to a pointer.

 > Given the following relation:

 >     array < q <  p;

 > there is no chance that measuring the distance between array
 > and q or between p and q would overflow if the distance from p
 > to array does not overflow. And that is all that shown above.
 > The value i will have the same (possibly
 > implementation-defined value) as (p - q) + (q - array).

Only if the standard requires it to.  Which, as far as I know,
isn't the case.

--=20
James Kanze                                    kanze.james@neuf.fr
Conseils en informatique orient=E9e objet/
                   Beratung in objektorientierter Datenverarbeitung
9 place S=E9mard, 78210 St.-Cyr-l'=C9cole, France +33 (0)1 30 23 00 34

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

Over on comp.lang.c++.moderated, Matthias Hofmann has noticed a technicality
in the Standard:

> Strangely, section 5.7/6 does not explicitly guarantee that this is
> legal C++: "When two pointers to elements of the same array object are
> subtracted, the result is the difference of the subscripts of the two
> array elements."

This paragraph brings into doubt whether the following code is OK:

    int array[5];

    int *p = array + 5;

    ptrdiff_t i = p - &array[0];

Is this code legal? Strictly speaking, "p" doesn't point to an element of the
array.

Perhaps the next Standard should clarify this matter?

--

Frederick Gotham

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

Frederick Gotham wrote:
> Over on comp.lang.c++.moderated, Matthias Hofmann has noticed a technicality
> in the Standard:
>
> > Strangely, section 5.7/6 does not explicitly guarantee that this is
> > legal C++: "When two pointers to elements of the same array object are
> > subtracted, the result is the difference of the subscripts of the two
> > array elements."
>
> This paragraph brings into doubt whether the following code is OK:
>
>     int array[5];
>
>     int *p = array + 5;
>
>     ptrdiff_t i = p - &array[0];
>
> Is this code legal? Strictly speaking, "p" doesn't point to an element of the
> array.

The code is legal. The question perhaps is whether "i" has a defined
value. The unsurprising answer is that i does have a defined value. And
here's how we can prove it:

First, we'll introduce a "q" pointer variable into the original program
that points to the last element of the array.

    int array[5];

    int *p = array + 5;
    int *q = array + 4;

Now, the plan is simple: use q in two pointer arithmetic expressions
whose value is defined and then add them together.

    (p - q) + (q - array);

Next we take advantage of the fact that the additive operators are
associative for built-in types to transform the above calculation into:

    p + (-q + q) - array;

Since the Standard tells us that a pointer subtracted from itself is
zero, and that zero added to a pointer does not change that pointer's
value - we can safely eliminate the middle portion of this calculation,
leaving just:

    p - array;

So via substitution, the last line in the original program could be
written as:

    ptr_diff i =  (p - q) + (q - array);

meaning that i's value is defined (as the sum of two defined, integral
values).

Greg

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

Greg Herlihy wrote:
>
>     (p - q) + (q - array);
>
> Next we take advantage of the fact that the additive operators are
> associative for built-in types to transform the above calculation into:
>
>     p + (-q + q) - array;

Additive operators are associative? Not true in general.

See 1.9/15; it says certain restrictions apply for associativity or
commutativity to hold, but it's basically a rephrase of the as-if rule,
and we may just as well say that operators are not associative or
commutative.

--
Seungbeom Kim

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

Seungbeom Kim posted:

> Greg Herlihy wrote:
>>
>>     (p - q) + (q - array);
>>
>> Next we take advantage of the fact that the additive operators are
>> associative for built-in types to transform the above calculation into:
>>
>>     p + (-q + q) - array;
>
> Additive operators are associative? Not true in general.


Do you not mean commutative? Only unsigned arithmetic is commutative.

The following may produce undefined behaviour:

    65535 + 5 - 400

while the following is perfectly sound:

    65535 - 400 +5

--

Frederick Gotham

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

Frederick Gotham wrote:
> Over on comp.lang.c++.moderated, Matthias Hofmann has noticed a technicality
> in the Standard:
>
> > Strangely, section 5.7/6 does not explicitly guarantee that this is
> > legal C++: "When two pointers to elements of the same array object are
> > subtracted, the result is the difference of the subscripts of the two
> > array elements."
>
> This paragraph brings into doubt whether the following code is OK:
>
>     int array[5];
>
>     int *p = array + 5;
>
>     ptrdiff_t i = p - &array[0];
>
> Is this code legal? Strictly speaking, "p" doesn't point to an element of the
> array.
>
> Perhaps the next Standard should clarify this matter?
>

5.7/6 addresses this in the fourth sentence after the one you quote:

  Moreover, if the expression P points either to an element of an
  array object or one past the last element of an array object,
  and the expression Q points to the last element of the same
  array object, the expression ((Q) + 1) - (P) has the same value
  as ((Q) - (P)) + 1 and as - ((P) - ((Q) + 1)), and has the value
  zero if the expression P points one past the last element of
  the array object, even though the expression (Q) + 1 does not
  point to an element of the array object.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

Seungbeom Kim wrote:
> Greg Herlihy wrote:
> >
> >     (p - q) + (q - array);
> >
> > Next we take advantage of the fact that the additive operators are
> > associative for built-in types to transform the above calculation into:
> >
> >     p + (-q + q) - array;
>
> Additive operators are associative? Not true in general.

Additive operators are associative for all real numbers. And I would
consider the set of all reals, a pretty "general" case.

Now the sets of numbers particular to C++
 they are certainly associative in this example
> See 1.9/15; it says certain restrictions apply for associativity or
> commutativity to hold, but it's basically a rephrase of the as-if rule,
> and we may just as well say that operators are not associative or
> commutative.

Only if there is a risk of overflow. Given the following relation:

    array < q <  p;

there is no chance that measuring the distance between array and q or
between p and q would overflow if the distance from p to array does not
overflow. And that is all that shown above. The value i will have the
same (possibly implementation-defined value) as (p - q) + (q - array).

Greg

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

Greg Herlihy wrote:
> Seungbeom Kim wrote:
> > Greg Herlihy wrote:
> > >
> > >     (p - q) + (q - array);
> > >
> > > Next we take advantage of the fact that the additive operators are
> > > associative for built-in types to transform the above calculation into:
> > >
> > >     p + (-q + q) - array;
> >
> > Additive operators are associative? Not true in general.
>
> Additive operators are associative for all real numbers. And I would
> consider the set of all reals, a pretty "general" case.

There's key differences between mathematical operators acting on real
numbers, and C++ operators acting on representations of arithmetic
types. The C++ operators operations are not, in general, either
associative nor commutative. They have finite upper and lower limits,
and for floating point numbers they have a finite precision that varies
depending upon the value being represented. They are associated and
commutative, when the values involved in the operations allow them to
be, as accurately as those values allow them to be, but it's not
possible for them to be associative for all sets of values, and for
floating point values they can't be exactly associative even for some
sets of values where it's possible for them to be approximately
associative.

Pointer arithmetic is another matter entirely. It's connected to math
only because it's defined in terms of positions in an array. That
connection means it's closely realited to integer arithmetic. However,
that definition only applies to pointers to positions within the array,
and by dint of special rules, it has been extended to include positions
one past the end of the array. Those rules say nothing that allow you
to extend associativity to include pointers that don't point into the
array, and don't point one past the end of the array. Instead, it
explicit says that simply creating such pointers has undefined
behavior; it says that for the simple reason that there are real, and
popular, architectures where creation of such pointers can cause your
program to abort.

> Now the sets of numbers particular to C++
>  they are certainly associative in this example
> > See 1.9/15; it says certain restrictions apply for associativity or
> > commutativity to hold, but it's basically a rephrase of the as-if rule,
> > and we may just as well say that operators are not associative or
> > commutative.
>
> Only if there is a risk of overflow. Given the following relation:
>
>     array < q <  p;
>
> there is no chance that measuring the distance between array and q or
> between p and q would overflow if the distance from p to array does not
> overflow. And that is all that shown above. The value i will have the
> same (possibly implementation-defined value) as (p - q) + (q - array).

There's no gurantee what it will have. All uses of p and q in either
expression,  (p-q)+(q-array) or p-array, make the behavior of your
program undefined.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

Greg Herlihy wrote:
.
> Next we take advantage of the fact that the additive operators are
> associative for built-in types ...

Citation, please?

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

On Thu, 10 Aug 2006 00:12:58 -0600, kuyper wrote:

> Greg Herlihy wrote:
>> Seungbeom Kim wrote:

> The C++ operators operations are not, in general, either
> associative nor commutative. They have finite upper and lower limits,

For unsigned types, addition and multiplication are necessarily
associative and commutative for all values. This follows directly
from the fact that they're cyclic groups with respect to both
addition and multiplication (group operators are always associative).

For signed types, I believe the correct qualifier to use is 'locally'.
This rough meaning of locally is: for suitably small compact
sets near zero. To be precise:

For small enough d > 0, then for all | i1 | < d and | i2 | < d
and | i3 | < d then

 i1 + (i2 + i3) = (i1 + i2) + i3

and similarly for commutative, and similarly for multiplication.
In all these cases, we can actually calculate the largest possible
value of d. Clearly, adding a set of n integers and getting the
same result independently of order of addition will increasingly
constrain the bound d. In fact, for addition, the bound is easily
calculated and close to MAXINT/n. For multiplication of course,
the bound rapidly drops to 1.

In fact in many 'pragmatic' calculations, programmers assume
associativity. We use 'int' and calculate things without carefully
considering whether we need to order the calculations to avoid
overflow, because usually all the possible partial results are
well within the reasonable bounds.

Unfortunately, in some cases, there's a difference between
the expected data, and what is possible. For a classic error
in a classic textbook: Foley and van Dam get this wrong
in the Beshnam (sp?) line drawing algorithm. This is an algorithm
to draw a line on a 2 dimensional grid: their calculation
is actually incorrect when the line is almost infinitely
steep, because addition and division only distribute locally:

 (a + b)/2

is NOT the same as

 a/2 + b/2

The latter cannot overflow. The former calculation can.
What's more .. the two give different results even when they
do not overflow:

 (3 + 3)/2 = 3
 3/2 + 3/2 = 2

It is not so easy to calculate (a+b)/2 correctly without overflow!

--
John Skaller <skaller at users dot sf dot net>
Try Felix, the successor to C++ http://felix.sf.net


---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

skaller wrote:
> On Thu, 10 Aug 2006 00:12:58 -0600, kuyper wrote:
.
> > The C++ operators operations are not, in general, either
> > associative nor commutative. They have finite upper and lower limits,
>
> For unsigned types, addition and multiplication are necessarily
> associative and commutative for all values. This follows directly
> from the fact that they're cyclic groups with respect to both
> addition and multiplication (group operators are always associative).

That's why I used the qualifier "generally". Since the context was
pointer arithmetic, which is not an exception, I didn't want to go into
the details of the cases that are exceptions,.

.
> For signed types, I believe the correct qualifier to use is 'locally'.
> This rough meaning of locally is: for suitably small compact
> sets near zero. To be precise:
>
> For small enough d > 0, then for all | i1 | < d and | i2 | < d
> and | i3 | < d then
>
>  i1 + (i2 + i3) = (i1 + i2) + i3

Note that while this is possible for integers, there's no value you can
choose for 'd' that will make that exactly true for floating point
types. The best you can do is have it be approximately true, and to
place upper limits on the size of the discrepancy.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

skaller wrote:
> In fact in many 'pragmatic' calculations, programmers assume
> associativity. We use 'int' and calculate things without carefully
> considering whether we need to order the calculations to avoid
> overflow, because usually all the possible partial results are
> well within the reasonable bounds.
>
> Unfortunately, in some cases, there's a difference between
> the expected data, and what is possible. For a classic error
> in a classic textbook: Foley and van Dam get this wrong
> in the Beshnam (sp?) line drawing algorithm. This is an algorithm
> to draw a line on a 2 dimensional grid: their calculation
> is actually incorrect when the line is almost infinitely
> steep, because addition and division only distribute locally:
>
> (a + b)/2
>
> is NOT the same as
>
> a/2 + b/2
>
> The latter cannot overflow. The former calculation can.

Actually, can't both overflow if INT_MIN is odd and division rounds down?
Rounding to zero is apparently recommended, and required in C99, but not
yet required in C++, right?

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]