Re: [lmi] Remainder of integer division

[Greg Chicares]

On 2018-09-10 21:49, Vadim Zeitlin wrote:
> On Mon, 10 Sep 2018 21:18:45 +0000 Greg Chicares <address@hidden> wrote:
> 
> GC> On 2018-09-07 13:52, Vadim Zeitlin wrote:
> GC> [...]
> GC> > I think dividing by a negative integer
> GC> > is such a rare operation
> GC> And I suppose taking the remainder of such an operation is even rarer, 
> but,
> GC> incidentally, I happened to try that something like a day or two ago. In
> GC> commit 177f78f2, this is one of the two statements that I wanted to 
> rewrite
> GC> so that it would work even with a page count of zero:
> GC> 
> GC> -    int const rows_on_last_page = total_rows_ - (page_count_ - 1) * 
> rows_per_page_;
> GC> +    int const pages_before_last = (0 == page_count_) ? 0 : page_count_ - 
> 1;
> GC> +    int const rows_on_last_page = total_rows_ - rows_per_page_ * 
> pages_before_last;
> GC> 
> GC> It offended my aesthetic sense to use the page count there at all, because
> GC> the number of rows on the last page can be calculated without it.
> 
>  Yes, but sometimes aesthetic and simplicity are not collinear

What I now realize more clearly is that, in a given circumstance, they
may be collinear in one language, but not even be coplanar in another.

> and in this
> case I optimized for the latter.

Yes, and the revision above retains that decision, merely extending it
to handle the zero-rows-of-data case...

> Because at least for me the most natural
> answer to the question of "how many rows are there on the last page?" is
> "all the remaining rows after filling all the previous page".

...by taking into account that, if there's only one page, and that page
has zero rows, then the "preceding" page is not "Page -1", and the
answer we seek is not (-1 * rows_per_page).

>  But if we really wanted to get rid of the page count, I'd write this as
> 
>       rows_on_last_page = total_rows_ % rows_per_page_;
>       if ( !rows_on_last_page )
>               rows_on_last_page = rows_per_page_;
> 
> which is only slightly less simple to understand but gives the same result
> for any strictly positive number of rows, which should be the case here
> (and if it isn't, a trivial addition of "&& total_rows_" would fix this).

Some such trivial addition is required. Below, I show a patch (which
won't be applied, of course) that contrasts and validates various
alternatives, including this one. (Looking back, I like your "&& ..."
better than what I added below.)

>  I definitely wouldn't write the above as a single expression although I
> could consider writing it as
> 
>       int const rows_on_last_page = [=]()
>               {
>               int const rem = total_rows_ % rows_per_page_;
>               return rem ? rem : rows_per_page_;
>               }();
> 
> just to keep the variable const.

Also included below, with an adjustment for the zero-rows case.

> GC> And I know how to do that in APL, where it's so simple: 'N-N|N-X' is
> GC> the natural answer for X rows in groups of N, and to handle the special
> GC> case of zero you just multiply by signum(X), so it's '(×X)×N-N|N-X'.
> GC> 
> GC> For example, with [1..9] rows in groups of 3:
> GC> 
> GC>     index origin 0
> GC>     N ← 3
> GC>     X ← ⍳10
> GC>     0  1  2  3  1  2  3  1  2  3   desired answer
> GC>     ----------------------------
> GC>     0  1  2  3  4  5  6  7  8  9              X
> GC>     3  2  1  0 ¯1 ¯2 ¯3 ¯4 ¯5 ¯6            N-X
> GC>     0  2  1  0  2  1  0  2  1  0          N|N-X
> GC>     3  1  2  3  1  2  3  1  2  3        N-N|N-X
> GC>     0  1  1  1  1  1  1  1  1  1    ×X
> GC>     0  1  2  3  1  2  3  1  2  3   (×X)×N-N|N-X
> GC> 
> GC> where
> GC>  ← is assignment
> GC>  ⍳ is like std::iota()
> GC>  | is "residue", like C's '%' for positive integers
> GC>  × with no left argument is signum
> GC>  × with left and right arguments is multiplication
> GC> and everything is read from right to left (all operators--same 
> precedence).
> 
>  I admit APL is pretty clear with your explanations _and_ the table above.
> I also admit I'd have some trouble unpacking this simple expression without
> either of them.

That's actually how APL is both read and written in practice.
What's wanted is just a scalar function of two scalars, so we
start with a reasonable value for the less interesting one, and
a 'vector' for the other one (number of data) that encompasses
enough of the intended range to constitute an adequate unit test.
Then we build up an expression, one character at a time, until it
does the right thing. Because it's an interpreted language,
anything we type on the console is evaluated and printed, e.g.:

      ⍳10
0 1 2 3 4 5 6 7 8 9

kind of like an elaborate "desk calculator".

Conversely, to read a complicated expression, we evaluate and
examine the results of subexpressions. With experience, we find
that we can read them without using "desk calculator" mode, and
the language has become a tool of thought. It's been a quarter
century since I wrote any APL, but I still know without thinking
that 'N-N|N-X' is the kernel of what's wanted here, and it takes
only a moment to see that the result must be multiplied by sgn(X).
(It could be multiplied by '0≠X' instead of '×X', but that would
require an entire extra character.)

Isn't that pretty much the way a lot of perl is written? It's
certainly the technique I use to write complex sed expressions.

> GC> I wondered whether I could do the same thing in C++ (of course I can)
> GC> and make it seem natural (I couldn't):
> 
>  FWIW the version with the immediately called after declaring it lambda
> above is seen as natural in modern C++, whether you like it or not (I
> rather do, although mostly in more complicated cases than this one).

That inspired the intriguing but unsuccessful experiment below where
I use a lambda to substitute APL-ish single-character names for C++
variables, in order to increase a C++ expression's density. Clarity
did not emerge as I had hoped, alas; without RPN, it can't be APL.

> GC>     for(auto& i : X) {i = (0!=i)*(N-(N+(N-i)%N)%N);}  show(X);
[...]
> GC> but the expression is unreadable.
> 
>  It's definitely less readable than any version above.

Yeah. FWIW, here's a throwaway patch that demonstrates all these
ideas, none of which IMO is better than commit 177f78f2. Observing
that this is a pretty common C idiom:
  quotient  = dividend / divisor;
  remainder = dividend % divisor;
I imagine that the ideal solution here would be to write a
"remainder" counterpart to outward_quotient(), which would give us
the missing element of the {quotient,remainder} pair directly. I'm
just not going to spend time on that right now.

diff --git a/report_table_test.cpp b/report_table_test.cpp
index 9b24a6da..0d3c5533 100644
--- a/report_table_test.cpp
+++ b/report_table_test.cpp
@@ -571,8 +571,62 @@ void report_table_test::test_paginator()
     std::cout << paginate(9, 2, 7) << std::endl;
 }
 
+#include "math_functions.hpp"           // outward_quotient()
+
+inline constexpr int residue(int modulus, int datum)
+{return (modulus + datum % modulus) % modulus;}
+
 int test_main(int, char*[])
 {
+    int const rows_per_page_ = 3;
+  for(int total_rows_ = 0; total_rows_ < 10; ++total_rows_)
+    {
+    int const page_count_ = outward_quotient(total_rows_, rows_per_page_);
+
+    int const pages_before_last = (0 == page_count_) ? 0 : page_count_ - 1;
+    int const rows_on_last_page = total_rows_ - rows_per_page_ * 
pages_before_last;
+
+    int rows_on_last_page1 = total_rows_ % rows_per_page_;
+    if(!rows_on_last_page1)
+        rows_on_last_page1 = rows_per_page_;
+    if(!total_rows_)
+        rows_on_last_page1 = 0;
+
+    int const rows_on_last_page2 = [=]()
+        {
+        int const rem = total_rows_ % rows_per_page_;
+        int const xyz = rem ? rem : rows_per_page_;
+        return total_rows_ ? xyz : 0;
+        }();
+
+    int const rows_on_last_page3 =
+          (rows_per_page_ - residue(rows_per_page_, rows_per_page_ - 
total_rows_))
+        * (0 != total_rows_)
+        ;
+
+    int const rows_on_last_page4 = [=]()
+        {
+        int const N = rows_per_page_;
+        int const X = total_rows_;
+        return (0!=X)*(N-(N+(N-X)%N)%N);
+        }();
+
+    std::cout
+        << total_rows_ << " total_rows_\n"
+        << rows_on_last_page  << " rows_on_last_page \n"
+        << rows_on_last_page1 << " rows_on_last_page1\n"
+        << rows_on_last_page2 << " rows_on_last_page2\n"
+        << rows_on_last_page3 << " rows_on_last_page3\n"
+        << rows_on_last_page4 << " rows_on_last_page4\n"
+        << std::endl
+        ;
+
+    LMI_ASSERT(rows_on_last_page == rows_on_last_page1);
+    LMI_ASSERT(rows_on_last_page == rows_on_last_page2);
+    LMI_ASSERT(rows_on_last_page == rows_on_last_page3);
+    LMI_ASSERT(rows_on_last_page == rows_on_last_page4);
+    }
+
     report_table_test::test();
     return EXIT_SUCCESS;
 }