changed
README.md
|
|
@@ -1,18 +1,24 @@
|
|
1
1
|
# Math
|
|
2
2
|
|
|
3
|
+ [](https://hex.pm/packages/math)
|
|
4
|
+ [](https://travis-ci.org/folz/math)
|
|
5
|
+
|
|
3
6
|
The Math module adds many useful functions that extend Elixir's standard library.
|
|
4
7
|
|
|
5
8
|
- General Functions
|
|
6
|
- - `a <~> b` Comparison of floats, to check if they are _nearly_ equal.
|
|
9
|
+ - `a <~> b` Comparison of floats, to check if they are effectively equal (if their absolute difference is less than `@epsilon`).
|
|
7
10
|
- `Math.pow(x, n)` Arithmetic exponentiation. Works both with integer powers and floats.
|
|
8
11
|
- `Math.sqrt(x)` The square root of *x*.
|
|
9
12
|
- `Math.nth_root(x, n)` The n-th root of *x*.
|
|
10
13
|
- `Math.isqrt(x)` The integer square root of *x*.
|
|
11
14
|
- `Math.gcd(a, b)` The greatest common divisor of *a* and *b*.
|
|
15
|
+ - `Math.egcd(a, b)` Calculates integers *gcd*, *s*, and *t* in `as + bt = gcd(a,b)`. See also `Math.gcd(a, b)`
|
|
12
16
|
- `Math.lcm(a, b)` The least common multiple of *a* and *b*.
|
|
13
17
|
- `Math.factorial(n)` The *n*-th factorial number.
|
|
14
18
|
- `Math.k_permutations(n, k)` The number of distinct ways to create groups of size *k* from *n* distinct elements.
|
|
15
19
|
- `Math.k_combinations(n, k)` The number of distinct ways to create groups of size *k* from *n* distinct elements where order does not matter.
|
|
20
|
+ - `Math.mod_inv(a, m)` An integer *b* that fufills `ab = 1 (mod m)`. Returns an ok/error tuple.
|
|
21
|
+ - `Math.mod_inv!(a, m)` See `Math.mod_inv(a, m)`, but returns the value or raises an error.
|
|
16
22
|
|
|
17
23
|
|
|
18
24
|
- Logarithms
|
|
|
@@ -51,25 +57,30 @@ The Math module adds many useful functions that extend Elixir's standard library
|
|
51
57
|
|
|
52
58
|
Math is [available in Hex](https://hex.pm/packages/math). The package can be installed by:
|
|
53
59
|
|
|
54
|
- 1. Add math to your list of dependencies in `mix.exs`:
|
|
60
|
+ 1. Add `math` to your list of dependencies in `mix.exs`:
|
|
55
61
|
|
|
56
|
- def deps do
|
|
57
|
- [
|
|
58
|
- {:math, "~> 0.3.1"}
|
|
59
|
- ]
|
|
60
|
- end
|
|
62
|
+ ```ex
|
|
63
|
+ def deps do
|
|
64
|
+ [
|
|
65
|
+ {:math, "~> 0.4.0"}
|
|
66
|
+ ]
|
|
67
|
+ end
|
|
68
|
+ ```
|
|
61
69
|
|
|
62
|
- 2. Require or import the Math library anywhere in your code you'd like:
|
|
70
|
+ 2. Require or import the Math library anywhere in your code you'd like:
|
|
63
71
|
|
|
64
|
- require Math
|
|
72
|
+ ```ex
|
|
73
|
+ require Math
|
|
65
74
|
|
|
66
|
- or
|
|
75
|
+ # or
|
|
67
76
|
|
|
68
|
- import Math
|
|
77
|
+ import Math
|
|
78
|
+ ```
|
|
69
79
|
|
|
70
|
- (Importing allows usage of the `<~>` operator)
|
|
80
|
+ (Importing allows usage of the `<~>` operator)
|
|
71
81
|
|
|
72
82
|
## Changelog
|
|
83
|
+ - 0.5.0 Adds `Math.mod_inv`, `Math.mod_inv!` and `Math.egcd`
|
|
73
84
|
- 0.4.0 Adds `Math.Enum.mode/1`.
|
|
74
85
|
- 0.3.1 Updates formatting to hide warnings in newer versions of Elixir.
|
|
75
86
|
- 0.3.0 Fixed incorrect median for lists with even number of items. Updated tests.
|
changed
hex_metadata.config
|
|
@@ -10,4 +10,4 @@
|
|
10
10
|
{<<"links">>,[{<<"GitHub">>,<<"https://github.com/folz/math">>}]}.
|
|
11
11
|
{<<"name">>,<<"math">>}.
|
|
12
12
|
{<<"requirements">>,[]}.
|
|
13
|
- {<<"version">>,<<"0.4.0">>}.
|
|
13
|
+ {<<"version">>,<<"0.5.0">>}.
|
changed
lib/math.ex
|
|
@@ -9,7 +9,7 @@ defmodule Math do
|
|
9
9
|
@epsilon 1.0e-15
|
|
10
10
|
|
|
11
11
|
# Theoretical limit is 1.80e308, but Erlang errors at that value, so the practical limit is slightly below that one.
|
|
12
|
- @max_value 1.79769313486231580793e308
|
|
12
|
+ @max_value 1.79_769_313_486_231_580_793e308
|
|
13
13
|
|
|
14
14
|
@type x :: number
|
|
15
15
|
@type y :: number
|
|
|
@@ -192,11 +192,43 @@ defmodule Math do
|
|
192
192
|
6
|
|
193
193
|
"""
|
|
194
194
|
@spec gcd(integer, integer) :: non_neg_integer
|
|
195
|
- def gcd(a, 0), do: abs(a)
|
|
196
195
|
|
|
197
|
- def gcd(0, b), do: abs(b)
|
|
198
|
- def gcd(a, b) when a < 0 or b < 0, do: gcd(abs(a), abs(b))
|
|
199
|
- def gcd(a, b), do: gcd(b, rem(a, b))
|
|
196
|
+ def gcd(a, b) when is_integer(a) and is_integer(b), do: egcd(a, b) |> elem(0)
|
|
197
|
+
|
|
198
|
+ @doc """
|
|
199
|
+ Calculates integers `gcd`, `s`, and `t` for `as + bt = gcd(a, b)`
|
|
200
|
+
|
|
201
|
+ Also see `Math.gcd/2`.
|
|
202
|
+
|
|
203
|
+ Returns a tuple: `{gcd, s, t}`
|
|
204
|
+
|
|
205
|
+ ## Examples
|
|
206
|
+
|
|
207
|
+ iex> Math.egcd(2, 4)
|
|
208
|
+ {2, 1, 0}
|
|
209
|
+ iex> Math.egcd(2, 3)
|
|
210
|
+ {1, -1, 1}
|
|
211
|
+ iex> Math.egcd(12, 8)
|
|
212
|
+ {4, 1, -1}
|
|
213
|
+ iex> Math.egcd(54, 24)
|
|
214
|
+ {6, 1, -2}
|
|
215
|
+ iex> Math.egcd(-54, 24)
|
|
216
|
+ {6, 1, -2}
|
|
217
|
+ """
|
|
218
|
+ @spec egcd(integer, integer) :: non_neg_integer
|
|
219
|
+ def egcd(a, b) when is_integer(a) and is_integer(b), do: _egcd(abs(a), abs(b), 0, 1, 1, 0)
|
|
220
|
+
|
|
221
|
+ defp _egcd(0, b, s, t, _u, _v), do: {b, s, t}
|
|
222
|
+
|
|
223
|
+ defp _egcd(a, b, s, t, u, v) do
|
|
224
|
+ q = div(b, a)
|
|
225
|
+ r = rem(b, a)
|
|
226
|
+
|
|
227
|
+ m = s - u * q
|
|
228
|
+ n = t - v * q
|
|
229
|
+
|
|
230
|
+ _egcd(r, a, u, v, m, n)
|
|
231
|
+ end
|
|
200
232
|
|
|
201
233
|
@doc """
|
|
202
234
|
Calculates the Least Common Multiple of two numbers.
|
|
|
@@ -472,4 +504,63 @@ defmodule Math do
|
|
472
504
|
"""
|
|
473
505
|
@spec atanh(x) :: float
|
|
474
506
|
defdelegate atanh(x), to: :math
|
|
507
|
+
|
|
508
|
+ @doc """
|
|
509
|
+ Computes the modular multiplicatibe inverse of `a` under modulo `m`
|
|
510
|
+
|
|
511
|
+ In other words, given integers `a` and `m` calculate a value `b` for `ab = 1 (mod m)`
|
|
512
|
+
|
|
513
|
+ Returns an `{:ok, b}` tuple or `{:error, :not_coprime}` when `b` cannot be calculated for the inputs.
|
|
514
|
+
|
|
515
|
+ ## Examples
|
|
516
|
+
|
|
517
|
+ iex> Math.mod_inv 3, 11
|
|
518
|
+ {:ok, 4}
|
|
519
|
+ iex> Math.mod_inv 10, 17
|
|
520
|
+ {:ok, 12}
|
|
521
|
+ iex> Math.mod_inv 123, 455
|
|
522
|
+ {:ok, 37}
|
|
523
|
+ iex> Math.mod_inv 123, 456
|
|
524
|
+ {:error, :not_coprime}
|
|
525
|
+
|
|
526
|
+ """
|
|
527
|
+ @spec mod_inv(a :: integer, m :: integer) :: {:ok, integer} | {:error, :not_coprime}
|
|
528
|
+ def mod_inv(a, m)
|
|
529
|
+
|
|
530
|
+ def mod_inv(a, m) when is_float(a) or is_float(m),
|
|
531
|
+ do: raise(ArgumentError, "Inputs cannot be of type float")
|
|
532
|
+
|
|
533
|
+ def mod_inv(a, m) when is_integer(a) and is_integer(m) do
|
|
534
|
+ case egcd(a, m) do
|
|
535
|
+ {1, s, _t} -> {:ok, rem(s + m, m)}
|
|
536
|
+ _ -> {:error, :not_coprime}
|
|
537
|
+ end
|
|
538
|
+ end
|
|
539
|
+
|
|
540
|
+ @doc """
|
|
541
|
+ Computes the modular multiplicatibe inverse of `a` under modulo `m`
|
|
542
|
+
|
|
543
|
+ Similar to `mod_in/2`, but returns only the value or raises an error.
|
|
544
|
+
|
|
545
|
+ ## Examples
|
|
546
|
+
|
|
547
|
+ iex> Math.mod_inv! 3, 11
|
|
548
|
+ 4
|
|
549
|
+ iex> Math.mod_inv! 10, 17
|
|
550
|
+ 12
|
|
551
|
+ iex> Math.mod_inv! 123, 455
|
|
552
|
+ 37
|
|
553
|
+ iex> Math.mod_inv! 123, 456
|
|
554
|
+ ** (ArithmeticError) Inputs are not coprime!
|
|
555
|
+
|
|
556
|
+ """
|
|
557
|
+ @spec mod_inv!(a :: integer, m :: integer) :: integer
|
|
558
|
+ def mod_inv!(a, m)
|
|
559
|
+
|
|
560
|
+ def mod_inv!(a, m) do
|
|
561
|
+ case mod_inv(a, m) do
|
|
562
|
+ {:ok, b} -> b
|
|
563
|
+ _ -> raise ArithmeticError, "Inputs are not coprime!"
|
|
564
|
+ end
|
|
565
|
+ end
|
|
475
566
|
end
|
changed
mix.exs
|
|
@@ -6,7 +6,7 @@ defmodule Math.Mixfile do
|
|
6
6
|
def project do
|
|
7
7
|
[
|
|
8
8
|
app: :math,
|
|
9
|
- version: "0.4.0",
|
|
9
|
+ version: "0.5.0",
|
|
10
10
|
elixir: "~> 1.2",
|
|
11
11
|
description: description(),
|
|
12
12
|
package: package(),
|