Proposal: guard-safe modulo function `mod(a, n)`

[Wiebe-Marten Wijnja]

Elixir has `rem(dividend, divisor)` to calculate the remainder of an integer division. However, as you probably know, there are different ways to handle remainders with negative numbers:

`rem` will take the remainder, but use the sign of the dividend, which means that the following function definition:

def is_odd(n)
  rem(n, 2) == 1
end

will fail for -1, -3, etc, as `rem(-3, 2)`, for instance, has as answer -1.

It is also possible to make a modulo function, which uses the sign of the divisor. This has the advantage over the remainder function that it maps the whole domain of integers unto a smaller, cyclic, range of numbers. This is highly useful in many algorithms dealing with numbers or indices.

Many programming languages both have a remainder and a modulo function. I have seen multiple people roll their own definitions of `mod` in their Elixir libraries, because they needed it. 

I propose the addition of the modulo function, `mod(a, n)` to Elixir.

A possible implementation is as follows:

defmacro mod(a, n) do
  quote do
    unquote(a) - (unquote(n) * div(unquote(a), unquote(n))
  end
end

This implementation is guard-safe, so it can be used anywhere where `div` and `rem` are also allowed.

[José Valim]

Yes, please send a pull request. :)

José Valim

www.plataformatec.com.br

Skype: jv.ptec

Founder and Director of R&D

--
You received this message because you are subscribed to the Google Groups "elixir-lang-core" group.
To unsubscribe from this group and stop receiving emails from it, send an email to elixir-lang-core+unsubscribe@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/elixir-lang-core/3b010961-59a1-408c-9b17-4bd9179d4a95%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Wiebe-Marten Wijnja]

I have been fiddling around with this for quite some time. Other than I thought, `div` also uses truncated division. (It makes sense, as it complements `rem`). This makes above implementation moot.

To be able to create `mod`, we need a floored division. I have not yet found a way to do this without using conditionals (an easy way would be to subtract one from the result of `div` iff the result is a negative number), which are not allowed in guard clauses.

I will not give up yet, but it might very well be impossible.

[eksperimental]

I have tried to implement a guard safe version this in the past, to no
avail. The limitation that I can remember was to not to be able to use
a conditional in the guards, which let me to create conditionals using
boolean operators.. it didn't work.
I will be happy to see a solution.

On Mon, 8 Aug 2016 03:25:34 -0700 (PDT)
Wiebe-Marten Wijnja <w.m.w...@panache-it.com> wrote:

> I have been fiddling around with this for quite some time. Other than
> I thought, `div` also uses truncated division. (It makes sense, as it
> complements `rem`). This makes above implementation moot.
>
> To be able to create `mod`, we need a floored division. I have not
> yet found a way to do this without using conditionals (an easy way
> would be to subtract one from the result of `div` iff the result is a
> negative number), which are not allowed in guard clauses.
>
> I will not give up yet, but it might very well be impossible.
>
> On Monday, August 8, 2016 at 10:24:12 AM UTC+2, Wiebe-Marten Wijnja
> wrote:
> >
> > Elixir has `rem(dividend, divisor)` to calculate the remainder of
> > an integer division. However, as you probably know, there are
> > different ways to handle remainders with negative numbers:
> >
> > `rem` will take the remainder, but use the sign of the dividend,
> > which means that the following function definition:
> >
> > def is_odd(n)
> > rem(n, 2) == 1
> > end
> >
> > will fail for -1, -3, etc, as `rem(-3, 2)`, for instance, has as

> > answer *-1*.
> >
> > It is also possible to make a *modulo* function, which uses the

[Wiebe-Marten Wijnja]

All right! It took most of today, but I've solved the problem!

Problem: Elixir does not have a (guard-safe) Floored Modulo Remainder function `mod`.

Proposed solution: Implement with floored division, as follows:

mod(a, n) === a - (n * floor_div(a, n))

Subproblem: Elixir does not have (guard-safe) Floored Division.

Proposed solution: Implement Floored Division by using the existing Truncated Division BIF `div/2`.

To change Truncated Division to Floored Division, 

we need to add (-1) to the result, iff one of the signs of `a` and `n` is negative,

Six cases: (n == 0 is invalid input as it would result in a division by 0)

a | n | div(a,n) + ?
+ | + |  0
- | + | -1
+ | - | -1
- | - |  0
0 | + |  0
0 | - |  0

New Subproblem: Find a function that produces these outputs, given `a` and `n`.

The approach I took, was to adapt the `sign` function.

x => sign(x)
+ => +1
- => -1
0 -> 0

 a | n  => sign(a * n)
 + | +  => +1
 - | +  => -1
 + | -  => -1
 - | -  => +1
 0 | +  =>  0
 0 | -  =>  0

Now we need to find the transforming function that maps the output of sign(a*n) to the requested format:

      -1 -> -1
 {0, +1} ->  0

Solution: div(sign(x) - 1, 2)

Truth table:

div(+1 - 1, 2)  =>  0
div(0 - 1, 2)   =>  0
div(-1 - 1, 2)  => -1

New Subproblem: Elixir does not have a (guard-safe) `sign/1` function.

Solution: `sign/1` can be constructed from dividing the number by its absolute value:

`div(x, abs(x))`

However, special care has to be taken to prevent division-by-zero!

This was where I was stuck for some time, but I found out we can circumvent this problem by 'cheating' a little: 

Observe:

 a) 0 / 1 == 0 which is the wanted output for sign(0).

 b) forall x != 0, abs(x) >= 1

Therefore, we can write the definition of `sign` as:

div(x, max(abs(x), 1)))

New Subproblem: Elixir does not have a guard-safe `max/2` function.

Solution: The implementation of this function is straightforward:

max(a, b) === div((a + b) + abs(a - b), 2)

I will now continue on making a pull request out of this.

This approach introduces quite a few intermediate steps, so `mod` is going to be less efficient than `rem`; fully expanded, `mod` will be:

div(a, n) + div(div(a * n, div((abs(a * n) + 1) + abs(abs(a * n) - 1), 2)) - 1, 2)

that is four `div/2` three `abs/1`, and a couple of +, - and * operations.

I am wondering: What should we do with the guard-safe `max` and `sign` implementations (and maybe `floor_div`) I found while attempting to make this?

Their advantage is that they work inside guard clauses. We could use this version of `max` inside a guards, similar as how `in` has a different implementation inside guards vs inside function bodies.

Their disadvantage is that they only work for integer operands, which might maybe confuse newcomers.

Inside the PR I could either:

- make full-fledged macros out of them that are documented and publicly visible. ( I would then also add a `min` variant, of course).

- make private macros out of them that are only used for `mod`.

- Not even make private macros out of them, but mention them inline in the implementation of `mod`.

What do you think?

On Monday, August 8, 2016 at 10:24:12 AM UTC+2, Wiebe-Marten Wijnja wrote:

[Wiebe-Marten Wijnja]

The PR can be found here, by the way: https://github.com/elixir-lang/elixir/pull/5112

On Monday, August 8, 2016 at 10:24:12 AM UTC+2, Wiebe-Marten Wijnja wrote: