Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.forth > #46294 > unrolled thread

The problem with implementation defined behaviour.

Back to article view | Back to comp.lang.forth

Contents

  The problem with implementation defined behaviour. Albert van der Horst <albert@spenarnc.xs4all.nl> - 2016-03-29 14:39 +0000
    Re: The problem with implementation defined behaviour. anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-03-29 16:20 +0000
      Re: The problem with implementation defined behaviour. "Elizabeth D. Rather" <erather@forth.com> - 2016-03-29 09:16 -1000
        Re: The problem with implementation defined behaviour. Bernd Paysan <bernd.paysan@gmx.de> - 2016-03-30 00:06 +0000
          Re: The problem with implementation defined behaviour. mhx@iae.nl - 2016-03-29 22:09 -0700
            Re: The problem with implementation defined behaviour. "Elizabeth D. Rather" <erather@forth.com> - 2016-03-29 21:37 -1000
            Re: The problem with implementation defined behaviour. Paul Rubin <no.email@nospam.invalid> - 2016-03-30 00:48 -0700
              Re: The problem with implementation defined behaviour. Paul Rubin <no.email@nospam.invalid> - 2016-03-30 00:48 -0700
            Re: The problem with implementation defined behaviour. anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-03-30 07:59 +0000
              Re: The problem with implementation defined behaviour. mhx@iae.nl - 2016-03-30 10:16 -0700
                Re: The problem with implementation defined behaviour. Bernd Paysan <bernd.paysan@gmx.de> - 2016-03-30 23:43 +0000
                  Re: The problem with implementation defined behaviour. mhx@iae.nl - 2016-03-31 06:01 -0700
                    Re: The problem with implementation defined behaviour. Bernd Paysan <bernd.paysan@gmx.de> - 2016-04-01 21:36 +0000
                      Re: The problem with implementation defined behaviour. mhx@iae.nl - 2016-04-01 14:57 -0700
                        Re: The problem with implementation defined behaviour. Bernd Paysan <bernd.paysan@gmx.de> - 2016-04-01 21:59 +0000
                          Re: The problem with implementation defined behaviour. mhx@iae.nl - 2016-04-02 00:51 -0700
                  Re: The problem with implementation defined behaviour. anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-04-01 08:25 +0000
                    Re: The problem with implementation defined behaviour. Bernd Paysan <bernd.paysan@gmx.de> - 2016-04-01 21:32 +0000
                      division performance (was: The problem with implementation defined ...) anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-04-05 11:12 +0000
                        Re: division performance (was: The problem with implementation defined ...) Bernd Paysan <bernd.paysan@gmx.de> - 2016-04-05 20:45 +0000
                          Re: division performance (was: The problem with implementation defined ...) anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-04-06 10:03 +0000
                            Re: division performance (was: The problem with implementation defined ...) Bernd Paysan <bernd.paysan@gmx.de> - 2016-04-08 22:53 +0000
                              Re: division performance (was: The problem with implementation defined ...) anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-04-09 10:14 +0000
                                Re: division performance (was: The problem with implementation defined ...) anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-04-09 13:43 +0000
                Re: The problem with implementation defined behaviour. anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-03-31 10:55 +0000
                  Re: The problem with implementation defined behaviour. mhx@iae.nl - 2016-03-31 06:38 -0700
                    Re: The problem with implementation defined behaviour. anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-03-31 16:21 +0000
                      Re: The problem with implementation defined behaviour. Paul Rubin <no.email@nospam.invalid> - 2016-03-31 11:49 -0700
                    Re: The problem with implementation defined behaviour. "Elizabeth D. Rather" <erather@forth.com> - 2016-03-31 10:11 -1000
                      Re: The problem with implementation defined behaviour. mhx@iae.nl - 2016-04-01 03:53 -0700
                        Re: The problem with implementation defined behaviour. anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-04-01 11:44 +0000
                          Re: The problem with implementation defined behaviour. Bernd Paysan <bernd.paysan@gmx.de> - 2016-04-01 21:53 +0000
                            Re: The problem with implementation defined behaviour. Andrew Haley <andrew29@littlepinkcloud.invalid> - 2016-04-02 11:46 -0500
                              Re: The problem with implementation defined behaviour. Bernd Paysan <bernd.paysan@gmx.de> - 2016-04-02 21:43 +0000
                                Re: The problem with implementation defined behaviour. Andrew Haley <andrew29@littlepinkcloud.invalid> - 2016-04-03 03:17 -0500
                      Re: The problem with implementation defined behaviour. hughaguilar96@gmail.com - 2016-04-01 23:54 -0700
            Re: The problem with implementation defined behaviour. Albert van der Horst <albert@spenarnc.xs4all.nl> - 2016-03-30 12:58 +0000
            Re: The problem with implementation defined behaviour. Bernd Paysan <bernd.paysan@gmx.de> - 2016-03-30 22:22 +0000
          Re: The problem with implementation defined behaviour. Albert van der Horst <albert@spenarnc.xs4all.nl> - 2016-03-30 12:55 +0000
        Re: The problem with implementation defined behaviour. anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-03-30 07:44 +0000
          Re: The problem with implementation defined behaviour. Albert van der Horst <albert@spenarnc.xs4all.nl> - 2016-03-30 13:08 +0000
            Re: The problem with implementation defined behaviour. anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-03-30 13:43 +0000
          Re: The problem with implementation defined behaviour. Bernd Paysan <bernd.paysan@gmx.de> - 2016-03-30 22:06 +0000
        Re: The problem with implementation defined behaviour. trevor <tgritchie@blueyonder.co.uk> - 2016-03-30 13:13 +0100
          Re: The problem with implementation defined behaviour. Albert van der Horst <albert@spenarnc.xs4all.nl> - 2016-03-30 13:56 +0000
        Re: The problem with implementation defined behaviour. Albert van der Horst <albert@spenarnc.xs4all.nl> - 2016-03-30 12:49 +0000

Page 3 of 3 — ← Prev page 1 2 [3]

#46327

anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:

>"Elizabeth D. Rather" <erather@forth.com> writes:
>>On 3/29/16 6:20 AM, Anton Ertl wrote:
>>> Albert van der Horst <albert@spenarnc.xs4all.nl> writes:
>>>> I have this package that calculates modulo a VARIABLE _m.
>>>> : +m   + _m @ MOD ;
>>>> *m -m /m
>>>> etc.
>...
>>A signed MOD makes no real-world sense. No one
>>has ever presented a mathematical argument for having a signed MOD that
>>I know of.

>I thought about recommending to use UM/MOD for the problem outlined
>above, but then found a case where negative dividends occur:

>: -m - _m @ MOD ;

>E.g., if you do 1 2 -M, the dividend is negative, so unsigned MOD
>won't cut it here.

>However, most people seem to only divide positive numbers by positive
>numbers, as evidenced by the complete lack of complaints from users
>when Gforth switched from symmetric to floored.

That is exactly why I didn't want to bother with defining what the
package does with negative _m. It is just never used in that way.

If you look into the package you see that I don't have an expensive
MOD and no branching in -m , assuming the input is normalized.
(The package is in the ciforth library forth.lab).

P.S.
Mathematically speaking the modulo classes of m and -m are exactly
the same. Choosing different representers of those classes cannot
be supported by mathematical arguments.
12 , 2 -3 are all equivalent modulo 5, as they are modulo -5.

>- anton
-- 
Albert van der Horst, UTRECHT,THE NETHERLANDS
Economic growth -- being exponential -- ultimately falters.
albert@spe&ar&c.xs4all.nl &=n http://home.hccnet.nl/a.w.m.van.der.horst

[toc] | [prev] | [next] | [standalone]

#46329

Albert van der Horst <albert@spenarnc.xs4all.nl> writes:
>anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:
>
>>"Elizabeth D. Rather" <erather@forth.com> writes:
>>>On 3/29/16 6:20 AM, Anton Ertl wrote:
>>>> Albert van der Horst <albert@spenarnc.xs4all.nl> writes:
>>>>> I have this package that calculates modulo a VARIABLE _m.
>>>>> : +m   + _m @ MOD ;
>>>>> *m -m /m
>>>>> etc.
...
>>I thought about recommending to use UM/MOD for the problem outlined
>>above, but then found a case where negative dividends occur:
>
>>: -m - _m @ MOD ;
...
>If you look into the package you see that I don't have an expensive
>MOD and no branching in -m , assuming the input is normalized.

The question is: why do you present a +M that uses an expensive MOD?

>(The package is in the ciforth library forth.lab).

And there you have a different implementation for +M.

- anton
-- 
M. Anton Ertl  http://www.complang.tuwien.ac.at/anton/home.html
comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
     New standard: http://www.forth200x.org/forth200x.html
   EuroForth 2015: http://www.rigwit.co.uk/EuroForth2015/

[toc] | [prev] | [next] | [standalone]

#46341

Am Wed, 30 Mar 2016 07:44:55 +0000 schrieb Anton Ertl:
> I thought about recommending to use UM/MOD for the problem outlined
> above, but then found a case where negative dividends occur:
> 
> : -m - _m @ MOD ;
> 
> E.g., if you do 1 2 -M, the dividend is negative, so unsigned MOD won't
> cut it here.

PolyForth had a signed by unsigned division, M/MOD was ( d u -- umod nquot 
), this is quite easy to implement (if d is negative, you just add u to 
the top half, and then do UM/MOD), i.e.

: m/mod ( d u -- um nq ) >r dup 0< r@ and + r> um/mod ;

This is a typical Chuck Moore solution: it obviously only solves the 
problem the users actually had, and not the "general problem".

It also fits with the mathematical definition of modulus, which simply is 
only for positive numbers.

Forth Inc. however lost with that during the ANS Forth debate (or maybe 
even before with the previous standards): Despite ANS Forth is somewhat 
ambiguous how negative numbers are handled with signed divisions, it does 
not offer the signed/unsigned mix from Forth Inc.

In my b16 projects, I've also found signed by unsigned multiplication 
useful, especially when the multiplication is supposed to be by [0..1[, 
using NIP to scale the result appropriate.  This signed/unsigned m* is

: m* ( n u -- d )  over 0< over and >r um* r> - ;

Note that both can be implemented branchless (as shown here), and 
therefore the overhead is pretty low on modern machines.

-- 
Bernd Paysan
"If you want it done right, you have to do it yourself"
net2o ID: kQusJzA;7*?t=uy@X}1GWr!+0qqp_Cn176t4(dQ*
http://bernd-paysan.de/

[toc] | [prev] | [next] | [standalone]

#46323

On 29/03/16 20:16, Elizabeth D. Rather wrote:
> On 3/29/16 6:20 AM, Anton Ertl wrote:
>> Albert van der Horst <albert@spenarnc.xs4all.nl> writes:
>>> I have this package that calculates modulo a VARIABLE _m.
>>> : +m   + _m @ MOD ;
>>> *m -m /m
>>> etc.
>>>
>>> The result of those operations result on a number 0<=n<=_m.
>>
>> [long discussion of protecting against negative _m]
>>
>> I don't know what you are getting at, but the implementation-defined
>> behaviour that I thought of first when seeing this code is that
>>
>> -2 3 mod
>>
>> produces -2 on some Forth systems and 1 on others.  A way to fix that
>> is to use FM/MOD, which produces positive numbers for a positive
>> dividend.
>>
>> But if, as you write, performance is important, and if _M does not
>> change often, I would go for implementing floored MOD through division
>> by multiplication with the inverse, which is quite a bit faster.  And
>> then your SET-M helps by allowing this implementation without changing
>> the interface.
>>
>>> The bottomline:
>>> The behaviour of the mod package for negative _m is
>>> undefined. I find this acceptable.
>>
>> And the GCC and LLVM people find undefined behaviour in C acceptable,
>> if that's what inspired this posting.  Does not mean that it's ok for
>> the rest of us.
>
> FORTH, Inc. argued for many years that the MOD operators should be
> unsigned; they were unsigned in our systems from the 1970's till
> SwiftForth (which conformed to Forth94). None of our users ever found a
> problem with this usage. A signed MOD makes no real-world sense. No one
> has ever presented a mathematical argument for having a signed MOD that
> I know of.
>
> Cheers,
> Elizabeth
>
I would agree if you mean that the modulus should not be signed. My 
Penguin Dictionary of Mathematics states: "two *integers* a and b are 
congruent to one another modulo n if they differ by a multiple of a 
chosen *natural* number n" By this definition it certainly makes no 
sense for n to be negative.

Trevor

[toc] | [prev] | [next] | [standalone]

#46330

trevor <tgritchie@blueyonder.co.uk> writes:

>On 29/03/16 20:16, Elizabeth D. Rather wrote:
>> On 3/29/16 6:20 AM, Anton Ertl wrote:
>>> Albert van der Horst <albert@spenarnc.xs4all.nl> writes:
>>>> I have this package that calculates modulo a VARIABLE _m.
>>>> : +m   + _m @ MOD ;
>>>> *m -m /m
>>>> etc.
>>>>
>>>> The result of those operations result on a number 0<=n<=_m.
>>>
>>> [long discussion of protecting against negative _m]
>>>
>>> I don't know what you are getting at, but the implementation-defined
>>> behaviour that I thought of first when seeing this code is that
>>>
>>> -2 3 mod
>>>
>>> produces -2 on some Forth systems and 1 on others.  A way to fix that
>>> is to use FM/MOD, which produces positive numbers for a positive
>>> dividend.
>>>
>>> But if, as you write, performance is important, and if _M does not
>>> change often, I would go for implementing floored MOD through division
>>> by multiplication with the inverse, which is quite a bit faster.  And
>>> then your SET-M helps by allowing this implementation without changing
>>> the interface.
>>>
>>>> The bottomline:
>>>> The behaviour of the mod package for negative _m is
>>>> undefined. I find this acceptable.
>>>
>>> And the GCC and LLVM people find undefined behaviour in C acceptable,
>>> if that's what inspired this posting.  Does not mean that it's ok for
>>> the rest of us.
>>
>> FORTH, Inc. argued for many years that the MOD operators should be
>> unsigned; they were unsigned in our systems from the 1970's till
>> SwiftForth (which conformed to Forth94). None of our users ever found a
>> problem with this usage. A signed MOD makes no real-world sense. No one
>> has ever presented a mathematical argument for having a signed MOD that
>> I know of.
>>
>> Cheers,
>> Elizabeth
>>
>I would agree if you mean that the modulus should not be signed. My
>Penguin Dictionary of Mathematics states: "two *integers* a and b are
>congruent to one another modulo n if they differ by a multiple of a
>chosen *natural* number n" By this definition it certainly makes no
>sense for n to be negative.

This agrees with the definition in my Burton: elementary number theory.

Based on this argument MOD should throw an expection 713
"unmathematical operation" as soon as its second operand is not
positive.

Although you lend credit to my lack of willingness to support
negative m in my package, mathematical arguments can get you so
far in implementing a computer language.

Of course the definition makes sense for n negative or even zero.
Definitions are choosen from many possibly definitions that are
equivalent. The mathematical concept that it tries to capture only
exists in the mathematical mind, but they are the same.

This definition is choosen, as always, to make the formulation of
theorems nicer:
The ring of integers modulo n is isomorphic with the ring modulo
m iff n equals m.

(This sounds better than bother that n and m are differing my
 a multiplicative unit of the ring, which is messy because there
 are two maybe not isomorphic rings here.)

>Trevor

Groetjes Albert
-- 
Albert van der Horst, UTRECHT,THE NETHERLANDS
Economic growth -- being exponential -- ultimately falters.
albert@spe&ar&c.xs4all.nl &=n http://home.hccnet.nl/a.w.m.van.der.horst

[toc] | [prev] | [next] | [standalone]

#46324

"Elizabeth D. Rather" <erather@forth.com> writes:

>On 3/29/16 6:20 AM, Anton Ertl wrote:
>> Albert van der Horst <albert@spenarnc.xs4all.nl> writes:
>>> I have this package that calculates modulo a VARIABLE _m.
>>> : +m   + _m @ MOD ;
>>> *m -m /m
>>> etc.
>>>
>>> The result of those operations result on a number 0<=n<=_m.
>>
>> [long discussion of protecting against negative _m]
>>
>> I don't know what you are getting at, but the implementation-defined
>> behaviour that I thought of first when seeing this code is that
>>
>> -2 3 mod
>>
>> produces -2 on some Forth systems and 1 on others.  A way to fix that
>> is to use FM/MOD, which produces positive numbers for a positive
>> dividend.
>>
>> But if, as you write, performance is important, and if _M does not
>> change often, I would go for implementing floored MOD through division
>> by multiplication with the inverse, which is quite a bit faster.  And
>> then your SET-M helps by allowing this implementation without changing
>> the interface.
>>
>>> The bottomline:
>>> The behaviour of the mod package for negative _m is
>>> undefined. I find this acceptable.
>>
>> And the GCC and LLVM people find undefined behaviour in C acceptable,
>> if that's what inspired this posting.  Does not mean that it's ok for
>> the rest of us.

>FORTH, Inc. argued for many years that the MOD operators should be
>unsigned; they were unsigned in our systems from the 1970's till
>SwiftForth (which conformed to Forth94). None of our users ever found a
>problem with this usage. A signed MOD makes no real-world sense. No one
>has ever presented a mathematical argument for having a signed MOD that
>I know of.

I don't know why this discussion has gone into this tangent.

The package I presented is well defined for positive _m.
All operations result in a number 0<x<_m. That is the MOD operator
you use too.

The undefined operations are when _m is negative which just makes
no sense for number theoretic operations and would lead to a number
of difficulties. It is not switching to complex numbers if someone
passes a negative number to SQRT.

>Cheers,
>Elizabeth

Groetjes Albert
-- 
Albert van der Horst, UTRECHT,THE NETHERLANDS
Economic growth -- being exponential -- ultimately falters.
albert@spe&ar&c.xs4all.nl &=n http://home.hccnet.nl/a.w.m.van.der.horst

[toc] | [prev] | [standalone]

Page 3 of 3 — ← Prev page 1 2 [3]

Back to top | Article view | comp.lang.forth

csiph-web