[erlang-questions] Proposal regarding integer arithmetic

Masatake Daimon daimon@REDACTED
Mon Nov 21 08:08:20 CET 2011


Hello,

I have a proposal for clarifying the documentation and additional BIFs
to the "math" module regarding integer arithmetic.


> *** Clarify the rounding mode of "div" operator ***
>
> Erlang's div operator is an "integer division" whose rounding mode is
> undocumented, while in the current implementation it's an integer
> division rounded towards zero. I claim that the rounding mode should
> be explicitly documented as it's *very* important for any serious
> integer arithmetic.
>
>   1> -10 div 3.
>   -3
>   2> 10 div -3.
>   -3
>   3> 10 div 3.
>   3
>
>
> *** Proposal for a new BIF, math:divfloor/2 ***
>
> Having only "div" is not always sufficient. In many situations an
> integer division *rounded towards negative infinity* is essentially
> needed. So I suggest adding a new BIF "divfloor/2" to the "math"
> module. Here is an example implementation in Erlang but it should
> really be a BIF:
>
>  -type non_zero_integer() :: pos_integer() | neg_integer().
>  -spec divfloor(pos_integer(), neg_integer()) -> neg_integer();
>                (neg_integer(), pos_integer()) -> neg_integer();
>                (0, non_zero_integer()) -> 0;
>                (X, X) -> non_neg_integer() when X :: non_zero_integer().
>  divfloor(X, Y) when X > 0 andalso Y < 0 ->
>      ((X - 1) div Y) - 1;
>  divfloor(X, Y) when X < 0 andalso Y > 0 ->
>      ((X + 1) div Y) - 1;
>  divfloor(X, Y) ->
>      X div Y.
>
>
> *** Clarify the property the "rem" operator satisfies ***
>
> The "rem" operator is only documented as "integer remainder of X/Y"
> but the exact property it satisfies is totally undocumented.
>
>   1> -10 rem 3.
>   -1
>   2> 10 rem -3.
>   1
>
> In the current implementation it seems a remainder operator,
> satisfying the following identity. This should really be
> documented. Without that it's obviously impossible for any
> inexperienced Erlang users to guess the exact behaviour of "rem"
> operator:
>
>   (X div Y)*Y + (X rem Y) =:= X
>
>
> *** Proposal for a new BIF, math:mod/2 ***
>
> Again, having only "rem" is not always sufficient. I suggest adding a
> BIF "mod/2" to the "math" module, satisfying the following identity:
>
>   math:divfloor(X, Y)*Y + math:mod(X, Y) =:= X
>
> Here is an example implementation in Erlang but it should
> really be a BIF:
>
>   -spec mod(0, non_zero_integer()) -> 0;
>            (non_zero_integer(), X) -> X when X :: non_zero_integer().
>   mod(X, Y) when (X > 0 andalso Y < 0) orelse
>                  (X < 0 andalso Y > 0) ->
>       case X rem Y of
>           0 -> 0;
>           R -> R + Y
>       end;
>   mod(X, Y) ->
>       X rem Y.
>
>
> *** Clarify the property the function erlang:trunc/1 satisfies ***
>
> The documentation for erlang:trunc/1 says nothing other than "Returns
> an integer by the truncating Number," but *how* does it truncate?
>
>   1> erlang:trunc(3.5).
>   3
>   2> erlang:trunc(-3.5).
>   -3
>
> So the current implementation of erlang:trunc/1 seems to truncate a
> number towards zero. That should be explicitly documented.
>
>
> *** Proposal for new BIFs, math:floor/1 and math:ceil/1 ***
>
> Why not having math:floor/1 and math:ceil/1? They truncate the
> argument towards negative and positive infinity, respectively. Here is
> an implementation in Erlang but these should be BIFs:
>
>   -spec floor(number()) -> integer().
>   floor(X) ->
>       Y = trunc(X),
>       case X - Y of
>           Neg when Neg < 0 -> Y - 1;
>           _ -> Y
>       end.
>
>   -spec ceil(number()) -> integer().
>   ceil(X) ->
>       Y = trunc(X),
>       case X - Y of
>           Pos when Pos > 0 -> Y + 1;
>           _ -> Y
>       end.
>
>
> *** Proposal for an improvement of the function math:pow/2 ***
>
> Currently math:pow/2 always returns float() for any arguments, but it
> should compute the result in integer() when the base is integer() and
> the exponent is non_neg_integer().
>
>   1> math:pow(2, 2.5).
>   5.656854249492381
>   2> math:pow(2, -2).
>   0.25
>   3> math:pow(2, 3).
>   8.0
>   4> math:pow(100, 1000).
>   ** exception error: bad argument in an arithmetic expression
>        in function  math:pow/2
>           called as math:pow(100,1000)
>
> Its function spec would be as follows:
>
>   -spec pow(integer(), non_neg_integer()) -> integer();
>         pow(number() , number()         ) -> number().
>
>
> *** Proposal for a new BIF, math:gcd/2 ***
>
> It would be handy to have a BIF math:gcd/2 which returns the greatest
> common divisor of its two arguments. An Erlang implementation is as
> follows:
>
>   -spec gcd(integer(), integer()) -> non_neg_integer().
>   gcd(X, Y) -> gcd_(abs(X), abs(Y)).
>
>   gcd_(X, 0) -> X;
>   gcd_(X, Y) -> gcd_(Y, X rem Y).
>
>
> *** Proposal for a new BIF, math:lcm/2 ***
>
> It would also be handy to have a BIF math:lcm/2 which returns the
> least common multiple of its two arguments. An Erlang implementation
> is as follows:
>
>   -spec lcm(integer(), integer()) -> non_neg_integer().
>   lcm(_, 0) -> 0;
>   lcm(0, _) -> 0;
>   lcm(X, Y) -> abs(math:divfloor(X, math:gcd(X, Y)) * Y).


I know I should submit an EEP for this rather than posting to
erlang-questions, but since that means I have to provide a reference
implementation it is a lot of load for me. Any comments or suggestions
on this proposal are highly welcomed.

Thanks,
Masatake Daimon
-- 
大門 正岳 <daimon@REDACTED>



More information about the erlang-questions mailing list