🔬58. A word on polymod in Perl 6

Before moving to the second part of the Real role, let us stop on the polymod method of the Int class.

The method takes a number and a list of arbitrary numbers (units) and returns the corresponding multipliers. So that you can easily say that 550 seconds, for example, is 9 minutes and 10 seconds:

> 550.polymod(60)
(10 9)

In the method call, the value of 60 is the number of seconds in a minute. In the result, 9 is a number of minutes, and 10 is a remainder, which is a number of seconds. So, 550 seconds = 10 second + 9 minutes.

If you want more details, add more units. For example, what is it 32768 seconds?

> 32768.polymod(60, 60, 24)
(8 6 9 0)

It is 8 seconds, 6 minutes, 9 hours, and 0 days.

Similarly, 132768 seconds are 1 day, 12 hours, 52 minutes, and 48 seconds:

> 132768.polymod(60, 60, 24)
(48 52 12 1)

Honestly, it was quite difficult for me to understand how it works and how to read the result.

Another example from the documentation was even harder:

> 120.polymod(1, 10, 100)
(0 0 12 0)

What does 12 mean? It is, obviously, 12 times 10. OK, But I asked to give me some information about the number of hundreds. My expectation is to have it like that: 120 is 2 times 10 and 1 time 100.

Try 121:

> 121.polymod(1, 10)
(0 1 12)

Erm, why zero? Zero plus 1 times 1 plus 12 times 10? Brr. Ah! You don’t need to specify an explicit 1 in the arguments:

> 121.polymod(10)
(1 12)

That makes more sense. Except the fact that I still don’t know how many hundreds are there in 121:

> 121.polymod(10, 100)
(1 12 0)
> 121.polymod(100, 10)
(21 1 0)

It’s time to take a look at the source code (src/core/Int.pm):

method polymod(Int:D: +@mods) {
    fail X::OutOfRange.new(
        :what('invocant to polymod'), :got(self), :range<0..^Inf>
    ) if self < 0; 

    gather { 
         my $more = self; 
         if @mods.is-lazy { 
             for @mods -> $mod {
                $more
                    ?? $mod
                    ?? take $more mod $mod
                    !! Failure.new(X::Numeric::DivideByZero.new:
                            using => 'polymod', numerator => $more)
                    !! last;
                $more = $more div $mod;
            }
            take $more if $more;
        }
        else {
            for @mods -> $mod {
                $mod
                    ?? take $more mod $mod
                    !! Failure.new(X::Numeric::DivideByZero.new:
                        using => 'polymod', numerator => $more);
                $more = $more div $mod;
            }
            take $more;
        }
    }
}

The method has two branches, one for lazy lists, and another one for non-lazy lists. Let us only focus on the second branch for now:

for @mods -> $mod {
    $mod
        ?? take $more mod $mod
        !! Failure.new(X::Numeric::DivideByZero.new:
                       using => 'polymod', numerator => $more);
    $more = $more div $mod;
}

take $more;

OK, the last take takes the remainder, that’s easy. In the loop, you divide the number by the next unit and then ‘count’ the intermediate reminder.

I would say I would implement it differently and switch the operators:

  for @mods -> $mod {
      $mod
-           ?? take $more mod $mod
+           ?? take $more div $div
          !! Failure.new(X::Numeric::DivideByZero.new:
                         using => 'polymod', numerator => $more);
-      $more = $more div $mod;
+      $more = $more mod $mod;
  }

  take $more;

With this code, I can get the number of hundreds, tens, and ones in 121:

> 121.polymod(100, 10, 1)
(1 2 1 0)

OK, let’s avoid two 1s:

> 1234.polymod(1000, 100, 10, 1)
(1 2 3 4 0)

Also works fine with the earlier example with seconds:

> 132768.polymod(86400, 3600, 60)
(1 12 52 48)

It is 1 day, 12 hours, 52 minutes, and 48 seconds.

As you see, now you have to use explicit units (8600 instead of 24) and you have to sort them in descending order, but now I can understand and explain the result, which I could hardly do for the original method.

 

8 thoughts on “🔬58. A word on polymod in Perl 6

  1. So, I don’t think I was in any way responsible for polymod, though I did vaguely remember it existed.

    But I think you’re getting tangled up here, led on by the weird (probably needs to be removed / seriously changed) 120.polymod(1, 10, 100) example. With the time examples, the numbers are 60, 60, 24:

    60 seconds in a minute.
    60 minutes in an hour.
    24 hours in a day.

    If you apply that logic to 1, 10, 100, what you are looking at is

    1 whatever in a whatever (completely pointless, as you work out).
    10 ones in a ten.
    100 tens in a thousand.

    So if you want to do ones, tens, hundreds, etc. you need to do polymod(10,10)

    10 ones in a ten.
    10 tens in a hundred.

    > 123.polymod(10,10)
    (3 2 1)

    When you look at it with that lens, the original code makes perfect sense. So if for some perverse reason you wanted to get your base 10 digits this way, it’s just

    > 12534.polymod(10 xx *)
    (4 3 5 2 1)

    Like

  2. As a mildly practical example, when I did https://github.com/colomon/monty, the game states are encoded in a big int and then decoded with bits like

    my $roll = ($big-num +& 0b110) div 2;
    my $reveal-cup = $big-num +& 0b1000 ?? 1 !! 0;

    If I’d known about polymon, I could have done the full decode in one much easier-to-read step:

    my ($entropy, $roll, $reveal-cup) = $big-num.polymon(2, 4, 2);

    Which makes me wonder if there is an opposite function to polymod?

    Like

    1. I kind of understand all of the above with 10 xx ** etc, but it is so unobvious why we need it in the core. The example with bits (which are not Perl’s target) supports the idea that there is no much sense of having the method in core Perl 🙂

      Like

  3. I would interpret polymod like a chaining of N pair of operations, namely mod and integer division, in the fashion you would do to convert a number to any base, collecting the reminders; so, 120.polymod(1,10,100) is: 120/1 is 120(reused for the next step in chain), r =0(collected), 120/10 is 12(…), r =0 (collected), 12/100 is 0, r=12(collected), and then the last remaining value is also collected, hence (0,0,12,0)

    Like

    1. Then, I like to add that it’s nice to have it in core perl6 also because it makes easy to convert a number to any base you want, using the already mentioned base xx * argument, being base the base you want to convert to.

      Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s