Coverage for /usr/lib/python3/dist-packages/sympy/external/pythonmpq.py: 32%

1""" 

2PythonMPQ: Rational number type based on Python integers. 

3 

4This class is intended as a pure Python fallback for when gmpy2 is not 

5installed. If gmpy2 is installed then its mpq type will be used instead. The 

6mpq type is around 20x faster. We could just use the stdlib Fraction class 

7here but that is slower: 

8 

9 from fractions import Fraction 

10 from sympy.external.pythonmpq import PythonMPQ 

11 nums = range(1000) 

12 dens = range(5, 1005) 

13 rats = [Fraction(n, d) for n, d in zip(nums, dens)] 

14 sum(rats) # <--- 24 milliseconds 

15 rats = [PythonMPQ(n, d) for n, d in zip(nums, dens)] 

16 sum(rats) # <--- 7 milliseconds 

17 

18Both mpq and Fraction have some awkward features like the behaviour of 

19division with // and %: 

20 

21 >>> from fractions import Fraction 

22 >>> Fraction(2, 3) % Fraction(1, 4) 

23 1/6 

24 

25For the QQ domain we do not want this behaviour because there should be no 

26remainder when dividing rational numbers. SymPy does not make use of this 

27aspect of mpq when gmpy2 is installed. Since this class is a fallback for that 

28case we do not bother implementing e.g. __mod__ so that we can be sure we 

29are not using it when gmpy2 is installed either. 

30""" 

31 

32 

33import operator 

34from math import gcd 

35from decimal import Decimal 

36from fractions import Fraction 

37import sys 

38from typing import Tuple as tTuple, Type 

39 

40 

41# Used for __hash__ 

42_PyHASH_MODULUS = sys.hash_info.modulus 

43_PyHASH_INF = sys.hash_info.inf 

44 

45 

46class PythonMPQ: 

47 """Rational number implementation that is intended to be compatible with 

48 gmpy2's mpq. 

49 

50 Also slightly faster than fractions.Fraction. 

51 

52 PythonMPQ should be treated as immutable although no effort is made to 

53 prevent mutation (since that might slow down calculations). 

54 """ 

55 __slots__ = ('numerator', 'denominator') 

56 

57 def __new__(cls, numerator, denominator=None): 

58 """Construct PythonMPQ with gcd computation and checks""" 

59 if denominator is not None: 

60 # 

61 # PythonMPQ(n, d): require n and d to be int and d != 0 

62 # 

63 if isinstance(numerator, int) and isinstance(denominator, int): 

64 # This is the slow part: 

65 divisor = gcd(numerator, denominator) 

66 numerator //= divisor 

67 denominator //= divisor 

68 return cls._new_check(numerator, denominator) 

69 else: 

70 # 

71 # PythonMPQ(q) 

72 # 

73 # Here q can be PythonMPQ, int, Decimal, float, Fraction or str 

74 # 

75 if isinstance(numerator, int): 

76 return cls._new(numerator, 1) 

77 elif isinstance(numerator, PythonMPQ): 

78 return cls._new(numerator.numerator, numerator.denominator) 

79 

80 # Let Fraction handle Decimal/float conversion and str parsing 

81 if isinstance(numerator, (Decimal, float, str)): 

82 numerator = Fraction(numerator) 

83 if isinstance(numerator, Fraction): 

84 return cls._new(numerator.numerator, numerator.denominator) 

85 # 

86 # Reject everything else. This is more strict than mpq which allows 

87 # things like mpq(Fraction, Fraction) or mpq(Decimal, any). The mpq 

88 # behaviour is somewhat inconsistent so we choose to accept only a 

89 # more strict subset of what mpq allows. 

90 # 

91 raise TypeError("PythonMPQ() requires numeric or string argument") 

92 

93 @classmethod 

94 def _new_check(cls, numerator, denominator): 

95 """Construct PythonMPQ, check divide by zero and canonicalize signs""" 

96 if not denominator: 

97 raise ZeroDivisionError(f'Zero divisor {numerator}/{denominator}') 

98 elif denominator < 0: 

99 numerator = -numerator 

100 denominator = -denominator 

101 return cls._new(numerator, denominator) 

102 

103 @classmethod 

104 def _new(cls, numerator, denominator): 

105 """Construct PythonMPQ efficiently (no checks)""" 

106 obj = super().__new__(cls) 

107 obj.numerator = numerator 

108 obj.denominator = denominator 

109 return obj 

110 

111 def __int__(self): 

112 """Convert to int (truncates towards zero)""" 

113 p, q = self.numerator, self.denominator 

114 if p < 0: 

115 return -(-p//q) 

116 return p//q 

117 

118 def __float__(self): 

119 """Convert to float (approximately)""" 

120 return self.numerator / self.denominator 

121 

122 def __bool__(self): 

123 """True/False if nonzero/zero""" 

124 return bool(self.numerator) 

125 

126 def __eq__(self, other): 

127 """Compare equal with PythonMPQ, int, float, Decimal or Fraction""" 

128 if isinstance(other, PythonMPQ): 

129 return (self.numerator == other.numerator 

130 and self.denominator == other.denominator) 

131 elif isinstance(other, self._compatible_types): 

132 return self.__eq__(PythonMPQ(other)) 

133 else: 

134 return NotImplemented 

135 

136 def __hash__(self): 

137 """hash - same as mpq/Fraction""" 

138 try: 

139 dinv = pow(self.denominator, -1, _PyHASH_MODULUS) 

140 except ValueError: 

141 hash_ = _PyHASH_INF 

142 else: 

143 hash_ = hash(hash(abs(self.numerator)) * dinv) 

144 result = hash_ if self.numerator >= 0 else -hash_ 

145 return -2 if result == -1 else result 

146 

147 def __reduce__(self): 

148 """Deconstruct for pickling""" 

149 return type(self), (self.numerator, self.denominator) 

150 

151 def __str__(self): 

152 """Convert to string""" 

153 if self.denominator != 1: 

154 return f"{self.numerator}/{self.denominator}" 

155 else: 

156 return f"{self.numerator}" 

157 

158 def __repr__(self): 

159 """Convert to string""" 

160 return f"MPQ({self.numerator},{self.denominator})" 

161 

162 def _cmp(self, other, op): 

163 """Helper for lt/le/gt/ge""" 

164 if not isinstance(other, self._compatible_types): 

165 return NotImplemented 

166 lhs = self.numerator * other.denominator 

167 rhs = other.numerator * self.denominator 

168 return op(lhs, rhs) 

169 

170 def __lt__(self, other): 

171 """self < other""" 

172 return self._cmp(other, operator.lt) 

173 

174 def __le__(self, other): 

175 """self <= other""" 

176 return self._cmp(other, operator.le) 

177 

178 def __gt__(self, other): 

179 """self > other""" 

180 return self._cmp(other, operator.gt) 

181 

182 def __ge__(self, other): 

183 """self >= other""" 

184 return self._cmp(other, operator.ge) 

185 

186 def __abs__(self): 

187 """abs(q)""" 

188 return self._new(abs(self.numerator), self.denominator) 

189 

190 def __pos__(self): 

191 """+q""" 

192 return self 

193 

194 def __neg__(self): 

195 """-q""" 

196 return self._new(-self.numerator, self.denominator) 

197 

198 def __add__(self, other): 

199 """q1 + q2""" 

200 if isinstance(other, PythonMPQ): 

201 # 

202 # This is much faster than the naive method used in the stdlib 

203 # fractions module. Not sure where this method comes from 

204 # though... 

205 # 

206 # Compare timings for something like: 

207 # nums = range(1000) 

208 # rats = [PythonMPQ(n, d) for n, d in zip(nums[:-5], nums[5:])] 

209 # sum(rats) # <-- time this 

210 # 

211 ap, aq = self.numerator, self.denominator 

212 bp, bq = other.numerator, other.denominator 

213 g = gcd(aq, bq) 

214 if g == 1: 

215 p = ap*bq + aq*bp 

216 q = bq*aq 

217 else: 

218 q1, q2 = aq//g, bq//g 

219 p, q = ap*q2 + bp*q1, q1*q2 

220 g2 = gcd(p, g) 

221 p, q = (p // g2), q * (g // g2) 

222 

223 elif isinstance(other, int): 

224 p = self.numerator + self.denominator * other 

225 q = self.denominator 

226 else: 

227 return NotImplemented 

228 

229 return self._new(p, q) 

230 

231 def __radd__(self, other): 

232 """z1 + q2""" 

233 if isinstance(other, int): 

234 p = self.numerator + self.denominator * other 

235 q = self.denominator 

236 return self._new(p, q) 

237 else: 

238 return NotImplemented 

239 

240 def __sub__(self ,other): 

241 """q1 - q2""" 

242 if isinstance(other, PythonMPQ): 

243 ap, aq = self.numerator, self.denominator 

244 bp, bq = other.numerator, other.denominator 

245 g = gcd(aq, bq) 

246 if g == 1: 

247 p = ap*bq - aq*bp 

248 q = bq*aq 

249 else: 

250 q1, q2 = aq//g, bq//g 

251 p, q = ap*q2 - bp*q1, q1*q2 

252 g2 = gcd(p, g) 

253 p, q = (p // g2), q * (g // g2) 

254 elif isinstance(other, int): 

255 p = self.numerator - self.denominator*other 

256 q = self.denominator 

257 else: 

258 return NotImplemented 

259 

260 return self._new(p, q) 

261 

262 def __rsub__(self, other): 

263 """z1 - q2""" 

264 if isinstance(other, int): 

265 p = self.denominator * other - self.numerator 

266 q = self.denominator 

267 return self._new(p, q) 

268 else: 

269 return NotImplemented 

270 

271 def __mul__(self, other): 

272 """q1 * q2""" 

273 if isinstance(other, PythonMPQ): 

274 ap, aq = self.numerator, self.denominator 

275 bp, bq = other.numerator, other.denominator 

276 x1 = gcd(ap, bq) 

277 x2 = gcd(bp, aq) 

278 p, q = ((ap//x1)*(bp//x2), (aq//x2)*(bq//x1)) 

279 elif isinstance(other, int): 

280 x = gcd(other, self.denominator) 

281 p = self.numerator*(other//x) 

282 q = self.denominator//x 

283 else: 

284 return NotImplemented 

285 

286 return self._new(p, q) 

287 

288 def __rmul__(self, other): 

289 """z1 * q2""" 

290 if isinstance(other, int): 

291 x = gcd(self.denominator, other) 

292 p = self.numerator*(other//x) 

293 q = self.denominator//x 

294 return self._new(p, q) 

295 else: 

296 return NotImplemented 

297 

298 def __pow__(self, exp): 

299 """q ** z""" 

300 p, q = self.numerator, self.denominator 

301 

302 if exp < 0: 

303 p, q, exp = q, p, -exp 

304 

305 return self._new_check(p**exp, q**exp) 

306 

307 def __truediv__(self, other): 

308 """q1 / q2""" 

309 if isinstance(other, PythonMPQ): 

310 ap, aq = self.numerator, self.denominator 

311 bp, bq = other.numerator, other.denominator 

312 x1 = gcd(ap, bp) 

313 x2 = gcd(bq, aq) 

314 p, q = ((ap//x1)*(bq//x2), (aq//x2)*(bp//x1)) 

315 elif isinstance(other, int): 

316 x = gcd(other, self.numerator) 

317 p = self.numerator//x 

318 q = self.denominator*(other//x) 

319 else: 

320 return NotImplemented 

321 

322 return self._new_check(p, q) 

323 

324 def __rtruediv__(self, other): 

325 """z / q""" 

326 if isinstance(other, int): 

327 x = gcd(self.numerator, other) 

328 p = self.denominator*(other//x) 

329 q = self.numerator//x 

330 return self._new_check(p, q) 

331 else: 

332 return NotImplemented 

333 

334 _compatible_types: tTuple[Type, ...] = () 

335 

336# 

337# These are the types that PythonMPQ will interoperate with for operations 

338# and comparisons such as ==, + etc. We define this down here so that we can 

339# include PythonMPQ in the list as well. 

340# 

341PythonMPQ._compatible_types = (PythonMPQ, int, Decimal, Fraction)