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:
>
> 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.
>
>
--
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 [email protected].
To view this discussion on the web visit
https://groups.google.com/d/msgid/elixir-lang-core/4b6a452f-c5e9-47af-b0f1-f12618d65d42%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
