codekingpro/portable-devtools

1#  Copyright 2011 Sybren A. Stüvel <sybren@stuvel.eu>
2#
3#  Licensed under the Apache License, Version 2.0 (the "License");
4#  you may not use this file except in compliance with the License.
5#  You may obtain a copy of the License at
6#
7#      https://www.apache.org/licenses/LICENSE-2.0
8#
9#  Unless required by applicable law or agreed to in writing, software
10#  distributed under the License is distributed on an "AS IS" BASIS,
11#  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12#  See the License for the specific language governing permissions and
13#  limitations under the License.
14
15"""Common functionality shared by several modules."""
16
17import typing
18
19
20class NotRelativePrimeError(ValueError):
21    def __init__(self, a: int, b: int, d: int, msg: str = "") -> None:
22        super().__init__(msg or "%d and %d are not relatively prime, divider=%i" % (a, b, d))
23        self.a = a
24        self.b = b
25        self.d = d
26
27
28def bit_size(num: int) -> int:
29    """
30    Number of bits needed to represent a integer excluding any prefix
31    0 bits.
32
33    Usage::
34
35        >>> bit_size(1023)
36        10
37        >>> bit_size(1024)
38        11
39        >>> bit_size(1025)
40        11
41
42    :param num:
43        Integer value. If num is 0, returns 0. Only the absolute value of the
44        number is considered. Therefore, signed integers will be abs(num)
45        before the number's bit length is determined.
46    :returns:
47        Returns the number of bits in the integer.
48    """
49
50    try:
51        return num.bit_length()
52    except AttributeError as ex:
53        raise TypeError("bit_size(num) only supports integers, not %r" % type(num)) from ex
54
55
56def byte_size(number: int) -> int:
57    """
58    Returns the number of bytes required to hold a specific long number.
59
60    The number of bytes is rounded up.
61
62    Usage::
63
64        >>> byte_size(1 << 1023)
65        128
66        >>> byte_size((1 << 1024) - 1)
67        128
68        >>> byte_size(1 << 1024)
69        129
70
71    :param number:
72        An unsigned integer
73    :returns:
74        The number of bytes required to hold a specific long number.
75    """
76    if number == 0:
77        return 1
78    return ceil_div(bit_size(number), 8)
79
80
81def ceil_div(num: int, div: int) -> int:
82    """
83    Returns the ceiling function of a division between `num` and `div`.
84
85    Usage::
86
87        >>> ceil_div(100, 7)
88        15
89        >>> ceil_div(100, 10)
90        10
91        >>> ceil_div(1, 4)
92        1
93
94    :param num: Division's numerator, a number
95    :param div: Division's divisor, a number
96
97    :return: Rounded up result of the division between the parameters.
98    """
99    quanta, mod = divmod(num, div)
100    if mod:
101        quanta += 1
102    return quanta
103
104
105def extended_gcd(a: int, b: int) -> typing.Tuple[int, int, int]:
106    """Returns a tuple (r, i, j) such that r = gcd(a, b) = ia + jb"""
107    # r = gcd(a,b) i = multiplicitive inverse of a mod b
108    #      or      j = multiplicitive inverse of b mod a
109    # Neg return values for i or j are made positive mod b or a respectively
110    # Iterateive Version is faster and uses much less stack space
111    x = 0
112    y = 1
113    lx = 1
114    ly = 0
115    oa = a  # Remember original a/b to remove
116    ob = b  # negative values from return results
117    while b != 0:
118        q = a // b
119        (a, b) = (b, a % b)
120        (x, lx) = ((lx - (q * x)), x)
121        (y, ly) = ((ly - (q * y)), y)
122    if lx < 0:
123        lx += ob  # If neg wrap modulo original b
124    if ly < 0:
125        ly += oa  # If neg wrap modulo original a
126    return a, lx, ly  # Return only positive values
127
128
129def inverse(x: int, n: int) -> int:
130    """Returns the inverse of x % n under multiplication, a.k.a x^-1 (mod n)
131
132    >>> inverse(7, 4)
133    3
134    >>> (inverse(143, 4) * 143) % 4
135    1
136    """
137
138    (divider, inv, _) = extended_gcd(x, n)
139
140    if divider != 1:
141        raise NotRelativePrimeError(x, n, divider)
142
143    return inv
144
145
146def crt(a_values: typing.Iterable[int], modulo_values: typing.Iterable[int]) -> int:
147    """Chinese Remainder Theorem.
148
149    Calculates x such that x = a[i] (mod m[i]) for each i.
150
151    :param a_values: the a-values of the above equation
152    :param modulo_values: the m-values of the above equation
153    :returns: x such that x = a[i] (mod m[i]) for each i
154
155
156    >>> crt([2, 3], [3, 5])
157    8
158
159    >>> crt([2, 3, 2], [3, 5, 7])
160    23
161
162    >>> crt([2, 3, 0], [7, 11, 15])
163    135
164    """
165
166    m = 1
167    x = 0
168
169    for modulo in modulo_values:
170        m *= modulo
171
172    for (m_i, a_i) in zip(modulo_values, a_values):
173        M_i = m // m_i
174        inv = inverse(M_i, m_i)
175
176        x = (x + a_i * M_i * inv) % m
177
178    return x
179
180
181if __name__ == "__main__":
182    import doctest
183
184    doctest.testmod()
185