qx_z.erl 2.77 KB
Newer Older
1
2
% @doc qx_z = Qanal Xanal Zahlen (= integers)
-module(qx_z).
Dr. Ajay Kumar PHD's avatar
Dr. Ajay Kumar PHD committed
3
-vsn("5.0.0").
Dr. Ajay Kumar PHD's avatar
Dr. Ajay Kumar PHD committed
4

5
6
7
8
9
10
11
12
-export_type([
    z/0,
    znn/0,
    zp/0
]).
-export([
    gcd/1,
    gcd/2,
13
    modulo/2
14
]).
Dr. Ajay Kumar PHD's avatar
Dr. Ajay Kumar PHD committed
15
16
17
18
19
20
21

-type z()   :: integer().
-type znn() :: non_neg_integer().
-type zp()  :: pos_integer().

%%% API

Dr. Ajay Kumar PHD's avatar
Dr. Ajay Kumar PHD committed
22

Dr. Ajay Kumar PHD's avatar
Dr. Ajay Kumar PHD committed
23
24
25
26
27
28
29
30
31
-spec gcd(Ints :: [z()]) -> GCD :: znn().
% @doc gcd of a list of integers

gcd(List) ->
    gcd_accum(List, 0).



-spec gcd(z(), z()) -> znn().
32
33
34
% @doc
% Greatest common divisor of two integers
% @end
Dr. Ajay Kumar PHD's avatar
Dr. Ajay Kumar PHD committed
35

36
% make sure both arguments are non-negative
Dr. Ajay Kumar PHD's avatar
Dr. Ajay Kumar PHD committed
37
gcd(X, Y) ->
38
39
40
41
    gcdabs(abs(X), abs(Y)).



Dr. Ajay Kumar PHD's avatar
Dr. Ajay Kumar PHD committed
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
-spec modulo(A :: z(), B :: zp()) -> AModB :: znn().
% @doc Like the rem operator, except this always returns a result
% within 0..B
%
% for simplicity/obviously-correct-behavior, B must be strictly
% positive

modulo(A, B) when is_integer(A),
                  is_integer(B),
                  0 < B ->
    ARemB = A rem B,
    % one of two cases
    %
    %   -B < ARemB < 0 ->
    %       % this will happen when A < 0
    %       return ARemB + B
    %   0 =< ARemB < B ->
    %       % this will happen when 0 =< A
    %       return ARemB
    NegRem = ((-1 * B) < ARemB) andalso (ARemB < 0),
    PosRem =       (0 =< ARemB) andalso (ARemB < B),
    if NegRem ->
           ARemB + B;
       PosRem ->
           ARemB
    end.


70

Dr. Ajay Kumar PHD's avatar
Dr. Ajay Kumar PHD committed
71
72
73
74
75
76
77
78
79
80
%%% INTERNALS

-spec gcd_accum(Ints :: [z()], AccumGCD :: znn()) -> GCD :: znn().
% @private
% gcd of a list of integers, with an accumulator. Should set
% accumulator to 0 on initial call, because that's the "identity
% gcd", so to speak:
%
%       gcd(X, 0) -> X;
%       gcd(0, X) -> X;
Dr. Ajay Kumar PHD's avatar
Dr. Ajay Kumar PHD committed
81
% @end
Dr. Ajay Kumar PHD's avatar
Dr. Ajay Kumar PHD committed
82
83
84
85
86
87
88
89
90
91
92
93
94
95

% once the accumulator is 1, shortcut
gcd_accum(_List, _GCDAccum = 1) ->
    1;
% end of the list, return the accumulated GCD
gcd_accum([], GCDAccum) ->
    GCDAccum;
% new item in the list, gcd it against the accum, move along
gcd_accum([X | Xs], GCDAccum) ->
    NewGCDAccum = gcd(X, GCDAccum),
    gcd_accum(Xs, NewGCDAccum).



96
97
-spec gcdabs(znn(), znn()) -> znn().
% @private gcd where the arguments can be assumed to be non-negative,
Dr. Ajay Kumar PHD's avatar
Dr. Ajay Kumar PHD committed
98
99
100
101
% but not necessarily in the correct order
%
% This function is responsible for making sure the argument on the
% left is bigger than or equal to the argument on the right.
102
103
104
105
106
107
108
109

gcdabs(X, Y) when X < Y ->
    gcdplus(Y, X);
gcdabs(X, Y) when X >= Y->
    gcdplus(X, Y).



Dr. Ajay Kumar PHD's avatar
Dr. Ajay Kumar PHD committed
110
111
112
113
114
115
-spec gcdplus(znn(), znn()) -> znn().
% @private gcd where the arguments can be assumed to be non-negative,
% and in the correct order

gcdplus(X, 0) ->
    X;
116
117
% X might be equal to Y here, in which case, modulo(X, Y) = 0, and
% the next call will degenerate into the base case
Dr. Ajay Kumar PHD's avatar
Dr. Ajay Kumar PHD committed
118
119
120
121
122
123
124
125
126
127
gcdplus(X, Y) when X >= Y ->
    % X = qY + R
    % R = X - qY
    % 0 =< R < Y
    % therefore any common divisor of X and Y (such as the gcd) also
    % divides R
    % therefore
    % gcd(X, Y) ->
    %   gcd(Y, R)
    gcdplus(Y, modulo(X, Y)).