[Bug-apl] Modulo or residue function is not generating consistent complete residue systems for some arguments

[Frederick Pitts]

Jürgen,

With gnu apl (svn 961 on Fedora 25, Intel(R) Core(TM) i7-6700
CPU), the residue function (∣) yields the following:

      5J3 ∣ 14J5
1J4
      5J3 | 1J4
¯4J1
      5J3 | ¯4J1
¯4J1
The above result means that two elements in the complete residue system
(CSR) for mod 5J3 are equal, i.e. 1J4 = ¯4J1 mod 5J3, which is not
allowed. None of the elements of a CSR can be equal modulo the CSR's
basis.

Regards,

Fred

[Jay Foad]

I hadn't heard of "complete residue systems" before. Perhaps another way of
saying the same thing is: f←{5J3|⍵} should be idempotent, so (f ⍵)≡f f ⍵
for any ⍵ ... ?

Jay.

JÃŒrgen,
With gnu apl (svn 961 on Fedora 25, Intel(R) Core(TM) i7-6700
5J3 ∣ 14J5
1J4
5J3 | 1J4
¯4J1
5J3 | ¯4J1
¯4J1
The above result means that two elements in the complete residue system
(CSR) for mod 5J3 are equal, i.e. 1J4 = ¯4J1 mod 5J3, which is not
allowed. None of the elements of a CSR can be equal modulo the CSR's
basis.
Regards,
Fred

[Jay Foad]

With the demo version of APL2 I get:

5J3 ∣ 14J5
¯4J1
5J3 | 1J4
¯4J1
5J3 | ¯4J1
¯4J1

Jay.

JÃŒrgen,
With gnu apl (svn 961 on Fedora 25, Intel(R) Core(TM) i7-6700
5J3 ∣ 14J5
1J4
5J3 | 1J4
¯4J1
5J3 | ¯4J1
¯4J1
The above result means that two elements in the complete residue system
(CSR) for mod 5J3 are equal, i.e. 1J4 = ¯4J1 mod 5J3, which is not
allowed. None of the elements of a CSR can be equal modulo the CSR's
basis.
Regards,
Fred

[Elias Mårtenson]

Wolfram Alpha tells me it should be 5J3:

https://www.wolframalpha.com/input/?i=(5%2B3i)+mod+(14%2B5i)

Regards,
Elias

5J3 ∣ 14J5
¯4J1
5J3 | 1J4
¯4J1
5J3 | ¯4J1
¯4J1
Jay.

JÃŒrgen,
With gnu apl (svn 961 on Fedora 25, Intel(R) Core(TM) i7-6700
5J3 ∣ 14J5
1J4
5J3 | 1J4
¯4J1
5J3 | ¯4J1
¯4J1
The above result means that two elements in the complete residue system
(CSR) for mod 5J3 are equal, i.e. 1J4 = ¯4J1 mod 5J3, which is not
allowed. None of the elements of a CSR can be equal modulo the CSR's
basis.
Regards,
Fred

[Jay Foad]

You need to swap the arguments; "⍺|⍵" in APL is "⍵ mod ⍺" or "⍵ rem ⍺" or
"⍵ % ⍺" in most other systems.

Post by Elias MÃ¥rtenson
https://www.wolframalpha.com/input/?i=(5%2B3i)+mod+(14%2B5i)
Regards,
Elias

5J3 ∣ 14J5
¯4J1
5J3 | 1J4
¯4J1
5J3 | ¯4J1
¯4J1
Jay.

JÃŒrgen,
With gnu apl (svn 961 on Fedora 25, Intel(R) Core(TM) i7-6700
5J3 ∣ 14J5
1J4
5J3 | 1J4
¯4J1
5J3 | ¯4J1
¯4J1
The above result means that two elements in the complete residue system
(CSR) for mod 5J3 are equal, i.e. 1J4 = ¯4J1 mod 5J3, which is not
allowed. None of the elements of a CSR can be equal modulo the CSR's
basis.
Regards,
Fred

[Elias Mårtenson]

You are right of course. I forgot about that part.

Speaking of which, I have often wished that - and ÷ behaved the same. I'm
really glad that ⍚ exists.

Post by Jay Foad
You need to swap the arguments; "⍺|⍵" in APL is "⍵ mod ⍺" or "⍵ rem ⍺" or
"⍵ % ⍺" in most other systems.

Post by Elias MÃ¥rtenson
https://www.wolframalpha.com/input/?i=(5%2B3i)+mod+(14%2B5i)
Regards,
Elias

5J3 ∣ 14J5
¯4J1
5J3 | 1J4
¯4J1
5J3 | ¯4J1
¯4J1
Jay.

JÃŒrgen,
With gnu apl (svn 961 on Fedora 25, Intel(R) Core(TM) i7-6700
5J3 ∣ 14J5
1J4
5J3 | 1J4
¯4J1
5J3 | ¯4J1
¯4J1
The above result means that two elements in the complete residue system
(CSR) for mod 5J3 are equal, i.e. 1J4 = ¯4J1 mod 5J3, which is not
allowed. None of the elements of a CSR can be equal modulo the CSR's
basis.
Regards,
Fred

[Xiao-Yong Jin]

I guess APL standard is really bad in this regard.
Dyalog APL gives the following:

Dyalog APL/S-64 Version 15.0.27700
Unicode Edition
Tue Jun 20 10:46:08 2017
5J3|14J5
1J4
5J3|1J4
¯4J1
5J3|¯4J1
¯4J1

which coincides with the previous gnu apl result.

Post by Frederick Pitts
5J3 ∣ 14J5
¯4J1
5J3 | 1J4
¯4J1
5J3 | ¯4J1
¯4J1
Jay.
Jürgen,
With gnu apl (svn 961 on Fedora 25, Intel(R) Core(TM) i7-6700
5J3 ∣ 14J5
1J4
5J3 | 1J4
¯4J1
5J3 | ¯4J1
¯4J1
The above result means that two elements in the complete residue system
(CSR) for mod 5J3 are equal, i.e. 1J4 = ¯4J1 mod 5J3, which is not
allowed. None of the elements of a CSR can be equal modulo the CSR's
basis.
Regards,
Fred

[Juergen Sauermann]

<html>
<head>
<meta content="text/html; charset=utf-8" http-equiv="Content-Type">
</head>
<body bgcolor="#FFFFFF" text="#000000">
<font face="Helvetica, Arial, sans-serif">Hi Frederick,<br>
<br>
the algorithm for <b>A ∣ B</b> used in GNU APL is this:<br>
<br>
<font face="Courier New, Courier, monospace"><b>- compute the
quotient Q</b><b>←</b><b>B÷A,</b><b><br>
</b><b>- "round down" Q to the next (complex) integer</b><b> Q1,</b><b><br>
</b><b>- return B - Q1×A</b></font><b><br>
</b><br>
Now the problem seems to be what is meant by "round down". There
are two candidates:<br>
<br>
<font face="Courier New, Courier, monospace">  <b>Q1 ← ⌊
Q                                          i.e. use APL floor</b><b>
to round down Q</b><b><br>
</b><b>  Q1 ← Complex( floor(Q.real(), </b></font></font><font
face="Helvetica, Arial, sans-serif"><font face="Courier New,
Courier, monospace"><b>floor(Q.</b><b>imag</b><b>()) )   </b><b>i,e,
use C/C++ floor() to round down Q.</b><b><br>
</b></font><br>
In your  <b>5J3 ∣ 14J5</b> example, the quotient is <b>2.5J¯0.5</b>,
which gives different results for the APL floor <b>⌊</b> and the
C/C++ floor().<br>
<br>
The APL floor <font face="Courier New, Courier, monospace"><b>⌊</b></font></font><font
face="Helvetica, Arial, sans-serif"><font face="Helvetica, Arial,
sans-serif"><font face="Courier New, Courier, monospace"><b>2.5J¯0.5</b></font>
is </font><font face="Courier New, Courier, monospace"><b>3J¯1</b></font>
(a somewhat dubious invention in the ISO standard on page 19,
which I used up to<br>
including <b>SVN 963</b>), while the C/C++ floor() is</font><font
face="Helvetica, Arial, sans-serif"><font face="Helvetica, Arial,
sans-serif"><font face="Courier New, Courier, monospace"><b>
2J¯1</b></font></font>. The difference between the APL floor
and the C/C++ floor is <b>1.0 </b>which,<br>
multiplied by the divisor, explains the differences that we see.<br>
<br>
As of <b>SVN 964</b> I have changed the residue function (<b>∣</b>)
to use the C/C++ floor instead of the APL floor. The APL floor and<br>
Ceiling functions (<b>⌊</b> and <b>⌈</b>) are still using the
apparently broken definition in the ISO standard.<br>
<br>
I hope this works better for you. At least I am getting this in <b>SVN
964</b>:<br>
<br>
<font face="Courier New, Courier, monospace"><b>      5J3 | 14J5</b><b><br>
</b><b>1J4</b><b><br>
</b><b>      5J3 | 1J4</b><b><br>
</b><b>1J4</b></font><b><br>
</b><br>
whereas <b>SVN 963</b> was giving:<br>
<br>
<font face="Courier New, Courier, monospace"><b>      5J3 | 14J5</b><b><br>
</b><b>¯4J1</b><b><br>
</b><b>      5J3 | 1J4</b><b><br>
</b><b>¯4J1</b></font><br>
<br>
<br>
Best Regards,<br>
/// Jürgen<br>
<br>
</font><br>
<br>
<div class="moz-cite-prefix">On 06/19/2017 07:03 PM, Frederick Pitts
wrote:<br>
</div>
<blockquote cite="mid:***@comcast.net"
type="cite">
<pre wrap="">Jürgen,

With gnu apl (svn 961 on Fedora 25, Intel(R) Core(TM) i7-6700
CPU), the residue function (∣) yields the following:

      5J3 ∣ 14J5
1J4
      5J3 | 1J4
¯4J1
      5J3 | ¯4J1
¯4J1
The above result means that two elements in the complete residue system
(CSR) for mod 5J3 are equal, i.e. 1J4 = ¯4J1 mod 5J3, which is not
allowed. None of the elements of a CSR can be equal modulo the CSR's
basis.

Regards,

Fred

</pre>
</blockquote>
<br>
</body>
</html>

[Frederick Pitts]

Hello JÃŒrgen,
SVN 964 moved us in the right direction but not completely out
of thewoods.  SVN 964 still exhibits errors.  For instance
      2J6 | 5J5¯1J7      2J6 | ¯1J7¯3J1      2J6 | ¯3J1¯3J1
I found this and previous residue function errors using the
attached APLcode files.  The files with base name ending in '0' use the
builtin residuefunction.  Those with base name ending in '1' use a
residue function implementedin APL.  The files with base name beginning
with 'CRSOTST' test if the order ofthe complete residue system (CRS)
equals the norm of the modulo basis.  Thattest fails for several modulo
bases, 2J6 being one of them, using the builtinresidue function. No
errors are detected with the APL implementation.  The other filescan be
used to plot the CRS for a given modulo basis where 'a' and 'b' in'a +
b * i' are limited to +15 to -15 range.  A full screen terminal window
isneeded to see the plot.
My APL implementation of the residue function is very close to
what youdescribed in your previous email.  Maybe comparing the two
implementations willgive insight into why the builtin residue function
fails for some modulo bases.
I make no assertion that my implementation is correct in
allaspects.
Regards,
Fred

    Hi Frederick,
      
      
      - compute the
          quotient Q←B÷A,
        - "round down" Q to the next (complex) integer Q1,
        - return B - Q1×A
      
      Now the problem seems to be what is meant by "round down".
There
      
        Q1 ← ⌊
          Q                                          i.e. use APL
floor
          to round down Q
          Q1 ← Complex( floor(Q.real(), floor(Q.imag()) )   i,e,
          use C/C++ floor() to round down Q.
        
      In your  5J3 ∣ 14J5 example, the quotient is 2.5J¯0.5,
      which gives different results for the APL floor ⌊ and the
      C/C++ floor().
      
      The APL floor ⌊2.5J¯0.5
        is 3J¯1
      (a somewhat dubious invention in the ISO standard on page 19,
      which I used up to
      including SVN 963), while the C/C++ floor() is
            2J¯1. The difference between the APL floor
      and the C/C++ floor is 1.0 which,
      multiplied by the divisor, explains the differences that we
see.
      
      As of SVN 964 I have changed the residue function (∣)
      to use the C/C++ floor instead of the APL floor. The APL floor
and
      Ceiling functions (⌊ and ⌈) are still using the
      apparently broken definition in the ISO standard.
      
      I hope this works better for you. At least I am getting this in
SVN
      
            5J3 | 14J5
        1J4
              5J3 | 1J4
        1J4
      
      
            5J3 | 14J5
        ¯4J1
              5J3 | 1J4
        ¯4J1
      
      
      Best Regards,
      /// JÌrgen
      
    
    
    On 06/19/2017 07:03 PM, Frederick Pitts
    
    

      JÌrgen,
With gnu apl (svn 961 on Fedora 25, Intel(R) Core(TM) i7-6700
      5J3 ∣ 14J5
1J4
      5J3 | 1J4
¯4J1
      5J3 | ¯4J1
¯4J1
The above result means that two elements in the complete residue system
(CSR) for mod 5J3 are equal, i.e. 1J4 = ¯4J1 mod 5J3, which is not
allowed.  None of the elements of a CSR can be equal modulo the
CSR's
basis.
Regards,
Fred
    

    
  

[Frederick Pitts]

JÃŒrgen,
This message is being resent because last minute changes I made
to CRS0.apl and CRS1.apl do not output thedata I intended.  This
message has corrected versions of those files attached.  Please discard
the old CRS0.apl and CRS1.apl files.  The first line of output is the
modulo basis, the second line is the calculated complete residue system
values and the third line is the number of residues in the CRS on the
previous line.
CRSOTST0.apl and CRSOTST1.apl are unchanged.
Also please find attached MOD_TEST.apl which compares the
residues calculated by MODJ and the builtin residue function and
reports discrepancies.  The first column of output is the modulo basis,
the second column the right argument to the functions, the third column
the MODJ result and the fourth column is the builtin residue function
result.
Regards
Fred
Hello JÃŒrgen,
SVN 964 moved us in the right direction but not completely out
of thewoods.  SVN 964 still exhibits errors.  For instance
      2J6 | 5J5¯1J7      2J6 | ¯1J7¯3J1      2J6 | ¯3J1¯3J1
I found this and previous residue function errors using the
attached APLcode files.  The files with base name ending in '0' use the
builtin residuefunction.  Those with base name ending in '1' use a
residue function implementedin APL.  The files with base name beginning
with 'CRSOTST' test if the order ofthe complete residue system (CRS)
equals the norm of the modulo basis.  Thattest fails for several modulo
bases, 2J6 being one of them, using the builtinresidue function. No
errors are detected with the APL implementation.  The other filescan be
used to plot the CRS for a given modulo basis where 'a' and 'b' in'a +
b * i' are limited to +15 to -15 range.  A full screen terminal window
isneeded to see the plot.
My APL implementation of the residue function is very close to
what youdescribed in your previous email.  Maybe comparing the two
implementations willgive insight into why the builtin residue function
fails for some modulo bases.
I make no assertion that my implementation is correct in
allaspects.
Regards,
Fred

    Hi Frederick,
      
      
      - compute the
          quotient Q←B÷A,
        - "round down" Q to the next (complex) integer Q1,
        - return B - Q1×A
      
      Now the problem seems to be what is meant by "round down".
There
      
        Q1 ← ⌊
          Q                                          i.e. use APL
floor
          to round down Q
          Q1 ← Complex( floor(Q.real(), floor(Q.imag()) )   i,e,
          use C/C++ floor() to round down Q.
        
      In your  5J3 ∣ 14J5 example, the quotient is 2.5J¯0.5,
      which gives different results for the APL floor ⌊ and the
      C/C++ floor().
      
      The APL floor ⌊2.5J¯0.5
        is 3J¯1
      (a somewhat dubious invention in the ISO standard on page 19,
      which I used up to
      including SVN 963), while the C/C++ floor() is
            2J¯1. The difference between the APL floor
      and the C/C++ floor is 1.0 which,
      multiplied by the divisor, explains the differences that we
see.
      
      As of SVN 964 I have changed the residue function (∣)
      to use the C/C++ floor instead of the APL floor. The APL floor
and
      Ceiling functions (⌊ and ⌈) are still using the
      apparently broken definition in the ISO standard.
      
      I hope this works better for you. At least I am getting this in
SVN
      
            5J3 | 14J5
        1J4
              5J3 | 1J4
        1J4
      
      
            5J3 | 14J5
        ¯4J1
              5J3 | 1J4
        ¯4J1
      
      
      Best Regards,
      /// JÌrgen
      
    
    
    On 06/19/2017 07:03 PM, Frederick Pitts
    
    

      JÌrgen,
With gnu apl (svn 961 on Fedora 25, Intel(R) Core(TM) i7-6700
      5J3 ∣ 14J5
1J4
      5J3 | 1J4
¯4J1
      5J3 | ¯4J1
¯4J1
The above result means that two elements in the complete residue system
(CSR) for mod 5J3 are equal, i.e. 1J4 = ¯4J1 mod 5J3, which is not
allowed.  None of the elements of a CSR can be equal modulo the
CSR's
basis.
Regards,
Fred
    

    
  

[Juergen Sauermann]

<html>
<head>
<meta content="text/html; charset=utf-8" http-equiv="Content-Type">
</head>
<body bgcolor="#FFFFFF" text="#000000">
<font face="Helvetica, Arial, sans-serif">Hi Fred,<br>
<br>
I have a question about the <b>MOD_test.apl</b> that you kindly
provided.<br>
<br>
In function <b>DIVJ</b> on line 57 ff it says:<br>
<br>
<font face="Courier New, Courier, monospace"><b>z ← q , a - b × q
← CMPLX ⌊ ( 9 11 ) ○ a ÷ b</b></font><br>
<br>
so the quotient is rounded down towards minus infinity.<br>
<br>
I wonder if that should be something like<br>
<br>
<font face="Courier New, Courier, monospace"><b>z ← q , (× q1) × a
- b × q ← CMPLX ⌊ ∣ 9 11 ○ q1 ← a ÷ b</b></font><br>
<br>
so that the quotient is rounded towards 0? Interestingly IBM and
ISO<br>
give different definitions for the residue in terms of APL:<br>
<br>
IBM (language reference, page 227):<br>
<font face="Courier New, Courier, monospace"><b>Z←L∣R</b><b><br>
</b><b>Z is R</b><b>-</b><b>L×⌊
R÷L+L=0</b></font><br>
<br>
ISO (chapter 7.2.9 Residue): <br>
<font face="Courier New, Courier, monospace"><b>R←Q∣P</b><b><br>
</b><b>R←P-(×P)×|Q×⌊|P÷Q<br>
and return R if (×R)=×Q, or R+Q<br>
otherwise.<br>
</b></font> </font><br>
That suggest that IBM rounds the quotient down towards minus
infinity while ISO rounds<br>
 towards 0.<br>
<br>
My naive view on remainder is that the nearest integer quotient
shall be smaller in<br>
magnitude and not smaller in value. Regarding your proposal (which
is different from<br>
both IBM and ISO) my concern is that may lead to different results
for <b>modulo N</b> and<br>
<b>modulo</b> <b>N×1J0</b><br>
<br>
Best Regards,<br>
Jürgen Sauermann<br>
<br>
<br>
<div class="moz-cite-prefix">On 06/21/2017 03:08 AM, Frederick Pitts
wrote:<br>
</div>
<blockquote cite="mid:***@comcast.net"
type="cite">
<meta content="text/html; charset=utf-8" http-equiv="Content-Type">
<div><span style="white-space: normal;">Jürgen,</span></div>
<div><span style="white-space: normal;"><br>
</span></div>
<div><span style="white-space: normal;"> This message is being
resent because last minute changes I made to CRS0.apl and
CRS1.apl do not output the</span></div>
<div><span style="white-space: normal;">data I intended.  This
message has corrected versions of those files attached.
 Please discard the old CRS0.apl and CRS1.apl files.  The
first line of output is the modulo basis, </span><span
style="white-space: normal;">the second line is the calculated
complete residue system values and the third line is the
number of residues in the CRS </span><span style="white-space:
normal;">on the previous line.</span></div>
<div><span style="white-space: normal;"><br>
</span></div>
<div><span style="white-space: normal;"> CRSOTST0.apl and
CRSOTST1.apl are unchanged.</span></div>
<div><span style="white-space: normal;"><br>
</span></div>
<div><span style="white-space: normal;"> Also please find attached
MOD_TEST.apl which compares the residues calculated by MODJ
and the builtin residue function and reports discrepancies.
 The first column of output is the modulo basis, the second
column the right argument to the functions, the third column
the MODJ result and the fourth column is the builtin residue
function result.</span></div>
<div><span style="white-space: normal;"><br>
</span></div>
<div><span style="white-space: normal;">Regards</span></div>
<div><span style="white-space: normal;"><br>
</span></div>
<div><span style="white-space: normal;">Fred</span></div>
<div><br>
</div>
<div>Hello Jürgen,</div>
<pre> SVN 964 moved us in the right direction but not completely out of the</pre>
<pre>woods. SVN 964 still exhibits errors. For instance</pre>
<pre> 2J6 | 5J5</pre>
<pre>¯1J7</pre>
<pre> 2J6 | ¯1J7</pre>
<pre>¯3J1</pre>
<pre> 2J6 | ¯3J1</pre>
<pre>¯3J1</pre>
<pre> I found this and previous residue function errors using the attached APL</pre>
<pre>code files. The files with base name ending in '0' use the builtin residue</pre>
<pre>function. Those with base name ending in '1' use a residue function implemented</pre>
<pre>in APL. The files with base name beginning with 'CRSOTST' test if the order of</pre>
<pre>the complete residue system (CRS) equals the norm of the modulo basis. That</pre>
<pre>test fails for several modulo bases, 2J6 being one of them, using the builtin</pre>
<pre>residue function. No errors are detected with the APL implementation. The other files</pre>
<pre>can be used to plot the CRS for a given modulo basis where 'a' and 'b' in</pre>
<pre>'a + b * i' are limited to +15 to -15 range. A full screen terminal window is</pre>
<pre>needed to see the plot.</pre>
<pre> My APL implementation of the residue function is very close to what you</pre>
<pre>described in your previous email. Maybe comparing the two implementations will</pre>
<pre>give insight into why the builtin residue function fails for some modulo bases.</pre>
<pre> I make no assertion that my implementation is correct in all</pre>
<pre>aspects.</pre>
<pre>Regards,</pre>
<pre>Fred</pre>
<div>On Tue, 2017-06-20 at 14:14 +0200, Juergen Sauermann wrote:</div>
<blockquote type="cite"> <font face="Helvetica, Arial,
sans-serif">Hi Frederick,<br>
<br>
the algorithm for <b>A ∣ B</b> used in GNU APL is this:<br>
<br>
<font face="Courier New, Courier, monospace"><b>- compute the
quotient Q</b><b>←</b><b>B÷A,</b><b><br>
</b><b>- "round down" Q to the next (complex) integer</b><b>
Q1,</b><b><br>
</b><b>- return B - Q1×A</b></font><b><br>
</b><br>
Now the problem seems to be what is meant by "round down".
There are two candidates:<br>
<br>
<font face="Courier New, Courier, monospace">  <b>Q1 ← ⌊
Q                                          i.e. use APL
floor</b><b> to round down Q</b><b><br>
</b><b>  Q1 ← Complex( floor(Q.real(), </b></font></font><font
face="Helvetica, Arial, sans-serif"><font face="Courier New,
Courier, monospace"><b>floor(Q.</b><b>imag</b><b>()) )   </b><b>i,e,
use C/C++ floor() to round down Q.</b><b><br>
</b></font><br>
In your  <b>5J3 ∣ 14J5</b> example, the quotient is <b>2.5J¯0.5</b>,
which gives different results for the APL floor <b>⌊</b> and
the C/C++ floor().<br>
<br>
The APL floor <font face="Courier New, Courier, monospace"><b>⌊</b></font></font><font
face="Helvetica, Arial, sans-serif"><font face="Helvetica,
Arial, sans-serif"><font face="Courier New, Courier,
monospace"><b>2.5J¯0.5</b></font> is </font><font
face="Courier New, Courier, monospace"><b>3J¯1</b></font> (a
somewhat dubious invention in the ISO standard on page 19,
which I used up to<br>
including <b>SVN 963</b>), while the C/C++ floor() is</font><font
face="Helvetica, Arial, sans-serif"><font face="Helvetica,
Arial, sans-serif"><font face="Courier New, Courier,
monospace"><b> 2J¯1</b></font></font>. The difference
between the APL floor and the C/C++ floor is <b>1.0 </b>which,<br>
multiplied by the divisor, explains the differences that we
see.<br>
<br>
As of <b>SVN 964</b> I have changed the residue function (<b>∣</b>)
to use the C/C++ floor instead of the APL floor. The APL floor
and<br>
Ceiling functions (<b>⌊</b> and <b>⌈</b>) are still using the
apparently broken definition in the ISO standard.<br>
<br>
I hope this works better for you. At least I am getting this
in <b>SVN 964</b>:<br>
<br>
<font face="Courier New, Courier, monospace"><b>      5J3 |
14J5</b><b><br>
</b><b>1J4</b><b><br>
</b><b>      5J3 | 1J4</b><b><br>
</b><b>1J4</b></font><b><br>
</b><br>
whereas <b>SVN 963</b> was giving:<br>
<br>
<font face="Courier New, Courier, monospace"><b>      5J3 |
14J5</b><b><br>
</b><b>¯4J1</b><b><br>
</b><b>      5J3 | 1J4</b><b><br>
</b><b>¯4J1</b></font><br>
<br>
<br>
Best Regards,<br>
/// Jürgen<br>
<br>
</font><br>
<br>
<div class="moz-cite-prefix">On 06/19/2017 07:03 PM, Frederick
Pitts wrote:<br>
</div>
<blockquote cite="mid:***@comcast.net"
type="cite">
<pre wrap="">Jürgen,

With gnu apl (svn 961 on Fedora 25, Intel(R) Core(TM) i7-6700
CPU), the residue function (∣) yields the following:

      5J3 ∣ 14J5
1J4
      5J3 | 1J4
¯4J1
      5J3 | ¯4J1
¯4J1
The above result means that two elements in the complete residue system
(CSR) for mod 5J3 are equal, i.e. 1J4 = ¯4J1 mod 5J3, which is not
allowed. None of the elements of a CSR can be equal modulo the CSR's
basis.

Regards,

Fred

</pre>
</blockquote>
<br>
</blockquote>
</blockquote>
<br>
</body>
</html>

[Frederick Pitts]

JÃŒrgen,
The proposed change to DIVJ does not work because 'q1' is a
complex number, so the '×' in '× q1' is the complex complement
function, not the sign function.  I tried the proposed change and every
test fails.
I will try to hack DIVJ to use a floor towards zero instead of
towards minus infinity for the real and imaginaryparts of the quotient
and see what happens.
Correct me if I am wrong, but my mind set is that the APL
residue function has to satisfy the following invariants:1) The order
of the complete residue system (residue count) for a given modulo 'n'
has to equal the norm of 'n'.2) And as Jay Foad so succinctly expressed
it, the residue function has to be idempotent with respect to its right
argument,     e.g.,  ( n | m ) = n | n | m .regardless of the
implementation of the residue function.
Later,
Fred 

    Hi Fred,
      
      I have a question about the MOD_test.apl that you kindly
      provided.
      
      
      z ← q , a - b × q
          ← CMPLX ⌊ ( 9 11 ) ○ a ÷ b
      
      so the quotient is rounded down towards minus infinity.
      
      I wonder if that should be something like
      
      z ← q , (× q1) × a
          - b × q ← CMPLX ⌊ ∣ 9 11 ○ q1 ← a ÷ b
      
      so that the quotient is rounded towards 0? Interestingly IBM
and
      ISO
      
      Z←L∣R
        Z is R-L×⌊
          R÷L+L=0
      
      ISO (chapter 7.2.9 Residue): 
      R←Q∣P
        R←P-(×P)×|Q×⌊|P÷Q
          and return R if (×R)=×Q, or R+Q
          otherwise.
         
    That suggest that IBM rounds the quotient down towards minus
    infinity while ISO rounds
     towards 0.
    
    My naive view on remainder is that the nearest integer quotient
    shall be smaller in
    magnitude and not smaller in value. Regarding your proposal
(which
    is different from
    both IBM and ISO) my concern is that may lead to different
results
    for modulo N and
    modulo N×1J0
    
    Best Regards,
    JÌrgen Sauermann
    
    
    On 06/21/2017 03:08 AM, Frederick Pitts
    
    

Post by Frederick Pitts
      
      JÌrgen,
      
        
       This message is being
          resent because last minute changes I made to CRS0.apl and
          CRS1.apl do not output the
      data I intended.  This
          message has corrected versions of those files attached.
           Please discard the old CRS0.apl and CRS1.apl files.  The
          first line of output is the modulo basis, the second line
is the calculated
          complete residue system values and the third line is the
          number of residues in the CRS on the previous line.
      
        
       CRSOTST0.apl and
          CRSOTST1.apl are unchanged.
      
        
       Also please find attached
          MOD_TEST.apl which compares the residues calculated by
MODJ
          and the builtin residue function and reports
discrepancies.
           The first column of output is the modulo basis, the
second
          column the right argument to the functions, the third
column
          the MODJ result and the fourth column is the builtin
residue
          function result.
      
        
      Regards
      
        
      Fred
      
      
      Hello JÌrgen,
       SVN 964 moved us in the right direction but not
completely out of the
      woods.  SVN 964 still exhibits errors.  For instance
            2J6 | 5J5
      ¯1J7
            2J6 | ¯1J7
      ¯3J1
            2J6 | ¯3J1
      ¯3J1
       I found this and previous residue function errors
using the attached APL
      code files.  The files with base name ending in '0' use the
builtin residue
      function.  Those with base name ending in '1' use a residue
function implemented
      in APL.  The files with base name beginning with 'CRSOTST'
test if the order of
      the complete residue system (CRS) equals the norm of the
modulo basis.  That
      test fails for several modulo bases, 2J6 being one of them,
using the builtin
      residue function. No errors are detected with the APL
implementation.  The other files
      can be used to plot the CRS for a given modulo basis where
'a' and 'b' in
      'a + b * i' are limited to +15 to -15 range.  A full screen
terminal window is
      needed to see the plot.
       My APL implementation of the residue function is very
close to what you
      described in your previous email.  Maybe comparing the two
implementations will
      give insight into why the builtin residue function fails for
some modulo bases.
       I make no assertion that my implementation is correct
in all
      aspects.
      Regards,
      Fred
      

 Hi Frederick,
          
          
          - compute the
              quotient Q←B÷A,
            - "round down" Q to the next (complex) integer
              Q1,
            - return B - Q1×A
          
          Now the problem seems to be what is meant by "round
down".
          
            Q1 ← ⌊
              Q                                          i.e. use
APL
              floor to round down Q
              Q1 ← Complex( floor(Q.real(), floor(Q.imag()) )  
i,e,
              use C/C++ floor() to round down Q.
            
          In your  5J3 ∣ 14J5 example, the quotient is 2.5J¯0.5,
          which gives different results for the APL floor ⌊ and
          the C/C++ floor().
          
          The APL floor ⌊2.5J¯0.5 is 3J¯1 (a
          somewhat dubious invention in the ISO standard on page
19,
          which I used up to
          including SVN 963), while the C/C++ floor() is 2J¯1.
The difference
          between the APL floor and the C/C++ floor is 1.0 which,
          multiplied by the divisor, explains the differences
that we
          see.
          
          As of SVN 964 I have changed the residue function (∣)
          to use the C/C++ floor instead of the APL floor. The
APL floor
          and
          Ceiling functions (⌊ and ⌈) are still using the
          apparently broken definition in the ISO standard.
          
          I hope this works better for you. At least I am getting
this
          
                5J3 |
              14J5
            1J4
                  5J3 | 1J4
            1J4
          
          
                5J3 |
              14J5
            ¯4J1
                  5J3 | 1J4
            ¯4J1
          
          
          Best Regards,
          /// JÌrgen
          
        
        
        On 06/19/2017 07:03 PM, Frederick
        
        

          JÌrgen,
With gnu apl (svn 961 on Fedora 25, Intel(R) Core(TM)
i7-6700
      5J3 ∣ 14J5
1J4
      5J3 | 1J4
¯4J1
      5J3 | ¯4J1
¯4J1
The above result means that two elements in the complete
residue system
(CSR) for mod 5J3 are equal, i.e. 1J4 = ¯4J1 mod 5J3, which is not
allowed.  None of the elements of a CSR can be equal modulo the
CSR's
basis.
Regards,
Fred
        

        
      

    

    
  

[Juergen Sauermann]

<html>
<head>
<meta content="text/html; charset=utf-8" http-equiv="Content-Type">
</head>
<body bgcolor="#FFFFFF" text="#000000">
<font face="Helvetica, Arial, sans-serif">Hi Fred at al.,<br>
<br>
I have made another attempt to fix the residue function, <b>SVN
965</b>.<br>
<br>
For complex <b>m∣b</b> It now rounds down the real() and imag()
parts of the quotient <b>q←b÷m</b> and returns <b>b-q</b>.<br>
Instead of always rounding towards 0 or -infinity, the rounding
direction is now (compared to the previous<br>
attempt) determined by the quadrant in which the modulus <b>m</b>
lies.<br>
</font><br>
There are still differences to the results displayed by <font
face="Helvetica, Arial, sans-serif"><b>MOD_test.apl</b>, but I
suppose they are<br>
caused by that program. For example, the first line of </font><font
face="Helvetica, Arial, sans-serif"><font face="Helvetica, Arial,
sans-serif"><b>MOD_test.apl</b>, says:<br>
<br>
</font><font face="Courier New, Courier, monospace"><b>  LA   
RA   MODJ   |</b><b><br>
</b><b>¯6J¯6 ¯6J¯5   0J¯11  0J1</b><br>
</font><br>
We have:<br>
<br>
<b>      (¯6J¯5 - 0J1) ÷ ¯6J¯6 </b><b><br>
</b><b>1</b><b><br>
</b><b>      (0J¯11 - 0J1) ÷ ¯6J¯6</b><b><br>
</b><b>1J1</b><br>
<br>
so both <b>0J¯11</b> and <b>0J1</b> are valid remainders modulo
<b>¯6J¯6</b>. However, the<br>
magnitude of </font><font face="Helvetica, Arial, sans-serif"><b>0J¯11</b>
(= <b>11</b>) is larger than the magnitude of the divisor </font><font
face="Helvetica, Arial, sans-serif"><b><font face="Helvetica,
Arial, sans-serif"><b>¯6J¯6</b></font></b><font
face="Helvetica, Arial, sans-serif"> (= around <b>8.4</b>).<br>
I suppose most people expect the remainder of a division to be
in some sense<br>
smaller than the divisor.<br>
<br>
Regarding Jay's idempotency requirement we now have:<br>
<br>
 <b><font face="Courier New, Courier, monospace">     f←{6J6|⍵}<br>
      f ¯3 ¯2 ¯3 ¯1 0 1 2 3<br>
3J6 4J6 3J6 5J6 0 ¯5J6 ¯4J6 ¯3J6<br>
      f f ¯3 ¯2 ¯3 ¯1 0 1 2 3<br>
3J6 4J6 3J6 5J6 0 ¯5J6 ¯4J6 ¯3J6</font></b><br>
<b><font face="Courier New, Courier, monospace"><br>
      f←{5J3|⍵}<br>
      f ¯3 ¯2 ¯3 ¯1 0 1 2 3<br>
2J3 3J3 2J3 4J3 0 ¯2J5 ¯1J5 0J5<br>
      f f ¯3 ¯2 ¯3 ¯1 0 1 2 3<br>
2J3 3J3 2J3 4J3 0 ¯2J5 ¯1J5 0J5<br>
</font></b><br>
so at least the first modulus seems to work as well. The result
is still different<br>
from APL2 as reported by Jay, but I can't tell why:<br>
<br>
IBM APL2:<br>
<br>
<font face="Courier New, Courier, monospace"><b>      5J3 ∣ 14J5
1J4 ¯4J1</b></font></font></font><br>
<font face="Helvetica, Arial, sans-serif"><font face="Helvetica,
Arial, sans-serif"><font face="Courier New, Courier, monospace"><b>¯4J1
</b></font></font></font><font face="Helvetica, Arial,
sans-serif"><font face="Helvetica, Arial, sans-serif"><font
face="Courier New, Courier, monospace"><b>¯4J1 </b></font></font></font><font
face="Helvetica, Arial, sans-serif"><font face="Helvetica, Arial,
sans-serif"><font face="Courier New, Courier, monospace"><b>¯4J1<br>
<br>
</b></font></font></font>GNU APL:<br>
<br>
<font face="Helvetica, Arial, sans-serif"><font face="Helvetica,
Arial, sans-serif"><font face="Helvetica, Arial, sans-serif"><font
face="Helvetica, Arial, sans-serif"><font face="Courier New,
Courier, monospace"><b>      5J3 ∣ 14J5 1J4 ¯4J1 </b><b><br>
</b><b>1J4 1J4 1J4</b></font><br>
<br>
</font></font>But both <b>1J4</b> and <b>¯4J1</b> are valid
remainders. Interestingly Jay's idempotency requirement seems to<br>
be fulfilled by both the GNU APL and by IBM APL2, so that that
requirement alone does not suffice<br>
to tell which result is correct.<br>
<br>
On the other hand this matter seems to be like discussing if the
square root of 4 is 2 or -2 with<br>
both answers being correct.<br>
<br>
Best Regards,<br>
Jürgen Sauermann<br>
<br>
<br>
</font><b><font face="Helvetica, Arial, sans-serif"><br>
</font></b><b></b> </font>
<div class="moz-cite-prefix">On 06/21/2017 10:25 PM, Frederick Pitts
wrote:<br>
</div>
<blockquote cite="mid:***@comcast.net"
type="cite">
<meta content="text/html; charset=utf-8" http-equiv="Content-Type">
<div>Jürgen,</div>
<div><br>
</div>
<div> The proposed change to DIVJ does not work because 'q1' is a
complex number, so the '×' in '× q1' is the complex complement
function, not the sign function. I tried the proposed change and
every test fails.</div>
<div><br>
</div>
<div> I will try to hack DIVJ to use a floor towards zero instead
of towards minus infinity for the real and imaginary</div>
<div>parts of the quotient and see what happens.</div>
<div><br>
</div>
<div> Correct me if I am wrong, but my mind set is that the APL
residue function has to satisfy the following invariants:</div>
<div>1) The order of the complete residue system (residue count)
for a given modulo 'n' has to equal the norm of 'n'.</div>
<div>2) And as Jay Foad so succinctly expressed it, the residue
function has to be idempotent with respect to its right
argument,</div>
<div> e.g., ( n | m ) = n | n | m .</div>
<div>regardless of the implementation of the residue function.</div>
<div><br>
</div>
<div>Later,</div>
<div><br>
</div>
<div>Fred </div>
<div><br>
</div>
<div><br>
</div>
<div><br>
</div>
<div><br>
</div>
<div>On Wed, 2017-06-21 at 19:46 +0200, Juergen Sauermann wrote:</div>
<blockquote type="cite"> <font face="Helvetica, Arial,
sans-serif">Hi Fred,<br>
<br>
I have a question about the <b>MOD_test.apl</b> that you
kindly provided.<br>
<br>
In function <b>DIVJ</b> on line 57 ff it says:<br>
<br>
<font face="Courier New, Courier, monospace"><b>z ← q , a - b
× q ← CMPLX ⌊ ( 9 11 ) ○ a ÷ b</b></font><br>
<br>
so the quotient is rounded down towards minus infinity.<br>
<br>
I wonder if that should be something like<br>
<br>
<font face="Courier New, Courier, monospace"><b>z ← q , (× q1)
× a - b × q ← CMPLX ⌊ ∣ 9 11 ○ q1 ← a ÷ b</b></font><br>
<br>
so that the quotient is rounded towards 0? Interestingly IBM
and ISO<br>
give different definitions for the residue in terms of APL:<br>
<br>
IBM (language reference, page 227):<br>
<font face="Courier New, Courier, monospace"><b>Z←L∣R</b><b><br>
</b><b>Z is R</b><b>-</b><b>L×⌊ R÷L+L=0</b></font><br>
<br>
ISO (chapter 7.2.9 Residue): <br>
<font face="Courier New, Courier, monospace"><b>R←Q∣P</b><b><br>
</b><b>R←P-(×P)×|Q×⌊|P÷Q<br>
and return R if (×R)=×Q, or R+Q<br>
otherwise.<br>
</b></font> </font><br>
That suggest that IBM rounds the quotient down towards minus
infinity while ISO rounds<br>
 towards 0.<br>
<br>
My naive view on remainder is that the nearest integer quotient
shall be smaller in<br>
magnitude and not smaller in value. Regarding your proposal
(which is different from<br>
both IBM and ISO) my concern is that may lead to different
results for <b>modulo N</b> and<br>
<b>modulo</b> <b>N×1J0</b><br>
<br>
Best Regards,<br>
Jürgen Sauermann<br>
<br>
<br>
<div class="moz-cite-prefix">On 06/21/2017 03:08 AM, Frederick
Pitts wrote:<br>
</div>
<blockquote cite="mid:***@comcast.net"
type="cite">
<div><span style="white-space: normal;">Jürgen,</span></div>
<div><span style="white-space: normal;"><br>
</span></div>
<div><span style="white-space: normal;"> This message is being
resent because last minute changes I made to CRS0.apl and
CRS1.apl do not output the</span></div>
<div><span style="white-space: normal;">data I intended.  This
message has corrected versions of those files attached.
 Please discard the old CRS0.apl and CRS1.apl files.  The
first line of output is the modulo basis, </span><span
style="white-space: normal;">the second line is the
calculated complete residue system values and the third
line is the number of residues in the CRS </span><span
style="white-space: normal;">on the previous line.</span></div>
<div><span style="white-space: normal;"><br>
</span></div>
<div><span style="white-space: normal;"> CRSOTST0.apl and
CRSOTST1.apl are unchanged.</span></div>
<div><span style="white-space: normal;"><br>
</span></div>
<div><span style="white-space: normal;"> Also please find
attached MOD_TEST.apl which compares the residues
calculated by MODJ and the builtin residue function and
reports discrepancies.  The first column of output is the
modulo basis, the second column the right argument to the
functions, the third column the MODJ result and the fourth
column is the builtin residue function result.</span></div>
<div><span style="white-space: normal;"><br>
</span></div>
<div><span style="white-space: normal;">Regards</span></div>
<div><span style="white-space: normal;"><br>
</span></div>
<div><span style="white-space: normal;">Fred</span></div>
<div><br>
</div>
<div>Hello Jürgen,</div>
<pre> SVN 964 moved us in the right direction but not completely out of the</pre>
<pre>woods. SVN 964 still exhibits errors. For instance</pre>
<pre> 2J6 | 5J5</pre>
<pre>¯1J7</pre>
<pre> 2J6 | ¯1J7</pre>
<pre>¯3J1</pre>
<pre> 2J6 | ¯3J1</pre>
<pre>¯3J1</pre>
<pre> I found this and previous residue function errors using the attached APL</pre>
<pre>code files. The files with base name ending in '0' use the builtin residue</pre>
<pre>function. Those with base name ending in '1' use a residue function implemented</pre>
<pre>in APL. The files with base name beginning with 'CRSOTST' test if the order of</pre>
<pre>the complete residue system (CRS) equals the norm of the modulo basis. That</pre>
<pre>test fails for several modulo bases, 2J6 being one of them, using the builtin</pre>
<pre>residue function. No errors are detected with the APL implementation. The other files</pre>
<pre>can be used to plot the CRS for a given modulo basis where 'a' and 'b' in</pre>
<pre>'a + b * i' are limited to +15 to -15 range. A full screen terminal window is</pre>
<pre>needed to see the plot.</pre>
<pre> My APL implementation of the residue function is very close to what you</pre>
<pre>described in your previous email. Maybe comparing the two implementations will</pre>
<pre>give insight into why the builtin residue function fails for some modulo bases.</pre>
<pre> I make no assertion that my implementation is correct in all</pre>
<pre>aspects.</pre>
<pre>Regards,</pre>
<pre>Fred</pre>
<div>On Tue, 2017-06-20 at 14:14 +0200, Juergen Sauermann
wrote:</div>
<blockquote type="cite"> <font face="Helvetica, Arial,
sans-serif">Hi Frederick,<br>
<br>
the algorithm for <b>A ∣ B</b> used in GNU APL is this:<br>
<br>
<font face="Courier New, Courier, monospace"><b>- compute
the quotient Q</b><b>←</b><b>B÷A,</b><b><br>
</b><b>- "round down" Q to the next (complex) integer</b><b>
Q1,</b><b><br>
</b><b>- return B - Q1×A</b></font><b><br>
</b><br>
Now the problem seems to be what is meant by "round down".
There are two candidates:<br>
<br>
<font face="Courier New, Courier, monospace">  <b>Q1 ← ⌊
Q                                          i.e. use
APL floor</b><b> to round down Q</b><b><br>
</b><b>  Q1 ← Complex( floor(Q.real(), </b></font></font><font
face="Helvetica, Arial, sans-serif"><font face="Courier
New, Courier, monospace"><b>floor(Q.</b><b>imag</b><b>())
)   </b><b>i,e, use C/C++ floor() to round down Q.</b><b><br>
</b></font><br>
In your  <b>5J3 ∣ 14J5</b> example, the quotient is <b>2.5J¯0.5</b>,
which gives different results for the APL floor <b>⌊</b>
and the C/C++ floor().<br>
<br>
The APL floor <font face="Courier New, Courier,
monospace"><b>⌊</b></font></font><font face="Helvetica,
Arial, sans-serif"><font face="Helvetica, Arial,
sans-serif"><font face="Courier New, Courier, monospace"><b>2.5J¯0.5</b></font>
is </font><font face="Courier New, Courier, monospace"><b>3J¯1</b></font>
(a somewhat dubious invention in the ISO standard on page
19, which I used up to<br>
including <b>SVN 963</b>), while the C/C++ floor() is</font><font
face="Helvetica, Arial, sans-serif"><font face="Helvetica,
Arial, sans-serif"><font face="Courier New, Courier,
monospace"><b> 2J¯1</b></font></font>. The difference
between the APL floor and the C/C++ floor is <b>1.0 </b>which,<br>
multiplied by the divisor, explains the differences that
we see.<br>
<br>
As of <b>SVN 964</b> I have changed the residue function
(<b>∣</b>) to use the C/C++ floor instead of the APL
floor. The APL floor and<br>
Ceiling functions (<b>⌊</b> and <b>⌈</b>) are still using
the apparently broken definition in the ISO standard.<br>
<br>
I hope this works better for you. At least I am getting
this in <b>SVN 964</b>:<br>
<br>
<font face="Courier New, Courier, monospace"><b>      5J3
| 14J5</b><b><br>
</b><b>1J4</b><b><br>
</b><b>      5J3 | 1J4</b><b><br>
</b><b>1J4</b></font><b><br>
</b><br>
whereas <b>SVN 963</b> was giving:<br>
<br>
<font face="Courier New, Courier, monospace"><b>      5J3
| 14J5</b><b><br>
</b><b>¯4J1</b><b><br>
</b><b>      5J3 | 1J4</b><b><br>
</b><b>¯4J1</b></font><br>
<br>
<br>
Best Regards,<br>
/// Jürgen<br>
<br>
</font><br>
<br>
<div class="moz-cite-prefix">On 06/19/2017 07:03 PM,
Frederick Pitts wrote:<br>
</div>
<blockquote cite="mid:***@comcast.net"
type="cite">
<pre wrap="">Jürgen,

With gnu apl (svn 961 on Fedora 25, Intel(R) Core(TM) i7-6700
CPU), the residue function (∣) yields the following:

      5J3 ∣ 14J5
1J4
      5J3 | 1J4
¯4J1
      5J3 | ¯4J1
¯4J1
The above result means that two elements in the complete residue system
(CSR) for mod 5J3 are equal, i.e. 1J4 = ¯4J1 mod 5J3, which is not
allowed. None of the elements of a CSR can be equal modulo the CSR's
basis.

Regards,

Fred

</pre>
</blockquote>
<br>
</blockquote>
</blockquote>
<br>
</blockquote>
</blockquote>
<br>
</body>
</html>

[Juergen Sauermann]

<html>
<head>
<meta content="text/html; charset=utf-8" http-equiv="Content-Type">
</head>
<body bgcolor="#FFFFFF" text="#000000">
Hi again,<br>
<br>
sorry a small typo below. Lines 19/20 should read:<br>
<br>
<b>      (¯6J¯5 - 0J¯11) ÷ ¯6J¯6 </b><b><br>
</b><b>0J¯1</b><b><br>
</b><br>
/// Jürgen<br>
<br>
<div class="moz-cite-prefix">On 06/22/2017 05:44 PM, Juergen
Sauermann wrote:<br>
</div>
<blockquote
cite="mid:b8297447-b2fa-13f4-399e-***@t-online.de"
type="cite">
<meta content="text/html; charset=utf-8" http-equiv="Content-Type">
<font face="Helvetica, Arial, sans-serif">Hi Fred at al.,<br>
<br>
I have made another attempt to fix the residue function, <b>SVN
965</b>.<br>
<br>
For complex <b>m∣b</b> It now rounds down the real() and imag()
parts of the quotient <b>q←b÷m</b> and returns <b>b-q</b>.<br>
Instead of always rounding towards 0 or -infinity, the rounding
direction is now (compared to the previous<br>
attempt) determined by the quadrant in which the modulus <b>m</b>
lies.<br>
</font><br>
There are still differences to the results displayed by <font
face="Helvetica, Arial, sans-serif"><b>MOD_test.apl</b>, but I
suppose they are<br>
caused by that program. For example, the first line of </font><font
face="Helvetica, Arial, sans-serif"><font face="Helvetica,
Arial, sans-serif"><b>MOD_test.apl</b>, says:<br>
<br>
</font><font face="Courier New, Courier, monospace"><b>  LA   
RA   MODJ   |</b><b><br>
</b><b>¯6J¯6 ¯6J¯5   0J¯11  0J1</b><br>
</font><br>
We have:<br>
<br>
<b>      (¯6J¯5 - 0J1) ÷ ¯6J¯6 </b><b><br>
</b><b>1</b><b><br>
</b><b>      (0J¯11 - 0J1) ÷ ¯6J¯6</b><b><br>
</b><b>1J1</b><br>
<br>
so both <b>0J¯11</b> and <b>0J1</b> are valid remainders
modulo <b>¯6J¯6</b>. However, the<br>
magnitude of </font><font face="Helvetica, Arial, sans-serif"><b>0J¯11</b>
(= <b>11</b>) is larger than the magnitude of the divisor </font><font
face="Helvetica, Arial, sans-serif"><b><font face="Helvetica,
Arial, sans-serif"><b>¯6J¯6</b></font></b><font
face="Helvetica, Arial, sans-serif"> (= around <b>8.4</b>).<br>
I suppose most people expect the remainder of a division to be
in some sense<br>
smaller than the divisor.<br>
<br>
Regarding Jay's idempotency requirement we now have:<br>
<br>
 <b><font face="Courier New, Courier, monospace">    
f←{6J6|⍵}<br>
      f ¯3 ¯2 ¯3 ¯1 0 1 2 3<br>
3J6 4J6 3J6 5J6 0 ¯5J6 ¯4J6 ¯3J6<br>
      f f ¯3 ¯2 ¯3 ¯1 0 1 2 3<br>
3J6 4J6 3J6 5J6 0 ¯5J6 ¯4J6 ¯3J6</font></b><br>
<b><font face="Courier New, Courier, monospace"><br>
      f←{5J3|⍵}<br>
      f ¯3 ¯2 ¯3 ¯1 0 1 2 3<br>
2J3 3J3 2J3 4J3 0 ¯2J5 ¯1J5 0J5<br>
      f f ¯3 ¯2 ¯3 ¯1 0 1 2 3<br>
2J3 3J3 2J3 4J3 0 ¯2J5 ¯1J5 0J5<br>
</font></b><br>
so at least the first modulus seems to work as well. The
result is still different<br>
from APL2 as reported by Jay, but I can't tell why:<br>
<br>
IBM APL2:<br>
<br>
<font face="Courier New, Courier, monospace"><b>      5J3 ∣
14J5 1J4 ¯4J1</b></font></font></font><br>
<font face="Helvetica, Arial, sans-serif"><font face="Helvetica,
Arial, sans-serif"><font face="Courier New, Courier,
monospace"><b>¯4J1 </b></font></font></font><font
face="Helvetica, Arial, sans-serif"><font face="Helvetica,
Arial, sans-serif"><font face="Courier New, Courier,
monospace"><b>¯4J1 </b></font></font></font><font
face="Helvetica, Arial, sans-serif"><font face="Helvetica,
Arial, sans-serif"><font face="Courier New, Courier,
monospace"><b>¯4J1<br>
<br>
</b></font></font></font>GNU APL:<br>
<br>
<font face="Helvetica, Arial, sans-serif"><font face="Helvetica,
Arial, sans-serif"><font face="Helvetica, Arial, sans-serif"><font
face="Helvetica, Arial, sans-serif"><font face="Courier
New, Courier, monospace"><b>      5J3 ∣ 14J5 1J4 ¯4J1 </b><b><br>
</b><b>1J4 1J4 1J4</b></font><br>
<br>
</font></font>But both <b>1J4</b> and <b>¯4J1</b> are
valid remainders. Interestingly Jay's idempotency requirement
seems to<br>
be fulfilled by both the GNU APL and by IBM APL2, so that that
requirement alone does not suffice<br>
to tell which result is correct.<br>
<br>
On the other hand this matter seems to be like discussing if
the square root of 4 is 2 or -2 with<br>
both answers being correct.<br>
<br>
Best Regards,<br>
Jürgen Sauermann<br>
<br>
<br>
</font><b><font face="Helvetica, Arial, sans-serif"><br>
</font></b> </font>
<div class="moz-cite-prefix">On 06/21/2017 10:25 PM, Frederick
Pitts wrote:<br>
</div>
<blockquote cite="mid:***@comcast.net"
type="cite">
<meta content="text/html; charset=utf-8"
http-equiv="Content-Type">
<div>Jürgen,</div>
<div><br>
</div>
<div> The proposed change to DIVJ does not work because 'q1' is
a complex number, so the '×' in '× q1' is the complex
complement function, not the sign function. I tried the
proposed change and every test fails.</div>
<div><br>
</div>
<div> I will try to hack DIVJ to use a floor towards zero
instead of towards minus infinity for the real and imaginary</div>
<div>parts of the quotient and see what happens.</div>
<div><br>
</div>
<div> Correct me if I am wrong, but my mind set is that the APL
residue function has to satisfy the following invariants:</div>
<div>1) The order of the complete residue system (residue count)
for a given modulo 'n' has to equal the norm of 'n'.</div>
<div>2) And as Jay Foad so succinctly expressed it, the residue
function has to be idempotent with respect to its right
argument,</div>
<div> e.g., ( n | m ) = n | n | m .</div>
<div>regardless of the implementation of the residue function.</div>
<div><br>
</div>
<div>Later,</div>
<div><br>
</div>
<div>Fred </div>
<div><br>
</div>
<div><br>
</div>
<div><br>
</div>
<div><br>
</div>
<div>On Wed, 2017-06-21 at 19:46 +0200, Juergen Sauermann wrote:</div>
<blockquote type="cite"> <font face="Helvetica, Arial,
sans-serif">Hi Fred,<br>
<br>
I have a question about the <b>MOD_test.apl</b> that you
kindly provided.<br>
<br>
In function <b>DIVJ</b> on line 57 ff it says:<br>
<br>
<font face="Courier New, Courier, monospace"><b>z ← q , a -
b × q ← CMPLX ⌊ ( 9 11 ) ○ a ÷ b</b></font><br>
<br>
so the quotient is rounded down towards minus infinity.<br>
<br>
I wonder if that should be something like<br>
<br>
<font face="Courier New, Courier, monospace"><b>z ← q , (×
q1) × a - b × q ← CMPLX ⌊ ∣ 9 11 ○ q1 ← a ÷ b</b></font><br>
<br>
so that the quotient is rounded towards 0? Interestingly IBM
and ISO<br>
give different definitions for the residue in terms of APL:<br>
<br>
IBM (language reference, page 227):<br>
<font face="Courier New, Courier, monospace"><b>Z←L∣R</b><b><br>
</b><b>Z is R</b><b>-</b><b>L×⌊ R÷L+L=0</b></font><br>
<br>
ISO (chapter 7.2.9 Residue): <br>
<font face="Courier New, Courier, monospace"><b>R←Q∣P</b><b><br>
</b><b>R←P-(×P)×|Q×⌊|P÷Q<br>
and return R if (×R)=×Q, or R+Q<br>
otherwise.<br>
</b></font> </font><br>
That suggest that IBM rounds the quotient down towards minus
infinity while ISO rounds<br>
 towards 0.<br>
<br>
My naive view on remainder is that the nearest integer
quotient shall be smaller in<br>
magnitude and not smaller in value. Regarding your proposal
(which is different from<br>
both IBM and ISO) my concern is that may lead to different
results for <b>modulo N</b> and<br>
<b>modulo</b> <b>N×1J0</b><br>
<br>
Best Regards,<br>
Jürgen Sauermann<br>
<br>
<br>
<div class="moz-cite-prefix">On 06/21/2017 03:08 AM, Frederick
Pitts wrote:<br>
</div>
<blockquote cite="mid:***@comcast.net"
type="cite">
<div><span style="white-space: normal;">Jürgen,</span></div>
<div><span style="white-space: normal;"><br>
</span></div>
<div><span style="white-space: normal;"> This message is
being resent because last minute changes I made to
CRS0.apl and CRS1.apl do not output the</span></div>
<div><span style="white-space: normal;">data I intended.
 This message has corrected versions of those files
attached.  Please discard the old CRS0.apl and CRS1.apl
files.  The first line of output is the modulo basis, </span><span
style="white-space: normal;">the second line is the
calculated complete residue system values and the third
line is the number of residues in the CRS </span><span
style="white-space: normal;">on the previous line.</span></div>
<div><span style="white-space: normal;"><br>
</span></div>
<div><span style="white-space: normal;"> CRSOTST0.apl and
CRSOTST1.apl are unchanged.</span></div>
<div><span style="white-space: normal;"><br>
</span></div>
<div><span style="white-space: normal;"> Also please find
attached MOD_TEST.apl which compares the residues
calculated by MODJ and the builtin residue function and
reports discrepancies.  The first column of output is
the modulo basis, the second column the right argument
to the functions, the third column the MODJ result and
the fourth column is the builtin residue function
result.</span></div>
<div><span style="white-space: normal;"><br>
</span></div>
<div><span style="white-space: normal;">Regards</span></div>
<div><span style="white-space: normal;"><br>
</span></div>
<div><span style="white-space: normal;">Fred</span></div>
<div><br>
</div>
<div>Hello Jürgen,</div>
<pre> SVN 964 moved us in the right direction but not completely out of the</pre>
<pre>woods. SVN 964 still exhibits errors. For instance</pre>
<pre> 2J6 | 5J5</pre>
<pre>¯1J7</pre>
<pre> 2J6 | ¯1J7</pre>
<pre>¯3J1</pre>
<pre> 2J6 | ¯3J1</pre>
<pre>¯3J1</pre>
<pre> I found this and previous residue function errors using the attached APL</pre>
<pre>code files. The files with base name ending in '0' use the builtin residue</pre>
<pre>function. Those with base name ending in '1' use a residue function implemented</pre>
<pre>in APL. The files with base name beginning with 'CRSOTST' test if the order of</pre>
<pre>the complete residue system (CRS) equals the norm of the modulo basis. That</pre>
<pre>test fails for several modulo bases, 2J6 being one of them, using the builtin</pre>
<pre>residue function. No errors are detected with the APL implementation. The other files</pre>
<pre>can be used to plot the CRS for a given modulo basis where 'a' and 'b' in</pre>
<pre>'a + b * i' are limited to +15 to -15 range. A full screen terminal window is</pre>
<pre>needed to see the plot.</pre>
<pre> My APL implementation of the residue function is very close to what you</pre>
<pre>described in your previous email. Maybe comparing the two implementations will</pre>
<pre>give insight into why the builtin residue function fails for some modulo bases.</pre>
<pre> I make no assertion that my implementation is correct in all</pre>
<pre>aspects.</pre>
<pre>Regards,</pre>
<pre>Fred</pre>
<div>On Tue, 2017-06-20 at 14:14 +0200, Juergen Sauermann
wrote:</div>
<blockquote type="cite"> <font face="Helvetica, Arial,
sans-serif">Hi Frederick,<br>
<br>
the algorithm for <b>A ∣ B</b> used in GNU APL is this:<br>
<br>
<font face="Courier New, Courier, monospace"><b>-
compute the quotient Q</b><b>←</b><b>B÷A,</b><b><br>
</b><b>- "round down" Q to the next (complex) integer</b><b>
Q1,</b><b><br>
</b><b>- return B - Q1×A</b></font><b><br>
</b><br>
Now the problem seems to be what is meant by "round
down". There are two candidates:<br>
<br>
<font face="Courier New, Courier, monospace">  <b>Q1 ←
⌊ Q                                          i.e.
use APL floor</b><b> to round down Q</b><b><br>
</b><b>  Q1 ← Complex( floor(Q.real(), </b></font></font><font
face="Helvetica, Arial, sans-serif"><font face="Courier
New, Courier, monospace"><b>floor(Q.</b><b>imag</b><b>())
)   </b><b>i,e, use C/C++ floor() to round down Q.</b><b><br>
</b></font><br>
In your  <b>5J3 ∣ 14J5</b> example, the quotient is <b>2.5J¯0.5</b>,
which gives different results for the APL floor <b>⌊</b>
and the C/C++ floor().<br>
<br>
The APL floor <font face="Courier New, Courier,
monospace"><b>⌊</b></font></font><font
face="Helvetica, Arial, sans-serif"><font
face="Helvetica, Arial, sans-serif"><font
face="Courier New, Courier, monospace"><b>2.5J¯0.5</b></font>
is </font><font face="Courier New, Courier,
monospace"><b>3J¯1</b></font> (a somewhat dubious
invention in the ISO standard on page 19, which I used
up to<br>
including <b>SVN 963</b>), while the C/C++ floor() is</font><font
face="Helvetica, Arial, sans-serif"><font
face="Helvetica, Arial, sans-serif"><font
face="Courier New, Courier, monospace"><b> 2J¯1</b></font></font>.
The difference between the APL floor and the C/C++ floor
is <b>1.0 </b>which,<br>
multiplied by the divisor, explains the differences that
we see.<br>
<br>
As of <b>SVN 964</b> I have changed the residue
function (<b>∣</b>) to use the C/C++ floor instead of
the APL floor. The APL floor and<br>
Ceiling functions (<b>⌊</b> and <b>⌈</b>) are still
using the apparently broken definition in the ISO
standard.<br>
<br>
I hope this works better for you. At least I am getting
this in <b>SVN 964</b>:<br>
<br>
<font face="Courier New, Courier, monospace"><b>     
5J3 | 14J5</b><b><br>
</b><b>1J4</b><b><br>
</b><b>      5J3 | 1J4</b><b><br>
</b><b>1J4</b></font><b><br>
</b><br>
whereas <b>SVN 963</b> was giving:<br>
<br>
<font face="Courier New, Courier, monospace"><b>     
5J3 | 14J5</b><b><br>
</b><b>¯4J1</b><b><br>
</b><b>      5J3 | 1J4</b><b><br>
</b><b>¯4J1</b></font><br>
<br>
<br>
Best Regards,<br>
/// Jürgen<br>
<br>
</font><br>
<br>
<div class="moz-cite-prefix">On 06/19/2017 07:03 PM,
Frederick Pitts wrote:<br>
</div>
<blockquote cite="mid:***@comcast.net"
type="cite">
<pre wrap="">Jürgen,

With gnu apl (svn 961 on Fedora 25, Intel(R) Core(TM) i7-6700
CPU), the residue function (∣) yields the following:

      5J3 ∣ 14J5
1J4
      5J3 | 1J4
¯4J1
      5J3 | ¯4J1
¯4J1
The above result means that two elements in the complete residue system
(CSR) for mod 5J3 are equal, i.e. 1J4 = ¯4J1 mod 5J3, which is not
allowed. None of the elements of a CSR can be equal modulo the CSR's
basis.

Regards,

Fred

</pre>
</blockquote>
<br>
</blockquote>
</blockquote>
<br>
</blockquote>
</blockquote>
<br>
</blockquote>
<br>
</body>
</html>

[Frederick Pitts]

Hello JÃŒrgen,
Some observations:
1) When performing a residue calculation on positive integers, a
straight-forward integer division with remainder
calculationsuffices.  For example, 5 ∣ 13  is computed with 13 / 5 = 2
r 3 and so 5 ∣ 13 = 3 where 3 is in the complete residue system{ 0, 1,
2, 3, 4 }.  When performing the calculation on negative integers, one
has to take advantage of the fact that theinteger division quotient and
remainder are not unique in order to compute a residue that is in the
complete residue system.For 5 ∣ ¯13, ¯13 / 5 = ¯2 r ¯3 where ¯3 is not
in the CRS.  However, ¯13 / 5 = ¯3 r 2 where 3 is in the CSR.  The same
concept applies Gaussian integers.
2) I suspect the decision to have the APL2 floor function round toward
negative infinity, instead of toward zero,was made  based on the desire
to save cpu cycles and memory in the residue function code.
3) I read at least one math literature article discussing Gaussian
integer Euclidean division algorithms, that recommendedrounding down to
the nearest real and imaginary part toward negative
infinity.  Unfortunately I cannot findthe article right now.  I will
continue to look for it.  None of the articles discussed using a
complex integer floor function.
4) The reason MOD_TEST.apl shows total disagreement  MODJ and the
builtin residue function is that the complex floor function code change
in SVN 965 relocated the CRS's on complex plane.  Attached are CRS0-
CRS1-6J-6-SVN964.outCRS0-CRS1-6J-6-SVN965.out.  The first file contains
a CRS map for modulus ¯6J¯6 produced with the residue functionfollowed
by a map for the same modulus produced with MODJ using SVN 964.  The
second file contains the same mapsusing SVN 965.  Observe that for SVN
964 the residue function CRS is in the bottom half of the complex
plane, but for SVN 965 it is in the top half.  The CRS for the MODJ
function is in the bottom half in both SVN cases.5)The complex floor
code change did not help with the issue that the builtin residue
function is not idempotent for all possible arguments and consequently
generates too many residues.  See attached CRSOTST0-SVN965.out.  For a
gridof Gaussian integers with real and imaginary parts ranging from ¯15
to 15, using every value with every other value as modulus and second
argument, there were 40 case where the order of CSR exceeded the
modulus norm.  I think thatwas the failure count with the previous SVN.
Sincerely, I think the complex floor and ceiling functions
should not be used by other functions even if IBM and ISOimply they are
in their documentations.  I'm not seeing them used in the Gaussian
integer literature.  Again, please correct me if I'm wrong.
Regards,
Fred

    Hi again,
    
    
          (¯6J¯5 - 0J¯11) ÷ ¯6J¯6 
    0J¯1
    
    /// JÌrgen
    
    On 06/22/2017 05:44 PM, Juergen
    
    

Post by Frederick Pitts
      
      Hi Fred at al.,
        
        I have made another attempt to fix the residue function,
SVN
          965.
        
        For complex m∣b It now rounds down the real() and imag()
        parts of the quotient q←b÷m and returns b-q.
        Instead of always rounding towards 0 or -infinity, the
rounding
        direction is now (compared to the previous
        attempt) determined by the quadrant in which the modulus m
        lies.
      
      There are still differences to the results displayed by
MOD_test.apl, but I
        suppose they are
        caused by that program. For example, the first line of
          
          LA   
            RA   MODJ   |
          ¯6J¯6 ¯6J¯5   0J¯11  0J1
        
        
              (¯6J¯5 - 0J1) ÷ ¯6J¯6 
        1
              (0J¯11 - 0J1) ÷ ¯6J¯6
        1J1
        
        so both 0J¯11 and 0J1 are valid remainders
        modulo ¯6J¯6. However, the
        magnitude of 0J¯11
        (= 11) is larger than the magnitude of the divisor ¯6J¯6 (=
around 8.4).
          I suppose most people expect the remainder of a division
to be
          in some sense
          smaller than the divisor.
          
          
               
              f←{6J6|⍵}
                    f ¯3 ¯2 ¯3 ¯1 0 1 2 3
              3J6 4J6 3J6 5J6 0 ¯5J6 ¯4J6 ¯3J6
                    f f ¯3 ¯2 ¯3 ¯1 0 1 2 3
              3J6 4J6 3J6 5J6 0 ¯5J6 ¯4J6 ¯3J6
          
                    f←{5J3|⍵}
                    f ¯3 ¯2 ¯3 ¯1 0 1 2 3
              2J3 3J3 2J3 4J3 0 ¯2J5 ¯1J5 0J5
                    f f ¯3 ¯2 ¯3 ¯1 0 1 2 3
              2J3 3J3 2J3 4J3 0 ¯2J5 ¯1J5 0J5
            
          so at least the first modulus seems to work as well. The
          result is still different
          
          
                5J3 ∣
              14J5 1J4 ¯4J1
      ¯4J1 ¯4J1 ¯4J1
              
      
            5J3 ∣ 14J5 1J4 ¯4J1 
                1J4 1J4 1J4
              
            But both 1J4 and ¯4J1 are
          valid remainders. Interestingly Jay's idempotency
requirement
          seems to
          be fulfilled by both the GNU APL and by IBM APL2, so that
that
          requirement alone does not suffice
          to tell which result is correct.
          
          On the other hand this matter seems to be like discussing
if
          the square root of 4 is 2 or -2 with
          both answers being correct.
          
          Best Regards,
          JÌrgen Sauermann
          
          
        
           
      On 06/21/2017 10:25 PM, Frederick
      
      

        
        JÌrgen,
        
        
         The proposed change to DIVJ does not work because 'q1'
is
          a complex number, so the '×' in '× q1' is the complex
          complement function, not the sign function. I tried the
          proposed change and every test fails.
        
        
         I will try to hack DIVJ to use a floor towards zero
          instead of towards minus infinity for the real and
imaginary
        parts of the quotient and see what happens.
        
        
         Correct me if I am wrong, but my mind set is that the
APL
          residue function has to satisfy the following
        1) The order of the complete residue system (residue
count)
          for a given modulo 'n' has to equal the norm of 'n'.
        2) And as Jay Foad so succinctly expressed it, the
residue
          function has to be idempotent with respect to its right
          argument,
         e.g., ( n | m ) = n | n | m .
        regardless of the implementation of the residue function.
        
        
        Later,
        
        
        Fred 
        
        
        
        
        
        
        
        
        On Wed, 2017-06-21 at 19:46 +0200, Juergen Sauermann
        

 Hi Fred,
            
            I have a question about the MOD_test.apl that you
            kindly provided.
            
            
            z ← q , a -
                b × q ← CMPLX ⌊ ( 9 11 ) ○ a ÷ b
            
            so the quotient is rounded down towards minus
infinity.
            
            I wonder if that should be something like
            
            z ← q , (×
                q1) × a - b × q ← CMPLX ⌊ ∣ 9 11 ○ q1 ← a ÷ b
            
            so that the quotient is rounded towards 0?
Interestingly IBM
            and ISO
            give different definitions for the residue in terms
            
            Z←L∣R
              Z is R-L×⌊ R÷L+L=0
            
            ISO (chapter 7.2.9 Residue): 
            R←Q∣P
              R←P-(×P)×|Q×⌊|P÷Q
                and return R if (×R)=×Q, or R+Q
                otherwise.
               
          That suggest that IBM rounds the quotient down
towards minus
          infinity while ISO rounds
           towards 0.
          
          My naive view on remainder is that the nearest
integer
          quotient shall be smaller in
          magnitude and not smaller in value. Regarding your
proposal
          (which is different from
          both IBM and ISO) my concern is that may lead to
different
          results for modulo N and
          modulo N×1J0
          
          Best Regards,
          JÌrgen Sauermann
          
          
          On 06/21/2017 03:08 AM, Frederick
          
          

            JÌrgen,
            
              
             This message is
                being resent because last minute changes I
made to
                CRS0.apl and CRS1.apl do not output the
            data I intended.
                 This message has corrected versions of those
files
                attached.  Please discard the old CRS0.apl
and CRS1.apl
                files.  The first line of output is the
modulo basis, the second line is the
                calculated complete residue system values and
the third
                line is the number of residues in the CRS on
the previous line.
            
              
             CRSOTST0.apl and
                CRSOTST1.apl are unchanged.
            
              
             Also please find
                attached MOD_TEST.apl which compares the
residues
                calculated by MODJ and the builtin residue
function and
                reports discrepancies.  The first column of
output is
                the modulo basis, the second column the right
argument
                to the functions, the third column the MODJ
result and
                the fourth column is the builtin residue
function
                result.
            
              
            Regards
            
              
            Fred
            
            
            Hello JÌrgen,
             SVN 964 moved us in the right direction
but not completely out of the
            woods.  SVN 964 still exhibits errors.  For
instance
                  2J6 | 5J5
            ¯1J7
                  2J6 | ¯1J7
            ¯3J1
                  2J6 | ¯3J1
            ¯3J1
             I found this and previous residue
function errors using the attached APL
            code files.  The files with base name ending in
'0' use the builtin residue
            function.  Those with base name ending in '1' use
a residue function implemented
            in APL.  The files with base name beginning with
'CRSOTST' test if the order of
            the complete residue system (CRS) equals the norm
of the modulo basis.  That
            test fails for several modulo bases, 2J6 being
one of them, using the builtin
            residue function. No errors are detected with the
APL implementation.  The other files
            can be used to plot the CRS for a given modulo
basis where 'a' and 'b' in
            'a + b * i' are limited to +15 to -15 range.  A
full screen terminal window is
            needed to see the plot.
             My APL implementation of the residue
function is very close to what you
            described in your previous email.  Maybe
comparing the two implementations will
            give insight into why the builtin residue
function fails for some modulo bases.
             I make no assertion that my
implementation is correct in all
            aspects.
            Regards,
            Fred
            On Tue, 2017-06-20 at 14:14 +0200, Juergen
Sauermann
            

 Hi Frederick,
                
                the algorithm for A ∣ B used in GNU APL is
                
                -
                    compute the quotient Q←B÷A,
                  - "round down" Q to the next (complex)
integer
                    Q1,
                  - return B - Q1×A
                
                Now the problem seems to be what is meant
by "round
                
                  Q1 ←
                    ⌊
Q                                          i.e.
                    use APL floor to round down Q
                    Q1 ← Complex( floor(Q.real(),
floor(Q.imag())
                    )   i,e, use C/C++ floor() to round
down Q.
                  
                In your  5J3 ∣ 14J5 example, the quotient
is 2.5J¯0.5,
                which gives different results for the APL
floor ⌊
                and the C/C++ floor().
                
                The APL floor ⌊2.5J¯0.5
                  is 3J¯1 (a somewhat dubious
                invention in the ISO standard on page 19,
which I used
                up to
                including SVN 963), while the C/C++ floor()
is 2J¯1.
                The difference between the APL floor and
the C/C++ floor
                is 1.0 which,
                multiplied by the divisor, explains the
differences that
                we see.
                
                As of SVN 964 I have changed the residue
                function (∣) to use the C/C++ floor instead
of
                the APL floor. The APL floor and
                Ceiling functions (⌊ and ⌈) are still
                using the apparently broken definition in
the ISO
                standard.
                
                I hope this works better for you. At least
I am getting
                
                     
                    5J3 | 14J5
                  1J4
                        5J3 | 1J4
                  1J4
                
                
                     
                    5J3 | 14J5
                  ¯4J1
                        5J3 | 1J4
                  ¯4J1
                
                
                Best Regards,
                /// JÌrgen
                
              
              
              On 06/19/2017 07:03 PM,
              
              

                JÌrgen,
With gnu apl (svn 961 on Fedora 25, Intel(R) Core(TM) i7-6700
      5J3 ∣ 14J5
1J4
      5J3 | 1J4
¯4J1
      5J3 | ¯4J1
¯4J1
The above result means that two elements in the complete
residue system
(CSR) for mod 5J3 are equal, i.e. 1J4 = ¯4J1 mod 5J3,
which is not
allowed.  None of the elements of a CSR can be equal
modulo the CSR's
basis.
Regards,
Fred
              

              
            

          

          
        

      

      
    

    
  

[Jay Foad]

I urge you to read Eugene McDonnell's Complex Floor
<http://www.jsoftware.com/papers/eem/complexfloor.htm>, which also
discusses Residue. I believe the design he comes up with in this paper was
adopted more or less verbatim in APL. Also bear in mind that Floor and
Residue in APL have to work well on all complex numbers, not *just* the
Gaussian integers.

Jay.

Post by Frederick Pitts
Hello JÃŒrgen,
1) When performing a residue calculation on positive integers, a
straight-forward integer division with remainder calculation
suffices. For example, 5 ∣ 13 is computed with 13 / 5 = 2 r 3 and so 5 ∣
13 = 3 where 3 is in the complete residue system
{ 0, 1, 2, 3, 4 }. When performing the calculation on negative integers,
one has to take advantage of the fact that the
integer division quotient and remainder are not unique in order to compute
a residue that is in the complete residue system.
For 5 ∣ ¯13, ¯13 / 5 = ¯2 r ¯3 where ¯3 is not in the CRS. However, ¯13 /
5 = ¯3 r 2 where 3 is in the CSR. The same concept applies Gaussian
integers.
2) I suspect the decision to have the APL2 floor function round toward
negative infinity, instead of toward zero,
was made based on the desire to save cpu cycles and memory in the residue
function code.
3) I read at least one math literature article discussing Gaussian integer
Euclidean division algorithms, that recommended
rounding down to the nearest real and imaginary part toward negative
infinity. Unfortunately I cannot find
the article right now. I will continue to look for it. None of the
articles discussed using a complex integer floor function.
4) The reason MOD_TEST.apl shows total disagreement MODJ and the builtin
residue function is that the complex floor function code change in SVN 965
relocated the CRS's on complex plane. Attached are CRS0-CRS1-6J-6-SVN964.out
CRS0-CRS1-6J-6-SVN965.out. The first file contains a CRS map for modulus
¯6J¯6 produced with the residue function
followed by a map for the same modulus produced with MODJ using SVN 964.
The second file contains the same maps
using SVN 965. Observe that for SVN 964 the residue function CRS is in the
bottom half of the complex plane, but for SVN 965 it is in the top half.
The CRS for the MODJ function is in the bottom half in both SVN cases.
5)The complex floor code change did not help with the issue that the
builtin residue function is not idempotent for all possible arguments and
consequently generates too many residues. See attached CRSOTST0-SVN965.out.
For a grid
of Gaussian integers with real and imaginary parts ranging from ¯15 to 15,
using every value with every other value as modulus and second argument,
there were 40 case where the order of CSR exceeded the modulus norm. I
think that
was the failure count with the previous SVN.
Sincerely, I think the complex floor and ceiling functions should not be
used by other functions even if IBM and ISO
imply they are in their documentations. I'm not seeing them used in the
Gaussian integer literature. Again, please correct me if I'm wrong.
Regards,
Fred
Hi again,
* (¯6J¯5 - 0J¯11) ÷ ¯6J¯6 *
*0J¯1*
/// JÃŒrgen
Hi Fred at al.,
I have made another attempt to fix the residue function, *SVN 965*.
For complex *m∣b* It now rounds down the real() and imag() parts of the
quotient *q←b÷m* and returns *b-q*.
Instead of always rounding towards 0 or -infinity, the rounding direction
is now (compared to the previous
attempt) determined by the quadrant in which the modulus *m* lies.
There are still differences to the results displayed by *MOD_test.apl*,
but I suppose they are
caused by that program. For example, the first line of *MOD_test.apl*,
* LA RA MODJ |*
*¯6J¯6 ¯6J¯5 0J¯11 0J1*
* (¯6J¯5 - 0J1) ÷ ¯6J¯6 *
*1*
* (0J¯11 - 0J1) ÷ ¯6J¯6*
*1J1*
so both *0J¯11* and *0J1* are valid remainders modulo *¯6J¯6*. However,
the
magnitude of *0J¯11* (= *11*) is larger than the magnitude of the divisor
*¯6J¯6* (= around *8.4*).
I suppose most people expect the remainder of a division to be in some
sense
smaller than the divisor.
* f←{6J6|⍵} f ¯3 ¯2 ¯3 ¯1 0 1 2 3 3J6 4J6 3J6 5J6 0 ¯5J6 ¯4J6
¯3J6 f f ¯3 ¯2 ¯3 ¯1 0 1 2 3 3J6 4J6 3J6 5J6 0 ¯5J6 ¯4J6 ¯3J6*
* f←{5J3|⍵} f ¯3 ¯2 ¯3 ¯1 0 1 2 3 2J3 3J3 2J3 4J3 0 ¯2J5 ¯1J5
0J5 f f ¯3 ¯2 ¯3 ¯1 0 1 2 3 2J3 3J3 2J3 4J3 0 ¯2J5 ¯1J5 0J5 *
so at least the first modulus seems to work as well. The result is still
different
* 5J3 ∣ 14J5 1J4 ¯4J1*
*¯4J1 **¯4J1 *
* 5J3 ∣ 14J5 1J4 ¯4J1 *
*1J4 1J4 1J4*
But both *1J4* and *¯4J1* are valid remainders. Interestingly Jay's
idempotency requirement seems to
be fulfilled by both the GNU APL and by IBM APL2, so that that requirement
alone does not suffice
to tell which result is correct.
On the other hand this matter seems to be like discussing if the square
root of 4 is 2 or -2 with
both answers being correct.
Best Regards,
JÃŒrgen Sauermann
JÃŒrgen,
The proposed change to DIVJ does not work because 'q1' is a complex
number, so the '×' in '× q1' is the complex complement function, not the
sign function. I tried the proposed change and every test fails.
I will try to hack DIVJ to use a floor towards zero instead of towards
minus infinity for the real and imaginary
parts of the quotient and see what happens.
Correct me if I am wrong, but my mind set is that the APL residue function
1) The order of the complete residue system (residue count) for a given
modulo 'n' has to equal the norm of 'n'.
2) And as Jay Foad so succinctly expressed it, the residue function has to
be idempotent with respect to its right argument,
e.g., ( n | m ) = n | n | m .
regardless of the implementation of the residue function.
Later,
Fred
Hi Fred,
I have a question about the *MOD_test.apl* that you kindly provided.
*z ← q , a - b × q ← CMPLX ⌊ ( 9 11 ) ○ a ÷ b*
so the quotient is rounded down towards minus infinity.
I wonder if that should be something like
*z ← q , (× q1) × a - b × q ← CMPLX ⌊ ∣ 9 11 ○ q1 ← a ÷ b*
so that the quotient is rounded towards 0? Interestingly IBM and ISO
*Z←L∣R*
*Z is R**-**L×⌊ R÷L+L=0*
*R←Q∣P*
*R←P-(×P)×|Q×⌊|P÷Q and return R if (×R)=×Q, or R+Q otherwise. *
That suggest that IBM rounds the quotient down towards minus infinity
while ISO rounds
towards 0.
My naive view on remainder is that the nearest integer quotient shall be
smaller in
magnitude and not smaller in value. Regarding your proposal (which is
different from
both IBM and ISO) my concern is that may lead to different results for *modulo
N* and
*modulo* *N×1J0*
Best Regards,
JÃŒrgen Sauermann
JÃŒrgen,
This message is being resent because last minute changes I made to
CRS0.apl and CRS1.apl do not output the
data I intended. This message has corrected versions of those files
attached. Please discard the old CRS0.apl and CRS1.apl files. The first
line of output is the modulo basis, the second line is the calculated
complete residue system values and the third line is the number of residues
in the CRS on the previous line.
CRSOTST0.apl and CRSOTST1.apl are unchanged.
Also please find attached MOD_TEST.apl which compares the residues
calculated by MODJ and the builtin residue function and reports
discrepancies. The first column of output is the modulo basis, the second
column the right argument to the functions, the third column the MODJ
result and the fourth column is the builtin residue function result.
Regards
Fred
Hello JÃŒrgen,
SVN 964 moved us in the right direction but not completely out of the
woods. SVN 964 still exhibits errors. For instance
2J6 | 5J5
¯1J7
2J6 | ¯1J7
¯3J1
2J6 | ¯3J1
¯3J1
I found this and previous residue function errors using the attached APL
code files. The files with base name ending in '0' use the builtin residue
function. Those with base name ending in '1' use a residue function implemented
in APL. The files with base name beginning with 'CRSOTST' test if the order of
the complete residue system (CRS) equals the norm of the modulo basis. That
test fails for several modulo bases, 2J6 being one of them, using the builtin
residue function. No errors are detected with the APL implementation. The other files
can be used to plot the CRS for a given modulo basis where 'a' and 'b' in
'a + b * i' are limited to +15 to -15 range. A full screen terminal window is
needed to see the plot.
My APL implementation of the residue function is very close to what you
described in your previous email. Maybe comparing the two implementations will
give insight into why the builtin residue function fails for some modulo bases.
I make no assertion that my implementation is correct in all
aspects.
Regards,
Fred
Hi Frederick,
*- compute the quotient Q**←**B÷A,*
*- "round down" Q to the next (complex) integer** Q1,*
*- return B - Q1×A*
Now the problem seems to be what is meant by "round down". There are two
*Q1 ← ⌊ Q i.e. use APL floor**
to round down Q*
* Q1 ← Complex( floor(Q.real(), **floor(Q.**imag**()) ) **i,e, use
C/C++ floor() to round down Q.*
In your *5J3 ∣ 14J5* example, the quotient is *2.5J¯0.5*, which gives
different results for the APL floor *⌊* and the C/C++ floor().
The APL floor *⌊**2.5J¯0.5* is *3J¯1* (a somewhat dubious invention in
the ISO standard on page 19, which I used up to
including *SVN 963*), while the C/C++ floor() is* 2J¯1*. The difference
between the APL floor and the C/C++ floor is *1.0 *which,
multiplied by the divisor, explains the differences that we see.
As of *SVN 964* I have changed the residue function (*∣*) to use the
C/C++ floor instead of the APL floor. The APL floor and
Ceiling functions (*⌊* and *⌈*) are still using the apparently broken
definition in the ISO standard.
* 5J3 | 14J5*
*1J4*
* 5J3 | 1J4*
*1J4*
* 5J3 | 14J5*
*¯4J1*
* 5J3 | 1J4*
*¯4J1*
Best Regards,
/// JÃŒrgen
JÃŒrgen,
With gnu apl (svn 961 on Fedora 25, Intel(R) Core(TM) i7-6700
5J3 ∣ 14J5
1J4
5J3 | 1J4
¯4J1
5J3 | ¯4J1
¯4J1
The above result means that two elements in the complete residue system
(CSR) for mod 5J3 are equal, i.e. 1J4 = ¯4J1 mod 5J3, which is not
allowed. None of the elements of a CSR can be equal modulo the CSR's
basis.
Regards,
Fred

[Louis de Forcrand]

In J it is implemented as

(X|Y)=Y-X mul flr Y div X+0=X
for all numerical X and Y,
where mul is multiplication, div is division, and flr is flooring as defined here for complex numbers:
http://www.jsoftware.com/help/dictionary/d011.htm

I believe it's implemented like in McDonnell's article which Jay already posted.

Perhaps this can help?
Louis

I urge you to read Eugene McDonnell's Complex Floor, which also discusses Residue. I believe the design he comes up with in this paper was adopted more or less verbatim in APL. Also bear in mind that Floor and Residue in APL have to work well on all complex numbers, not just the Gaussian integers.
Jay.

Post by Frederick Pitts
Hello JÃŒrgen,
1) When performing a residue calculation on positive integers, a straight-forward integer division with remainder calculation
suffices. For example, 5 ∣ 13 is computed with 13 / 5 = 2 r 3 and so 5 ∣ 13 = 3 where 3 is in the complete residue system
{ 0, 1, 2, 3, 4 }. When performing the calculation on negative integers, one has to take advantage of the fact that the
integer division quotient and remainder are not unique in order to compute a residue that is in the complete residue system.
For 5 ∣ ¯13, ¯13 / 5 = ¯2 r ¯3 where ¯3 is not in the CRS. However, ¯13 / 5 = ¯3 r 2 where 3 is in the CSR. The same concept applies Gaussian integers.
2) I suspect the decision to have the APL2 floor function round toward negative infinity, instead of toward zero,
was made based on the desire to save cpu cycles and memory in the residue function code.
3) I read at least one math literature article discussing Gaussian integer Euclidean division algorithms, that recommended
rounding down to the nearest real and imaginary part toward negative infinity. Unfortunately I cannot find
the article right now. I will continue to look for it. None of the articles discussed using a complex integer floor function.
4) The reason MOD_TEST.apl shows total disagreement MODJ and the builtin residue function is that the complex floor function code change in SVN 965 relocated the CRS's on complex plane. Attached are CRS0-CRS1-6J-6-SVN964.out
CRS0-CRS1-6J-6-SVN965.out. The first file contains a CRS map for modulus ¯6J¯6 produced with the residue function
followed by a map for the same modulus produced with MODJ using SVN 964. The second file contains the same maps
using SVN 965. Observe that for SVN 964 the residue function CRS is in the bottom half of the complex plane, but for SVN 965 it is in the top half. The CRS for the MODJ function is in the bottom half in both SVN cases.
5)The complex floor code change did not help with the issue that the builtin residue function is not idempotent for all possible arguments and consequently generates too many residues. See attached CRSOTST0-SVN965.out. For a grid
of Gaussian integers with real and imaginary parts ranging from ¯15 to 15, using every value with every other value as modulus and second argument, there were 40 case where the order of CSR exceeded the modulus norm. I think that
was the failure count with the previous SVN.
Sincerely, I think the complex floor and ceiling functions should not be used by other functions even if IBM and ISO
imply they are in their documentations. I'm not seeing them used in the Gaussian integer literature. Again, please correct me if I'm wrong.
Regards,
Fred

Post by Juergen Sauermann
Hi again,
(¯6J¯5 - 0J¯11) ÷ ¯6J¯6
0J¯1
/// JÃŒrgen

Post by Juergen Sauermann
Hi Fred at al.,
I have made another attempt to fix the residue function, SVN 965.
For complex m∣b It now rounds down the real() and imag() parts of the quotient q←b÷m and returns b-q.
Instead of always rounding towards 0 or -infinity, the rounding direction is now (compared to the previous
attempt) determined by the quadrant in which the modulus m lies.
There are still differences to the results displayed by MOD_test.apl, but I suppose they are
LA RA MODJ |
¯6J¯6 ¯6J¯5 0J¯11 0J1
(¯6J¯5 - 0J1) ÷ ¯6J¯6
1
(0J¯11 - 0J1) ÷ ¯6J¯6
1J1
so both 0J¯11 and 0J1 are valid remainders modulo ¯6J¯6. However, the
magnitude of 0J¯11 (= 11) is larger than the magnitude of the divisor ¯6J¯6 (= around 8.4).
I suppose most people expect the remainder of a division to be in some sense
smaller than the divisor.
f←{6J6|⍵}
f ¯3 ¯2 ¯3 ¯1 0 1 2 3
3J6 4J6 3J6 5J6 0 ¯5J6 ¯4J6 ¯3J6
f f ¯3 ¯2 ¯3 ¯1 0 1 2 3
3J6 4J6 3J6 5J6 0 ¯5J6 ¯4J6 ¯3J6
f←{5J3|⍵}
f ¯3 ¯2 ¯3 ¯1 0 1 2 3
2J3 3J3 2J3 4J3 0 ¯2J5 ¯1J5 0J5
f f ¯3 ¯2 ¯3 ¯1 0 1 2 3
2J3 3J3 2J3 4J3 0 ¯2J5 ¯1J5 0J5
so at least the first modulus seems to work as well. The result is still different
5J3 ∣ 14J5 1J4 ¯4J1
¯4J1 ¯4J1 ¯4J1
5J3 ∣ 14J5 1J4 ¯4J1
1J4 1J4 1J4
But both 1J4 and ¯4J1 are valid remainders. Interestingly Jay's idempotency requirement seems to
be fulfilled by both the GNU APL and by IBM APL2, so that that requirement alone does not suffice
to tell which result is correct.
On the other hand this matter seems to be like discussing if the square root of 4 is 2 or -2 with
both answers being correct.
Best Regards,
JÃŒrgen Sauermann

JÃŒrgen,
The proposed change to DIVJ does not work because 'q1' is a complex number, so the '×' in '× q1' is the complex complement function, not the sign function. I tried the proposed change and every test fails.
I will try to hack DIVJ to use a floor towards zero instead of towards minus infinity for the real and imaginary
parts of the quotient and see what happens.
1) The order of the complete residue system (residue count) for a given modulo 'n' has to equal the norm of 'n'.
2) And as Jay Foad so succinctly expressed it, the residue function has to be idempotent with respect to its right argument,
e.g., ( n | m ) = n | n | m .
regardless of the implementation of the residue function.
Later,
Fred

Post by Juergen Sauermann
Hi Fred,
I have a question about the MOD_test.apl that you kindly provided.
z ← q , a - b × q ← CMPLX ⌊ ( 9 11 ) ○ a ÷ b
so the quotient is rounded down towards minus infinity.
I wonder if that should be something like
z ← q , (× q1) × a - b × q ← CMPLX ⌊ ∣ 9 11 ○ q1 ← a ÷ b
so that the quotient is rounded towards 0? Interestingly IBM and ISO
Z←L∣R
Z is R-L×⌊ R÷L+L=0
R←Q∣P
R←P-(×P)×|Q×⌊|P÷Q
and return R if (×R)=×Q, or R+Q
otherwise.
That suggest that IBM rounds the quotient down towards minus infinity while ISO rounds
towards 0.
My naive view on remainder is that the nearest integer quotient shall be smaller in
magnitude and not smaller in value. Regarding your proposal (which is different from
both IBM and ISO) my concern is that may lead to different results for modulo N and
modulo N×1J0
Best Regards,
JÃŒrgen Sauermann

JÃŒrgen,
This message is being resent because last minute changes I made to CRS0.apl and CRS1.apl do not output the
data I intended. This message has corrected versions of those files attached. Please discard the old CRS0.apl and CRS1.apl files. The first line of output is the modulo basis, the second line is the calculated complete residue system values and the third line is the number of residues in the CRS on the previous line.
CRSOTST0.apl and CRSOTST1.apl are unchanged.
Also please find attached MOD_TEST.apl which compares the residues calculated by MODJ and the builtin residue function and reports discrepancies. The first column of output is the modulo basis, the second column the right argument to the functions, the third column the MODJ result and the fourth column is the builtin residue function result.
Regards
Fred
Hello JÃŒrgen,
SVN 964 moved us in the right direction but not completely out of the
woods. SVN 964 still exhibits errors. For instance
2J6 | 5J5
¯1J7
2J6 | ¯1J7
¯3J1
2J6 | ¯3J1
¯3J1
I found this and previous residue function errors using the attached APL
code files. The files with base name ending in '0' use the builtin residue
function. Those with base name ending in '1' use a residue function implemented
in APL. The files with base name beginning with 'CRSOTST' test if the order of
the complete residue system (CRS) equals the norm of the modulo basis. That
test fails for several modulo bases, 2J6 being one of them, using the builtin
residue function. No errors are detected with the APL implementation. The other files
can be used to plot the CRS for a given modulo basis where 'a' and 'b' in
'a + b * i' are limited to +15 to -15 range. A full screen terminal window is
needed to see the plot.
My APL implementation of the residue function is very close to what you
described in your previous email. Maybe comparing the two implementations will
give insight into why the builtin residue function fails for some modulo bases.
I make no assertion that my implementation is correct in all
aspects.
Regards,
Fred

Post by Juergen Sauermann
Hi Frederick,
- compute the quotient Q←B÷A,
- "round down" Q to the next (complex) integer Q1,
- return B - Q1×A
Q1 ← ⌊ Q i.e. use APL floor to round down Q
Q1 ← Complex( floor(Q.real(), floor(Q.imag()) ) i,e, use C/C++ floor() to round down Q.
In your 5J3 ∣ 14J5 example, the quotient is 2.5J¯0.5, which gives different results for the APL floor ⌊ and the C/C++ floor().
The APL floor ⌊2.5J¯0.5 is 3J¯1 (a somewhat dubious invention in the ISO standard on page 19, which I used up to
including SVN 963), while the C/C++ floor() is 2J¯1. The difference between the APL floor and the C/C++ floor is 1.0 which,
multiplied by the divisor, explains the differences that we see.
As of SVN 964 I have changed the residue function (∣) to use the C/C++ floor instead of the APL floor. The APL floor and
Ceiling functions (⌊ and ⌈) are still using the apparently broken definition in the ISO standard.
5J3 | 14J5
1J4
5J3 | 1J4
1J4
5J3 | 14J5
¯4J1
5J3 | 1J4
¯4J1
Best Regards,
/// JÃŒrgen

JÃŒrgen,
With gnu apl (svn 961 on Fedora 25, Intel(R) Core(TM) i7-6700
5J3 ∣ 14J5
1J4
5J3 | 1J4
¯4J1
5J3 | ¯4J1
¯4J1
The above result means that two elements in the complete residue system
(CSR) for mod 5J3 are equal, i.e. 1J4 = ¯4J1 mod 5J3, which is not
allowed. None of the elements of a CSR can be equal modulo the CSR's
basis.
Regards,
Fred

[Juergen Sauermann]

<html>
<head>
<meta content="text/html; charset=utf-8" http-equiv="Content-Type">
</head>
<body bgcolor="#FFFFFF" text="#000000">
<font face="Helvetica, Arial, sans-serif">Hi,<br>
<br>
I have changed <b>A∣B</b> to literally follow the paper pointed
out by Jay.<br>
The complex floor itself was already implemented like described in
the paper,<br>
but <b>A</b><b>∣</b><b>B</b> was not.<br>
<br>
Now (<b>SVN 969</b>) the complex <b>A∣B</b> is computed as<br>
<br>
<font face="Courier New, Courier, monospace"><b>Z←B-A×⌊B÷A+A=0</b></font><br>
<br>
without any attempts to improve the performance of the operation.<br>
<br>
The result in the <b>5J3 </b>modulus are now the same as in IBM
APL2 (and I suppose also in J)<br>
<br>
<font face="Courier New, Courier, monospace"><b>      5J3 ∣ 14J5
1J4 ¯4J1 </b><b><br>
</b><b>¯4J1 ¯4J1 ¯4J1</b></font><br>
<br>
I hope this finally fixed it. Thanks a lot to all that helped
fixing this bug.<br>
<br>
/// Jürgen<br>
</font><br>
<br>
<div class="moz-cite-prefix">On 06/23/2017 09:34 AM, Jay Foad wrote:<br>
</div>
<blockquote
cite="mid:CANd1uZnA3KXJB8-=***@mail.gmail.com"
type="cite">
<div dir="ltr">I urge you to read Eugene McDonnell's <a
moz-do-not-send="true"
href="http://www.jsoftware.com/papers/eem/complexfloor.htm">Complex
Floor</a>, which also discusses Residue. I believe the design
he comes up with in this paper was adopted more or less verbatim
in APL. Also bear in mind that Floor and Residue in APL have to
work well on all complex numbers, not <i>just</i> the Gaussian
integers.
<div><br>
</div>
<div>Jay.</div>
</div>
<div class="gmail_extra"><br>
<div class="gmail_quote">On 23 June 2017 at 01:42, Frederick
Pitts <span dir="ltr">&lt;<a moz-do-not-send="true"
href="mailto:***@comcast.net" target="_blank">***@comcast.net</a>&gt;</span>
wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0
.8ex;border-left:1px #ccc solid;padding-left:1ex">
<div>
<div>Hello Jürgen,</div>
<div><br>
</div>
<div> Some observations:</div>
<div><br>
</div>
<div>1) When performing a residue calculation on positive
integers, a straight-forward integer division with
remainder calculation</div>
<div>suffices. For example, 5 ∣ 13 is computed with 13 / 5
= 2 r 3 and so 5 ∣ 13 = 3 where 3 is in the complete
residue system</div>
<div>{ 0, 1, 2, 3, 4 }. When performing the calculation on
negative integers, one has to take advantage of the fact
that the</div>
<div>integer division quotient and remainder are not
unique in order to compute a residue that is in the
complete residue system.</div>
<div>For 5 ∣ ¯13, ¯13 / 5 = ¯2 r ¯3 where ¯3 is not in the
CRS. However, ¯13 / 5 = ¯3 r 2 where 3 is in the CSR.
The same concept applies Gaussian integers.</div>
<div><br>
</div>
<div>2) I suspect the decision to have the APL2 floor
function round toward negative infinity, instead of
toward zero,</div>
<div>was made based on the desire to save cpu cycles and
memory in the residue function code.</div>
<div><br>
</div>
<div>3) I read at least one math literature article
discussing Gaussian integer Euclidean division
algorithms, that recommended</div>
<div>rounding down to the nearest real and imaginary part
toward negative infinity. Unfortunately I cannot find</div>
<div>the article right now. I will continue to look for
it. None of the articles discussed using a complex
integer floor function.</div>
<div><br>
</div>
<div>4) The reason MOD_TEST.apl shows total disagreement
MODJ and the builtin residue function is that the
complex floor function code change in SVN 965 relocated
the CRS's on complex plane. Attached are
CRS0-CRS1-6J-6-SVN964.out</div>
<div>CRS0-CRS1-6J-6-SVN965.out. The first file contains a
CRS map for modulus ¯6J¯6 produced with the residue
function</div>
<div>followed by a map for the same modulus produced with
MODJ using SVN 964. The second file contains the same
maps</div>
<div>using SVN 965. Observe that for SVN 964 the residue
function CRS is in the bottom half of the complex plane,
but for SVN 965 it is in the top half. The CRS for the
MODJ function is in the bottom half in both SVN cases.</div>
<div>5)The complex floor code change did not help with the
issue that the builtin residue function is not
idempotent for all possible arguments and consequently
generates too many residues. See attached
CRSOTST0-SVN965.out. For a grid</div>
<div>of Gaussian integers with real and imaginary parts
ranging from ¯15 to 15, using every value with every
other value as modulus and second argument, there were
40 case where the order of CSR exceeded the modulus
norm. I think that</div>
<div>was the failure count with the previous SVN.</div>
<div><br>
</div>
<div> Sincerely, I think the complex floor and ceiling
functions should not be used by other functions even if
IBM and ISO</div>
<div>imply they are in their documentations. I'm not
seeing them used in the Gaussian integer literature.
Again, please correct me if I'm wrong.</div>
<div><br>
</div>
<div>Regards,</div>
<div><br>
</div>
<div>Fred</div>
<div>
<div class="h5">
<div><br>
</div>
<div>On Thu, 2017-06-22 at 18:08 +0200, Juergen
Sauermann wrote:</div>
<blockquote type="cite"> Hi again,<br>
<br>
sorry a small typo below. Lines 19/20 should read:<br>
<br>
<b>      (¯6J¯5 - 0J¯11) ÷ ¯6J¯6 </b><b><br>
</b><b>0J¯1</b><b><br>
</b><br>
/// Jürgen<br>
<br>
<div class="m_5990767214693122393moz-cite-prefix">On
06/22/2017 05:44 PM, Juergen Sauermann wrote:<br>
</div>
<blockquote type="cite"> <font face="Helvetica,
Arial, sans-serif">Hi Fred at al.,<br>
<br>
I have made another attempt to fix the residue
function, <b>SVN 965</b>.<br>
<br>
For complex <b>m∣b</b> It now rounds down the
real() and imag() parts of the quotient <b>q←b÷m</b>
and returns <b>b-q</b>.<br>
Instead of always rounding towards 0 or
-infinity, the rounding direction is now
(compared to the previous<br>
attempt) determined by the quadrant in which the
modulus <b>m</b> lies.<br>
</font><br>
There are still differences to the results
displayed by <font face="Helvetica, Arial,
sans-serif"><b>MOD_test.apl</b>, but I suppose
they are<br>
caused by that program. For example, the first
line of </font><font face="Helvetica, Arial,
sans-serif"><font face="Helvetica, Arial,
sans-serif"><b>MOD_test.apl</b>, says:<br>
<br>
</font><font face="Courier New, Courier,
monospace"><b>  LA    RA   MODJ   |</b><b><br>
</b><b>¯6J¯6 ¯6J¯5   0J¯11  0J1</b><br>
</font><br>
We have:<br>
<br>
<b>      (¯6J¯5 - 0J1) ÷ ¯6J¯6 </b><b><br>
</b><b>1</b><b><br>
</b><b>      (0J¯11 - 0J1) ÷ ¯6J¯6</b><b><br>
</b><b>1J1</b><br>
<br>
so both <b>0J¯11</b> and <b>0J1</b> are valid
remainders modulo <b>¯6J¯6</b>. However, the<br>
magnitude of </font><font face="Helvetica,
Arial, sans-serif"><b>0J¯11</b> (= <b>11</b>)
is larger than the magnitude of the divisor </font><font
face="Helvetica, Arial, sans-serif"><b><font
face="Helvetica, Arial, sans-serif"><b>¯6J¯6</b></font></b><font
face="Helvetica, Arial, sans-serif"> (= around
<b>8.4</b>).<br>
I suppose most people expect the remainder of
a division to be in some sense<br>
smaller than the divisor.<br>
<br>
Regarding Jay's idempotency requirement we now
have:<br>
<br>
 <b><font face="Courier New, Courier,
monospace">     f←{6J6|⍵}<br>
      f ¯3 ¯2 ¯3 ¯1 0 1 2 3<br>
3J6 4J6 3J6 5J6 0 ¯5J6 ¯4J6 ¯3J6<br>
      f f ¯3 ¯2 ¯3 ¯1 0 1 2 3<br>
3J6 4J6 3J6 5J6 0 ¯5J6 ¯4J6 ¯3J6</font></b><br>
<b><font face="Courier New, Courier,
monospace"><br>
      f←{5J3|⍵}<br>
      f ¯3 ¯2 ¯3 ¯1 0 1 2 3<br>
2J3 3J3 2J3 4J3 0 ¯2J5 ¯1J5 0J5<br>
      f f ¯3 ¯2 ¯3 ¯1 0 1 2 3<br>
2J3 3J3 2J3 4J3 0 ¯2J5 ¯1J5 0J5<br>
</font></b><br>
so at least the first modulus seems to work as
well. The result is still different<br>
from APL2 as reported by Jay, but I can't tell
why:<br>
<br>
IBM APL2:<br>
<br>
<font face="Courier New, Courier, monospace"><b>     
5J3 ∣ 14J5 1J4 ¯4J1</b></font></font></font><br>
<font face="Helvetica, Arial, sans-serif"><font
face="Helvetica, Arial, sans-serif"><font
face="Courier New, Courier, monospace"><b>¯4J1
</b></font></font></font><font
face="Helvetica, Arial, sans-serif"><font
face="Helvetica, Arial, sans-serif"><font
face="Courier New, Courier, monospace"><b>¯4J1
</b></font></font></font><font
face="Helvetica, Arial, sans-serif"><font
face="Helvetica, Arial, sans-serif"><font
face="Courier New, Courier, monospace"><b>¯4J1<br>
<br>
</b></font></font></font>GNU APL:<br>
<br>
<font face="Helvetica, Arial, sans-serif"><font
face="Helvetica, Arial, sans-serif"><font
face="Helvetica, Arial, sans-serif"><font
face="Helvetica, Arial, sans-serif"><font
face="Courier New, Courier, monospace"><b>     
5J3 ∣ 14J5 1J4 ¯4J1 </b><b><br>
</b><b>1J4 1J4 1J4</b></font><br>
<br>
</font></font>But both <b>1J4</b> and <b>¯4J1</b>
are valid remainders. Interestingly Jay's
idempotency requirement seems to<br>
be fulfilled by both the GNU APL and by IBM
APL2, so that that requirement alone does not
suffice<br>
to tell which result is correct.<br>
<br>
On the other hand this matter seems to be like
discussing if the square root of 4 is 2 or -2
with<br>
both answers being correct.<br>
<br>
Best Regards,<br>
Jürgen Sauermann<br>
<br>
<br>
</font><b><font face="Helvetica, Arial,
sans-serif"><br>
</font></b> </font>
<div class="m_5990767214693122393moz-cite-prefix">On
06/21/2017 10:25 PM, Frederick Pitts wrote:<br>
</div>
<blockquote type="cite">
<div>Jürgen,</div>
<div><br>
</div>
<div> The proposed change to DIVJ does not work
because 'q1' is a complex number, so the '×'
in '× q1' is the complex complement function,
not the sign function. I tried the proposed
change and every test fails.</div>
<div><br>
</div>
<div> I will try to hack DIVJ to use a floor
towards zero instead of towards minus infinity
for the real and imaginary</div>
<div>parts of the quotient and see what happens.</div>
<div><br>
</div>
<div> Correct me if I am wrong, but my mind set
is that the APL residue function has to
satisfy the following invariants:</div>
<div>1) The order of the complete residue system
(residue count) for a given modulo 'n' has to
equal the norm of 'n'.</div>
<div>2) And as Jay Foad so succinctly expressed
it, the residue function has to be idempotent
with respect to its right argument,</div>
<div> e.g., ( n | m ) = n | n | m .</div>
<div>regardless of the implementation of the
residue function.</div>
<div><br>
</div>
<div>Later,</div>
<div><br>
</div>
<div>Fred </div>
<div><br>
</div>
<div><br>
</div>
<div><br>
</div>
<div><br>
</div>
<div>On Wed, 2017-06-21 at 19:46 +0200, Juergen
Sauermann wrote:</div>
<blockquote type="cite"> <font face="Helvetica,
Arial, sans-serif">Hi Fred,<br>
<br>
I have a question about the <b>MOD_test.apl</b>
that you kindly provided.<br>
<br>
In function <b>DIVJ</b> on line 57 ff it
says:<br>
<br>
<font face="Courier New, Courier, monospace"><b>z
← q , a - b × q ← CMPLX ⌊ ( 9 11 ) ○ a ÷
b</b></font><br>
<br>
so the quotient is rounded down towards
minus infinity.<br>
<br>
I wonder if that should be something like<br>
<br>
<font face="Courier New, Courier, monospace"><b>z
← q , (× q1) × a - b × q ← CMPLX ⌊ ∣ 9
11 ○ q1 ← a ÷ b</b></font><br>
<br>
so that the quotient is rounded towards 0?
Interestingly IBM and ISO<br>
give different definitions for the residue
in terms of APL:<br>
<br>
IBM (language reference, page 227):<br>
<font face="Courier New, Courier, monospace"><b>Z←L∣R</b><b><br>
</b><b>Z is R</b><b>-</b><b>L×⌊ R÷L+L=0</b></font><br>
<br>
ISO (chapter 7.2.9 Residue): <br>
<font face="Courier New, Courier, monospace"><b>R←Q∣P</b><b><br>
</b><b>R←P-(×P)×|Q×⌊|P÷Q<br>
and return R if (×R)=×Q, or R+Q<br>
otherwise.<br>
</b></font> </font><br>
That suggest that IBM rounds the quotient down
towards minus infinity while ISO rounds<br>
 towards 0.<br>
<br>
My naive view on remainder is that the nearest
integer quotient shall be smaller in<br>
magnitude and not smaller in value. Regarding
your proposal (which is different from<br>
both IBM and ISO) my concern is that may lead
to different results for <b>modulo N</b> and<br>
<b>modulo</b> <b>N×1J0</b><br>
<br>
Best Regards,<br>
Jürgen Sauermann<br>
<br>
<br>
<div
class="m_5990767214693122393moz-cite-prefix">On
06/21/2017 03:08 AM, Frederick Pitts wrote:<br>
</div>
<blockquote type="cite">
<div><span style="white-space:normal">Jürgen,</span></div>
<div><span style="white-space:normal"><br>
</span></div>
<div><span style="white-space:normal"> This
message is being resent because last
minute changes I made to CRS0.apl and
CRS1.apl do not output the</span></div>
<div><span style="white-space:normal">data I
intended.  This message has corrected
versions of those files attached. 
Please discard the old CRS0.apl and
CRS1.apl files.  The first line of
output is the modulo basis, </span><span
style="white-space:normal">the second
line is the calculated complete residue
system values and the third line is the
number of residues in the CRS </span><span
style="white-space:normal">on the
previous line.</span></div>
<div><span style="white-space:normal"><br>
</span></div>
<div><span style="white-space:normal">
CRSOTST0.apl and CRSOTST1.apl are
unchanged.</span></div>
<div><span style="white-space:normal"><br>
</span></div>
<div><span style="white-space:normal"> Also
please find attached MOD_TEST.apl which
compares the residues calculated by MODJ
and the builtin residue function and
reports discrepancies.  The first column
of output is the modulo basis, the
second column the right argument to the
functions, the third column the MODJ
result and the fourth column is the
builtin residue function result.</span></div>
<div><span style="white-space:normal"><br>
</span></div>
<div><span style="white-space:normal">Regards</span></div>
<div><span style="white-space:normal"><br>
</span></div>
<div><span style="white-space:normal">Fred</span></div>
<div><br>
</div>
<div>Hello Jürgen,</div>
<pre> SVN 964 moved us in the right direction but not completely out of the</pre>
<pre>woods. SVN 964 still exhibits errors. For instance</pre>
<pre> 2J6 | 5J5</pre>
<pre>¯1J7</pre>
<pre> 2J6 | ¯1J7</pre>
<pre>¯3J1</pre>
<pre> 2J6 | ¯3J1</pre>
<pre>¯3J1</pre>
<pre> I found this and previous residue function errors using the attached APL</pre>
<pre>code files. The files with base name ending in '0' use the builtin residue</pre>
<pre>function. Those with base name ending in '1' use a residue function implemented</pre>
<pre>in APL. The files with base name beginning with 'CRSOTST' test if the order of</pre>
<pre>the complete residue system (CRS) equals the norm of the modulo basis. That</pre>
<pre>test fails for several modulo bases, 2J6 being one of them, using the builtin</pre>
<pre>residue function. No errors are detected with the APL implementation. The other files</pre>
<pre>can be used to plot the CRS for a given modulo basis where 'a' and 'b' in</pre>
<pre>'a + b * i' are limited to +15 to -15 range. A full screen terminal window is</pre>
<pre>needed to see the plot.</pre>
<pre> My APL implementation of the residue function is very close to what you</pre>
<pre>described in your previous email. Maybe comparing the two implementations will</pre>
<pre>give insight into why the builtin residue function fails for some modulo bases.</pre>
<pre> I make no assertion that my implementation is correct in all</pre>
<pre>aspects.</pre>
<pre>Regards,</pre>
<pre>Fred</pre>
<div>On Tue, 2017-06-20 at 14:14 +0200,
Juergen Sauermann wrote:</div>
<blockquote type="cite"> <font
face="Helvetica, Arial, sans-serif">Hi
Frederick,<br>
<br>
the algorithm for <b>A ∣ B</b> used in
GNU APL is this:<br>
<br>
<font face="Courier New, Courier,
monospace"><b>- compute the quotient Q</b><b>←</b><b>B÷A,</b><b><br>
</b><b>- "round down" Q to the next
(complex) integer</b><b> Q1,</b><b><br>
</b><b>- return B - Q1×A</b></font><b><br>
</b><br>
Now the problem seems to be what is
meant by "round down". There are two
candidates:<br>
<br>
<font face="Courier New, Courier,
monospace">  <b>Q1 ← ⌊
Q                             <wbr>        
    i.e. use APL floor</b><b> to
round down Q</b><b><br>
</b><b>  Q1 ← Complex( floor(Q.real(),
</b></font></font><font
face="Helvetica, Arial, sans-serif"><font
face="Courier New, Courier, monospace"><b>floor(Q.</b><b>imag</b><b>())
)   </b><b>i,e, use C/C++ floor()
to round down Q.</b><b><br>
</b></font><br>
In your  <b>5J3 ∣ 14J5</b> example, the
quotient is <b>2.5J¯0.5</b>, which
gives different results for the APL
floor <b>⌊</b> and the C/C++ floor().<br>
<br>
The APL floor <font face="Courier New,
Courier, monospace"><b>⌊</b></font></font><font
face="Helvetica, Arial, sans-serif"><font
face="Helvetica, Arial, sans-serif"><font
face="Courier New, Courier,
monospace"><b>2.5J¯0.5</b></font> is
</font><font face="Courier New, Courier,
monospace"><b>3J¯1</b></font> (a
somewhat dubious invention in the ISO
standard on page 19, which I used up to<br>
including <b>SVN 963</b>), while the
C/C++ floor() is</font><font
face="Helvetica, Arial, sans-serif"><font
face="Helvetica, Arial, sans-serif"><font
face="Courier New, Courier,
monospace"><b> 2J¯1</b></font></font>.
The difference between the APL floor and
the C/C++ floor is <b>1.0 </b>which,<br>
multiplied by the divisor, explains the
differences that we see.<br>
<br>
As of <b>SVN 964</b> I have changed the
residue function (<b>∣</b>) to use the
C/C++ floor instead of the APL floor.
The APL floor and<br>
Ceiling functions (<b>⌊</b> and <b>⌈</b>)
are still using the apparently broken
definition in the ISO standard.<br>
<br>
I hope this works better for you. At
least I am getting this in <b>SVN 964</b>:<br>
<br>
<font face="Courier New, Courier,
monospace"><b>      5J3 | 14J5</b><b><br>
</b><b>1J4</b><b><br>
</b><b>      5J3 | 1J4</b><b><br>
</b><b>1J4</b></font><b><br>
</b><br>
whereas <b>SVN 963</b> was giving:<br>
<br>
<font face="Courier New, Courier,
monospace"><b>      5J3 | 14J5</b><b><br>
</b><b>¯4J1</b><b><br>
</b><b>      5J3 | 1J4</b><b><br>
</b><b>¯4J1</b></font><br>
<br>
<br>
Best Regards,<br>
/// Jürgen<br>
<br>
</font><br>
<br>
<div
class="m_5990767214693122393moz-cite-prefix">On
06/19/2017 07:03 PM, Frederick Pitts
wrote:<br>
</div>
<blockquote type="cite">
<pre>Jürgen,

With gnu apl (svn 961 on Fedora 25, Intel(R) Core(TM) i7-6700
CPU), the residue function (∣) yields the following:

      5J3 ∣ 14J5
1J4
      5J3 | 1J4
¯4J1
      5J3 | ¯4J1
¯4J1
The above result means that two elements in the complete residue system
(CSR) for mod 5J3 are equal, i.e. 1J4 = ¯4J1 mod 5J3, which is not
allowed. None of the elements of a CSR can be equal modulo the CSR's
basis.

Regards,

Fred

</pre>
</blockquote>
<br>
</blockquote>
</blockquote>
<br>
</blockquote>
</blockquote>
<br>
</blockquote>
<br>
</blockquote>
</div>
</div>
</div>
</blockquote>
</div>
<br>
</div>
</blockquote>
<br>
</body>
</html>

[Frederick Pitts]

Hello JÃŒrgen,


SVN 969 on my platform (Fedora 25, Intel(R) Core(TM) i7-6700
CPU) 

      5J3 | 14J5 1J4 ¯4J1

gives

1J4 ¯4J1 ¯4J1


not


¯1J4 ¯4J1 ¯4J1

Regards,


Fred

    Hi,
      
      I have changed A∣B to literally follow the paper pointed
      out by Jay.
      The complex floor itself was already implemented like described
in
      the paper,
      but A∣B was not.
      
      Now (SVN 969) the complex A∣B is computed as
      
      Z←B-A×⌊B÷A+A=0
      
      without any attempts to improve the performance of the
operation.
      
      The result in the 5J3 modulus are now the same as in IBM
      APL2 (and I suppose also in J)
      
            5J3 ∣ 14J5
          1J4 ¯4J1 
        ¯4J1 ¯4J1 ¯4J1
      
      I hope this finally fixed it. Thanks a lot to all that helped
      fixing this bug.
      
      /// JÌrgen
    
    
    
    

      I urge you to read Eugene McDonnell's Complex
          Floor, which also discusses Residue. I believe the design
        he comes up with in this paper was adopted more or less
verbatim
        in APL. Also bear in mind that Floor and Residue in APL
have to
        work well on all complex numbers, not just the Gaussian
        integers.
        
        
        Jay.
      
      
        On 23 June 2017 at 01:42, Frederick
          

            
              Hello JÌrgen,
              
              
              
              
              1) When performing a residue calculation on
positive
                integers, a straight-forward integer division
with
                remainder calculation
              suffices. For example, 5 ∣ 13 is computed with 13 /
5
                = 2 r 3 and so 5 ∣ 13 = 3 where 3 is in the
complete
                residue system
              { 0, 1, 2, 3, 4 }. When performing the calculation
on
                negative integers, one has to take advantage of
the fact
                that the
              integer division quotient and remainder are not
                unique in order to compute a residue that is in
the
                complete residue system.
              For 5 ∣ ¯13, ¯13 / 5 = ¯2 r ¯3 where ¯3 is not in
the
                CRS. However, ¯13 / 5 = ¯3 r 2 where 3 is in the
CSR.
                The same concept applies Gaussian integers.
              
              
              2) I suspect the decision to have the APL2 floor
                function round toward negative infinity, instead
of
                toward zero,
              was made based on the desire to save cpu cycles and
                memory in the residue function code.
              
              
              3) I read at least one math literature article
                discussing Gaussian integer Euclidean division
                algorithms, that recommended
              rounding down to the nearest real and imaginary
part
                toward negative infinity. Unfortunately I cannot
find
              the article right now. I will continue to look for
                it. None of the articles discussed using a
complex
                integer floor function.
              
              
              4) The reason MOD_TEST.apl shows total disagreement
                MODJ and the builtin residue function is that the
                complex floor function code change in SVN 965
relocated
                the CRS's on complex plane. Attached are
                CRS0-CRS1-6J-6-SVN964.out
              CRS0-CRS1-6J-6-SVN965.out. The first file contains
a
                CRS map for modulus ¯6J¯6 produced with the
residue
                function
              followed by a map for the same modulus produced
with
                MODJ using SVN 964. The second file contains the
same
                maps
              using SVN 965. Observe that for SVN 964 the residue
                function CRS is in the bottom half of the complex
plane,
                but for SVN 965 it is in the top half. The CRS
for the
                MODJ function is in the bottom half in both SVN
cases.
              5)The complex floor code change did not help with
the
                issue that the builtin residue function is not
                idempotent for all possible arguments and
consequently
                generates too many residues. See attached
                CRSOTST0-SVN965.out. For a grid
              of Gaussian integers with real and imaginary parts
                ranging from ¯15 to 15, using every value with
every
                other value as modulus and second argument, there
were
                40 case where the order of CSR exceeded the
modulus
                norm. I think that
              was the failure count with the previous SVN.
              
              
               Sincerely, I think the complex floor and ceiling
                functions should not be used by other functions
even if
                IBM and ISO
              imply they are in their documentations. I'm not
                seeing them used in the Gaussian integer
literature.
                Again, please correct me if I'm wrong.
              
              
              Regards,
              
              
              Fred
              
                
                  
                  
                  On Thu, 2017-06-22 at 18:08 +0200, Juergen
                  

 Hi again,
                    
                    sorry a small typo below. Lines 19/20
                    
                          (¯6J¯5 - 0J¯11) ÷ ¯6J¯6 
                    0J¯1
                    
                    /// JÌrgen
                    
                    On
                      06/22/2017 05:44 PM, Juergen Sauermann
                    
                    

Post by Frederick Pitts
 Hi Fred at al.,
                        
                        I have made another attempt to fix
the residue
                        function, SVN 965.
                        
                        For complex m∣b It now rounds down
the
                        real() and imag() parts of the
quotient q←b÷m
                        and returns b-q.
                        Instead of always rounding towards 0
or
                        -infinity, the rounding direction is
now
                        (compared to the previous
                        attempt) determined by the quadrant
in which the
                        modulus m lies.
                      
                      There are still differences to the
results
                      displayed by MOD_test.apl, but I
suppose
                        they are
                        caused by that program. For example,
the first
                          
                          LA    RA   MODJ   |
                          ¯6J¯6 ¯6J¯5   0J¯11  0J1
                        
                        
                              (¯6J¯5 - 0J1) ÷ ¯6J¯6 
                        1
                              (0J¯11 - 0J1) ÷ ¯6J¯6
                        1J1
                        
                        so both 0J¯11 and 0J1 are valid
                        remainders modulo ¯6J¯6. However, the
                        magnitude of 0J¯11 (= 11)
                        is larger than the magnitude of the
divisor ¯6J¯6 (= around
                          8.4).
                          I suppose most people expect the
remainder of
                          a division to be in some sense
                          smaller than the divisor.
                          
                          Regarding Jay's idempotency
requirement we now
                          
                                f←{6J6|⍵}
                                    f ¯3 ¯2 ¯3 ¯1 0 1 2 3
                              3J6 4J6 3J6 5J6 0 ¯5J6 ¯4J6
¯3J6
                                    f f ¯3 ¯2 ¯3 ¯1 0 1 2 3
                              3J6 4J6 3J6 5J6 0 ¯5J6 ¯4J6
¯3J6
                          
                                    f←{5J3|⍵}
                                    f ¯3 ¯2 ¯3 ¯1 0 1 2 3
                              2J3 3J3 2J3 4J3 0 ¯2J5 ¯1J5 0J5
                                    f f ¯3 ¯2 ¯3 ¯1 0 1 2 3
                              2J3 3J3 2J3 4J3 0 ¯2J5 ¯1J5 0J5
                            
                          so at least the first modulus seems
to work as
                          well. The result is still different
                          from APL2 as reported by Jay, but I
can't tell
                          
                          
                               
                              5J3 ∣ 14J5 1J4 ¯4J1
                      ¯4J1
                            ¯4J1
                            ¯4J1
                              
                      
                           
                                  5J3 ∣ 14J5 1J4 ¯4J1 
                                1J4 1J4 1J4
                              
                            But both 1J4 and ¯4J1
                          are valid remainders. Interestingly
Jay's
                          idempotency requirement seems to
                          be fulfilled by both the GNU APL
and by IBM
                          APL2, so that that requirement
alone does not
                          suffice
                          to tell which result is correct.
                          
                          On the other hand this matter seems
to be like
                          discussing if the square root of 4
is 2 or -2
                          with
                          both answers being correct.
                          
                          Best Regards,
                          JÌrgen Sauermann
                          
                          
                        
                           
                      On
                        06/21/2017 10:25 PM, Frederick Pitts
                      
                      

                        JÌrgen,
                        
                        
                         The proposed change to DIVJ does
not work
                          because 'q1' is a complex number,
so the '×'
                          in '× q1' is the complex
complement function,
                          not the sign function. I tried
the proposed
                          change and every test fails.
                        
                        
                         I will try to hack DIVJ to use a
floor
                          towards zero instead of towards
minus infinity
                          for the real and imaginary
                        parts of the quotient and see what
happens.
                        
                        
                         Correct me if I am wrong, but my
mind set
                          is that the APL residue function
has to
                        1) The order of the complete
residue system
                          (residue count) for a given
modulo 'n' has to
                          equal the norm of 'n'.
                        2) And as Jay Foad so succinctly
expressed
                          it, the residue function has to
be idempotent
                          with respect to its right
argument,
                         e.g., ( n | m ) = n | n | m .
                        regardless of the implementation of
the
                          residue function.
                        
                        
                        Later,
                        
                        
                        Fred 
                        
                        
                        
                        
                        
                        
                        
                        
                        On Wed, 2017-06-21 at 19:46 +0200,
Juergen
                        

 Hi Fred,
                            
                            I have a question about the
MOD_test.apl
                            that you kindly provided.
                            
                            In function DIVJ on line 57
ff it
                            
                            z
                                ← q , a - b × q ← CMPLX ⌊
( 9 11 ) ○ a ÷
                                b
                            
                            so the quotient is rounded
down towards
                            minus infinity.
                            
                            I wonder if that should be
something like
                            
                            z
                                ← q , (× q1) × a - b × q
← CMPLX ⌊ ∣ 9
                                11 ○ q1 ← a ÷ b
                            
                            so that the quotient is
rounded towards 0?
                            Interestingly IBM and ISO
                            give different definitions
for the residue
                            
                            IBM (language reference, page
                            Z←L∣R
                              Z is R-L×⌊ R÷L+L=0
                            
                            ISO (chapter 7.2.9 Residue): 
                            R←Q∣P
                              R←P-(×P)×|Q×⌊|P÷Q
                                and return R if (×R)=×Q,
or R+Q
                                otherwise.
                               
                          That suggest that IBM rounds
the quotient down
                          towards minus infinity while
ISO rounds
                           towards 0.
                          
                          My naive view on remainder is
that the nearest
                          integer quotient shall be
smaller in
                          magnitude and not smaller in
value. Regarding
                          your proposal (which is
different from
                          both IBM and ISO) my concern is
that may lead
                          to different results for modulo
N and
                          modulo N×1J0
                          
                          Best Regards,
                          JÌrgen Sauermann
                          
                          
                          On
                            06/21/2017 03:08 AM,
                          
                          

                            JÌrgen,
                            
                              
                             This
                                message is being resent
because last
                                minute changes I made
to CRS0.apl and
                                CRS1.apl do not output
the
                            data I
                                intended.  This message
has corrected
                                versions of those files
attached. 
                                Please discard the old
CRS0.apl and
                                CRS1.apl files.  The
first line of
                                output is the modulo
basis, the second
                                line is the calculated
complete residue
                                system values and the
third line is the
                                number of residues in
the CRS on the
                                previous line.
                            
                              
                            
                                CRSOTST0.apl and
CRSOTST1.apl are
                                unchanged.
                            
                              
                             Also
                                please find attached
MOD_TEST.apl which
                                compares the residues
calculated by MODJ
                                and the builtin residue
function and
                                reports discrepancies. 
The first column
                                of output is the modulo
basis, the
                                second column the right
argument to the
                                functions, the third
column the MODJ
                                result and the fourth
column is the
                                builtin residue
function result.
                            
                              
                            Regards
                            
                              
                            Fred
                            
                            
                            Hello JÌrgen,
                             SVN 964 moved us in
the right direction but not completely out of the
                            woods.  SVN 964 still
exhibits errors.  For instance
                                  2J6 | 5J5
                            ¯1J7
                                  2J6 | ¯1J7
                            ¯3J1
                                  2J6 | ¯3J1
                            ¯3J1
                             I found this and
previous residue function errors using the attached APL
                            code files.  The files with
base name ending in '0' use the builtin residue
                            function.  Those with base
name ending in '1' use a residue function implemented
                            in APL.  The files with
base name beginning with 'CRSOTST' test if the order of
                            the complete residue system
(CRS) equals the norm of the modulo basis.  That
                            test fails for several
modulo bases, 2J6 being one of them, using the builtin
                            residue function. No errors
are detected with the APL implementation.  The other
files
                            can be used to plot the CRS
for a given modulo basis where 'a' and 'b' in
                            'a + b * i' are limited to
+15 to -15 range.  A full screen terminal window is
                            needed to see the plot.
                             My APL
implementation of the residue function is very close to
what you
                            described in your previous
email.  Maybe comparing the two implementations will
                            give insight into why the
builtin residue function fails for some modulo bases.
                             I make no assertion
that my implementation is correct in all
                            aspects.
                            Regards,
                            Fred
                            On Tue, 2017-06-20 at 14:14
+0200,
                            

 Hi
                                Frederick,
                                
                                the algorithm for A ∣
B used in
                                
                                - compute the
quotient Q←B÷A,
                                  - "round down" Q to
the next
                                    (complex) integer
Q1,
                                  - return B - Q1×A
                                
                                Now the problem seems
to be what is
                                meant by "round
down". There are two
                                
                                  Q1 ← ⌊
                                    Q                
                     
                                        i.e. use APL
floor to
                                    round down Q
                                    Q1 ← Complex(
floor(Q.real(),
                                  floor(Q.imag())
                                    )   i,e, use
C/C++ floor()
                                    to round down Q.
                                  
                                In your  5J3 ∣ 14J5
example, the
                                quotient is 2.5J¯0.5,
which
                                gives different
results for the APL
                                floor ⌊ and the C/C++
floor().
                                
                                The APL floor
⌊2.5J¯0.5 is
                                3J¯1 (a
                                somewhat dubious
invention in the ISO
                                standard on page 19,
which I used up to
                                including SVN 963),
while the
                                C/C++ floor() is
2J¯1.
                                The difference
between the APL floor and
                                the C/C++ floor is
1.0 which,
                                multiplied by the
divisor, explains the
                                differences that we
see.
                                
                                As of SVN 964 I have
changed the
                                residue function (∣)
to use the
                                C/C++ floor instead
of the APL floor.
                                The APL floor and
                                Ceiling functions (⌊
and ⌈)
                                are still using the
apparently broken
                                definition in the ISO
standard.
                                
                                I hope this works
better for you. At
                                least I am getting
                                
                                      5J3 | 14J5
                                  1J4
                                        5J3 | 1J4
                                  1J4
                                
                                whereas SVN 963 was
                                
                                      5J3 | 14J5
                                  ¯4J1
                                        5J3 | 1J4
                                  ¯4J1
                                
                                
                                Best Regards,
                                /// JÌrgen
                                
                              
                              
                              On
                                06/19/2017 07:03 PM,
Frederick Pitts
                              
                              

                                JÌrgen,
With gnu apl (svn 961 on Fedora 25, Intel(R)
Core(TM) i7-6700
CPU), the residue function (∣) yields the
      5J3 ∣ 14J5
1J4
      5J3 | 1J4
¯4J1
      5J3 | ¯4J1
¯4J1
The above result means that two elements in the
complete residue system
(CSR) for mod 5J3 are equal, i.e. 1J4 = ¯4J1 mod
5J3, which is not
allowed.  None of the elements of a CSR can be
equal modulo the CSR's
basis.
Regards,
Fred
                              

                              
                            

                          

                          
                        

                      

                      
                    

                    
                  

                
              
            
          

        
        
      
    

    
  

[Juergen Sauermann]

[Juergen Sauermann]

<html>
<head>
<meta content="text/html; charset=utf-8" http-equiv="Content-Type">
</head>
<body bgcolor="#FFFFFF" text="#000000">
<font face="Helvetica, Arial, sans-serif">Hi,<br>
<br>
please disregard my comment on <b>bif_floor()</b> below.<br>
<br>
The proper line should be this (note the <font face="Courier New,
Courier, monospace"><b>-</b></font> instead of <font
face="Courier New, Courier, monospace"><b>+</b></font>):<br>
</font><br>
<font face="Helvetica, Arial, sans-serif"><font face="Courier New,
Courier, monospace"><b>if (D &lt; 1.0 - Workspace::get_CT())  
return zv(Z, fr, fi);<br>
<br>
</b><font face="Helvetica, Arial, sans-serif">With that change
my testcases (which contain the examples of both the ISO
standard and<br>
the IBM language reference) are now properly working again.
Fixed in <b>SVN 970</b>.<br>
<br>
/// Jürgen<br>
<br>
</font><b><br>
</b></font></font>
<div class="moz-cite-prefix">On 06/23/2017 09:02 PM, Juergen
Sauermann wrote:<br>
</div>
<blockquote
cite="mid:a8574933-7e73-d88e-95c2-***@t-online.de"
type="cite">
<meta content="text/html; charset=utf-8" http-equiv="Content-Type">
<font face="Helvetica, Arial, sans-serif">Hi Frederick,<br>
<br>
I suppose that this is caused by a rounding error just before
the complex floor.<br>
I have attached a debug version of <b>ComplexCell.cc</b> that
prints every partial result of the computation.<br>
<br>
If I run it then I get:<br>
<br>
<font face="Courier New, Courier, monospace"><b>      5J3 | 14J5</b><b><br>
</b><b>modulus (A) is: (5,3)</b><b><br>
</b><b>A=0 is: (0,0)</b><b><br>
</b><b>A+A=0 is: (5,3)</b><b><br>
</b><b>B÷A+A=0 is: (2.5,-0.5)</b><b><br>
</b><b>⌊B÷A+A=0 is: (3,-1)</b><b><br>
</b><b>A×⌊B÷A+A=0 is: (18,4)</b><b><br>
</b><b>B-A×⌊B÷A+A=0 is: (-4,1)</b><b><br>
</b><b>¯4J1</b></font><br>
<br>
However if I use a slightly smaller <b>B</b> (kind of
simulating a rounding error) then I get:<br>
<br>
<font face="Courier New, Courier, monospace"><b>      5J3 |
14J4.999999999</b><b><br>
</b><b>modulus (A) is: (5,3)</b><b><br>
</b><b>A=0 is: (0,0)</b><b><br>
</b><b>A+A=0 is: (5,3)</b><b><br>
</b><b>B÷A+A=0 is: (2.4999999999118,-0.50000000014706)</b><b><br>
</b><b>⌊B÷A+A=0 is: (2,-1)</b><b><br>
</b><b>A×⌊B÷A+A=0 is: (13,1)</b><b><br>
</b><b>B-A×⌊B÷A+A=0 is: (1,3.999999999)</b><b><br>
</b><b>1J3.999999999</b></font><br>
<br>
I suppose that is what happens on your machine but not on mine.<br>
<br>
<br>
You may also want to try out the following. In <b>ComplexCell::bif_floor()</b>
around line <b>23</b><b>1 ff</b> it says:<br>
<br>
<font face="Courier New, Courier, monospace"><b>   // ISO: if D
is tolerantly less than 1 return fr + 0J1×fi</b><b><br>
</b><b>   // IBM: if D is            less than 1 return fr +
0J1×fi</b><b><br>
</b><b>   // However, ISO examples follow IBM (and so do we)</b><b><br>
</b><b>   //</b><b><br>
</b><b>// if (D &lt; 1.0 + Workspace::get_CT())   return zv(Z,
fr, fi);   // ISO</b><b><br>
</b><b>   if (D &lt; 1.0)    return zv(Z, fr, fi);   // IBM
and examples in ISO</b><b><br>
</b></font><br>
If you uncomment the first if statement then you get the ISO
variant of <b>bif_floor() </b>while otherwise you<br>
get the IBM variant (which is also the one described in the
McDonnel paper). It could be that the ISO variant<br>
works better for the <b>bif_residue()</b> function, but it
causes problems in other places. If uncommenting the <b>if</b><br>
line should fix your problem, then I can create two variants of
<b>bif_floor()</b>: one for <b>bif_residue()</b> and one<br>
for the rest.<br>
<br>
Best Regards,<br>
Jürgen Sauermann<br>
<br>
</font><br>
<div class="moz-cite-prefix">On 06/23/2017 07:31 PM, Frederick
Pitts wrote:<br>
</div>
<blockquote cite="mid:***@comcast.net"
type="cite">
<meta content="text/html; charset=utf-8"
http-equiv="Content-Type">
<div><span style="font-family: Helvetica, Arial, sans-serif;">Hello
Jürgen,</span></div>
<div><span style="font-family: Helvetica, Arial, sans-serif;"><br>
</span></div>
<div><span style="font-family: Helvetica, Arial, sans-serif;">
SVN 969 on my platform (Fedora 25, </span>Intel(R) Core(TM)
i7-6700 CPU) </div>
<blockquote type="cite"> </blockquote>
<div><span style="font-family: Helvetica, Arial, sans-serif;"><br>
</span></div>
<span style="font-family: Helvetica, Arial, sans-serif;">      5J3
| 14J5 1J4 ¯4J1</span>
<div><font face="Helvetica, Arial, sans-serif"><br>
</font></div>
<div><font face="Helvetica, Arial, sans-serif">gives</font></div>
<div><font face="Helvetica, Arial, sans-serif"><br>
</font>
<div><span style="font-family: Helvetica, Arial, sans-serif;">1J4
¯4J1 ¯4J1</span></div>
<div><font face="Helvetica, Arial, sans-serif"><br>
</font></div>
<div><font face="Helvetica, Arial, sans-serif">not</font></div>
<div><font face="Helvetica, Arial, sans-serif"><br>
</font></div>
<div>¯<span style="font-family: Helvetica, Arial, sans-serif;">1J4
¯4J1 ¯4J1</span></div>
<div><font face="Helvetica, Arial, sans-serif"><br>
</font></div>
<div><font face="Helvetica, Arial, sans-serif">Regards,</font></div>
<div><font face="Helvetica, Arial, sans-serif"><br>
</font></div>
<div><font face="Helvetica, Arial, sans-serif">Fred<br>
</font>
<div><br>
</div>
<div>On Fri, 2017-06-23 at 17:38 +0200, Juergen Sauermann
wrote:</div>
<blockquote type="cite"> <font face="Helvetica, Arial,
sans-serif">Hi,<br>
<br>
I have changed <b>A∣B</b> to literally follow the paper
pointed out by Jay.<br>
The complex floor itself was already implemented like
described in the paper,<br>
but <b>A</b><b>∣</b><b>B</b> was not.<br>
<br>
Now (<b>SVN 969</b>) the complex <b>A∣B</b> is computed
as<br>
<br>
<font face="Courier New, Courier, monospace"><b>Z←B-A×⌊B÷A+A=0</b></font><br>
<br>
without any attempts to improve the performance of the
operation.<br>
<br>
The result in the <b>5J3 </b>modulus are now the same
as in IBM APL2 (and I suppose also in J)<br>
<br>
<font face="Courier New, Courier, monospace"><b>     
5J3 ∣ 14J5 1J4 ¯4J1 </b><b><br>
</b><b>¯4J1 ¯4J1 ¯4J1</b></font><br>
<br>
I hope this finally fixed it. Thanks a lot to all that
helped fixing this bug.<br>
<br>
/// Jürgen<br>
</font><br>
<br>
<div class="moz-cite-prefix">On 06/23/2017 09:34 AM, Jay
Foad wrote:<br>
</div>
<blockquote
cite="mid:CANd1uZnA3KXJB8-=***@mail.gmail.com"
type="cite">
<div dir="ltr">I urge you to read Eugene McDonnell's <a
moz-do-not-send="true"
href="http://www.jsoftware.com/papers/eem/complexfloor.htm">Complex
Floor</a>, which also discusses Residue. I believe
the design he comes up with in this paper was adopted
more or less verbatim in APL. Also bear in mind that
Floor and Residue in APL have to work well on all
complex numbers, not <i>just</i> the Gaussian
integers.
<div><br>
</div>
<div>Jay.</div>
</div>
<div class="gmail_extra"><br>
<div class="gmail_quote">On 23 June 2017 at 01:42,
Frederick Pitts <span dir="ltr">&lt;<a
moz-do-not-send="true"
href="mailto:***@comcast.net"
target="_blank">***@comcast.net</a>&gt;</span>
wrote:<br>
<blockquote type="cite">
<div>
<div>Hello Jürgen,</div>
<div><br>
</div>
<div> Some observations:</div>
<div><br>
</div>
<div>1) When performing a residue calculation on
positive integers, a straight-forward integer
division with remainder calculation</div>
<div>suffices. For example, 5 ∣ 13 is computed
with 13 / 5 = 2 r 3 and so 5 ∣ 13 = 3 where 3
is in the complete residue system</div>
<div>{ 0, 1, 2, 3, 4 }. When performing the
calculation on negative integers, one has to
take advantage of the fact that the</div>
<div>integer division quotient and remainder are
not unique in order to compute a residue that
is in the complete residue system.</div>
<div>For 5 ∣ ¯13, ¯13 / 5 = ¯2 r ¯3 where ¯3 is
not in the CRS. However, ¯13 / 5 = ¯3 r 2
where 3 is in the CSR. The same concept
applies Gaussian integers.</div>
<div><br>
</div>
<div>2) I suspect the decision to have the APL2
floor function round toward negative infinity,
instead of toward zero,</div>
<div>was made based on the desire to save cpu
cycles and memory in the residue function
code.</div>
<div><br>
</div>
<div>3) I read at least one math literature
article discussing Gaussian integer Euclidean
division algorithms, that recommended</div>
<div>rounding down to the nearest real and
imaginary part toward negative infinity.
Unfortunately I cannot find</div>
<div>the article right now. I will continue to
look for it. None of the articles discussed
using a complex integer floor function.</div>
<div><br>
</div>
<div>4) The reason MOD_TEST.apl shows total
disagreement MODJ and the builtin residue
function is that the complex floor function
code change in SVN 965 relocated the CRS's on
complex plane. Attached are
CRS0-CRS1-6J-6-SVN964.out</div>
<div>CRS0-CRS1-6J-6-SVN965.out. The first file
contains a CRS map for modulus ¯6J¯6 produced
with the residue function</div>
<div>followed by a map for the same modulus
produced with MODJ using SVN 964. The second
file contains the same maps</div>
<div>using SVN 965. Observe that for SVN 964 the
residue function CRS is in the bottom half of
the complex plane, but for SVN 965 it is in
the top half. The CRS for the MODJ function is
in the bottom half in both SVN cases.</div>
<div>5)The complex floor code change did not
help with the issue that the builtin residue
function is not idempotent for all possible
arguments and consequently generates too many
residues. See attached CRSOTST0-SVN965.out.
For a grid</div>
<div>of Gaussian integers with real and
imaginary parts ranging from ¯15 to 15, using
every value with every other value as modulus
and second argument, there were 40 case where
the order of CSR exceeded the modulus norm. I
think that</div>
<div>was the failure count with the previous
SVN.</div>
<div><br>
</div>
<div> Sincerely, I think the complex floor and
ceiling functions should not be used by other
functions even if IBM and ISO</div>
<div>imply they are in their documentations. I'm
not seeing them used in the Gaussian integer
literature. Again, please correct me if I'm
wrong.</div>
<div><br>
</div>
<div>Regards,</div>
<div><br>
</div>
<div>Fred</div>
<div>
<div class="h5">
<div><br>
</div>
<div>On Thu, 2017-06-22 at 18:08 +0200,
Juergen Sauermann wrote:</div>
<blockquote type="cite"> Hi again,<br>
<br>
sorry a small typo below. Lines 19/20
should read:<br>
<br>
<b>      (¯6J¯5 - 0J¯11) ÷ ¯6J¯6 </b><b><br>
</b><b>0J¯1</b><b><br>
</b><br>
/// Jürgen<br>
<br>
<div
class="m_5990767214693122393moz-cite-prefix">On
06/22/2017 05:44 PM, Juergen Sauermann
wrote:<br>
</div>
<blockquote type="cite"> <font
face="Helvetica, Arial, sans-serif">Hi
Fred at al.,<br>
<br>
I have made another attempt to fix the
residue function, <b>SVN 965</b>.<br>
<br>
For complex <b>m∣b</b> It now rounds
down the real() and imag() parts of
the quotient <b>q←b÷m</b> and returns
<b>b-q</b>.<br>
Instead of always rounding towards 0
or -infinity, the rounding direction
is now (compared to the previous<br>
attempt) determined by the quadrant in
which the modulus <b>m</b> lies.<br>
</font><br>
There are still differences to the
results displayed by <font
face="Helvetica, Arial, sans-serif"><b>MOD_test.apl</b>,
but I suppose they are<br>
caused by that program. For example,
the first line of </font><font
face="Helvetica, Arial, sans-serif"><font
face="Helvetica, Arial, sans-serif"><b>MOD_test.apl</b>,
says:<br>
<br>
</font><font face="Courier New,
Courier, monospace"><b>  LA    RA  
MODJ   |</b><b><br>
</b><b>¯6J¯6 ¯6J¯5   0J¯11  0J1</b><br>
</font><br>
We have:<br>
<br>
<b>      (¯6J¯5 - 0J1) ÷ ¯6J¯6 </b><b><br>
</b><b>1</b><b><br>
</b><b>      (0J¯11 - 0J1) ÷ ¯6J¯6</b><b><br>
</b><b>1J1</b><br>
<br>
so both <b>0J¯11</b> and <b>0J1</b>
are valid remainders modulo <b>¯6J¯6</b>.
However, the<br>
magnitude of </font><font
face="Helvetica, Arial, sans-serif"><b>0J¯11</b>
(= <b>11</b>) is larger than the
magnitude of the divisor </font><font
face="Helvetica, Arial, sans-serif"><b><font
face="Helvetica, Arial,
sans-serif"><b>¯6J¯6</b></font></b><font
face="Helvetica, Arial, sans-serif">
(= around <b>8.4</b>).<br>
I suppose most people expect the
remainder of a division to be in
some sense<br>
smaller than the divisor.<br>
<br>
Regarding Jay's idempotency
requirement we now have:<br>
<br>
 <b><font face="Courier New,
Courier, monospace">    
f←{6J6|⍵}<br>
      f ¯3 ¯2 ¯3 ¯1 0 1 2 3<br>
3J6 4J6 3J6 5J6 0 ¯5J6 ¯4J6 ¯3J6<br>
      f f ¯3 ¯2 ¯3 ¯1 0 1 2 3<br>
3J6 4J6 3J6 5J6 0 ¯5J6 ¯4J6 ¯3J6</font></b><br>
<b><font face="Courier New, Courier,
monospace"><br>
      f←{5J3|⍵}<br>
      f ¯3 ¯2 ¯3 ¯1 0 1 2 3<br>
2J3 3J3 2J3 4J3 0 ¯2J5 ¯1J5 0J5<br>
      f f ¯3 ¯2 ¯3 ¯1 0 1 2 3<br>
2J3 3J3 2J3 4J3 0 ¯2J5 ¯1J5 0J5<br>
</font></b><br>
so at least the first modulus seems
to work as well. The result is still
different<br>
from APL2 as reported by Jay, but I
can't tell why:<br>
<br>
IBM APL2:<br>
<br>
<font face="Courier New, Courier,
monospace"><b>      5J3 ∣ 14J5 1J4
¯4J1</b></font></font></font><br>
<font face="Helvetica, Arial,
sans-serif"><font face="Helvetica,
Arial, sans-serif"><font
face="Courier New, Courier,
monospace"><b>¯4J1 </b></font></font></font><font
face="Helvetica, Arial, sans-serif"><font
face="Helvetica, Arial, sans-serif"><font
face="Courier New, Courier,
monospace"><b>¯4J1 </b></font></font></font><font
face="Helvetica, Arial, sans-serif"><font
face="Helvetica, Arial, sans-serif"><font
face="Courier New, Courier,
monospace"><b>¯4J1<br>
<br>
</b></font></font></font>GNU APL:<br>
<br>
<font face="Helvetica, Arial,
sans-serif"><font face="Helvetica,
Arial, sans-serif"><font
face="Helvetica, Arial,
sans-serif"><font face="Helvetica,
Arial, sans-serif"><font
face="Courier New, Courier,
monospace"><b>      5J3 ∣ 14J5
1J4 ¯4J1 </b><b><br>
</b><b>1J4 1J4 1J4</b></font><br>
<br>
</font></font>But both <b>1J4</b>
and <b>¯4J1</b> are valid
remainders. Interestingly Jay's
idempotency requirement seems to<br>
be fulfilled by both the GNU APL and
by IBM APL2, so that that
requirement alone does not suffice<br>
to tell which result is correct.<br>
<br>
On the other hand this matter seems
to be like discussing if the square
root of 4 is 2 or -2 with<br>
both answers being correct.<br>
<br>
Best Regards,<br>
Jürgen Sauermann<br>
<br>
<br>
</font><b><font face="Helvetica,
Arial, sans-serif"><br>
</font></b> </font>
<div
class="m_5990767214693122393moz-cite-prefix">On
06/21/2017 10:25 PM, Frederick Pitts
wrote:<br>
</div>
<blockquote type="cite">
<div>Jürgen,</div>
<div><br>
</div>
<div> The proposed change to DIVJ does
not work because 'q1' is a complex
number, so the '×' in '× q1' is the
complex complement function, not the
sign function. I tried the proposed
change and every test fails.</div>
<div><br>
</div>
<div> I will try to hack DIVJ to use a
floor towards zero instead of
towards minus infinity for the real
and imaginary</div>
<div>parts of the quotient and see
what happens.</div>
<div><br>
</div>
<div> Correct me if I am wrong, but my
mind set is that the APL residue
function has to satisfy the
following invariants:</div>
<div>1) The order of the complete
residue system (residue count) for a
given modulo 'n' has to equal the
norm of 'n'.</div>
<div>2) And as Jay Foad so succinctly
expressed it, the residue function
has to be idempotent with respect to
its right argument,</div>
<div> e.g., ( n | m ) = n | n | m .</div>
<div>regardless of the implementation
of the residue function.</div>
<div><br>
</div>
<div>Later,</div>
<div><br>
</div>
<div>Fred </div>
<div><br>
</div>
<div><br>
</div>
<div><br>
</div>
<div><br>
</div>
<div>On Wed, 2017-06-21 at 19:46
+0200, Juergen Sauermann wrote:</div>
<blockquote type="cite"> <font
face="Helvetica, Arial,
sans-serif">Hi Fred,<br>
<br>
I have a question about the <b>MOD_test.apl</b>
that you kindly provided.<br>
<br>
In function <b>DIVJ</b> on line
57 ff it says:<br>
<br>
<font face="Courier New, Courier,
monospace"><b>z ← q , a - b × q
← CMPLX ⌊ ( 9 11 ) ○ a ÷ b</b></font><br>
<br>
so the quotient is rounded down
towards minus infinity.<br>
<br>
I wonder if that should be
something like<br>
<br>
<font face="Courier New, Courier,
monospace"><b>z ← q , (× q1) × a
- b × q ← CMPLX ⌊ ∣ 9 11 ○ q1
← a ÷ b</b></font><br>
<br>
so that the quotient is rounded
towards 0? Interestingly IBM and
ISO<br>
give different definitions for the
residue in terms of APL:<br>
<br>
IBM (language reference, page
227):<br>
<font face="Courier New, Courier,
monospace"><b>Z←L∣R</b><b><br>
</b><b>Z is R</b><b>-</b><b>L×⌊
R÷L+L=0</b></font><br>
<br>
ISO (chapter 7.2.9 Residue): <br>
<font face="Courier New, Courier,
monospace"><b>R←Q∣P</b><b><br>
</b><b>R←P-(×P)×|Q×⌊|P÷Q<br>
and return R if (×R)=×Q, or
R+Q<br>
otherwise.<br>
</b></font> </font><br>
That suggest that IBM rounds the
quotient down towards minus infinity
while ISO rounds<br>
 towards 0.<br>
<br>
My naive view on remainder is that
the nearest integer quotient shall
be smaller in<br>
magnitude and not smaller in value.
Regarding your proposal (which is
different from<br>
both IBM and ISO) my concern is that
may lead to different results for <b>modulo
N</b> and<br>
<b>modulo</b> <b>N×1J0</b><br>
<br>
Best Regards,<br>
Jürgen Sauermann<br>
<br>
<br>
<div
class="m_5990767214693122393moz-cite-prefix">On
06/21/2017 03:08 AM, Frederick
Pitts wrote:<br>
</div>
<blockquote type="cite">
<div><span
style="white-space:normal">Jürgen,</span></div>
<div><span
style="white-space:normal"><br>
</span></div>
<div><span
style="white-space:normal">
This message is being resent
because last minute changes I
made to CRS0.apl and CRS1.apl
do not output the</span></div>
<div><span
style="white-space:normal">data
I intended.  This message has
corrected versions of those
files attached.  Please
discard the old CRS0.apl and
CRS1.apl files.  The first
line of output is the modulo
basis, </span><span
style="white-space:normal">the
second line is the calculated
complete residue system values
and the third line is the
number of residues in the CRS </span><span
style="white-space:normal">on
the previous line.</span></div>
<div><span
style="white-space:normal"><br>
</span></div>
<div><span
style="white-space:normal">
CRSOTST0.apl and CRSOTST1.apl
are unchanged.</span></div>
<div><span
style="white-space:normal"><br>
</span></div>
<div><span
style="white-space:normal">
Also please find attached
MOD_TEST.apl which compares
the residues calculated by
MODJ and the builtin residue
function and reports
discrepancies.  The first
column of output is the modulo
basis, the second column the
right argument to the
functions, the third column
the MODJ result and the fourth
column is the builtin residue
function result.</span></div>
<div><span
style="white-space:normal"><br>
</span></div>
<div><span
style="white-space:normal">Regards</span></div>
<div><span
style="white-space:normal"><br>
</span></div>
<div><span
style="white-space:normal">Fred</span></div>
<div><br>
</div>
<div>Hello Jürgen,</div>
<pre> SVN 964 moved us in the right direction but not completely out of the</pre>
<pre>woods. SVN 964 still exhibits errors. For instance</pre>
<pre> 2J6 | 5J5</pre>
<pre>¯1J7</pre>
<pre> 2J6 | ¯1J7</pre>
<pre>¯3J1</pre>
<pre> 2J6 | ¯3J1</pre>
<pre>¯3J1</pre>
<pre> I found this and previous residue function errors using the attached APL</pre>
<pre>code files. The files with base name ending in '0' use the builtin residue</pre>
<pre>function. Those with base name ending in '1' use a residue function implemented</pre>
<pre>in APL. The files with base name beginning with 'CRSOTST' test if the order of</pre>
<pre>the complete residue system (CRS) equals the norm of the modulo basis. That</pre>
<pre>test fails for several modulo bases, 2J6 being one of them, using the builtin</pre>
<pre>residue function. No errors are detected with the APL implementation. The other files</pre>
<pre>can be used to plot the CRS for a given modulo basis where 'a' and 'b' in</pre>
<pre>'a + b * i' are limited to +15 to -15 range. A full screen terminal window is</pre>
<pre>needed to see the plot.</pre>
<pre> My APL implementation of the residue function is very close to what you</pre>
<pre>described in your previous email. Maybe comparing the two implementations will</pre>
<pre>give insight into why the builtin residue function fails for some modulo bases.</pre>
<pre> I make no assertion that my implementation is correct in all</pre>
<pre>aspects.</pre>
<pre>Regards,</pre>
<pre>Fred</pre>
<div>On Tue, 2017-06-20 at 14:14
+0200, Juergen Sauermann wrote:</div>
<blockquote type="cite"> <font
face="Helvetica, Arial,
sans-serif">Hi Frederick,<br>
<br>
the algorithm for <b>A ∣ B</b>
used in GNU APL is this:<br>
<br>
<font face="Courier New,
Courier, monospace"><b>-
compute the quotient Q</b><b>←</b><b>B÷A,</b><b><br>
</b><b>- "round down" Q to
the next (complex) integer</b><b>
Q1,</b><b><br>
</b><b>- return B - Q1×A</b></font><b><br>
</b><br>
Now the problem seems to be
what is meant by "round down".
There are two candidates:<br>
<br>
<font face="Courier New,
Courier, monospace">  <b>Q1
← ⌊
Q                             <wbr>        
    i.e. use APL floor</b><b>
to round down Q</b><b><br>
</b><b>  Q1 ← Complex(
floor(Q.real(), </b></font></font><font
face="Helvetica, Arial,
sans-serif"><font
face="Courier New, Courier,
monospace"><b>floor(Q.</b><b>imag</b><b>())
)   </b><b>i,e, use C/C++
floor() to round down Q.</b><b><br>
</b></font><br>
In your  <b>5J3 ∣ 14J5</b>
example, the quotient is <b>2.5J¯0.5</b>,
which gives different results
for the APL floor <b>⌊</b>
and the C/C++ floor().<br>
<br>
The APL floor <font
face="Courier New, Courier,
monospace"><b>⌊</b></font></font><font
face="Helvetica, Arial,
sans-serif"><font
face="Helvetica, Arial,
sans-serif"><font
face="Courier New,
Courier, monospace"><b>2.5J¯0.5</b></font>
is </font><font
face="Courier New, Courier,
monospace"><b>3J¯1</b></font>
(a somewhat dubious invention
in the ISO standard on page
19, which I used up to<br>
including <b>SVN 963</b>),
while the C/C++ floor() is</font><font
face="Helvetica, Arial,
sans-serif"><font
face="Helvetica, Arial,
sans-serif"><font
face="Courier New,
Courier, monospace"><b>
2J¯1</b></font></font>.
The difference between the APL
floor and the C/C++ floor is <b>1.0
</b>which,<br>
multiplied by the divisor,
explains the differences that
we see.<br>
<br>
As of <b>SVN 964</b> I have
changed the residue function (<b>∣</b>)
to use the C/C++ floor instead
of the APL floor. The APL
floor and<br>
Ceiling functions (<b>⌊</b>
and <b>⌈</b>) are still using
the apparently broken
definition in the ISO
standard.<br>
<br>
I hope this works better for
you. At least I am getting
this in <b>SVN 964</b>:<br>
<br>
<font face="Courier New,
Courier, monospace"><b>     
5J3 | 14J5</b><b><br>
</b><b>1J4</b><b><br>
</b><b>      5J3 | 1J4</b><b><br>
</b><b>1J4</b></font><b><br>
</b><br>
whereas <b>SVN 963</b> was
giving:<br>
<br>
<font face="Courier New,
Courier, monospace"><b>     
5J3 | 14J5</b><b><br>
</b><b>¯4J1</b><b><br>
</b><b>      5J3 | 1J4</b><b><br>
</b><b>¯4J1</b></font><br>
<br>
<br>
Best Regards,<br>
/// Jürgen<br>
<br>
</font><br>
<br>
<div
class="m_5990767214693122393moz-cite-prefix">On
06/19/2017 07:03 PM, Frederick
Pitts wrote:<br>
</div>
<blockquote type="cite">
<pre>Jürgen,

With gnu apl (svn 961 on Fedora 25, Intel(R) Core(TM) i7-6700
CPU), the residue function (∣) yields the following:

      5J3 ∣ 14J5
1J4
      5J3 | 1J4
¯4J1
      5J3 | ¯4J1
¯4J1
The above result means that two elements in the complete residue system
(CSR) for mod 5J3 are equal, i.e. 1J4 = ¯4J1 mod 5J3, which is not
allowed. None of the elements of a CSR can be equal modulo the CSR's
basis.

Regards,

Fred

</pre>
</blockquote>
<br>
</blockquote>
</blockquote>
<br>
</blockquote>
</blockquote>
<br>
</blockquote>
<br>
</blockquote>
</div>
</div>
</div>
<br>
</blockquote>
</div>
<br>
</div>
</blockquote>
<br>
</blockquote>
</div>
</div>
</blockquote>
<br>
</blockquote>
<br>
</body>
</html>

[Frederick Pitts]

Hello JÃŒrgen,


This is a followup to my previous email.


I have found that if I replace | and ⌊ invocations in the test
code with residue AND floor (š needed with floor) functions (see below)
from Eugene McDonnell's article, the idempotency and complete residue
system count tests are successful.


∇g ← floor z  r ← 9 ○ z
  i ← 11 ○ z
  b ← ( ⌊ r ) + 0J1 × ⌊ i
  x ← 1 ∣ r
  y ← 1 ∣ i
  → ( 1 ≀ x + y ) / L0
  g ← b
  → 0
 L0:
  → ( x < y ) / L1
  g ← b + 1
  → 0
 L1:
  g ← b + 0J1
∇


∇ r ← w residue z
  r ← z - w × floor z ÷ w + w = 0
∇
Maybe a faithful implementation of both these function in Gnu
APL is required.
Regards,
Fred

    Hi,
      
      please disregard my comment on bif_floor() below.
      
    
    if (D < 1.0 - Workspace::get_CT())  
          return zv(Z, fr, fi);
          
        With that change
          my testcases (which contain the examples of both the ISO
          standard and
          the IBM language reference) are now properly working again.
          Fixed in SVN 970.
          
          /// JÌrgen
          
        
        
    On 06/23/2017 09:02 PM, Juergen
    
    

Post by Frederick Pitts
      
      Hi Frederick,
        
        I suppose that this is caused by a rounding error just
before
        the complex floor.
        I have attached a debug version of ComplexCell.cc that
        prints every partial result of the computation.
        
        
              5J3 | 14J5
          modulus (A) is: (5,3)
          A=0 is: (0,0)
          A+A=0 is: (5,3)
          B÷A+A=0 is: (2.5,-0.5)
          ⌊B÷A+A=0 is: (3,-1)
          A×⌊B÷A+A=0 is: (18,4)
          B-A×⌊B÷A+A=0 is: (-4,1)
          ¯4J1
        
        However if I use a slightly smaller B (kind of
        
              5J3 |
            14J4.999999999
          modulus (A) is: (5,3)
          A=0 is: (0,0)
          A+A=0 is: (5,3)
          B÷A+A=0 is: (2.4999999999118,-0.50000000014706)
          ⌊B÷A+A=0 is: (2,-1)
          A×⌊B÷A+A=0 is: (13,1)
          B-A×⌊B÷A+A=0 is: (1,3.999999999)
          1J3.999999999
        
        I suppose that is what happens on your machine but not on
mine.
        
        
        You may also want to try out the following. In
ComplexCell::bif_floor()
        
           // ISO: if D
            is tolerantly less than 1 return fr + 0J1×fi
             // IBM: if D is            less than 1 return fr +
            0J1×fi
             // However, ISO examples follow IBM (and so do we)
             //
          // if (D < 1.0 + Workspace::get_CT())   return zv(Z,
            fr, fi);   // ISO
             if (D < 1.0)    return zv(Z, fr, fi);   // IBM
            and examples in ISO
          
        If you uncomment the first if statement then you get the
ISO
        variant of bif_floor() while otherwise you
        get the IBM variant (which is also the one described in the
        McDonnel paper). It could be that the ISO variant
        works better for the bif_residue() function, but it
        causes problems in other places. If uncommenting the if
        line should fix your problem, then I can create two
variants of
        bif_floor(): one for bif_residue() and one
        for the rest.
        
        Best Regards,
        JÌrgen Sauermann
        
      
      On 06/23/2017 07:31 PM, Frederick
      
      

        
        Hello
            JÌrgen,
        
          
        
            SVN 969 on my platform (Fedora 25, Intel(R) Core(TM)
          i7-6700 CPU) 
        

 

        
          
              5J3
          | 14J5 1J4 ¯4J1
        
          
        gives
        
          
          1J4
              ¯4J1 ¯4J1
          
            
          not
          
            
          ¯1J4
              ¯4J1 ¯4J1
          
            
          Regards,
          
            
          Fred
            
            
            
            On Fri, 2017-06-23 at 17:38 +0200, Juergen Sauermann
            

 Hi,
                
                I have changed A∣B to literally follow the
paper
                pointed out by Jay.
                The complex floor itself was already
implemented like
                described in the paper,
                but A∣B was not.
                
                Now (SVN 969) the complex A∣B is computed
                as
                
                Z←B-A×⌊B÷A+A=0
                
                without any attempts to improve the performance
of the
                operation.
                
                The result in the 5J3 modulus are now the same
                as in IBM APL2 (and I suppose also in J)
                
                     
                    5J3 ∣ 14J5 1J4 ¯4J1 
                  ¯4J1 ¯4J1 ¯4J1
                
                I hope this finally fixed it. Thanks a lot to
all that
                helped fixing this bug.
                
                /// JÌrgen
              
              
              On 06/23/2017 09:34 AM, Jay
              
              

                I urge you to read Eugene McDonnell's Complex
                    Floor, which also discusses Residue. I
believe
                  the design he comes up with in this paper
was adopted
                  more or less verbatim in APL. Also bear in
mind that
                  Floor and Residue in APL have to work well
on all
                  complex numbers, not just the Gaussian
                  integers.
                  
                  
                  Jay.
                
                
                  On 23 June 2017 at 01:42,
                    

                      
                        Hello JÌrgen,
                        
                        
                        
                        
                        1) When performing a residue
calculation on
                          positive integers, a straight-
forward integer
                          division with remainder
calculation
                        suffices. For example, 5 ∣ 13 is
computed
                          with 13 / 5 = 2 r 3 and so 5 ∣ 13
= 3 where 3
                          is in the complete residue system
                        { 0, 1, 2, 3, 4 }. When performing
the
                          calculation on negative integers,
one has to
                          take advantage of the fact that
the
                        integer division quotient and
remainder are
                          not unique in order to compute a
residue that
                          is in the complete residue
system.
                        For 5 ∣ ¯13, ¯13 / 5 = ¯2 r ¯3
where ¯3 is
                          not in the CRS. However, ¯13 / 5
= ¯3 r 2
                          where 3 is in the CSR. The same
concept
                          applies Gaussian integers.
                        
                        
                        2) I suspect the decision to have
the APL2
                          floor function round toward
negative infinity,
                          instead of toward zero,
                        was made based on the desire to
save cpu
                          cycles and memory in the residue
function
                          code.
                        
                        
                        3) I read at least one math
literature
                          article discussing Gaussian
integer Euclidean
                          division algorithms, that
recommended
                        rounding down to the nearest real
and
                          imaginary part toward negative
infinity.
                          Unfortunately I cannot find
                        the article right now. I will
continue to
                          look for it. None of the articles
discussed
                          using a complex integer floor
function.
                        
                        
                        4) The reason MOD_TEST.apl shows
total
                          disagreement MODJ and the builtin
residue
                          function is that the complex
floor function
                          code change in SVN 965 relocated
the CRS's on
                          complex plane. Attached are
                          CRS0-CRS1-6J-6-SVN964.out
                        CRS0-CRS1-6J-6-SVN965.out. The
first file
                          contains a CRS map for modulus
¯6J¯6 produced
                          with the residue function
                        followed by a map for the same
modulus
                          produced with MODJ using SVN 964.
The second
                          file contains the same maps
                        using SVN 965. Observe that for SVN
964 the
                          residue function CRS is in the
bottom half of
                          the complex plane, but for SVN
965 it is in
                          the top half. The CRS for the
MODJ function is
                          in the bottom half in both SVN
cases.
                        5)The complex floor code change did
not
                          help with the issue that the
builtin residue
                          function is not idempotent for
all possible
                          arguments and consequently
generates too many
                          residues. See attached CRSOTST0-
SVN965.out.
                          For a grid
                        of Gaussian integers with real and
                          imaginary parts ranging from ¯15
to 15, using
                          every value with every other
value as modulus
                          and second argument, there were
40 case where
                          the order of CSR exceeded the
modulus norm. I
                          think that
                        was the failure count with the
previous
                          SVN.
                        
                        
                         Sincerely, I think the complex
floor and
                          ceiling functions should not be
used by other
                          functions even if IBM and ISO
                        imply they are in their
documentations. I'm
                          not seeing them used in the
Gaussian integer
                          literature. Again, please correct
me if I'm
                          wrong.
                        
                        
                        Regards,
                        
                        
                        Fred
                        
                          
                            
                            
                            On Thu, 2017-06-22 at 18:08
+0200,
                            

 Hi again,
                              
                              sorry a small typo below.
Lines 19/20
                              
                                    (¯6J¯5 - 0J¯11) ÷
¯6J¯6 
                              0J¯1
                              
                              /// JÌrgen
                              
                              On
                                06/22/2017 05:44 PM,
Juergen Sauermann
                              
                              

 Hi
                                  Fred at al.,
                                  
                                  I have made another
attempt to fix the
                                  residue function, SVN
965.
                                  
                                  For complex m∣b It
now rounds
                                  down the real() and
imag() parts of
                                  the quotient q←b÷m
and returns
                                  b-q.
                                  Instead of always
rounding towards 0
                                  or -infinity, the
rounding direction
                                  is now (compared to
the previous
                                  attempt) determined
by the quadrant in
                                  which the modulus m
lies.
                                
                                There are still
differences to the
                                results displayed by
MOD_test.apl,
                                  but I suppose they
are
                                  caused by that
program. For example,
                                  the first line of
MOD_test.apl,
                                    
                                    LA    RA  
                                      MODJ   |
                                    ¯6J¯6 ¯6J¯5  
0J¯11  0J1
                                  
                                  
                                        (¯6J¯5 - 0J1) ÷
¯6J¯6 
                                  1
                                        (0J¯11 - 0J1) ÷
¯6J¯6
                                  1J1
                                  
                                  so both 0J¯11 and 0J1
                                  are valid remainders
modulo ¯6J¯6.
                                  However, the
                                  magnitude of 0J¯11
                                  (= 11) is larger than
the
                                  magnitude of the
divisor ¯6J¯6
                                    (= around 8.4).
                                    I suppose most
people expect the
                                    remainder of a
division to be in
                                    some sense
                                    smaller than the
divisor.
                                    
                                    Regarding Jay's
idempotency
                                    requirement we now
                                    
                                         
                                        f←{6J6|⍵}
                                              f ¯3 ¯2
¯3 ¯1 0 1 2 3
                                        3J6 4J6 3J6 5J6
0 ¯5J6 ¯4J6 ¯3J6
                                              f f ¯3 ¯2
¯3 ¯1 0 1 2 3
                                        3J6 4J6 3J6 5J6
0 ¯5J6 ¯4J6 ¯3J6
                                    
                                              f←{5J3|⍵}
                                              f ¯3 ¯2
¯3 ¯1 0 1 2 3
                                        2J3 3J3 2J3 4J3
0 ¯2J5 ¯1J5 0J5
                                              f f ¯3 ¯2
¯3 ¯1 0 1 2 3
                                        2J3 3J3 2J3 4J3
0 ¯2J5 ¯1J5 0J5
                                      
                                    so at least the
first modulus seems
                                    to work as well.
The result is still
                                    different
                                    from APL2 as
reported by Jay, but I
                                    
                                    
                                          5J3 ∣ 14J5
1J4
                                        ¯4J1
                                ¯4J1 ¯4J1 ¯4J1
                                        
                                
                                      5J3 ∣ 14J5
                                            1J4 ¯4J1 
                                          1J4 1J4 1J4
                                        
                                      But both 1J4
                                    and ¯4J1 are valid
                                    remainders.
Interestingly Jay's
                                    idempotency
requirement seems to
                                    be fulfilled by
both the GNU APL and
                                    by IBM APL2, so
that that
                                    requirement alone
does not suffice
                                    to tell which
result is correct.
                                    
                                    On the other hand
this matter seems
                                    to be like
discussing if the square
                                    root of 4 is 2 or
-2 with
                                    both answers being
correct.
                                    
                                    Best Regards,
                                    JÌrgen Sauermann
                                    
                                    
                                  
                                     
                                On
                                  06/21/2017 10:25 PM,
Frederick Pitts
                                
                                

                                  JÌrgen,
                                  
                                  
                                   The proposed
change to DIVJ does
                                    not work because
'q1' is a complex
                                    number, so the
'×' in '× q1' is the
                                    complex
complement function, not the
                                    sign function. I
tried the proposed
                                    change and every
test fails.
                                  
                                  
                                   I will try to hack
DIVJ to use a
                                    floor towards
zero instead of
                                    towards minus
infinity for the real
                                    and imaginary
                                  parts of the
quotient and see
                                    what happens.
                                  
                                  
                                   Correct me if I am
wrong, but my
                                    mind set is that
the APL residue
                                    function has to
satisfy the
                                    following
                                  1) The order of the
complete
                                    residue system
(residue count) for a
                                    given modulo 'n'
has to equal the
                                    norm of 'n'.
                                  2) And as Jay Foad
so succinctly
                                    expressed it, the
residue function
                                    has to be
idempotent with respect to
                                    its right
argument,
                                   e.g., ( n | m ) =
n | n | m .
                                  regardless of the
implementation
                                    of the residue
function.
                                  
                                  
                                  Later,
                                  
                                  
                                  Fred 
                                  
                                  
                                  
                                  
                                  
                                  
                                  
                                  
                                  On Wed, 2017-06-21
at 19:46
                                    +0200, Juergen
                                  

 Hi Fred,
                                      
                                      I have a
question about the MOD_test.apl
                                      that you
kindly provided.
                                      
                                      In function
DIVJ on line
                                      57 ff it
                                      
                                      z ← q , a - b
× q
                                          ← CMPLX ⌊
( 9 11 ) ○ a ÷ b
                                      
                                      so the
quotient is rounded down
                                      towards minus
infinity.
                                      
                                      I wonder if
that should be
                                      something
like
                                      
                                      z ← q , (×
q1) × a
                                          - b × q ←
CMPLX ⌊ ∣ 9 11 ○ q1
                                          ← a ÷ b
                                      
                                      so that the
quotient is rounded
                                      towards 0?
Interestingly IBM and
                                      ISO
                                      give
different definitions for the
                                      residue in
                                      
                                      IBM (language
reference, page
                                      Z←L∣R
                                        Z is R-L×⌊
                                          R÷L+L=0
                                      
                                      ISO (chapter
7.2.9 Residue): 
                                      R←Q∣P
                                        R←P-
(×P)×|Q×⌊|P÷Q
                                          and
return R if (×R)=×Q, or
                                          R+Q
                                          otherwise
.
                                         
                                    That suggest
that IBM rounds the
                                    quotient down
towards minus infinity
                                    while ISO
rounds
                                     towards 0.
                                    
                                    My naive view
on remainder is that
                                    the nearest
integer quotient shall
                                    be smaller in
                                    magnitude and
not smaller in value.
                                    Regarding your
proposal (which is
                                    different from
                                    both IBM and
ISO) my concern is that
                                    may lead to
different results for modulo
                                      N and
                                    modulo N×1J0
                                    
                                    Best Regards,
                                    JÌrgen
Sauermann
                                    
                                    
                                    On
                                      06/21/2017
03:08 AM, Frederick
                                    
                                    

                                      JÌrgen,
                                      
                                        
                                      
                                          This
message is being resent
                                          because
last minute changes I
                                          made to
CRS0.apl and CRS1.apl
                                          do not
output the
                                      data
                                          I
intended.  This message has
                                          correct
ed versions of those
                                          files
attached.  Please
                                          discard
the old CRS0.apl and
                                          CRS1.ap
l files.  The first
                                          line of
output is the modulo
                                          basis, 
the
                                          second
line is the calculated
                                          complet
e residue system values
                                          and the
third line is the
                                          number
of residues in the CRS on
                                          the
previous line.
                                      
                                        
                                      
                                          CRSOTST
0.apl and CRSOTST1.apl
                                          are
unchanged.
                                      
                                        
                                      
                                          Also
please find attached
                                          MOD_TES
T.apl which compares
                                          the
residues calculated by
                                          MODJ
and the builtin residue
                                          functio
n and reports
                                          discrep
ancies.  The first
                                          column
of output is the modulo
                                          basis,
the second column the
                                          right
argument to the
                                          functio
ns, the third column
                                          the
MODJ result and the fourth
                                          column
is the builtin residue
                                          functio
n result.
                                      
                                        
                                      Regards
                                      
                                        
                                      Fred
                                      
                                      
                                      Hello
JÃŒrgen,
                                       SVN
964 moved us in the right direction but not
completely out of the
                                      woods.  SVN
964 still exhibits errors.  For instance
                                            2J6 |
5J5
                                      ¯1J7
                                            2J6 |
¯1J7
                                      ¯3J1
                                            2J6 |
¯3J1
                                      ¯3J1
                                       I
found this and previous residue function errors
using the attached APL
                                      code
files.  The files with base name ending in '0'
use the builtin residue
                                      function.  
Those with base name ending in '1' use a residue
function implemented
                                      in
APL.  The files with base name beginning with
'CRSOTST' test if the order of
                                      the
complete residue system (CRS) equals the norm of
the modulo basis.  That
                                      test fails
for several modulo bases, 2J6 being one of them,
using the builtin
                                      residue
function. No errors are detected with the APL
implementation.  The other files
                                      can be used
to plot the CRS for a given modulo basis where
'a' and 'b' in
                                      'a + b * i'
are limited to +15 to -15 range.  A full screen
terminal window is
                                      needed to
see the plot.
                                       My
APL implementation of the residue function is
very close to what you
                                      described
in your previous email.  Maybe comparing the two
implementations will
                                      give
insight into why the builtin residue function
fails for some modulo bases.
                                       I
make no assertion that my implementation is
correct in all
                                      aspects.
                                      Regards,
                                      Fred
                                      On Tue,
2017-06-20 at 14:14
                                        +0200,
                                      

 Hi Frederick,
                                          
                                          the
algorithm for A ∣ B
                                          used
                                          
                                          -
                                              c
ompute the quotient Q←B÷A,
                                            -
"round down" Q to
                                              t
he next (complex) integer
                                              Q
1,
                                            -
return B - Q1×A
                                          
                                          Now
the problem seems to be
                                          what
is meant by "round down".
                                          There
                                          
                                            Q1
                                              ←
⌊
                                              Q
                                     
                                               
  i.e. use APL floor
                                              t
o round down Q
                                             
Q1 ← Complex(
                                              f
loor(Q.real(), floor(Q.imag())
                                              )
  i,e, use C/C++
                                              f
loor() to round down Q.
                                            
                                          In
your  5J3 ∣ 14J5
                                          examp
le, the quotient is 2.5J¯0.5,
                                          which
gives different results
                                          for
the APL floor ⌊
                                          and
the C/C++ floor().
                                          
                                          The
APL floor ⌊2.5J¯0.5
                                            is
3J¯1
                                          (a
somewhat dubious invention
                                          in
the ISO standard on page
                                          19,
which I used up to
                                          inclu
ding SVN 963),
                                          while
the C/C++ floor() is
                                               
 2J¯1.
                                          The
difference between the APL
                                          floor
and the C/C++ floor is 1.0
                                          which
,
                                          multi
plied by the divisor,
                                          expla
ins the differences that
                                          we
see.
                                          
                                          As of
SVN 964 I have
                                          chang
ed the residue function (∣)
                                          to
use the C/C++ floor instead
                                          of
the APL floor. The APL
                                          floor
and
                                          Ceili
ng functions (⌊
                                          and
⌈) are still using
                                          the
apparently broken
                                          defin
ition in the ISO
                                          stand
ard.
                                          
                                          I
hope this works better for
                                          you.
At least I am getting
                                          this
                                          
                                               
                                              5
J3 | 14J5
                                            1J4
                                               
   5J3 | 1J4
                                            1J4
                                          
                                          where
as SVN 963 was
                                          givin
                                          
                                               
                                              5
J3 | 14J5
                                            ¯4J
1
                                               
   5J3 | 1J4
                                            ¯4J
1
                                          
                                          
                                          Best
Regards,
                                          ///
JÃŒrgen
                                          
                                        
                                        
                                        On
                                          06/19
/2017 07:03 PM, Frederick
                                          Pitts
                                        
                                        

                                          JÌr
gen,
With gnu apl (svn 961 on Fedora 25,
Intel(R) Core(TM) i7-6700
CPU), the residue function (∣) yields the
      5J3 ∣ 14J5
1J4
      5J3 | 1J4
¯4J1
      5J3 | ¯4J1
¯4J1
The above result means that two elements in
the complete residue system
(CSR) for mod 5J3 are equal, i.e. 1J4 = ¯4J1
mod 5J3, which is not
allowed.  None of the elements of a CSR can
be equal modulo the CSR's
basis.
Regards,
Fred
                                        

                                        
                                      

                                    

                                    
                                  

                                

                                
                              

                              
                            

                          
                        
                      
                      
                    

                  
                  
                
              

              
            

          
        
      

      
    

    
  

[Juergen Sauermann]

[Frederick Pitts]

JÃŒrgen,
A cut-and-paste of the output on my platform is:
      5J3 | 4J¯1⎕CT is: 1e-13modulus (A) is: (5,3)A=0 is: (0,0)A+A=0
is: (5,3)B÷A+A=0 is: (0.5,-0.5)⌊B÷A+A=0 is: (1,-1)A×⌊B÷A+A=0 is: (8,-
2)B-A×⌊B÷A+A=0 is: (-4,1)¯4J1
It is identical to the output you supplied me.  But I don't think an
error occurs during the evaluation of 5J3 | 4J¯1.  I thinkthe error
occurs during the evaluation of
      5J3 | ¯7J6⎕CT is: 1e-13modulus (A) is: (5,3)A=0 is: (0,0)A+A=0
is: (5,3)B÷A+A=0 is: (-0.5,1.5)⌊B÷A+A=0 is: (-1,2)A×⌊B÷A+A=0 is: (-
11,7)B-A×⌊B÷A+A=0 is: (4,-1)4J¯1
because it says 4J¯1 is in the complete residue system for modulus 5J3,
while the 5J3 | 4J¯1 evaluation above says it isn't.If it were,
evaluating 5J3 | 4J¯1 should spit 4J¯1 back at me.
Here is a transcript of evaluating 5J3 | ¯7J6 using the
McDonnell floor function I sent in anearlier email
      A ← 5J3      A = 00      A + A = 05J3      B ← ¯7J6      B ÷ A +
A = 0¯0.5J1.5      floor B ÷ A + A = 00J1      A × floor B ÷ A + A =
0¯3J5      B - A × floor B ÷ A + A = 0¯4J1
Note that the result of the floor evaluation is 0J1, not ¯1J2 and that
residue result at the end is correct.
Regards,
Fred

    Hi Fred,
      
      could you please run the attached debug version of
ComplexCell.cc?
      
      
             
        5J3 | 4J¯1
      ⎕CT is: 1e-13
      modulus (A) is: (5,3)
      A=0 is: (0,0)
      A+A=0 is: (5,3)
      B÷A+A=0 is: (0.5,-0.5)
      ⌊B÷A+A=0 is: (1,-1)
      A×⌊B÷A+A=0 is: (8,-2)
      B-A×⌊B÷A+A=0 is: (-4,1)
      ¯4J1
    
    The above printout are the intermediate results of the following
    computation
          //                           // op       Z
          before     Z after
             new (Z) IntCell(0);          // Z←0      any          0
             Z->bif_equal(Z, A);          // Z←A=Z   
            0            A=0
             Z->bif_add(Z, A);            // Z←A+Z   
            A=0          A+A=0
             Z->bif_divide(Z, this);      // Z←B÷Z   
            A+A=0        B÷A+A=0
             Z->bif_floor(Z);             // Z←⌊Z    
            B÷A+A=0      ⌊B÷A+A=0
             Z->bif_multiply(Z, A);       // Z←A×Z   
            ⌊B÷A+A=0     A×⌊B÷A+A=0
             Z->bif_subtract(Z, this);    // Z←A-Z   
            A×⌊B÷A+A=0   B-A×⌊B÷A+A=0
        
      which I believe is a faithful (apart from errors)
      implementation of Z←B-A×⌊B÷A+A=0
        as given in the McDonnell paper.
      
    
        (0.5,-0.5)
      ⌊B÷A+A=0 is: (1,-1)
      
        Best Regards,
        /// JÌrgen
        
        
      
    On 06/24/2017 01:48 AM, Frederick Pitts
    
    

Post by Frederick Pitts
      
      Hello JÌrgen,
      
        
      
          This is a followup to my previous email.
      
        
       I
          have found that if I replace | and ⌊ invocations in the
test
          code with residue AND floor (š needed with floor)
functions
          (see below) from Eugene McDonnell's article, the
idempotency
          and complete residue system count tests are successful.
      
        
      ∇g ←
        floor z
        r
          ← 9 ○ z
        i
          ← 11 ○ z
        b
          ← ( ⌊ r ) + 0J1 × ⌊ i
        x
          ← 1 ∣ r
        y
          ← 1 ∣ i
        →
          ( 1 ≀ x + y ) / L0
        g
          ← b
        →
          0
        →
          ( x < y ) / L1
        g
          ← b + 1
        →
          0
        g
          ← b + 0J1
      ∇
      
        
      ∇ r ← w residue z
        r ← z - w × floor
          z ÷ w + w = 0
      ∇
        
        
         Maybe a faithful implementation of both these function in
          Gnu APL is required.
        
        
        Regards,
        
        
        Fred
        
        
        

 Hi,
            
            please disregard my comment on bif_floor() below.
            
            The proper line should be this (note the -
          
          if (D < 1.0 -
                Workspace::get_CT())   return zv(Z, fr, fi);
                
              With that
                change my testcases (which contain the examples
of both
                the ISO standard and
                the IBM language reference) are now properly
working
                again. Fixed in SVN 970.
                
                /// JÌrgen
                
              
              
          On 06/23/2017 09:02 PM, Juergen
          
          

            
            Hi Frederick,
              
              I suppose that this is caused by a rounding error
just
              before the complex floor.
              I have attached a debug version of ComplexCell.cc
              that prints every partial result of the
computation.
              
              
                    5J3
                  | 14J5
                modulus (A) is: (5,3)
                A=0 is: (0,0)
                A+A=0 is: (5,3)
                B÷A+A=0 is: (2.5,-0.5)
                ⌊B÷A+A=0 is: (3,-1)
                A×⌊B÷A+A=0 is: (18,4)
                B-A×⌊B÷A+A=0 is: (-4,1)
                ¯4J1
              
              However if I use a slightly smaller B (kind of
              
                    5J3
                  | 14J4.999999999
                modulus (A) is: (5,3)
                A=0 is: (0,0)
                A+A=0 is: (5,3)
                B÷A+A=0 is: (2.4999999999118,-0.50000000014706)
                ⌊B÷A+A=0 is: (2,-1)
                A×⌊B÷A+A=0 is: (13,1)
                B-A×⌊B÷A+A=0 is: (1,3.999999999)
                1J3.999999999
              
              I suppose that is what happens on your machine
but not on
              mine.
              
              
              You may also want to try out the following. In
ComplexCell::bif_floor()
              
                  if D is tolerantly less than 1 return fr +
0J1×fi
                   // IBM: if D is            less than 1
return
                  fr + 0J1×fi
                   // However, ISO examples follow IBM (and so
do
                  we)
                   //
                // if (D < 1.0 + Workspace::get_CT())   return
                  zv(Z, fr, fi);   // ISO
                   if (D < 1.0)    return zv(Z, fr, fi);   //
                  IBM and examples in ISO
                
              If you uncomment the first if statement then you
get the
              ISO variant of bif_floor() while otherwise you
              get the IBM variant (which is also the one
described in
              the McDonnel paper). It could be that the ISO
variant
              works better for the bif_residue() function, but
              it causes problems in other places. If
uncommenting the if
              line should fix your problem, then I can create
two
              variants of bif_floor(): one for bif_residue()
              and one
              for the rest.
              
              Best Regards,
              JÌrgen Sauermann
              
            
            On 06/23/2017 07:31 PM,
            
            

              
              Hello JÌrgen,
              
                
               SVN 969 on my platform (Fedora 25, Intel(R)
                Core(TM) i7-6700 CPU) 
              

 

              
                
                    5J3
                | 14J5 1J4 ¯4J1
              
                
              gives
              
                
                1J4 ¯4J1 ¯4J1
                
                  
                not
                
                  
                ¯1J4 ¯4J1 ¯4J1
                
                  
                Regards,
                
                  
                Fred
                  
                  
                  
                  On Fri, 2017-06-23 at 17:38 +0200, Juergen
                  

 Hi,
                      
                      I have changed A∣B to literally
follow the
                      paper pointed out by Jay.
                      The complex floor itself was already
implemented
                      like described in the paper,
                      but A∣B was not.
                      
                      Now (SVN 969) the complex A∣B is
                      computed as
                      
                      Z←B-A×⌊B÷A+A=0
                      
                      without any attempts to improve the
performance of
                      the operation.
                      
                      The result in the 5J3 modulus are now
the
                      same as in IBM APL2 (and I suppose
also in J)
                      
                           
                          5J3 ∣ 14J5 1J4 ¯4J1 
                        ¯4J1 ¯4J1 ¯4J1
                      
                      I hope this finally fixed it. Thanks
a lot to all
                      that helped fixing this bug.
                      
                      /// JÌrgen
                    
                    
                    On 06/23/2017 09:34 AM,
                    
                    

                      I urge you to read Eugene
                        McDonnell's Complex
                          Floor, which also discusses
Residue. I
                        believe the design he comes up
with in this
                        paper was adopted more or less
verbatim in APL.
                        Also bear in mind that Floor and
Residue in APL
                        have to work well on all complex
numbers, not just the
                        Gaussian integers.
                        
                        
                        Jay.
                      
                      
                        On 23 June 2017 at
                          01:42, Frederick Pitts <fred.pi
                          

                            
                              Hello JÌrgen,
                              
                              
                              
                              
                              1) When performing a
residue
                                calculation on positive
integers, a
                                straight-forward
integer division with
                                remainder calculation
                              suffices. For example, 5
∣ 13 is
                                computed with 13 / 5 =
2 r 3 and so 5 ∣
                                13 = 3 where 3 is in
the complete
                                residue system
                              { 0, 1, 2, 3, 4 }. When
performing
                                the calculation on
negative integers,
                                one has to take
advantage of the fact
                                that the
                              integer division quotient
and
                                remainder are not
unique in order to
                                compute a residue that
is in the
                                complete residue
system.
                              For 5 ∣ ¯13, ¯13 / 5 = ¯2
r ¯3 where
                                ¯3 is not in the CRS.
However, ¯13 / 5 =
                                ¯3 r 2 where 3 is in
the CSR. The same
                                concept applies
Gaussian integers.
                              
                              
                              2) I suspect the decision
to have the
                                APL2 floor function
round toward
                                negative infinity,
instead of toward
                                zero,
                              was made based on the
desire to save
                                cpu cycles and memory
in the residue
                                function code.
                              
                              
                              3) I read at least one
math
                                literature article
discussing Gaussian
                                integer Euclidean
division algorithms,
                                that recommended
                              rounding down to the
nearest real and
                                imaginary part toward
negative infinity.
                                Unfortunately I cannot
find
                              the article right now. I
will
                                continue to look for
it. None of the
                                articles discussed
using a complex
                                integer floor function.
                              
                              
                              4) The reason
MOD_TEST.apl shows
                                total disagreement MODJ
and the builtin
                                residue function is
that the complex
                                floor function code
change in SVN 965
                                relocated the CRS's on
complex plane.
                                Attached are CRS0-CRS1-
6J-6-SVN964.out
                              CRS0-CRS1-6J-6-
SVN965.out. The first
                                file contains a CRS map
for modulus
                                ¯6J¯6 produced with the
residue function
                              followed by a map for the
same
                                modulus produced with
MODJ using SVN
                                964. The second file
contains the same
                                maps
                              using SVN 965. Observe
that for SVN
                                964 the residue
function CRS is in the
                                bottom half of the
complex plane, but
                                for SVN 965 it is in
the top half. The
                                CRS for the MODJ
function is in the
                                bottom half in both SVN
cases.
                              5)The complex floor code
change did
                                not help with the issue
that the builtin
                                residue function is not
idempotent for
                                all possible arguments
and consequently
                                generates too many
residues. See
                                attached CRSOTST0-
SVN965.out. For a grid
                              of Gaussian integers with
real and
                                imaginary parts ranging
from ¯15 to 15,
                                using every value with
every other value
                                as modulus and second
argument, there
                                were 40 case where the
order of CSR
                                exceeded the modulus
norm. I think that
                              was the failure count
with the
                                previous SVN.
                              
                              
                               Sincerely, I think the
complex floor
                                and ceiling functions
should not be used
                                by other functions even
if IBM and ISO
                              imply they are in their
                                documentations. I'm not
seeing them used
                                in the Gaussian integer
literature.
                                Again, please correct
me if I'm wrong.
                              
                              
                              Regards,
                              
                              
                              Fred
                              
                                
                                  
                                  
                                  On Thu, 2017-06-22 at
18:08
                                    +0200, Juergen
                                  

 Hi again,
                                    
                                    sorry a small
typo below. Lines
                                    19/20 should
                                    
                                          (¯6J¯5 -
0J¯11) ÷ ¯6J¯6 
                                    0J¯1
                                    
                                    /// JÌrgen
                                    
                                    On
                                      06/22/2017
05:44 PM, Juergen
                                      Sauermann
                                    
                                    

Post by Frederick Pitts
 Hi Fred at al.,
                                        
                                        I have made
another attempt to
                                        fix the
residue function, SVN
                                          965.
                                        
                                        For complex
m∣b It now
                                        rounds down
the real() and
                                        imag()
parts of the quotient q←b÷m
                                        and returns
b-q.
                                        Instead of
always rounding
                                        towards 0
or -infinity, the
                                        rounding
direction is now
                                        (compared
to the previous
                                        attempt)
determined by the
                                        quadrant in
which the modulus m
                                        lies.
                                      
                                      There are
still differences to the
                                      results
displayed by MOD_test.apl,
                                        but I
suppose they are
                                        caused by
that program. For
                                        example,
the first line of MOD_test.apl,
                                          
                                          LA   
                                            RA  
MODJ   |
                                          ¯6J¯6
¯6J¯5   0J¯11 
                                            0J1
                                        
                                        
                                             
(¯6J¯5 - 0J1) ÷ ¯6J¯6 
                                        1
                                             
(0J¯11 - 0J1) ÷
                                          ¯6J¯6
                                        1J1
                                        
                                        so both
0J¯11 and 0J1
                                        are valid
remainders modulo ¯6J¯6.
                                        However,
the
                                        magnitude
of 0J¯11 (= 11)
                                        is larger
than the magnitude of
                                        the divisor
¯6J¯6 (= around 8.4).
                                          I suppose
most people expect
                                          the
remainder of a division to
                                          be in
some sense
                                          smaller
than the divisor.
                                          
                                          Regarding
Jay's idempotency
                                          requireme
                                          
                                               
                                              f←{6J
6|⍵}
                                                   
f ¯3 ¯2 ¯3 ¯1 0 1 2
                                              3
                                              3J6
4J6 3J6 5J6 0 ¯5J6
                                              ¯4J6
¯3J6
                                                   
f f ¯3 ¯2 ¯3 ¯1 0 1
                                              2 3
                                              3J6
4J6 3J6 5J6 0 ¯5J6
                                              ¯4J6
¯3J6
                                          
                                                   
f←{5J3|⍵}
                                                   
f ¯3 ¯2 ¯3 ¯1 0 1 2
                                              3
                                              2J3
3J3 2J3 4J3 0 ¯2J5
                                              ¯1J5
0J5
                                                   
f f ¯3 ¯2 ¯3 ¯1 0 1
                                              2 3
                                              2J3
3J3 2J3 4J3 0 ¯2J5
                                              ¯1J5
0J5
                                            
                                          so at
least the first modulus
                                          seems to
work as well. The
                                          result is
still different
                                          from APL2
as reported by Jay,
                                          but I
                                          
                                          
                                               
                                              5J3 ∣
14J5 1J4 ¯4J1
                                      ¯4J1 ¯4J1
¯4J1
                                              
                                            GNU
                                      
                                           
                                                  5
J3 ∣ 14J5 1J4 ¯4J1 
                                                1J4
1J4 1J4
                                              
                                            But
both 1J4
                                          and ¯4J1
are valid
                                          remainder
s. Interestingly
                                          Jay's
idempotency requirement
                                          seems to
                                          be
fulfilled by both the GNU
                                          APL and
by IBM APL2, so that
                                          that
requirement alone does
                                          not
suffice
                                          to tell
which result is
                                          correct.
                                          
                                          On the
other hand this matter
                                          seems to
be like discussing if
                                          the
square root of 4 is 2 or
                                          -2 with
                                          both
answers being correct.
                                          
                                          Best
Regards,
                                          JÌrgen
Sauermann
                                          
                                          
                                        
                                           
                                      On
                                        06/21/2017
10:25 PM, Frederick
                                        Pitts
                                      
                                      

                                        JÌrgen,
                                        
                                        
                                         The
proposed change to
                                          DIVJ
does not work because
                                          'q1' is
a complex number, so
                                          the '×'
in '× q1' is the
                                          complex
complement function,
                                          not the
sign function. I tried
                                          the
proposed change and every
                                          test
fails.
                                        
                                        
                                         I will
try to hack DIVJ to
                                          use a
floor towards zero
                                          instead
of towards minus
                                          infinit
y for the real and
                                          imagina
ry
                                        parts of
the quotient and
                                          see
what happens.
                                        
                                        
                                         Correct
me if I am wrong,
                                          but my
mind set is that the
                                          APL
residue function has to
                                          satisfy
the following
                                          invaria
                                        1) The
order of the
                                          complet
e residue system
                                          (residu
e count) for a given
                                          modulo
'n' has to equal the
                                          norm of
'n'.
                                        2) And as
Jay Foad so
                                          succinc
tly expressed it, the
                                          residue
function has to be
                                          idempot
ent with respect to its
                                          right
argument,
                                         e.g., (
n | m ) = n | n |
                                          m .
                                        regardles
s of the
                                          impleme
ntation of the residue
                                          functio
n.
                                        
                                        
                                        Later,
                                        
                                        
                                        Fred 
                                        
                                        
                                        
                                        
                                        
                                        
                                        
                                        
                                        On Wed,
2017-06-21 at 19:46
                                          +0200,
Juergen Sauermann
                                        

 Hi Fred,
                                            
                                            I
have a question about the
                                            MOD
_test.apl that you
                                            kin
dly provided.
                                            
                                            In
function DIVJ on
                                            lin
                                            
                                            z ←
                                               
 q , a - b × q ← CMPLX ⌊
                                               
 ( 9 11 ) ○ a ÷ b
                                            
                                            so
the quotient is rounded
                                            dow
n towards minus infinity.
                                            
                                            I
wonder if that should be
                                            som
ething like
                                            
                                            z ←
                                               
 q , (× q1) × a - b × q ←
                                               
 CMPLX ⌊ ∣ 9 11 ○ q1 ← a
                                               
 ÷ b
                                            
                                            so
that the quotient is
                                            rou
nded towards 0?
                                            Int
erestingly IBM and ISO
                                            giv
e different definitions
                                            for
the residue in terms of
                                            APL
                                            
                                            IBM
(language reference,
                                            pag
                                            Z←L
∣R
                                              Z
is R-L×⌊
                                               
 R÷L+L=0
                                            
                                            ISO
                                            
                                            R←Q
∣P
                                              R
←P-(×P)×|Q×⌊|P÷Q
                                               
 and return R if (×R)=×Q,
                                               
 or R+Q
                                               
 otherwise.
                                               
                                          That
suggest that IBM rounds
                                          the
quotient down towards
                                          minus
infinity while ISO
                                          round
s
                                           towa
rds 0.
                                          
                                          My
naive view on remainder is
                                          that
the nearest integer
                                          quoti
ent shall be smaller in
                                          magni
tude and not smaller in
                                          value
. Regarding your proposal
                                          (whic
h is different from
                                          both
IBM and ISO) my concern
                                          is
that may lead to different
                                          resul
ts for modulo N
                                          and
                                          modul
o N×1J0
                                          
                                          Best
Regards,
                                          JÌrge
n Sauermann
                                          
                                          
                                          On
                                            06/
21/2017 03:08 AM,
                                            Fre
                                          
                                          

                                            J
ÃŒrgen,
                                            
                                             
 
                                            
                                             
   This message is being
                                             
   resent because last
                                             
   minute changes I made to
                                             
   CRS0.apl and CRS1.apl do
                                             
   not output the
                                            d
ata
                                             
   I intended.  This
                                             
   message has corrected
                                             
   versions of those files
                                             
   attached.  Please
                                             
   discard the old CRS0.apl
                                             
   and CRS1.apl files.  The
                                             
   first line of output is
                                             
   the modulo basis, the second line is the
calculated complete
                                             
   residue system values
                                             
   and the third line is
                                             
   the number of residues
                                             
   in the CRS on the previous line.
                                            
                                             
 
                                            
                                             
   CRSOTST0.apl and
                                             
   CRSOTST1.apl are
                                             
   unchanged.
                                            
                                             
 
                                            
                                             
   Also please find
                                             
   attached MOD_TEST.apl
                                             
   which compares the
                                             
   residues calculated by
                                             
   MODJ and the builtin
                                             
   residue function and
                                             
   reports discrepancies. 
                                             
   The first column of
                                             
   output is the modulo
                                             
   basis, the second column
                                             
   the right argument to
                                             
   the functions, the third
                                             
   column the MODJ result
                                             
   and the fourth column is
                                             
   the builtin residue
                                             
   function result.
                                            
                                             
 
                                            R
egards
                                            
                                             
 
                                            F
red
                                            
                                            
                                            H
ello JÃŒrgen,
                                            
SVN 964 moved us in the right direction but
not completely out of the
                                            w
oods.  SVN 964 still exhibits errors.  For
instance
                                             
     2J6 | 5J5
                                            ¯
1J7
                                             
     2J6 | ¯1J7
                                            ¯
3J1
                                             
     2J6 | ¯3J1
                                            ¯
3J1
                                            
I found this and previous residue function
errors using the attached APL
                                            c
ode files.  The files with base name ending
in '0' use the builtin residue
                                            f
unction.  Those with base name ending in '1'
use a residue function implemented
                                            i
n APL.  The files with base name beginning
with 'CRSOTST' test if the order of
                                            t
he complete residue system (CRS) equals the
norm of the modulo basis.  That
                                            t
est fails for several modulo bases, 2J6 being
one of them, using the builtin
                                            r
esidue function. No errors are detected with
the APL implementation.  The other files
                                            c
an be used to plot the CRS for a given modulo
basis where 'a' and 'b' in
                                            '
a + b * i' are limited to +15 to -15
range.  A full screen terminal window is
                                            n
eeded to see the plot.
                                            
My APL implementation of the residue function
is very close to what you
                                            d
escribed in your previous email.  Maybe
comparing the two implementations will
                                            g
ive insight into why the builtin residue
function fails for some modulo bases.
                                            
I make no assertion that my implementation is
correct in all
                                            a
spects.
                                            R
egards,
                                            F
red
                                            O
n Tue, 2017-06-20 at
                                             
 14:14 +0200, Juergen
                                             
                                            

 Hi
                                           
     Frederick,
                                           
     
                                           
     the algorithm for A
                                           
       ∣ B used in GNU
                                           
                                           
     
                                           
     -
                                           
         compute the quotient
                                           
         Q←B÷A,
                                           
       - "round down"
                                           
         Q to the next
                                           
         (complex) integer
                                           
         Q1,
                                           
       - return B -
                                           
         Q1×A
                                           
     
                                           
     Now the problem seems to
                                           
     be what is meant by
                                           
     "round down". There are
                                           
                                           
     
                                           
      
                                           
       Q1 ← ⌊
                                           
         Q                                 
    
                                           
             i.e. use APL
                                           
         floor to
                                           
         round down Q
                                           
         Q1 ← Complex(
                                           
         floor(Q.real(), floor(Q.imag())
                                           
         )   i,e, use
                                           
         C/C++ floor() to
                                           
         round down Q.
                                           
       
                                           
     In your  5J3 ∣ 14J5
                                           
     example, the quotient is
                                           
     2.5J¯0.5, which
                                           
     gives different results
                                           
     for the APL floor ⌊
                                           
     and the C/C++ floor().
                                           
     
                                           
     The APL floor ⌊2.5J¯0.5
                                           
       is 3J¯1
                                           
     (a somewhat dubious
                                           
     invention in the ISO
                                           
     standard on page 19,
                                           
     which I used up to
                                           
     including SVN 963),
                                           
     while the C/C++ floor()
                                           
     is
                                           
           2J¯1.
                                           
     The difference between
                                           
     the APL floor and the
                                           
     C/C++ floor is 1.0 which,
                                           
     multiplied by the
                                           
     divisor, explains the
                                           
     differences that we see.
                                           
     
                                           
     As of SVN 964 I
                                           
     have changed the residue
                                           
     function (∣) to
                                           
     use the C/C++ floor
                                           
     instead of the APL
                                           
     floor. The APL floor and
                                           
     Ceiling functions (⌊
                                           
     and ⌈) are still
                                           
     using the apparently
                                           
     broken definition in the
                                           
     ISO standard.
                                           
     
                                           
     I hope this works better
                                           
     for you. At least I am
                                           
     getting this in SVN
                                           
                                           
     
                                           
          
                                           
         5J3 | 14J5
                                           
       1J4
                                           
             5J3 | 1J4
                                           
       1J4
                                           
     
                                           
     whereas SVN 963
                                           
                                           
     
                                           
          
                                           
         5J3 | 14J5
                                           
       ¯4J1
                                           
             5J3 | 1J4
                                           
       ¯4J1
                                           
     
                                           
     
                                           
     Best Regards,
                                           
     /// JÌrgen
                                           
     
                                           
   
                                           
   
                                           
   On
                                           
     06/19/2017 07:03 PM,
                                           
                                           
   
                                           
   

                                         
       JÌrgen,
With gnu apl (svn 961 on Fedora 25,
Intel(R) Core(TM) i7-6700
CPU), the residue function (∣) yields the
      5J3 ∣ 14J5
1J4
      5J3 | 1J4
¯4J1
      5J3 | ¯4J1
¯4J1
The above result means that two elements
in the complete residue system
(CSR) for mod 5J3 are equal, i.e. 1J4 =
¯4J1 mod 5J3, which is not
allowed.  None of the elements of a CSR
can be equal modulo the CSR's
basis.
Regards,
Fred
                                         
     

                                           
   
                                           
 

                                          

                                          
                                        

                                      

                                      
                                    

                                    
                                  

                                
                              
                            
                            
                          

                        
                        
                      
                    

                    
                  

                
              
            

            
          

          
        

      
    

    
  

[Juergen Sauermann]

<html>
<head>
<meta content="text/html; charset=utf-8" http-equiv="Content-Type">
</head>
<body bgcolor="#FFFFFF" text="#000000">
<font face="Helvetica, Arial, sans-serif">Hi Fred,<br>
<br>
OK, I was using  </font><b>4J¯1</b> because that was the number
where I believed you<br>
were suspocting the error/difference was. But OK, <b>5J3 | 4J¯1</b>
is <b>¯4J1</b>
<div>on your box and on mine.<br>
<br>
Now to <b>5J3 | ¯7J6</b>:<br>
<br>
My machine says:<br>
 <br>
<font face="Courier New, Courier, monospace"><b>      5J3 | ¯7J6</b><b><br>
</b><b>⎕CT is: 1e-13</b><b><br>
</b><b>modulus (A) is: (5,3)</b><b><br>
</b><b>A=0 is: (0,0)</b><b><br>
</b><b>A+A=0 is: (5,3)</b><b><br>
</b><b>B÷A+A=0 is: (-0.5,1.5)</b><b><br>
</b><b>⌊B÷A+A=0 is: (0,1)</b><b><br>
</b><b>A×⌊B÷A+A=0 is: (-3,5)</b><b><br>
</b><b>B-A×⌊B÷A+A=0 is: (-4,1)</b><b><br>
</b><b>¯4J1</b></font><br>
<br>
Both machines agree that:<br>
<br>
<font face="Courier New, Courier, monospace"><b>B÷A+A=0 is:
(-0.5,1.5)<br>
<br>
</b><font face="Helvetica, Arial, sans-serif">but they disagree
what <font face="Courier New, Courier, monospace"><b>⌊</b></font></font></font><font
face="Courier New, Courier, monospace"><font face="Helvetica,
Arial, sans-serif"><font face="Courier New, Courier,
monospace"><b>-0.5,1.5</b><font face="Helvetica, Arial,
sans-serif"> should be. My machine says <b>0J1</b><br>
while yours says <b>¯1J2.</b> That is, my machine rounds
down the real part and rounds<br>
up the imag part, while yours rounds up the real part and
rounds down the<br>
imag part.<br>
<br>
SInce the code of <b>bif</b><b>_</b><b>floor</b><b>()</b>
has become quite trivial recently:<br>
<br>
<font face="Courier New, Courier, monospace"><b>ErrorCode</b><b><br>
</b><b>ComplexCell::bif_floor(Cell * Z) const</b><b><br>
</b><b>{</b><b><br>
</b><b>const APL_Float fr = floor(value.cval_r);    //
fr ≤ value.cval_r</b><b><br>
</b><b>const APL_Float Dr = value.cval_r - fr;      // 0
≤ Dr &lt; 1</b><b><br>
</b><b>const APL_Float fi = floor(value2.cval_i);   //
fi ≤ value2.cval_i</b><b><br>
</b><b>const APL_Float Di = value2.cval_i - fi;     // 0
≤ Di &lt; 1</b><b><br>
</b><b>const APL_Float D = Dr + Di;                 // 0
≤ D &lt; 2</b><b><br>
</b><b><br>
</b><b>   if (D &lt; 1.0 - Workspace::get_CT())   return
zv(Z, fr, fi);   // ISO</b><b><br>
</b><b><br>
</b><b>   if (Dr &lt; Di)   return zv(Z, fr, fi + 1.0);</b><b><br>
</b><b>   else           return zv(Z, fr + 1.0, fi);</b><b><br>
</b><b>}</b></font><b><br>
</b><br>
it appears as if our machines disagree on the comparison </font></font></font></font><font
face="Courier New, Courier, monospace"><font face="Helvetica,
Arial, sans-serif"><font face="Courier New, Courier,
monospace"><font face="Helvetica, Arial, sans-serif"><font
face="Courier New, Courier, monospace"><font
face="Helvetica, Arial, sans-serif"><font
face="Courier New, Courier, monospace"><font
face="Helvetica, Arial, sans-serif"><font
face="Courier New, Courier, monospace"><b>Dr
&lt; Di</b>.<font face="Helvetica, Arial,
sans-serif"> The <b>Dr</b> (for difference
real) and <b>Di</b> (for difference<br>
imag) are exactly the <b>x</b> and <b>y</b>
in the McDonnell paper. So your machine lands
in area <b>c</b> while mine lands in area <b>b</b>
of<br>
Figure 2 in the paper.<br>
<br>
That explains what we see, but not what we can
do about it.<br>
<br>
The ISO standard (which interestingly lists
McDonnell as one of the 3 editors) computes <b>Dr
+ Di &lt; 1</b> as a tolerant compare<br>
(i.e. involves <b>⎕CT</b> in the test for
equality (page 19 of the ISO standard)) and
computes </font></font></font></font></font></font></font></font></font></font><font
face="Courier New, Courier, monospace"><font face="Helvetica,
Arial, sans-serif"><font face="Courier New, Courier,
monospace"><font face="Helvetica, Arial, sans-serif"><font
face="Courier New, Courier, monospace"><font
face="Helvetica, Arial, sans-serif"><font
face="Courier New, Courier, monospace"><font
face="Helvetica, Arial, sans-serif"><font
face="Courier New, Courier, monospace"><font
face="Helvetica, Arial, sans-serif"><font
face="Courier New, Courier, monospace"><font
face="Helvetica, Arial, sans-serif"><font
face="Courier New, Courier, monospace"><font
face="Helvetica, Arial, sans-serif"><font
face="Courier New, Courier,
monospace"><font face="Helvetica,
Arial, sans-serif"><font
face="Courier New, Courier,
monospace"><font
face="Helvetica, Arial,
sans-serif"><font
face="Courier New, Courier,
monospace"><font
face="Helvetica, Arial,
sans-serif"><b>Dr &lt; Di</b></font></font></font></font></font></font></font></font></font></font>
as a strict compare (i.e.<br>
<b>not</b> considering <b>⎕CT</b>). The APL2
language reference claims that both
comparisons are made with <b>⎕CT=0</b>. It<br>
might be that both are wrong.<br>
</font><br>
<font face="Helvetica, Arial, sans-serif">My
proposal would therefore be to change the last
<b>if</b> statement like this:</font></font></font></font></font></font></font></font></font></font><br>
<font face="Courier New, Courier, monospace"><font
face="Helvetica, Arial, sans-serif"><font face="Courier New,
Courier, monospace"><font face="Helvetica, Arial,
sans-serif"><font face="Courier New, Courier, monospace"><font
face="Helvetica, Arial, sans-serif"><font
face="Courier New, Courier, monospace"><font
face="Helvetica, Arial, sans-serif"><font
face="Courier New, Courier, monospace"><font
face="Helvetica, Arial, sans-serif"><font
face="Courier New, Courier, monospace"><font
face="Helvetica, Arial, sans-serif"><font
face="Courier New, Courier, monospace"><font
face="Helvetica, Arial, sans-serif"><font
face="Courier New, Courier,
monospace"><b><br>
</b><b>   if (Dr &lt; Di </b></font></font></font></font></font></font></font></font></font></font></font></font></font></font></font><font
face="Courier New, Courier, monospace"><font face="Helvetica,
Arial, sans-serif"><font face="Courier New, Courier,
monospace"><font face="Helvetica, Arial, sans-serif"><font
face="Courier New, Courier, monospace"><font
face="Helvetica, Arial, sans-serif"><font
face="Courier New, Courier, monospace"><font
face="Helvetica, Arial, sans-serif"><font
face="Courier New, Courier, monospace"><font
face="Helvetica, Arial, sans-serif"><font
face="Courier New, Courier, monospace"><font
face="Helvetica, Arial, sans-serif"><font
face="Courier New, Courier, monospace"><font
face="Helvetica, Arial, sans-serif"><font
face="Courier New, Courier,
monospace"><b><font face="Courier
New, Courier, monospace"><font
face="Helvetica, Arial,
sans-serif"><font
face="Courier New, Courier,
monospace"><font
face="Helvetica, Arial,
sans-serif"><font
face="Courier New,
Courier, monospace"><b>-
Workspace::get_CT()</b></font></font></font></font></font>)  
return zv(Z, fr, fi + 1.0);</b><b><br>
</b></font></font></font></font></font></font></font></font></font></font></font></font></font></font><b><br>
</b></font><font face="Helvetica, Arial, sans-serif">Maybe you
want to try that with the last debug version of ComplexCell.cc
that I sent earlier today<br>
before I commit it as a new SVN version.<br>
<br>
Best Regards,<br>
Jürgen Sauermann<br>
<br>
</font></div>
<br>
<div class="moz-cite-prefix">On 06/24/2017 04:54 PM, Frederick Pitts
wrote:<br>
</div>
<blockquote cite="mid:***@comcast.net"
type="cite">
<meta content="text/html; charset=utf-8" http-equiv="Content-Type">
<div>J<span style="font-family: Helvetica, Arial, sans-serif;">ü</span>rgen,</div>
<div><br>
</div>
<div> A cut-and-paste of the output on my platform is:</div>
<div><br>
</div>
<div>      5J3 | 4J¯1</div>
<div>⎕CT is: 1e-13</div>
<div>modulus (A) is: (5,3)</div>
<div>A=0 is: (0,0)</div>
<div>A+A=0 is: (5,3)</div>
<div>B÷A+A=0 is: (0.5,-0.5)</div>
<div>⌊B÷A+A=0 is: (1,-1)</div>
<div>A×⌊B÷A+A=0 is: (8,-2)</div>
<div>B-A×⌊B÷A+A=0 is: (-4,1)</div>
<div>¯4J1</div>
<div><br>
</div>
<div>It is identical to the output you supplied me. But I don't
think an error occurs during the evaluation of 5J3 | 4J¯1. I
think</div>
<div>the error occurs during the evaluation of</div>
<div><br>
</div>
<div>      5J3 | ¯7J6</div>
<div>⎕CT is: 1e-13</div>
<div>modulus (A) is: (5,3)</div>
<div>A=0 is: (0,0)</div>
<div>A+A=0 is: (5,3)</div>
<div>B÷A+A=0 is: (-0.5,1.5)</div>
<div>⌊B÷A+A=0 is: (-1,2)</div>
<div>A×⌊B÷A+A=0 is: (-11,7)</div>
<div>B-A×⌊B÷A+A=0 is: (4,-1)</div>
<div>4J¯1</div>
<div><br>
</div>
<div>because it says 4J¯1 is in the complete residue system for
modulus 5J3, while the 5J3 | 4J¯1 evaluation above says it
isn't.</div>
<div>If it were, evaluating 5J3 | 4J¯1 should spit 4J¯1 back at
me.</div>
<div><br>
</div>
<div> Here is a transcript of evaluating 5J3 | ¯7J6 using the
McDonnell floor function I sent in an</div>
<div>earlier email</div>
<div><br>
</div>
<div>      A ← 5J3</div>
<div>      A = 0</div>
<div>0</div>
<div>      A + A = 0</div>
<div>5J3</div>
<div>      B ← ¯7J6</div>
<div>      B ÷ A + A = 0</div>
<div>¯0.5J1.5</div>
<div>      floor B ÷ A + A = 0</div>
<div>0J1</div>
<div>      A × floor B ÷ A + A = 0</div>
<div>¯3J5</div>
<div>      B - A × floor B ÷ A + A = 0</div>
<div>¯4J1</div>
<div><br>
</div>
<div>Note that the result of the floor evaluation is 0J1, not ¯1J2
and that residue result at the end is correct.</div>
<div><br>
</div>
<div>Regards,</div>
<div><br>
</div>
<div>Fred</div>
<div><br>
</div>
<br>
</blockquote>
<br>
</body>
</html>

[Juergen Sauermann]

<html>
<head>
<meta content="text/html; charset=utf-8" http-equiv="Content-Type">
</head>
<body bgcolor="#FFFFFF" text="#000000">
<font face="Helvetica, Arial, sans-serif">Hi Fred,<br>
<br>
I am glad to hear that. It is in <b>SVN 971</b> now. It was Jay
who moved us into the right<br>
direction, thanks for that. I had used the Donell paper earlier
(when designing complex<br>
floor) but the borderline cases (i.e. when <b>⎕CT</b> makes a
difference) were not considered<br>
in the paper, and the descriptions in both ISO and the APL2
language reference are<br>
entirely misleading in that respect.<br>
<br>
Have a nice weekend,<br>
<br>
Best Regards,<br>
/// Jürgen<br>
<br>
</font><br>
<div class="moz-cite-prefix">On 06/24/2017 07:55 PM, Frederick Pitts
wrote:<br>
</div>
<blockquote cite="mid:***@comcast.net"
type="cite">
<meta content="text/html; charset=utf-8" http-equiv="Content-Type">
<div>Hello J<span style="font-family: Helvetica, Arial,
sans-serif;">ürgen,</span></div>
<div><span style="font-family: Helvetica, Arial, sans-serif;"><br>
</span></div>
<div><span style="font-family: Helvetica, Arial, sans-serif;">
SUCCESS.</span></div>
<div><span style="font-family: Helvetica, Arial, sans-serif;"><br>
</span></div>
<div><span style="font-family: Helvetica, Arial, sans-serif;"> The
cut-and-paste below from my platform is identical to yours</span></div>
<div><span style="font-family: Helvetica, Arial, sans-serif;"><br>
</span></div>
<div>      5J3 | ¯7J6</div>
<div>⎕CT is: 1e-13</div>
<div>modulus (A) is: (5,3)</div>
<div>A=0 is: (0,0)</div>
<div>A+A=0 is: (5,3)</div>
<div>B÷A+A=0 is: (-0.5,1.5)</div>
<div>⌊B÷A+A=0 is: (0,1)</div>
<div>A×⌊B÷A+A=0 is: (-3,5)</div>
<div>B-A×⌊B÷A+A=0 is: (-4,1)</div>
<div>¯4J1</div>
<div><br>
</div>
<div>and 5J3 | 4J¯1 ¯4J1 give the correct answer too.</div>
<div><br>
</div>
<div> If you want, I can patch the undebugged version of
Complex.cc and run a battery of tests. If not, I will wait and
run the tests on the next SVN version.</div>
<div><br>
</div>
<div> I think i need to find something useful to do with Gaussian
integers.</div>
<div><br>
</div>
<div>Regards,</div>
<div><br>
</div>
<div>Fred</div>
</blockquote>
<br>
</body>
</html>

[Peter Teeson]

<http://mathworld.wolfram.com/CompleteResidueSystem.html <http://mathworld.wolfram.com/CompleteResidueSystem.html>>

Post by Juergen Sauermann
Hi Fred,
I am glad to hear that. It is in SVN 971 now. It was Jay who moved us into the right
direction, thanks for that. I had used the Donell paper earlier (when designing complex
floor) but the borderline cases (i.e. when ⎕CT makes a difference) were not considered
in the paper, and the descriptions in both ISO and the APL2 language reference are
entirely misleading in that respect.
Have a nice weekend,
Best Regards,
/// JÃŒrgen

Post by Frederick Pitts
Hello JÃŒrgen,
SUCCESS.
The cut-and-paste below from my platform is identical to yours
5J3 | ¯7J6
⎕CT is: 1e-13
modulus (A) is: (5,3)
A=0 is: (0,0)
A+A=0 is: (5,3)
B÷A+A=0 is: (-0.5,1.5)
⌊B÷A+A=0 is: (0,1)
A×⌊B÷A+A=0 is: (-3,5)
B-A×⌊B÷A+A=0 is: (-4,1)
¯4J1
and 5J3 | 4J¯1 ¯4J1 give the correct answer too.
If you want, I can patch the undebugged version of Complex.cc and run a battery of tests. If not, I will wait and run the tests on the next SVN version.
I think i need to find something useful to do with Gaussian integers.
Regards,
Fred

[Frederick Pitts]

JÃŒrgen,
Using SVN 971 and testing all possible parings of Gaussian
integers where the real and imaginary parts range independently from
¯15 to 15, the residue function yields the following anomalous results
      ¯11J¯1 | ¯10J¯12 1J¯111J¯11 0      ¯11J1 | ¯12J¯10  ¯1J¯11¯1J¯11
0       ¯1J¯11 | 10J¯12  11J¯111J¯1 0      1J¯11 | 12J¯10  11J111J1
0       ¯1J11 | ¯12J10  ¯11J¯1¯11J¯1 0        1J11 | ¯10J12  ¯11J1¯11J1
0       11J¯1 | 12J10 1J111J11 0       11J1 | 10J12 ¯1J11¯1J11 0
The first item in each test result line is not in the complete residue
system  for the given modulus as evidenced by the second item on the
line.  
The same test using McDonnell's APL implementations of floor
and residue yields no errors.
Regards,
Fred

    Hi Fred,
      
      I am glad to hear that. It is in SVN 971 now. It was Jay
      who moved us into the right
      direction, thanks for that. I had used the Donell paper earlier
      (when designing complex
      floor) but the borderline cases (i.e. when ⎕CT makes a
      difference) were not considered
      in the paper, and the descriptions in both ISO and the APL2
      language reference are
      entirely misleading in that respect.
      
      Have a nice weekend,
      
      Best Regards,
      /// JÌrgen
      
    
    On 06/24/2017 07:55 PM, Frederick Pitts
    
    

Post by Frederick Pitts
      
      Hello JÌrgen,
      
        
      
          SUCCESS.
      
        
       The
          cut-and-paste below from my platform is identical to
yours
      
        
            5J3 | ¯7J6
      ⎕CT is: 1e-13
      modulus (A) is: (5,3)
      A=0 is: (0,0)
      A+A=0 is: (5,3)
      B÷A+A=0 is: (-0.5,1.5)
      ⌊B÷A+A=0 is: (0,1)
      A×⌊B÷A+A=0 is: (-3,5)
      B-A×⌊B÷A+A=0 is: (-4,1)
      ¯4J1
      
      
      and 5J3 | 4J¯1 ¯4J1 give the correct answer too.
      
      
       If you want, I can patch the undebugged version of
        Complex.cc and run a battery of tests. If not, I will wait
and
        run the tests on the next SVN version.
      
      
       I think i need to find something useful to do with Gaussian
        integers.
      
      
      Regards,
      
      
      Fred
    

    
  

[Juergen Sauermann]

[Frederick Pitts]

Hello JÃŒrgen,
I get
      ¯11J¯1 | ¯10J¯12modulus (A) is: (-11,-1)⎕CT is: 1e-13A=0 is:
(0,0)A+A=0 is: (-11,-1)B÷A+A=0 is: (1,1)bif_floor(): area c: x=1,
y=1⌊B÷A+A=0 is: (1,0)A×⌊B÷A+A=0 is: (-11,-1)B-A×⌊B÷A+A=0 is: (1,-
11)1J¯11
According to the diagram in Eugene's article, ⌊ 1J1 is 1J0, not
1J1.
Regards,
Fred

    Hi Fred,
      
      
            ¯11J¯1 |
          ¯10J¯12
          modulus (A) is: (-11,-1)
          ⎕CT is: 1e-13
          A=0 is: (0,0)
          A+A=0 is: (-11,-1)
          B÷A+A=0 is: (1,1)
          bif_floor(): area a/d: x=0, y=0
          ⌊B÷A+A=0 is: (1,1)
          A×⌊B÷A+A=0 is: (-10,-12)
          B-A×⌊B÷A+A=0 is: (0,0)
          0
      
      Attached is a debug variant using SVN 761.
      
      Best Regards,
      JÌrgen
      
    
    On 06/24/2017 09:27 PM, Frederick Pitts
    
    

Post by Frederick Pitts
      
      JÌrgen,
      
        
       Using SVN 971 and testing all possible parings of Gaussian
        integers where the real and imaginary parts range
independently
        from ¯15 to 15, the residue function yields the following
        anomalous results
      
      
            ¯11J¯1 | ¯10J¯12 1J¯11
      1J¯11 0
            ¯11J1 | ¯12J¯10  ¯1J¯11
      ¯1J¯11 0
             ¯1J¯11 | 10J¯12  11J¯1
      11J¯1 0
            1J¯11 | 12J¯10  11J1
      11J1 0
             ¯1J11 | ¯12J10  ¯11J¯1
      ¯11J¯1 0
              1J11 | ¯10J12  ¯11J1
      ¯11J1 0
             11J¯1 | 12J10 1J11
      1J11 0
             11J1 | 10J12 ¯1J11
      ¯1J11 0
      
      
      The first item in each test result line is not in the
        complete residue system for the given modulus as evidenced
by
        the second item on the line. 
      
      
       The same test using McDonnell's APL implementations of floor
        and residue yields no errors.
      
      
      Regards,
      
      
      Fred
      
      
      
      
      

 Hi Fred,
          
          I am glad to hear that. It is in SVN 971 now. It was
          Jay who moved us into the right
          direction, thanks for that. I had used the Donell paper
          earlier (when designing complex
          floor) but the borderline cases (i.e. when ⎕CT makes a
          difference) were not considered
          in the paper, and the descriptions in both ISO and the
APL2
          language reference are
          entirely misleading in that respect.
          
          Have a nice weekend,
          
          Best Regards,
          /// JÌrgen
          
        
        On 06/24/2017 07:55 PM, Frederick
        
        

          
          Hello JÌrgen,
          
            
          
              SUCCESS.
          
            
          
              The cut-and-paste below from my platform is
identical to
              yours
          
            
                5J3 | ¯7J6
          ⎕CT is: 1e-13
          modulus (A) is: (5,3)
          A=0 is: (0,0)
          A+A=0 is: (5,3)
          B÷A+A=0 is: (-0.5,1.5)
          ⌊B÷A+A=0 is: (0,1)
          A×⌊B÷A+A=0 is: (-3,5)
          B-A×⌊B÷A+A=0 is: (-4,1)
          ¯4J1
          
          
          and 5J3 | 4J¯1 ¯4J1 give the correct answer too.
          
          
           If you want, I can patch the undebugged version of
            Complex.cc and run a battery of tests. If not, I
will wait
            and run the tests on the next SVN version.
          
          
           I think i need to find something useful to do with
            Gaussian integers.
          
          
          Regards,
          
          
          Fred
        

        
      

    

    
  

[Juergen Sauermann]

<html>
<head>
<meta content="text/html; charset=utf-8" http-equiv="Content-Type">
</head>
<body bgcolor="#FFFFFF" text="#000000">
<font face="Helvetica, Arial, sans-serif">Hi Fred,<br>
<br>
thanks. Fixed in <b>SVN 972</b>.<br>
<br>
/// Jürgen<br>
<br>
</font><br>
<div class="moz-cite-prefix">On 06/24/2017 11:50 PM, Frederick Pitts
wrote:<br>
</div>
<blockquote cite="mid:***@comcast.net"
type="cite">
<meta content="text/html; charset=utf-8" http-equiv="Content-Type">
<div>Hello <span style="font-family: Helvetica, Arial,
sans-serif;">Jürgen,</span></div>
<div><br>
</div>
<div> I get</div>
<div><br>
</div>
<div>      ¯11J¯1 | ¯10J¯12</div>
<div>modulus (A) is: (-11,-1)</div>
<div>⎕CT is: 1e-13</div>
<div>A=0 is: (0,0)</div>
<div>A+A=0 is: (-11,-1)</div>
<div>B÷A+A=0 is: (1,1)</div>
<div>bif_floor(): area c: x=1, y=1</div>
<div>⌊B÷A+A=0 is: (1,0)</div>
<div>A×⌊B÷A+A=0 is: (-11,-1)</div>
<div>B-A×⌊B÷A+A=0 is: (1,-11)</div>
<div>1J¯11</div>
<div><br>
</div>
<div> According to the diagram in Eugene's article, ⌊ 1J1 is 1J0,
not 1J1.</div>
<div><br>
</div>
<div>Regards,</div>
<div><br>
</div>
<div>Fred</div>
<div><br>
</div>
<div><br>
</div>
<div>On Sat, 2017-06-24 at 23:12 +0200, Juergen Sauermann wrote:</div>
<blockquote type="cite"> <font face="Helvetica, Arial,
sans-serif">Hi Fred,<br>
<br>
interesting. I get:<br>
<br>
<b><font face="Courier New, Courier, monospace">      ¯11J¯1 |
¯10J¯12<br>
modulus (A) is: (-11,-1)<br>
⎕CT is: 1e-13<br>
A=0 is: (0,0)<br>
A+A=0 is: (-11,-1)<br>
B÷A+A=0 is: (1,1)<br>
bif_floor(): area a/d: x=0, y=0<br>
⌊B÷A+A=0 is: (1,1)<br>
A×⌊B÷A+A=0 is: (-10,-12)<br>
B-A×⌊B÷A+A=0 is: (0,0)<br>
0</font><br>
</b><br>
Attached is a debug variant using SVN 761.<br>
<br>
Best Regards,<br>
Jürgen<br>
<br>
</font><br>
<div class="moz-cite-prefix">On 06/24/2017 09:27 PM, Frederick
Pitts wrote:<br>
</div>
<blockquote cite="mid:***@comcast.net"
type="cite">
<meta content="text/html; charset=utf-8"
http-equiv="Content-Type">
<div><span style="font-family: Helvetica, Arial, sans-serif;">Jürgen,</span></div>
<div><span style="font-family: Helvetica, Arial, sans-serif;"><br>
</span></div>
<div> Using SVN 971 and testing all possible parings of
Gaussian integers where the real and imaginary parts range
independently from ¯15 to 15, the residue function yields
the following anomalous results</div>
<div><br>
</div>
<div>      ¯11J¯1 | ¯10J¯12 1J¯11</div>
<div>1J¯11 0</div>
<div>      ¯11J1 | ¯12J¯10  ¯1J¯11</div>
<div>¯1J¯11 0</div>
<div>       ¯1J¯11 | 10J¯12  11J¯1</div>
<div>11J¯1 0</div>
<div>      1J¯11 | 12J¯10  11J1</div>
<div>11J1 0</div>
<div>       ¯1J11 | ¯12J10  ¯11J¯1</div>
<div>¯11J¯1 0</div>
<div>        1J11 | ¯10J12  ¯11J1</div>
<div>¯11J1 0</div>
<div>       11J¯1 | 12J10 1J11</div>
<div>1J11 0</div>
<div>       11J1 | 10J12 ¯1J11</div>
<div>¯1J11 0</div>
<div><br>
</div>
<div>The first item in each test result line is not in the
complete residue system for the given modulus as evidenced
by the second item on the line. </div>
<div><br>
</div>
<div> The same test using McDonnell's APL implementations of
floor and residue yields no errors.</div>
<div><br>
</div>
<div>Regards,</div>
<div><br>
</div>
<div>Fred</div>
<div><br>
</div>
<div><br>
</div>
<div>On Sat, 2017-06-24 at 20:21 +0200, Juergen Sauermann
wrote:</div>
<blockquote type="cite"> <font face="Helvetica, Arial,
sans-serif">Hi Fred,<br>
<br>
I am glad to hear that. It is in <b>SVN 971</b> now. It
was Jay who moved us into the right<br>
direction, thanks for that. I had used the Donell paper
earlier (when designing complex<br>
floor) but the borderline cases (i.e. when <b>⎕CT</b>
makes a difference) were not considered<br>
in the paper, and the descriptions in both ISO and the
APL2 language reference are<br>
entirely misleading in that respect.<br>
<br>
Have a nice weekend,<br>
<br>
Best Regards,<br>
/// Jürgen<br>
<br>
</font><br>
<div class="moz-cite-prefix">On 06/24/2017 07:55 PM,
Frederick Pitts wrote:<br>
</div>
<blockquote cite="mid:***@comcast.net"
type="cite">
<meta content="text/html; charset=utf-8"
http-equiv="Content-Type">
<div>Hello J<span style="font-family: Helvetica, Arial,
sans-serif;">ürgen,</span></div>
<div><span style="font-family: Helvetica, Arial,
sans-serif;"><br>
</span></div>
<div><span style="font-family: Helvetica, Arial,
sans-serif;"> SUCCESS.</span></div>
<div><span style="font-family: Helvetica, Arial,
sans-serif;"><br>
</span></div>
<div><span style="font-family: Helvetica, Arial,
sans-serif;"> The cut-and-paste below from my platform
is identical to yours</span></div>
<div><span style="font-family: Helvetica, Arial,
sans-serif;"><br>
</span></div>
<div>      5J3 | ¯7J6</div>
<div>⎕CT is: 1e-13</div>
<div>modulus (A) is: (5,3)</div>
<div>A=0 is: (0,0)</div>
<div>A+A=0 is: (5,3)</div>
<div>B÷A+A=0 is: (-0.5,1.5)</div>
<div>⌊B÷A+A=0 is: (0,1)</div>
<div>A×⌊B÷A+A=0 is: (-3,5)</div>
<div>B-A×⌊B÷A+A=0 is: (-4,1)</div>
<div>¯4J1</div>
<div><br>
</div>
<div>and 5J3 | 4J¯1 ¯4J1 give the correct answer too.</div>
<div><br>
</div>
<div> If you want, I can patch the undebugged version of
Complex.cc and run a battery of tests. If not, I will
wait and run the tests on the next SVN version.</div>
<div><br>
</div>
<div> I think i need to find something useful to do with
Gaussian integers.</div>
<div><br>
</div>
<div>Regards,</div>
<div><br>
</div>
<div>Fred</div>
</blockquote>
<br>
</blockquote>
</blockquote>
<br>
</blockquote>
</blockquote>
<br>
</body>
</html>

[Louis Chrétien]

For your information, Dyalog APL returns this:

Dyalog APL/S-64 Version 15.0.29644
Unicode Edition
Sat Jun 24 07:28:16 2017
clear ws
5J3 ∣ 14J5 1J4 ¯4J1
1J4 ¯4J1 ¯4J1


The same as what Fred was getting.

Post by Frederick Pitts
Hello JÃŒrgen,
SVN 969 on my platform (Fedora 25, Intel(R) Core(TM) i7-6700 CPU)
5J3 | 14J5 1J4 ¯4J1
gives
1J4 ¯4J1 ¯4J1
not
¯1J4 ¯4J1 ¯4J1
Regards,
Fred

Hi,
I have changed A∣B to literally follow the paper pointed out by Jay.
The complex floor itself was already implemented like described in the paper,
but A∣B was not.
Now (SVN 969) the complex A∣B is computed as
Z←B-A×⌊B÷A+A=0
without any attempts to improve the performance of the operation.
The result in the 5J3 modulus are now the same as in IBM APL2 (and I suppose also in J)
5J3 ∣ 14J5 1J4 ¯4J1
¯4J1 ¯4J1 ¯4J1
I hope this finally fixed it. Thanks a lot to all that helped fixing this bug.
/// JÃŒrgen

I urge you to read Eugene McDonnell's Complex Floor <http://www.jsoftware.com/papers/eem/complexfloor.htm>, which also discusses Residue. I believe the design he comes up with in this paper was adopted more or less verbatim in APL. Also bear in mind that Floor and Residue in APL have to work well on all complex numbers, not just the Gaussian integers.
Jay.

Post by Frederick Pitts
Hello JÃŒrgen,
1) When performing a residue calculation on positive integers, a straight-forward integer division with remainder calculation
suffices. For example, 5 ∣ 13 is computed with 13 / 5 = 2 r 3 and so 5 ∣ 13 = 3 where 3 is in the complete residue system
{ 0, 1, 2, 3, 4 }. When performing the calculation on negative integers, one has to take advantage of the fact that the
integer division quotient and remainder are not unique in order to compute a residue that is in the complete residue system.
For 5 ∣ ¯13, ¯13 / 5 = ¯2 r ¯3 where ¯3 is not in the CRS. However, ¯13 / 5 = ¯3 r 2 where 3 is in the CSR. The same concept applies Gaussian integers.
2) I suspect the decision to have the APL2 floor function round toward negative infinity, instead of toward zero,
was made based on the desire to save cpu cycles and memory in the residue function code.
3) I read at least one math literature article discussing Gaussian integer Euclidean division algorithms, that recommended
rounding down to the nearest real and imaginary part toward negative infinity. Unfortunately I cannot find
the article right now. I will continue to look for it. None of the articles discussed using a complex integer floor function.
4) The reason MOD_TEST.apl shows total disagreement MODJ and the builtin residue function is that the complex floor function code change in SVN 965 relocated the CRS's on complex plane. Attached are CRS0-CRS1-6J-6-SVN964.out
CRS0-CRS1-6J-6-SVN965.out. The first file contains a CRS map for modulus ¯6J¯6 produced with the residue function
followed by a map for the same modulus produced with MODJ using SVN 964. The second file contains the same maps
using SVN 965. Observe that for SVN 964 the residue function CRS is in the bottom half of the complex plane, but for SVN 965 it is in the top half. The CRS for the MODJ function is in the bottom half in both SVN cases.
5)The complex floor code change did not help with the issue that the builtin residue function is not idempotent for all possible arguments and consequently generates too many residues. See attached CRSOTST0-SVN965.out. For a grid
of Gaussian integers with real and imaginary parts ranging from ¯15 to 15, using every value with every other value as modulus and second argument, there were 40 case where the order of CSR exceeded the modulus norm. I think that
was the failure count with the previous SVN.
Sincerely, I think the complex floor and ceiling functions should not be used by other functions even if IBM and ISO
imply they are in their documentations. I'm not seeing them used in the Gaussian integer literature. Again, please correct me if I'm wrong.
Regards,
Fred

Post by Juergen Sauermann
Hi again,
(¯6J¯5 - 0J¯11) ÷ ¯6J¯6
0J¯1
/// JÃŒrgen

Post by Juergen Sauermann
Hi Fred at al.,
I have made another attempt to fix the residue function, SVN 965.
For complex m∣b It now rounds down the real() and imag() parts of the quotient q←b÷m and returns b-q.
Instead of always rounding towards 0 or -infinity, the rounding direction is now (compared to the previous
attempt) determined by the quadrant in which the modulus m lies.
There are still differences to the results displayed by MOD_test.apl, but I suppose they are
LA RA MODJ |
¯6J¯6 ¯6J¯5 0J¯11 0J1
(¯6J¯5 - 0J1) ÷ ¯6J¯6
1
(0J¯11 - 0J1) ÷ ¯6J¯6
1J1
so both 0J¯11 and 0J1 are valid remainders modulo ¯6J¯6. However, the
magnitude of 0J¯11 (= 11) is larger than the magnitude of the divisor ¯6J¯6 (= around 8.4).
I suppose most people expect the remainder of a division to be in some sense
smaller than the divisor.
f←{6J6|⍵}
f ¯3 ¯2 ¯3 ¯1 0 1 2 3
3J6 4J6 3J6 5J6 0 ¯5J6 ¯4J6 ¯3J6
f f ¯3 ¯2 ¯3 ¯1 0 1 2 3
3J6 4J6 3J6 5J6 0 ¯5J6 ¯4J6 ¯3J6
f←{5J3|⍵}
f ¯3 ¯2 ¯3 ¯1 0 1 2 3
2J3 3J3 2J3 4J3 0 ¯2J5 ¯1J5 0J5
f f ¯3 ¯2 ¯3 ¯1 0 1 2 3
2J3 3J3 2J3 4J3 0 ¯2J5 ¯1J5 0J5
so at least the first modulus seems to work as well. The result is still different
5J3 ∣ 14J5 1J4 ¯4J1
¯4J1 ¯4J1 ¯4J1
5J3 ∣ 14J5 1J4 ¯4J1
1J4 1J4 1J4
But both 1J4 and ¯4J1 are valid remainders. Interestingly Jay's idempotency requirement seems to
be fulfilled by both the GNU APL and by IBM APL2, so that that requirement alone does not suffice
to tell which result is correct.
On the other hand this matter seems to be like discussing if the square root of 4 is 2 or -2 with
both answers being correct.
Best Regards,
JÃŒrgen Sauermann

JÃŒrgen,
The proposed change to DIVJ does not work because 'q1' is a complex number, so the '×' in '× q1' is the complex complement function, not the sign function. I tried the proposed change and every test fails.
I will try to hack DIVJ to use a floor towards zero instead of towards minus infinity for the real and imaginary
parts of the quotient and see what happens.
1) The order of the complete residue system (residue count) for a given modulo 'n' has to equal the norm of 'n'.
2) And as Jay Foad so succinctly expressed it, the residue function has to be idempotent with respect to its right argument,
e.g., ( n | m ) = n | n | m .
regardless of the implementation of the residue function.
Later,
Fred

Post by Juergen Sauermann
Hi Fred,
I have a question about the MOD_test.apl that you kindly provided.
z ← q , a - b × q ← CMPLX ⌊ ( 9 11 ) ○ a ÷ b
so the quotient is rounded down towards minus infinity.
I wonder if that should be something like
z ← q , (× q1) × a - b × q ← CMPLX ⌊ ∣ 9 11 ○ q1 ← a ÷ b
so that the quotient is rounded towards 0? Interestingly IBM and ISO
Z←L∣R
Z is R-L×⌊ R÷L+L=0
R←Q∣P
R←P-(×P)×|Q×⌊|P÷Q
and return R if (×R)=×Q, or R+Q
otherwise.
That suggest that IBM rounds the quotient down towards minus infinity while ISO rounds
towards 0.
My naive view on remainder is that the nearest integer quotient shall be smaller in
magnitude and not smaller in value. Regarding your proposal (which is different from
both IBM and ISO) my concern is that may lead to different results for modulo N and
modulo N×1J0
Best Regards,
JÃŒrgen Sauermann

JÃŒrgen,
This message is being resent because last minute changes I made to CRS0.apl and CRS1.apl do not output the
data I intended. This message has corrected versions of those files attached. Please discard the old CRS0.apl and CRS1.apl files. The first line of output is the modulo basis, the second line is the calculated complete residue system values and the third line is the number of residues in the CRS on the previous line.
CRSOTST0.apl and CRSOTST1.apl are unchanged.
Also please find attached MOD_TEST.apl which compares the residues calculated by MODJ and the builtin residue function and reports discrepancies. The first column of output is the modulo basis, the second column the right argument to the functions, the third column the MODJ result and the fourth column is the builtin residue function result.
Regards
Fred
Hello JÃŒrgen,
SVN 964 moved us in the right direction but not completely out of the
woods. SVN 964 still exhibits errors. For instance
2J6 | 5J5
¯1J7
2J6 | ¯1J7
¯3J1
2J6 | ¯3J1
¯3J1
I found this and previous residue function errors using the attached APL
code files. The files with base name ending in '0' use the builtin residue
function. Those with base name ending in '1' use a residue function implemented
in APL. The files with base name beginning with 'CRSOTST' test if the order of
the complete residue system (CRS) equals the norm of the modulo basis. That
test fails for several modulo bases, 2J6 being one of them, using the builtin
residue function. No errors are detected with the APL implementation. The other files
can be used to plot the CRS for a given modulo basis where 'a' and 'b' in
'a + b * i' are limited to +15 to -15 range. A full screen terminal window is
needed to see the plot.
My APL implementation of the residue function is very close to what you
described in your previous email. Maybe comparing the two implementations will
give insight into why the builtin residue function fails for some modulo bases.
I make no assertion that my implementation is correct in all
aspects.
Regards,
Fred

Post by Juergen Sauermann
Hi Frederick,
- compute the quotient Q←B÷A,
- "round down" Q to the next (complex) integer Q1,
- return B - Q1×A
Q1 ← ⌊ Q i.e. use APL floor to round down Q
Q1 ← Complex( floor(Q.real(), floor(Q.imag()) ) i,e, use C/C++ floor() to round down Q.
In your 5J3 ∣ 14J5 example, the quotient is 2.5J¯0.5, which gives different results for the APL floor ⌊ and the C/C++ floor().
The APL floor ⌊2.5J¯0.5 is 3J¯1 (a somewhat dubious invention in the ISO standard on page 19, which I used up to
including SVN 963), while the C/C++ floor() is 2J¯1. The difference between the APL floor and the C/C++ floor is 1.0 which,
multiplied by the divisor, explains the differences that we see.
As of SVN 964 I have changed the residue function (∣) to use the C/C++ floor instead of the APL floor. The APL floor and
Ceiling functions (⌊ and ⌈) are still using the apparently broken definition in the ISO standard.
5J3 | 14J5
1J4
5J3 | 1J4
1J4
5J3 | 14J5
¯4J1
5J3 | 1J4
¯4J1
Best Regards,
/// JÃŒrgen

JÃŒrgen,
With gnu apl (svn 961 on Fedora 25, Intel(R) Core(TM) i7-6700
5J3 ∣ 14J5
1J4
5J3 | 1J4
¯4J1
5J3 | ¯4J1
¯4J1
The above result means that two elements in the complete residue system
(CSR) for mod 5J3 are equal, i.e. 1J4 = ¯4J1 mod 5J3, which is not
allowed. None of the elements of a CSR can be equal modulo the CSR's
basis.
Regards,
Fred

---
Louis Chrétien
***@mac.com

[Frederick Pitts]

Jay,
Before your email, I had read portions of McDonnell's Complex
Floor article.  Now I've read it in its entirety.  I do not see
anything in the article that contradicts my view the residue function
should be idempotent and capable of reproducing the complete residue
system for a given modulus.
Gaussian integers ARE complex numbers. If the APL residue
function has to work well on all complex numbers, it has to work well
on Gaussian integers which is not happening right now in Gnu APL.
Respectfully,
Fred

I urge you to read Eugene McDonnell's Complex Floor, which also
discusses Residue. I believe the design he comes up with in this
paper was adopted more or less verbatim in APL. Also bear in mind
that Floor and Residue in APL have to work well on all complex
numbers, not just the Gaussian integers.
Jay.

Post by Frederick Pitts
    
  
  Hello JÌrgen,
1) When performing a residue calculation on positive integers, a
straight-forward integer division with remainder calculation
suffices.  For example, 5 ∣ 13  is computed with 13 / 5 = 2 r 3 and
so 5 ∣ 13 = 3 where 3 is in the complete residue system
{ 0, 1, 2, 3, 4 }.  When performing the calculation on negative
integers, one has to take advantage of the fact that the
integer division quotient and remainder are not unique in order to
compute a residue that is in the complete residue system.
For 5 ∣ ¯13, ¯13 / 5 = ¯2 r ¯3 where ¯3 is not in the
CRS.  However, ¯13 / 5 = ¯3 r 2 where 3 is in the CSR.  The same
concept applies Gaussian integers.
2) I suspect the decision to have the APL2 floor function round
toward negative infinity, instead of toward zero,
was made  based on the desire to save cpu cycles and memory in the
residue function code.
3) I read at least one math literature article discussing Gaussian
integer Euclidean division algorithms, that recommended
rounding down to the nearest real and imaginary part toward
negative infinity.  Unfortunately I cannot find
the article right now.  I will continue to look for it.  None of
the articles discussed using a complex integer floor function.
4) The reason MOD_TEST.apl shows total disagreement  MODJ and the
builtin residue function is that the complex floor function code
change in SVN 965 relocated the CRS's on complex plane.  Attached
are CRS0-CRS1-6J-6-SVN964.out
CRS0-CRS1-6J-6-SVN965.out.  The first file contains a CRS map for
modulus ¯6J¯6 produced with the residue function
followed by a map for the same modulus produced with MODJ using SVN
964.  The second file contains the same maps
using SVN 965.  Observe that for SVN 964 the residue function CRS
is in the bottom half of the complex plane, but for SVN 965 it is
in the top half.  The CRS for the MODJ function is in the bottom
half in both SVN cases.
5)The complex floor code change did not help with the issue that
the builtin residue function is not idempotent for all possible
arguments and consequently generates too many residues.  See
attached CRSOTST0-SVN965.out.  For a grid
of Gaussian integers with real and imaginary parts ranging from ¯15
to 15, using every value with every other value as modulus and
second argument, there were 40 case where the order of CSR exceeded
the modulus norm.  I think that
was the failure count with the previous SVN.
Sincerely, I think the complex floor and ceiling functions
should not be used by other functions even if IBM and ISO
imply they are in their documentations.  I'm not seeing them used
in the Gaussian integer literature.  Again, please correct me if
I'm wrong.
Regards,
Fred

    Hi again,
    
    
          (¯6J¯5 - 0J¯11) ÷ ¯6J¯6 
    0J¯1
    
    /// JÌrgen
    
    On 06/22/2017 05:44 PM, Juergen
    
    

Post by Frederick Pitts
      
      Hi Fred at al.,
        
        I have made another attempt to fix the residue
function, SVN
          965.
        
        For complex m∣b It now rounds down the real() and
imag()
        parts of the quotient q←b÷m and returns b-q.
        Instead of always rounding towards 0 or -infinity, the
rounding
        direction is now (compared to the previous
        attempt) determined by the quadrant in which the
modulus m
        lies.
      
      There are still differences to the results displayed by
MOD_test.apl, but I
        suppose they are
        caused by that program. For example, the first line of
          
          LA   
            RA   MODJ   |
          ¯6J¯6 ¯6J¯5   0J¯11  0J1
        
        
              (¯6J¯5 - 0J1) ÷ ¯6J¯6 
        1
              (0J¯11 - 0J1) ÷ ¯6J¯6
        1J1
        
        so both 0J¯11 and 0J1 are valid remainders
        modulo ¯6J¯6. However, the
        magnitude of 0J¯11
        (= 11) is larger than the magnitude of the divisor
¯6J¯6 (= around 8.4).
          I suppose most people expect the remainder of a
division to be
          in some sense
          smaller than the divisor.
          
          
               
              f←{6J6|⍵}
                    f ¯3 ¯2 ¯3 ¯1 0 1 2 3
              3J6 4J6 3J6 5J6 0 ¯5J6 ¯4J6 ¯3J6
                    f f ¯3 ¯2 ¯3 ¯1 0 1 2 3
              3J6 4J6 3J6 5J6 0 ¯5J6 ¯4J6 ¯3J6
          
                    f←{5J3|⍵}
                    f ¯3 ¯2 ¯3 ¯1 0 1 2 3
              2J3 3J3 2J3 4J3 0 ¯2J5 ¯1J5 0J5
                    f f ¯3 ¯2 ¯3 ¯1 0 1 2 3
              2J3 3J3 2J3 4J3 0 ¯2J5 ¯1J5 0J5
            
          so at least the first modulus seems to work as well.
The
          result is still different
          
          
                5J3 ∣
              14J5 1J4 ¯4J1
      ¯4J1 ¯4J1 ¯4J1
              
      
            5J3 ∣ 14J5 1J4 ¯4J1 
                1J4 1J4 1J4
              
            But both 1J4 and ¯4J1 are
          valid remainders. Interestingly Jay's idempotency
requirement
          seems to
          be fulfilled by both the GNU APL and by IBM APL2, so
that that
          requirement alone does not suffice
          to tell which result is correct.
          
          On the other hand this matter seems to be like
discussing if
          the square root of 4 is 2 or -2 with
          both answers being correct.
          
          Best Regards,
          JÌrgen Sauermann
          
          
        
           
      On 06/21/2017 10:25 PM, Frederick
      
      

        
        JÌrgen,
        
        
         The proposed change to DIVJ does not work because
'q1' is
          a complex number, so the '×' in '× q1' is the
complex
          complement function, not the sign function. I tried
the
          proposed change and every test fails.
        
        
         I will try to hack DIVJ to use a floor towards zero
          instead of towards minus infinity for the real and
imaginary
        parts of the quotient and see what happens.
        
        
         Correct me if I am wrong, but my mind set is that
the APL
          residue function has to satisfy the following
        1) The order of the complete residue system (residue
count)
          for a given modulo 'n' has to equal the norm of
'n'.
        2) And as Jay Foad so succinctly expressed it, the
residue
          function has to be idempotent with respect to its
right
          argument,
         e.g., ( n | m ) = n | n | m .
        regardless of the implementation of the residue
function.
        
        
        Later,
        
        
        Fred 
        
        
        
        
        
        
        
        
        On Wed, 2017-06-21 at 19:46 +0200, Juergen Sauermann
        

 Hi Fred,
            
            I have a question about the MOD_test.apl that
you
            kindly provided.
            
            
            z ← q , a -
                b × q ← CMPLX ⌊ ( 9 11 ) ○ a ÷ b
            
            so the quotient is rounded down towards minus
infinity.
            
            I wonder if that should be something like
            
            z ← q , (×
                q1) × a - b × q ← CMPLX ⌊ ∣ 9 11 ○ q1 ← a ÷
b
            
            so that the quotient is rounded towards 0?
Interestingly IBM
            and ISO
            give different definitions for the residue in
            
            Z←L∣R
              Z is R-L×⌊  R÷L+L=0
            
            ISO (chapter 7.2.9 Residue): 
            R←Q∣P
              R←P-(×P)×|Q×⌊|P÷Q
                and return R if (×R)=×Q, or R+Q
                otherwise.
               
          That suggest that IBM rounds the quotient down
towards minus
          infinity while ISO rounds
           towards 0.
          
          My naive view on remainder is that the nearest
integer
          quotient shall be smaller in
          magnitude and not smaller in value. Regarding
your proposal
          (which is different from
          both IBM and ISO) my concern is that may lead to
different
          results for modulo N and
          modulo N×1J0
          
          Best Regards,
          JÌrgen Sauermann
          
          
          On 06/21/2017 03:08 AM, Frederick
          
          

            JÌrgen,
            
              
             This message is
                being resent because last minute changes
I made to
                CRS0.apl and CRS1.apl do not output the
            data I intended.
                 This message has corrected versions of
those files
                attached.  Please discard the old
CRS0.apl and CRS1.apl
                files.  The first line of output is the
modulo basis, the second line is the
                calculated complete residue system values
and the third
                line is the number of residues in the
CRS on the previous line.
            
              
             CRSOTST0.apl and
                CRSOTST1.apl are unchanged.
            
              
             Also please find
                attached MOD_TEST.apl which compares the
residues
                calculated by MODJ and the builtin
residue function and
                reports discrepancies.  The first column
of output is
                the modulo basis, the second column the
right argument
                to the functions, the third column the
MODJ result and
                the fourth column is the builtin residue
function
                result.
            
              
            Regards
            
              
            Fred
            
            
            Hello JÌrgen,
             SVN 964 moved us in the right
direction but not completely out of the
            woods.  SVN 964 still exhibits errors.  For
instance
                  2J6 | 5J5
            ¯1J7
                  2J6 | ¯1J7
            ¯3J1
                  2J6 | ¯3J1
            ¯3J1
             I found this and previous residue
function errors using the attached APL
            code files.  The files with base name ending
in '0' use the builtin residue
            function.  Those with base name ending in '1'
use a residue function implemented
            in APL.  The files with base name beginning
with 'CRSOTST' test if the order of
            the complete residue system (CRS) equals the
norm of the modulo basis.  That
            test fails for several modulo bases, 2J6
being one of them, using the builtin
            residue function. No errors are detected with
the APL implementation.  The other files
            can be used to plot the CRS for a given
modulo basis where 'a' and 'b' in
            'a + b * i' are limited to +15 to -15
range.  A full screen terminal window is
            needed to see the plot.
             My APL implementation of the residue
function is very close to what you
            described in your previous email.  Maybe
comparing the two implementations will
            give insight into why the builtin residue
function fails for some modulo bases.
             I make no assertion that my
implementation is correct in all
            aspects.
            Regards,
            Fred
            On Tue, 2017-06-20 at 14:14 +0200, Juergen
Sauermann
            

 Hi Frederick,
                
                the algorithm for A ∣ B used in GNU APL
                
                -
                    compute the quotient Q←B÷A,
                  - "round down" Q to the next
(complex) integer
                    Q1,
                  - return B - Q1×A
                
                Now the problem seems to be what is
meant by "round
                
                  Q1 ←
                    ⌊
Q                                          i.e.
                    use APL floor to round down Q
                    Q1 ← Complex( floor(Q.real(),
floor(Q.imag())
                    )   i,e, use C/C++ floor() to round
down Q.
                  
                In your  5J3 ∣ 14J5 example, the
quotient is 2.5J¯0.5,
                which gives different results for the
APL floor ⌊
                and the C/C++ floor().
                
                The APL floor ⌊2.5J¯0.5
                  is 3J¯1 (a somewhat dubious
                invention in the ISO standard on page
19, which I used
                up to
                including SVN 963), while the C/C++
floor() is 2J¯1.
                The difference between the APL floor
and the C/C++ floor
                is 1.0 which,
                multiplied by the divisor, explains the
differences that
                we see.
                
                As of SVN 964 I have changed the
residue
                function (∣) to use the C/C++ floor
instead of
                the APL floor. The APL floor and
                Ceiling functions (⌊ and ⌈) are still
                using the apparently broken definition
in the ISO
                standard.
                
                I hope this works better for you. At
least I am getting
                
                     
                    5J3 | 14J5
                  1J4
                        5J3 | 1J4
                  1J4
                
                
                     
                    5J3 | 14J5
                  ¯4J1
                        5J3 | 1J4
                  ¯4J1
                
                
                Best Regards,
                /// JÌrgen
                
              
              
              On 06/19/2017 07:03 PM,
              
              

                JÌrgen,
With gnu apl (svn 961 on Fedora 25, Intel(R)
Core(TM) i7-6700
      5J3 ∣ 14J5
1J4
      5J3 | 1J4
¯4J1
      5J3 | ¯4J1
¯4J1
The above result means that two elements in the
complete residue system
(CSR) for mod 5J3 are equal, i.e. 1J4 = ¯4J1 mod 5J3,
which is not
allowed.  None of the elements of a CSR can be equal
modulo the CSR's
basis.
Regards,
Fred