Recent

Author Topic: Do we need a "number theory" compatible version of modulo?  (Read 5678 times)

uart

  • Jr. Member
  • **
  • Posts: 58
Re: Do we need a "number theory" compatible version of modulo?
« Reply #30 on: February 22, 2020, 03:38:13 am »
Doesn't {$modeswitch ISOMOD} do what you want?

Thanks FPK. I wasn't aware of that compiler directive, but you are correct it does force it to do a "number theory compatible" version of mod, albeit for only positive values of the second argument (and a runtime error for negative values of the second argument).

Actually that answers another thing that I was wondering. While researching this earlier I noticed a few people were saying that ISO Pascal's DIV and MOD were broken, with DIV not even being self consistent with MOD.  As in: N <> (N div D) + (N mod D)

I knew that this was not the case with any of the versions of Pascal I've used (mainly Turbo Pascal, Delphi and Free Pascal), with DIV and MOD always working correctly together.  But it appears that in the original ISO Pascal specs this was not the case. They had DIV the same as it currently is, but then they had a number theory compatible MOD that didn't properly mesh with DIV.

So it seems that they messed this up initially, and probably should have had a separate REM (for remainder) operator to do what the current version of MOD does, and kept the original MOD operator as the number theory compatible definition.

Still at this stage, I think I'd rather inline my own version of number theory modulo than to risk breaking other code by redefining the meaning of the existing mod with that directive. Still, thanks for pointing it out to me, it's historically very interesting. :)
« Last Edit: February 22, 2020, 04:33:16 am by uart »

munair

  • Hero Member
  • *****
  • Posts: 798
  • compiler developer @SharpBASIC
    • SharpBASIC
Re: Do we need a "number theory" compatible version of modulo?
« Reply #31 on: February 22, 2020, 09:37:37 am »
What is addressed here I think is the difference between a modulo operation and a remainder operation:
Code: Pascal  [Select][+][-]
  1. function remx(const a, b: integer): integer;
  2. // remainder
  3. begin
  4.   result := a - b * trunc(a / b);
  5. end;
  6.  
  7. function modx(const a, b: integer): integer;
  8. // modulo
  9. begin
  10.   result := a - b * floor(a / b);
  11. end;

If both a and b are positive then modulo and remainder give the same result. If a and b have different signs then the result is different. Here modx(-8, 12) returns 4, whereas remx(-8, 12) returns -8.
keep it simple

Thaddy

  • Hero Member
  • *****
  • Posts: 14204
  • Probably until I exterminate Putin.
Re: Do we need a "number theory" compatible version of modulo?
« Reply #32 on: February 22, 2020, 10:06:15 am »
Those involve float operations and will slow down even further. modulo operations are quite expensive. (Also note I introduced a fmod  like mod operator already in 3.2.0 I have to look if that satisfies the rules suggested too. It is in math )
Specialize a type, not a var.

munair

  • Hero Member
  • *****
  • Posts: 798
  • compiler developer @SharpBASIC
    • SharpBASIC
Re: Do we need a "number theory" compatible version of modulo?
« Reply #33 on: February 22, 2020, 11:15:33 am »
Those involve float operations and will slow down even further. modulo operations are quite expensive. (Also note I introduced a fmod  like mod operator already in 3.2.0 I have to look if that satisfies the rules suggested too. It is in math )
The purpose of my example is to demonstrate the difference from a mathematical point of view in the clearest manner (trunc vs floor). It is not meant to provide the fastest solution.
keep it simple

MarkMLl

  • Hero Member
  • *****
  • Posts: 6676
Re: Do we need a "number theory" compatible version of modulo?
« Reply #34 on: April 10, 2020, 10:00:50 pm »
Doesn't {$modeswitch ISOMOD} do what you want?

What version of FPC implements this?

MarkMLl
MT+86 & Turbo Pascal v1 on CCP/M-86, multitasking with LAN & graphics in 128Kb.
Pet hate: people who boast about the size and sophistication of their computer.
GitHub repositories: https://github.com/MarkMLl?tab=repositories

PascalDragon

  • Hero Member
  • *****
  • Posts: 5446
  • Compiler Developer
Re: Do we need a "number theory" compatible version of modulo?
« Reply #35 on: April 11, 2020, 02:23:47 pm »
Doesn't {$modeswitch ISOMOD} do what you want?

What version of FPC implements this?

3.2 and newer.

MarkMLl

  • Hero Member
  • *****
  • Posts: 6676
Re: Do we need a "number theory" compatible version of modulo?
« Reply #36 on: April 11, 2020, 04:13:12 pm »
Doesn't {$modeswitch ISOMOD} do what you want?

What version of FPC implements this?

3.2 and newer.

Thanks for that, I was using 3.0.4 and ended up overloading the >< operator so that it behaved the same way as was expected by a Python example I was transcribing... which is probably the first time I've been polite about Python.

MarkMLl
MT+86 & Turbo Pascal v1 on CCP/M-86, multitasking with LAN & graphics in 128Kb.
Pet hate: people who boast about the size and sophistication of their computer.
GitHub repositories: https://github.com/MarkMLl?tab=repositories

MarkMLl

  • Hero Member
  • *****
  • Posts: 6676
Re: Do we need a "number theory" compatible version of modulo?
« Reply #37 on: January 05, 2021, 10:50:11 pm »
I'm cross-posting this from a more recent discussion so that if anybody stumbles on this thread via Google they can see this contribution as a putative conclusion.

Quote
Unfortunately, Pascal's mod does not satisfy the above property.
For example: 16 mod 12 = 4
however: (16 - 3*12) mod 12 = -8
... (should be)
(16 + abs(-3 *12)) mod 12 = 4

I've just run this fragment of ALGOL through a B5500 emulator:


  WRITE(OUTPUT, <"16 MOD 12: ", I8>, 16 MOD 12);
  WRITE(OUTPUT, <"(16 - 3*12) MOD 12: ", I8>, (16 - 3*12) MOD 12);


The results that appeared on the output cards were


16 MOD 12:        4
(16 - 3 | 12) MOD 12:       -8


So since the machine on which Wirth did his PhD didn't have a divide instruction, it's reasonable to assume that he picked up his "bad habits" working on the B5500 at Stanford. The Burroughs ALGOL manual states that

Y MOD Z = Y - (Z * (SIGN (Y/Z) * ENTIER (ABS (Y/Z))))

but I haven't attempted to reconcile that with the published ALGOL-60 specification or any other variant of reality.

MarkMLl
MT+86 & Turbo Pascal v1 on CCP/M-86, multitasking with LAN & graphics in 128Kb.
Pet hate: people who boast about the size and sophistication of their computer.
GitHub repositories: https://github.com/MarkMLl?tab=repositories

Warfley

  • Hero Member
  • *****
  • Posts: 1499
Re: Do we need a "number theory" compatible version of modulo?
« Reply #38 on: January 06, 2021, 04:17:28 pm »
After the discussion in the other thread, I did a little bit of research with regards to other languages and how they handle this and their rationale.

So it seems that there are two competing definitions of mod. Let's consider x = a mod m.
The number theoretic model says that the mod operation should return the congruence class as represented by the smalles positive number. I.e. x is element of [0..m-1] such that there is a k element Z such that a = k*m + x. This is how it is employed by for example Python.
The other definition of mod is the remainder of the definition, which is basically defined together with the integer divide operation. Here the definition of mod is x, k element N such that a = k*m + x where k is a div m. This is employed this way in languages like C++. The rationale behind this is simple, div and mod should be complementary implementations, i.e. if you have x = a mod m and y = a div m, you can reconstruct a by just calculating y*m+a.

Both have their use cases. The GMP for example implements both, mpz_tdiv_qr(q, r, n, d) stands for trunk div quotient and remainder and returns a quotient and remainder such that q rounds to 0 and q*d+r = n, while mpz_mod(r, n, d) returns an r such that r = n mod d and r is in [0..d-1].

So long story short, the default implementation used by the FPC is basically what is commonly referred to as the remainder and is complementary to the integer division such that (a div d)*d + (a mod d) = a, and is also used this way in for example C and C++, while with {$ModeSwitch isomod} the mod operation does not compute the remainder, but the congruence class as commonly used in discrete maths/number theory
« Last Edit: January 06, 2021, 04:23:48 pm by Warfley »

Zoran

  • Hero Member
  • *****
  • Posts: 1829
    • http://wiki.lazarus.freepascal.org/User:Zoran
Re: Do we need a "number theory" compatible version of modulo?
« Reply #39 on: January 06, 2021, 04:34:37 pm »
It seems that the "other thread" MarkMLI mentioned (but forgot to link to it) is this one: https://forum.lazarus.freepascal.org/index.php/topic,52772.msg389763.html#msg389763.


MarkMLl

  • Hero Member
  • *****
  • Posts: 6676
Re: Do we need a "number theory" compatible version of modulo?
« Reply #40 on: January 06, 2021, 05:38:39 pm »
It seems that the "other thread" MarkMLI mentioned (but forgot to link to it) is this one: https://forum.lazarus.freepascal.org/index.php/topic,52772.msg389763.html#msg389763.

"The other thread" wasn't mentioned by me, I only said "a more recent discussion" and intentionally didn't link it since modulo behaviour was only tenuously related to somebody else's question and I didn't want to encourage further discussion there.

I notice an interesting chart at https://en.wikipedia.org/wiki/Modulo_operation#In_programming_languages which among other things shows the difference between "Object Pascal" and "Pascal (ISO-7185 and -10206)", hence explains Florian's mention of the compiler mode.

MarkMLl
MT+86 & Turbo Pascal v1 on CCP/M-86, multitasking with LAN & graphics in 128Kb.
Pet hate: people who boast about the size and sophistication of their computer.
GitHub repositories: https://github.com/MarkMLl?tab=repositories

 

TinyPortal © 2005-2018