Coverage for pycommons/math/int_math.py: 100%

1""" 

2Mathematics routines combining integers and floats. 

3 

4These routines try to return results with the highest possible precision, 

5ideally as integers. 

6If floating point values need to be converted to integers, then we round 

7towards the nearest integer numbers, whereas `0.5` is always rounded up and 

8`-0.5` is always rounded down. 

9Thus, `1.5` becomes `2` and `-1.5` becomes `-2`. 

10""" 

11 

12from contextlib import suppress 

13from math import gcd, isfinite, isqrt, sqrt 

14from sys import float_info 

15from typing import Final 

16 

17from pycommons.types import type_error 

18 

19#: The positive limit for doubles that can be represented exactly as ints. 

20#: We cannot represent any number `z` with `|z| >= 2 ** 53` as float without 

21#: losing some digits, because floats have only 52 bits. 

22#: `float(9007199254740992) == 9007199254740992.0` 

23#: `float(9007199254740991) == 9007199254740991.0` 

24#: But: 

25#: #: `float(9007199254740993) == 9007199254740992.0`. 

26__DBL_INT_LIMIT_P_I: Final[int] = 2 ** float_info.mant_dig 

27#: The positive limit for doubles that can be represented exactly as ints. 

28__DBL_INT_LIMIT_P_F: Final[float] = float(__DBL_INT_LIMIT_P_I) # = 1 << 53 

29#: The negative limit for doubles that can be represented exactly as ints. 

30__DBL_INT_LIMIT_N_I: Final[int] = -__DBL_INT_LIMIT_P_I 

31#: The negative limit for doubles that can be represented exactly as ints. 

32__DBL_INT_LIMIT_N_F: Final[float] = __DBL_INT_LIMIT_N_I 

33 

34 

35def __try_int(val: float) -> int | float: 

36 """ 

37 Convert a float to an int without any fancy checks. 

38 

39 :param val: the flot 

40 :returns: the float or int 

41 

42 >>> from math import inf, nan, nextafter 

43 >>> type(__try_int(0.0)) 

44 <class 'int'> 

45 >>> type(__try_int(0.5)) 

46 <class 'float'> 

47 >>> type(__try_int(inf)) 

48 <class 'float'> 

49 >>> type(__try_int(-inf)) 

50 <class 'float'> 

51 >>> type(__try_int(nan)) 

52 <class 'float'> 

53 >>> 1 << 53 

54 9007199254740992 

55 >>> type(__try_int(9007199254740992.0)) 

56 <class 'int'> 

57 >>> __try_int(9007199254740992.0) 

58 9007199254740992 

59 >>> too_big = nextafter(9007199254740992.0, inf) 

60 >>> print(too_big) 

61 9007199254740994.0 

62 >>> type(__try_int(too_big)) 

63 <class 'float'> 

64 >>> type(__try_int(-9007199254740992.0)) 

65 <class 'int'> 

66 >>> __try_int(-9007199254740992.0) 

67 -9007199254740992 

68 >>> type(__try_int(-too_big)) 

69 <class 'float'> 

70 """ 

71 if __DBL_INT_LIMIT_N_F <= val <= __DBL_INT_LIMIT_P_F: 

72 a = int(val) 

73 if a == val: 

74 return a 

75 return val 

76 

77 

78def try_int(value: int | float) -> int | float: 

79 """ 

80 Attempt to convert a float to an integer. 

81 

82 This method will convert a floating point number to an integer if the 

83 floating point number was representing an exact integer. This is the 

84 case if it has a) no fractional part and b) is in the range 

85 `-9007199254740992...9007199254740992`, i.e., the range where `+1` and 

86 `-1` work without loss of precision. 

87 

88 :param value: the input value, which must either be `int` or `float` 

89 :returns: an `int` if `value` can be represented as `int` without loss of 

90 precision, `val` otherwise 

91 :raises TypeError: if `value` is neither an instance of `int` nor of 

92 `float` 

93 :raises ValueError: if `value` is a `float`, but not finite 

94 

95 >>> print(type(try_int(10.5))) 

96 <class 'float'> 

97 >>> print(type(try_int(10))) 

98 <class 'int'> 

99 

100 >>> from math import inf, nan, nextafter 

101 >>> type(try_int(0.0)) 

102 <class 'int'> 

103 >>> type(try_int(0.5)) 

104 <class 'float'> 

105 

106 >>> try: 

107 ... try_int(inf) 

108 ... except ValueError as ve: 

109 ... print(ve) 

110 Value must be finite, but is inf. 

111 

112 >>> try: 

113 ... try_int(-inf) 

114 ... except ValueError as ve: 

115 ... print(ve) 

116 Value must be finite, but is -inf. 

117 

118 >>> try: 

119 ... try_int(nan) 

120 ... except ValueError as ve: 

121 ... print(ve) 

122 Value must be finite, but is nan. 

123 

124 >>> try: 

125 ... try_int("blab") # noqa # type: off 

126 ... except TypeError as te: 

127 ... print(te) 

128 value should be an instance of any in {float, int} but is str, namely \ 

129'blab'. 

130 

131 >>> type(try_int(9007199254740992.0)) 

132 <class 'int'> 

133 >>> try_int(9007199254740992.0) 

134 9007199254740992 

135 >>> too_big = nextafter(9007199254740992.0, inf) 

136 >>> print(too_big) 

137 9007199254740994.0 

138 >>> type(try_int(too_big)) 

139 <class 'float'> 

140 >>> type(try_int(-9007199254740992.0)) 

141 <class 'int'> 

142 >>> try_int(-9007199254740992.0) 

143 -9007199254740992 

144 >>> type(try_int(-too_big)) 

145 <class 'float'> 

146 """ 

147 if isinstance(value, int): 

148 return value 

149 if isinstance(value, float): 

150 if not isfinite(value): 

151 raise ValueError(f"Value must be finite, but is {value}.") 

152 if __DBL_INT_LIMIT_N_F <= value <= __DBL_INT_LIMIT_P_F: 

153 a = int(value) 

154 if a == value: 

155 return a 

156 return value 

157 raise type_error(value, "value", (int, float)) 

158 

159 

160def __choose_frac(num1: int, denom1: int, num2: int, denom2: int) \ 

161 -> tuple[int, int]: 

162 """ 

163 Choose the more compact one of two fractions. 

164 

165 :param num1: the first numerator 

166 :param denom1: the first denominator 

167 :param num2: the second numerator 

168 :param denom2: the second denominator 

169 :return: the numerator, denominator 

170 

171 >>> __choose_frac(10, 100, 1, 10) 

172 (1, 10) 

173 >>> __choose_frac(1, 10, 10, 100) 

174 (1, 10) 

175 >>> __choose_frac(1, 10, 1, 11) 

176 (1, 10) 

177 >>> __choose_frac(1, 11, 1, 10) 

178 (1, 10) 

179 >>> __choose_frac(1, 11, 2, 10) 

180 (2, 10) 

181 >>> __choose_frac(2, 10, 1, 11) 

182 (2, 10) 

183 >>> __choose_frac(2, 10, 1, 10) 

184 (1, 10) 

185 >>> __choose_frac(1, 10, 2, 10) 

186 (1, 10) 

187 """ 

188 return (num1, denom1) if (denom1 < denom2) or ( 

189 (num1 + denom1) < (num2 + denom2)) else (num2, denom2) 

190 

191 

192def __minimize_frac(value: float, num: int, denom: int) -> tuple[int, int]: 

193 """ 

194 Try to find a more compact equivalent representation of a given fraction. 

195 

196 If you convert `1/7` directly from the `float` format to an integer 

197 fraction via `(1/7).as_integer_ratio()`, you get 

198 `(2573485501354569, 18014398509481984)`. This is a precise conversion, 

199 as `2573485501354569/18014398509481984 - 1/7 == 0` 

200 However, `2573485501354569 * 7 = 18014398509481983`. Thus, the chosen 

201 denominator is just 1 off the perfect one, because 

202 `18014398509481983` divided by `2573485501354569` would give us exactly 

203 `7`. Therefore, in this function, we try to check some adjacent 

204 denominators for a given fraction. If they have a :func:`gcd` greater than 

205 `1` with the numerator, then we choose them instead. 

206 

207 :param value: the floating point value 

208 :param num: the numerator 

209 :param denom: the denominator 

210 :return: the fraction 

211 

212 >>> (1/7).as_integer_ratio() 

213 (2573485501354569, 18014398509481984) 

214 >>> 2573485501354569/18014398509481984 - 1/7 

215 0.0 

216 

217 >>> __minimize_frac(1/7, 2573485501354569, 18014398509481984) 

218 (1, 7) 

219 

220 >>> __minimize_frac(1/3, 6004799503160661, 18014398509481984) 

221 (1, 3) 

222 

223 >>> __minimize_frac(1/3, 1, 3) 

224 (1, 3) 

225 

226 >>> __minimize_frac(1/7, 1, 7) 

227 (1, 7) 

228 

229 >>> __minimize_frac(1/7, 10, 70) 

230 (1, 7) 

231 

232 >>> __minimize_frac(1e-20, 1, 1_0000_0000_0000_0000_0000) 

233 (1, 100000000000000000000) 

234 >>> __minimize_frac(1e-20, 1, 1_0000_0000_0000_0000_0001) 

235 (1, 100000000000000000001) 

236 >>> __minimize_frac(1e-20, 12, 12_0000_0000_0000_0000_0001) 

237 (1, 100000000000000000000) 

238 """ 

239 # First, we reduce with the GCD to simplify the fraction 

240 g: int = gcd(num, denom) # the greatest common divisor 

241 num //= g # simplify the fraction 

242 denom //= g 

243 best_num = num 

244 best_denom = denom 

245 min_gcd: int = 1 

246 

247 for num_add in range(-5, 5): 

248 use_num = num + num_add 

249 if use_num <= 0: 

250 continue 

251 for denom_add in range(-5, 5): 

252 use_denom = denom + denom_add 

253 if use_denom <= 0: 

254 continue 

255 if (use_num / use_denom) != value: 

256 continue 

257 g = gcd(use_num, use_denom) 

258 if g > min_gcd: 

259 min_gcd = g 

260 best_num, best_denom = __choose_frac( 

261 best_num, best_denom, use_num // g, use_denom // g) 

262 return best_num, best_denom 

263 

264 

265def float_to_frac(value: int | float) -> tuple[int, int]: 

266 """ 

267 Turn a floating point number into an integer fraction. 

268 

269 If we want to translate a floating point number to an integer fraction, 

270 then we have several possible ways to go about this. The reason is that, 

271 due to the loss in precision when representing fractions as floating point 

272 numbers, several different integer fractions can produce the exactly same 

273 floating point number. 

274 

275 One choice would be to use :meth:`float.as_integer_ratio`, which turns the 

276 binary representation of the floating point number to an integer fraction. 

277 This is the canonical way that, without losing any precision, will return 

278 an integer fraction that fits exactly to the floating point value. 

279 

280 However, as said, there may be multiple such fractions. And some of them 

281 may be more "compact" than others. 

282 

283 A second approach would be to first represent the floating point value as 

284 a string. The string that this produces also represents exactly this 

285 floating point value, obviously. Now we can translate the string to a 

286 fraction - and this can give us a different result. 

287 

288 Which of the two is right? 

289 

290 Both of them are. Kind of. So I'd figure we test both and stick with the 

291 :meth:`float.as_integer_ratio` default result - unless the string path 

292 provides a more compact representation. As simple yard stick, in such 

293 cases, we use the fraction with the smaller denominator. If the 

294 demoninators are the same, then we use the one with the smaller absolute 

295 numerator. 

296 

297 :param value: the floating point value 

298 :returns: the integer fraction 

299 :raises TypeError: if value is neither an integer nor a float 

300 :raises ValueError: if value is not finite 

301 

302 >>> float_to_frac(0.1) 

303 (1, 10) 

304 

305 >>> float_to_frac(1e-1) 

306 (1, 10) 

307 

308 >>> float_to_frac(1e-20) 

309 (1, 100000000000000000000) 

310 

311 >>> 1e-20.as_integer_ratio() 

312 (6646139978924579, 664613997892457936451903530140172288) 

313 

314 >>> float_to_frac(1e-30) 

315 (1, 1000000000000000000000000000000) 

316 

317 >>> float_to_frac(1e30) 

318 (1000000000000000000000000000000, 1) 

319 

320 >>> float_to_frac(1000) 

321 (1000, 1) 

322 

323 >>> float_to_frac(1000.567) 

324 (1000567, 1000) 

325 

326 >>> float_to_frac(1.234e-5) 

327 (617, 50000000) 

328 

329 >>> float_to_frac(1.234e5) 

330 (123400, 1) 

331 

332 >>> float_to_frac(0) 

333 (0, 1) 

334 >>> 0 / 1 

335 0.0 

336 

337 >>> float_to_frac(-5376935265607590) 

338 (-5376935265607590, 1) 

339 >>> -5376935265607590 / 1 

340 -5376935265607590.0 

341 

342 >>> float_to_frac(4) 

343 (4, 1) 

344 >>> 4 / 1 

345 4.0 

346 

347 >>> float_to_frac(1 / 7) 

348 (1, 7) 

349 

350 >>> float_to_frac(1 / 11) 

351 (1, 11) 

352 

353 >>> float_to_frac(1 / 10000) 

354 (1, 10000) 

355 

356 >>> float_to_frac(-21844.45693689149) 

357 (-2184445693689149, 100000000000) 

358 >>> -2184445693689149 / 100000000000 

359 -21844.45693689149 

360 

361 >>> float_to_frac(-3010907.436657168) 

362 (-188181714791073, 62500000) 

363 >>> -188181714791073 / 62500000 

364 -3010907.436657168 

365 

366 >>> float_to_frac(13660.023207762431) 

367 (26679732827661, 1953125000) 

368 >>> 26679732827661 / 1953125000 

369 13660.023207762431 

370 

371 >>> float_to_frac(438027.68586526066) 

372 (58791080797933, 134217728) 

373 >>> 58791080797933 / 134217728 

374 438027.68586526066 

375 

376 >>> float_to_frac(-8338355882.478134) 

377 (-546462491114087, 65536) 

378 >>> -546462491114087 / 65536 

379 -8338355882.478134 

380 

381 >>> float_to_frac(-32835294.95774138) 

382 (-275442417964869, 8388608) 

383 >>> -275442417964869 / 8388608 

384 -32835294.95774138 

385 

386 >>> float_to_frac(-0.8436071305882418) 

387 (-1054508913235303, 1250000000000001) 

388 >>> -1054508913235303 / 1250000000000001 

389 -0.8436071305882418 

390 

391 >>> float_to_frac(-971533.786640197) 

392 (-32599264379521, 33554432) 

393 >>> -32599264379521 / 33554432 

394 -971533.786640197 

395 

396 >>> float_to_frac(187487280836.01147) 

397 (767947902304303, 4096) 

398 >>> 767947902304303 / 4096 

399 187487280836.01147 

400 

401 >>> float_to_frac(24214223389953.125) 

402 (193713787119625, 8) 

403 >>> 193713787119625 / 8 

404 24214223389953.125 

405 

406 >>> float_to_frac(2645.112807929305) 

407 (363541536137187, 137438953472) 

408 >>> 363541536137187 / 137438953472 

409 2645.112807929305 

410 

411 >>> float_to_frac(92129361.64291245) 

412 (1545674200225257, 16777216) 

413 >>> 1545674200225257 / 16777216 

414 92129361.64291245 

415 

416 >>> float_to_frac(7218177.564653773) 

417 (1937614786056805, 268435456) 

418 >>> 1937614786056805 / 268435456 

419 7218177.564653773 

420 

421 >>> float_to_frac(-1.4589908563595052e+16) 

422 (-14589908563595052, 1) 

423 >>> -14589908563595052 / 1 

424 -1.4589908563595052e+16 

425 

426 >>> float_to_frac(-1.607745417434216e+16) 

427 (-16077454174342160, 1) 

428 >>> -16077454174342160 / 1 

429 -1.607745417434216e+16 

430 

431 >>> float_to_frac(-952261813.8291152) 

432 (-595163633643197, 625000) 

433 >>> -595163633643197 / 625000 

434 -952261813.8291152 

435 

436 >>> float_to_frac(124.69515801820336) 

437 (779344737613771, 6250000000000) 

438 >>> 779344737613771 / 6250000000000 

439 124.69515801820336 

440 

441 >>> float_to_frac(1.041491959175676e+16) 

442 (10414919591756760, 1) 

443 >>> 10414919591756760 / 1 

444 1.041491959175676e+16 

445 

446 >>> float_to_frac(1.4933667846659504e+16) 

447 (14933667846659504, 1) 

448 >>> 14933667846659504 / 1 

449 1.4933667846659504e+16 

450 

451 >>> float_to_frac(-6.034817133993009e-05) 

452 (-271784001959, 4503599627370496) 

453 >>> -271784001959 / 4503599627370496 

454 -6.034817133993009e-05 

455 

456 >>> float_to_frac(-2.682658826813622e-05) 

457 (-1887753327, 70368744177664) 

458 >>> -1887753327 / 70368744177664 

459 -2.682658826813622e-05 

460 

461 >>> float_to_frac(6.342974725370709e-05) 

462 (17853886631, 281474976710656) 

463 >>> 17853886631 / 281474976710656 

464 6.342974725370709e-05 

465 

466 >>> float_to_frac(8.759559844406795e-05) 

467 (3081996129, 35184372088832) 

468 >>> 3081996129 / 35184372088832 

469 8.759559844406795e-05 

470 

471 >>> float_to_frac(-9.6e-09) 

472 (-3, 312500000) 

473 >>> -3 / 312500000 

474 -9.6e-09 

475 

476 >>> float_to_frac(-0.4) 

477 (-2, 5) 

478 >>> -2 / 5 

479 -0.4 

480 

481 >>> float_to_frac(2e-10) 

482 (1, 5000000000) 

483 >>> 1 / 5000000000 

484 2e-10 

485 

486 >>> float_to_frac(0.3) 

487 (3, 10) 

488 >>> 3 / 10 

489 0.3 

490 

491 >>> float_to_frac(-3e-09) 

492 (-3, 1000000000) 

493 >>> -3 / 1000000000 

494 -3e-09 

495 

496 >>> float_to_frac(1e-07) 

497 (1, 10000000) 

498 >>> 1 / 10000000 

499 1e-07 

500 

501 >>> float_to_frac(-8e-08) 

502 (-1, 12500000) 

503 >>> -1 / 12500000 

504 -8e-08 

505 

506 >>> float_to_frac(-0.01) 

507 (-1, 100) 

508 >>> -1 / 100 

509 -0.01 

510 

511 >>> float_to_frac(1e-08) 

512 (1, 100000000) 

513 >>> 1 / 100000000 

514 1e-08 

515 

516 >>> float_to_frac(0.01) 

517 (1, 100) 

518 >>> 1 / 100 

519 0.01 

520 

521 >>> float_to_frac(-2e-06) 

522 (-1, 500000) 

523 >>> -1 / 500000 

524 -2e-06 

525 

526 >>> float_to_frac(-6e-08) 

527 (-3, 50000000) 

528 >>> -3 / 50000000 

529 -6e-08 

530 

531 >>> float_to_frac(7e-05) 

532 (7, 100000) 

533 >>> 7 / 100000 

534 7e-05 

535 

536 >>> float_to_frac(-1e+40) 

537 (-10000000000000000000000000000000000000000, 1) 

538 >>> -10000000000000000000000000000000000000000 / 1 

539 -1e+40 

540 

541 >>> float_to_frac(1e+40) 

542 (10000000000000000000000000000000000000000, 1) 

543 >>> 10000000000000000000000000000000000000000 / 1 

544 1e+40 

545 

546 >>> float_to_frac(1.6152587208080178e+161) 

547 (16152587208080177786162779887253130808505244217290853753086392891829620\ 

5481092892491941055809815064259587161746312711311289043311353137951968371237523\ 

549928335253504000, 1) 

550 """ 

551 value = try_int(value) 

552 if isinstance(value, int): 

553 return value, 1 

554 

555 minus: Final[bool] = value < 0.0 

556 if minus: 

557 value = -value 

558 

559 # Get the minimized fraction. 

560 num1, denom1 = __minimize_frac(value, *value.as_integer_ratio()) 

561 

562 # First, we convert the floating point number to a string, which 

563 # necessarily exactly represents the value. Then we will go and turn 

564 # the string into a fraction. 

565 value_str: Final[str] = float.__repr__(value) 

566 

567 end_idx: int = str.__len__(value_str) 

568 dot_idx: Final[int] = str.find(value_str, ".") 

569 exp_idx: Final[int] = str.find(value_str, "e") 

570 

571 denom2: int = 1 

572 multiplier: int = 1 

573 if exp_idx > 0: 

574 int_exp = int(value_str[exp_idx + 1:end_idx]) 

575 if int_exp < 0: 

576 denom2 = 10 ** (-int_exp) 

577 else: 

578 multiplier = 10 ** int_exp 

579 end_idx = exp_idx 

580 

581 num2: int = 0 

582 if dot_idx >= 0: 

583 int_denom_2 = 10 ** (end_idx - dot_idx - 1) 

584 num2 = ((int(value_str[:dot_idx]) * int_denom_2) 

585 + int(value_str[dot_idx + 1:end_idx])) 

586 denom2 *= int_denom_2 

587 else: 

588 num2 = int(value_str[:end_idx]) 

589 

590 num2 *= multiplier 

591 if num2 / denom2 == value: 

592 num1, denom1 = __choose_frac(*__minimize_frac( 

593 value, num2, denom2), num1, denom1) 

594 return (-num1 if minus else num1), denom1 

595 

596 

597def try_int_div(a: int, b: int) -> int | float: 

598 """ 

599 Try to divide two integers at best precision. 

600 

601 Floating point divisions can incur some loss of precision. We try 

602 to avoid this here as much as possible. First, we check if `a` is 

603 divisible by `b` without any fractional part. If this is true, then 

604 we can do a pure integer division without loss of any precision. 

605 In other words, if `a % b == 0`, then `a / b` is itself an integer, 

606 i.e., can be represented exactly. 

607 

608 Otherwise, it will have a fractional part, so it would ideally be a 

609 `float`. 

610 Well. 

611 

612 What if the integer `a` is really large? Converting it to floating 

613 point number may then incur a loss of precision. And why do we convert 

614 it to a `float` in the first place? To properly represent the fractional 

615 part. Because the integer part is `a // b` is an integer. The fractional 

616 part `f` is then by definition `f = (a % b) // b == (a - b*(a // b)) / b`. 

617 Obviously, `0<f<1`. It may be entirely possible that we lose several full 

618 integer *digits* by converting the integer `a` to a `float` ... just to 

619 then be able to add a fraction `f`. So this loss of precision may be much 

620 larger than the little fractional part that we would add (which will 

621 always be in `(0, 1)`. In such a case, it may be much better to stay in 

622 the realm of integers and instead lose the fractional part. Thus, we also 

623 test whether multiplying the result of the floating point computation with 

624 `b` is closer to `a` than integer results rounded in either direction. 

625 

626 During this procedure, we try to pick the result closest to the original 

627 value. This, however, may only be possible if we can actually compute the 

628 difference. If we deal with floating point numbers and integers, some 

629 integers may simply be too large for being ever converted to a float. In 

630 this case, we remain entirely in the integer realm and only round if need 

631 be. 

632 

633 :param a: the first integer 

634 :param b: the second integer 

635 :returns: a/b, either as `int` or as `float` but always a finite value 

636 :raises ZeroDivisionError: if `b==0` 

637 :raises TypeError: if `a` or `b` are not integers 

638 

639 >>> print(try_int_div(10, 2)) 

640 5 

641 >>> print(try_int_div(10, -2)) 

642 -5 

643 >>> print(try_int_div(-10, 2)) 

644 -5 

645 >>> print(try_int_div(-10, -2)) 

646 5 

647 >>> print(type(try_int_div(10, 2))) 

648 <class 'int'> 

649 >>> print(try_int_div(10, 3)) 

650 3.3333333333333335 

651 >>> print(try_int_div(-10, 3)) 

652 -3.3333333333333335 

653 >>> print(try_int_div(10, -3)) 

654 -3.3333333333333335 

655 >>> print(try_int_div(-10, -3)) 

656 3.3333333333333335 

657 >>> print(type(try_int_div(10, 3))) 

658 <class 'float'> 

659 >>> print(try_int_div(9007199254740992, 1)) 

660 9007199254740992 

661 >>> print(try_int_div(2109792310235001520128, 234234)) 

662 9007199254740992 

663 >>> print(try_int_div(2109792310235001520128, 234235)) 

664 9007160801054503 

665 >>> print(try_int_div(2109792310235001520128, 234233)) 

666 9007237708755818 

667 >>> large = 123456789012345678901234567890123456789012345678901234567\ 

66889012345678901234567890123456789012345678901234567890123456789012345678901234\ 

66956789012345678901234567890123456789012345678901234567890123456789012345678901\ 

67023456789012345678901234567890123456789012345678901234567890123456789012345678\ 

67190123456789012345678901234567890123456789012345678901234567890123456789012345\ 

67267890123456789012345678901234567890123456789012345678901234567890123456789012\ 

6733456789012345678901234567890123456789012345678901234567890123456789012345678\ 

67490123456789012345678901234567890123456789012345678901234567890123456789012345\ 

675678901234567890123456789012345678901234567890 

676 

677 >>> try: 

678 ... large / 1 

679 ... except OverflowError as oe: 

680 ... print(oe) 

681 integer division result too large for a float 

682 >>> try_int_div(large, 1) 

683 123456789012345678901234567890123456789012345678901234567\ 

68489012345678901234567890123456789012345678901234567890123456789012345678901234\ 

68556789012345678901234567890123456789012345678901234567890123456789012345678901\ 

68623456789012345678901234567890123456789012345678901234567890123456789012345678\ 

68790123456789012345678901234567890123456789012345678901234567890123456789012345\ 

68867890123456789012345678901234567890123456789012345678901234567890123456789012\ 

6893456789012345678901234567890123456789012345678901234567890123456789012345678\ 

69090123456789012345678901234567890123456789012345678901234567890123456789012345\ 

691678901234567890123456789012345678901234567890 

692 

693 >>> try_int_div(large * 7, 1 * 7) 

694 123456789012345678901234567890123456789012345678901234567\ 

69589012345678901234567890123456789012345678901234567890123456789012345678901234\ 

69656789012345678901234567890123456789012345678901234567890123456789012345678901\ 

69723456789012345678901234567890123456789012345678901234567890123456789012345678\ 

69890123456789012345678901234567890123456789012345678901234567890123456789012345\ 

69967890123456789012345678901234567890123456789012345678901234567890123456789012\ 

7003456789012345678901234567890123456789012345678901234567890123456789012345678\ 

70190123456789012345678901234567890123456789012345678901234567890123456789012345\ 

702678901234567890123456789012345678901234567890 

703 

704 >>> res = try_int_div(large, 7) 

705 >>> print(res) 

706 1763668414462081127160493827001763668414462081127160493827001763668414462\ 

70708112716049382700176366841446208112716049382700176366841446208112716049382700\ 

70817636684144620811271604938270017636684144620811271604938270017636684144620811\ 

70927160493827001763668414462081127160493827001763668414462081127160493827001763\ 

71066841446208112716049382700176366841446208112716049382700176366841446208112716\ 

71104938270017636684144620811271604938270017636684144620811271604938270017636684\ 

71214462081127160493827001763668414462081127160493827001763668414462081127160493\ 

71382700176366841446208112716049382700176366841446208112716049382700176366841446\ 

714208112716049382700176366841 

715 >>> large - (res * 7) 

716 3 

717 

718 >>> res = try_int_div(large - 1, 7) 

719 >>> print(res) 

720 1763668414462081127160493827001763668414462081127160493827001763668414462\ 

72108112716049382700176366841446208112716049382700176366841446208112716049382700\ 

72217636684144620811271604938270017636684144620811271604938270017636684144620811\ 

72327160493827001763668414462081127160493827001763668414462081127160493827001763\ 

72466841446208112716049382700176366841446208112716049382700176366841446208112716\ 

72504938270017636684144620811271604938270017636684144620811271604938270017636684\ 

72614462081127160493827001763668414462081127160493827001763668414462081127160493\ 

72782700176366841446208112716049382700176366841446208112716049382700176366841446\ 

728208112716049382700176366841 

729 >>> (large - 1) - (res * 7) 

730 2 

731 

732 >>> res = try_int_div(large + 1, 7) 

733 >>> print(res) 

734 1763668414462081127160493827001763668414462081127160493827001763668414462\ 

73508112716049382700176366841446208112716049382700176366841446208112716049382700\ 

73617636684144620811271604938270017636684144620811271604938270017636684144620811\ 

73727160493827001763668414462081127160493827001763668414462081127160493827001763\ 

73866841446208112716049382700176366841446208112716049382700176366841446208112716\ 

73904938270017636684144620811271604938270017636684144620811271604938270017636684\ 

74014462081127160493827001763668414462081127160493827001763668414462081127160493\ 

74182700176366841446208112716049382700176366841446208112716049382700176366841446\ 

742208112716049382700176366842 

743 >>> (large + 1) - (res * 7) 

744 -3 

745 

746 >>> try: 

747 ... try_int_div(0, 0) 

748 ... except ZeroDivisionError as zde: 

749 ... print("by zero" in str(zde)) 

750 True 

751 

752 >>> try: 

753 ... try_int_div(1, 0) 

754 ... except ZeroDivisionError as zde: 

755 ... print("by zero" in str(zde)) 

756 True 

757 

758 >>> try: 

759 ... try_int_div(-1, 0) 

760 ... except ZeroDivisionError as zde: 

761 ... print("by zero" in str(zde)) 

762 True 

763 

764 >>> try_int_div(153, 17) 

765 9 

766 >>> try_int_div(-153, 17) 

767 -9 

768 >>> try_int_div(626240198453350272215815210991, 180) 

769 3479112213629723734532306728 

770 >>> try_int_div(-626240198453350272215815210991, 180) 

771 -3479112213629723734532306728 

772 >>> try_int_div(312641328808813509022862142116, 184) 

773 1699137656569638635993815990 

774 >>> try_int_div(-312641328808813509022862142116, 184) 

775 -1699137656569638635993815990 

776 >>> try_int_div(300228563787891776398328530521, 6) 

777 50038093964648629399721421754 

778 >>> try_int_div(300228563787891776398328530520, 6) 

779 50038093964648629399721421753 

780 >>> try_int_div(-300228563787891776398328530521, 6) 

781 -50038093964648629399721421754 

782 

783 >>> try_int_div(153, -17) 

784 -9 

785 >>> try_int_div(-153, -17) 

786 9 

787 >>> try_int_div(626240198453350272215815210991, -180) 

788 -3479112213629723734532306728 

789 >>> try_int_div(-626240198453350272215815210991, -180) 

790 3479112213629723734532306728 

791 >>> try_int_div(312641328808813509022862142116, -184) 

792 -1699137656569638635993815990 

793 >>> try_int_div(-312641328808813509022862142116, -184) 

794 1699137656569638635993815990 

795 >>> try_int_div(300228563787891776398328530521, -6) 

796 -50038093964648629399721421754 

797 >>> try_int_div(-300228563787891776398328530521, -6) 

798 50038093964648629399721421754 

799 

800 >>> try_int_div(471560594207063922064065980174, 160) 

801 2947253713794149512900412376 

802 

803 >>> try_int_div(7995687632, 605623302520652727304862084393) 

804 1.3202410803417417e-20 

805 

806 >>> try_int_div(308201705551808339041017943851, 23) 

807 13400074154426449523522519298 

808 

809 >>> try_int_div(899348944156468188933109403939, 54) 

810 16654610076971633128390914888 

811 

812 >>> try_int_div(494818043590514116668712249977, 42) 

813 11781381990250336111159815476 

814 

815 >>> try_int_div(738070379515233920, 205) 

816 3600343314708458 

817 

818 >>> try_int_div(3502315235185234554036893628, 2914324106703) 

819 1201759003787480 

820 

821 >>> try_int_div(7410628973168661103, 3869) 

822 1915386139356076.8 

823 

824 >>> try_int_div(1230161216449799063065724370370, 4689247521470) 

825 262336592559346126 

826 

827 >>> try_int_div(1052870426843577701006624798274, 28) 

828 37602515244413489321665171367 

829 

830 >>> try_int_div(218235816140080518429116, 65180391) 

831 3348182065064330.5 

832 

833 >>> try_int_div(542681063252950460111634072, 1417) 

834 382978873149576894927053 

835 

836 >>> try_int_div(6347580784084238615827, 9508617) 

837 667560885466754.9 

838 

839 >>> try_int_div(25864142832167873073008, 8621014) 

840 3000127691727199.5 

841 

842 >>> try_int_div(35377667634669293542601414338, 8678403583) 

843 4076517909811212054 

844 

845 >>> try_int_div(1423204593957046760175, 6) 

846 237200765659507793363 

847 

848 >>> try_int_div(1959151753859121847452742, 155502) 

849 12598884605079817928 

850 

851 >>> try_int_div(153429321515534965993379305, 15165212220) 

852 10117189215010864 

853 

854 >>> try_int_div(638685779810794590594721888599, 6355644831674) 

855 100491106209686119 

856 

857 >>> try_int_div(14634805, 3163458943542033136) 

858 4.626203551614245e-12 

859 

860 >>> try_int_div(2728490692514068837390, 1134) 

861 2406076448425104795 

862 

863 >>> try_int_div(52133244, 2145832361321597595907) 

864 2.4295115005112346e-14 

865 

866 >>> try_int_div(989732710522254024, 870) 

867 1137623805197993.2 

868 

869 >>> try_int_div(1015, 4100715151904) 

870 2.475178017494646e-10 

871 

872 >>> try_int_div(750731, 60649291746) 

873 1.2378231936228884e-05 

874 

875 >>> try_int_div(7972413701754221571302566, 1660418690) 

876 4801447821425222 

877 

878 >>> try_int_div(356135676699525125944, 46208) 

879 7707229845471025 

880 

881 >>> try_int_div(10448177882855961291672, 1739414) 

882 6006722886475538 

883 

884 >>> try_int_div(739391142068058031063862, 8456) 

885 87439822855730609161 

886 

887 >>> try_int_div(316514845935646909034735039673, 32172) 

888 9838208564455020173900753 

889 

890 >>> try_int_div(4158458869534984918534998087, 30) 

891 138615295651166163951166603 

892 

893 >>> try_int_div(102306108211747181839762853503, 29118) 

894 3513500522417308257427119 

895 

896 >>> all(try_int_div(1, y) == (1 / y) for y in range(2, 10)) 

897 True 

898 

899 >>> all(try_int_div(2, y) == (2 / y) for y in range(3, 10)) 

900 True 

901 

902 >>> try_int_div(820432337843942760, 85) 

903 9652145151105209 

904 

905 >>> try_int_div(84050617, 3577089862) 

906 0.023496926340286613 

907 

908 >>> try_int_div(812060021745358856, 996816531) 

909 814653445.7356013 

910 

911 >>> try_int_div(38029336, 472982612237) 

912 8.040324319775297e-05 

913 

914 >>> try_int_div(50229909719349513, 9) 

915 5581101079927724 

916 

917 >>> try_int_div(61320503685013026, 2728161164469337) 

918 22.476862614874392 

919 

920 >>> try_int_div(23134400382350491, 8) 

921 2891800047793811.5 

922 

923 >>> try_int_div(12510965, 67561917605841203) 

924 1.8517776645993746e-10 

925 

926 >>> try_int_div(27246707584980173, 4) 

927 6811676896245043 

928 

929 >>> try_int_div(135385235231741420, 6) 

930 22564205871956903 

931 

932 >>> try_int_div(90, 153429501803) 

933 5.865886217603572e-10 

934 

935 >>> try_int_div(734553401849288248, 951111) 

936 772310909924.5916 

937 

938 >>> try_int_div(9820998979656, 4239082999146) 

939 2.3167744018304255 

940 

941 >>> try_int_div(133105116441194557, 17) 

942 7829712731834974 

943 

944 >>> try_int_div(1004604250960040176, 14) 

945 71757446497145727 

946 

947 >>> try_int_div(246148731190755584, 6) 

948 41024788531792597 

949 

950 >>> try_int_div(991564, 72057594037927936) 

951 1.3760714789867734e-11 

952 

953 >>> try_int_div(2623725286393384, 139634775865757) 

954 18.789912972079378 

955 

956 >>> try_int_div(63010439554808723, 9) 

957 7001159950534303 

958 

959 >>> try_int_div(2801452, 427673) 

960 6.550453266865105 

961 

962 >>> try_int_div(14177411351567, 349688426689780) 

963 0.04054298132132421 

964 

965 >>> try_int_div(126660394112336947, 368) 

966 344185853566133 

967 

968 >>> try_int_div(1031427640916897886, 7) 

969 147346805845271127 

970 

971 >>> try_int_div(33290935002573849, 2) 

972 16645467501286925 

973 

974 >>> try_int_div(209062743096233332, 64) 

975 3266605360878646 

976 

977 >>> try_int_div(253174817711179642, 57) 

978 4441663468617186.5 

979 

980 >>> try_int_div(29462133006911895, 24943246) 

981 1181166757.8033707 

982 

983 >>> try_int_div(93475849985676023, 60673699562) 

984 1540632.1134276118 

985 

986 >>> try_int_div(-16, -16) 

987 1 

988 

989 >>> try_int_div(242, 150) 

990 1.6133333333333333 

991 

992 >>> try_int_div(-547, -698) 

993 0.7836676217765043 

994 

995 >>> try_int_div(463, 105) 

996 4.40952380952381 

997 

998 >>> try_int_div(-148, -203) 

999 0.729064039408867 

1000 

1001 >>> try_int_div(0, -25) 

1002 0 

1003 

1004 >>> try_int_div(24, -177) 

1005 -0.13559322033898305 

1006 

1007 >>> try_int_div(-166, 186) 

1008 -0.8924731182795699 

1009 

1010 >>> try_int_div(-608143760099358008316, 16) 

1011 -38008985006209875520 

1012 

1013 >>> try_int_div(-6917198296130591233, 2932) 

1014 -2359208150112753 

1015 

1016 >>> try_int_div(-40068404846647758412, 2431) 

1017 -16482272664190769 

1018 

1019 >>> try_int_div(809884532216820092, -80) 

1020 -10123556652710251 

1021 

1022 >>> try_int_div(-9428902965475478968, -1946) 

1023 4845273877428304 

1024 

1025 >>> try_int_div(94881103250893722164, 174) 

1026 545293696844216794 

1027 

1028 >>> try_int_div(558275776531402194, 196) 

1029 2848345798629603 

1030 

1031 >>> try_int_div(-5470954588630039684, -1425) 

1032 3839266377985993 

1033 

1034 >>> x = 52051907638184435686872083537997907834107397007408814104887055550\ 

103562651162584515572343506336421788506498764827396236326664325857298113627143047\ 

103651960058116028166468699987611855171916670918181477368243402962224866666859483\ 

103727106641344727853102203836313167806475289935694133683049416723665601922267867\ 

103843423073756386687744959209264639678418438341653942959851578625489694262628828\ 

103901502680997461128779292890987864647476268814586685317933377503211673153129336\ 

104003 

1041 >>> y = -1390354761575126197823721816501267487365151253235077143453455350\ 

104242071715351921681111638693456863646113210365045493352 

1043 >>> try_int_div(x, y) 

1044 -374378605207314720094873468836285633819929467061778300817269205498029513\ 

104565402433513265745971266615921400317429877366670340545494622384105823993306348\ 

104652843139170606054848072439314573682429224161889047753873201343420620892557508\ 

104762700497112616274728625215898978448963212698759159253800300962780904741771804\ 

1048645167943738988195771748632862162 

1049 

1050 >>> x = -2371099749665044990658141554075074237566818135879925492767658755\ 

105191466431785344954996723447284617738104563308335316636469414432945133872626562\ 

105247514537471872530515191642703803616012611248118482218872482697827387761273565\ 

105386825000794528611072492997052827719254891404531142028847153355973782623685875\ 

105455388033455119839506838214696423221276537787120528956164822252461892023157114\ 

105502799038227958323905920667727058869625829951896827916647011550854954614174228\ 

10560327582498733595995697631187168710055335569609973997123439124471957303314220 

1057 >>> y = 23343578649740692313745114608806472033684574464287511781560680643\ 

105878701796266433578371331497 

1059 >>> try_int_div(x, y) 

1060 -101573961098350440775039372298606794268469908577045401233130406288914282\ 

106192918893248309802232281829255680862092165642164462698933290177430764947955661\ 

106287652857199541665161754173953190591131037518696771010612358486878465958542091\ 

106354914381056640460582835505879418330902968200425941036454902030259440742425865\ 

106493440206970165106076445287259870479244010983474198088053313334979762284802017\ 

10651153886834216445854191456742632611734684212485945595091 

1066 

1067 >>> x = 40410061884642793201602670149115414017394734761323545080847020296\ 

106825252534757283636685784303675489231680221820894136736092474359799408796002401\ 

106987921742390653841150636438854369236710256224057607718115525186887758631639670\ 

107082468402380054839668544662058030344964306015945683011983835531538788295592437\ 

107165716882229369219075665520432950975969718863463181388344946182200519006147179\ 

107264461315530742161850062785306859778524746068148875909170944464910610460508750\ 

1073707051996751159775959805908309 

1074 >>> try_int_div(x, 455824846955327759894405021890034373481341853483437732) 

1075 8865260890133771894279961299939580714408739728863480476996077470796169955\ 

107643085620471927592765951912973058793385603301586629745150439814928912960267883\ 

107766400412702824502182496145839556516762964408587815797906905800899307550385283\ 

107859797468484699310297417864757571840405529641545438878013277855865542975695833\ 

107988146919245416237227940140677498927052487483630425657258239092995434299050034\ 

1080021769275549143357256693312576946435784210430 

1081 

1082 >>> x = -6232936786190843094006005233017695847240511752635979691082519622\ 

108389671822451515008492890632740917254159586399372900046205300278719490624751881\ 

108476026655230475873682972201137642189143060727745274448518821915960488822897219\ 

108519105433159267999911968464110051361652323090653411336081715581855840751539611\ 

108644549510551090842769903146173949669899963195645511983189442245054559694895154\ 

108728690282113755080383328799009405959846487733552322199361433571441631699077621\ 

1088235779724223724145601506861527256455350316142 

1089 >>> y = -672227780379448967615099076221459579351218967417588220 

1090 >>> try_int_div(x, y) 

1091 9272060703401113879042492429626067042706252670698636022710487050821126676\ 

109243853746484009770979124008642489211907343513622775392767108564692587266167738\ 

109393885766234994122772733590708011238049750176667082969644614903930265971589853\ 

109426674807243894898200722561326294551914700598739493395761954564220400052036328\ 

109558909594484124974270252599224045683880122299500249240856446063861849302671425\ 

109605617327729864850535306650812894643758024556770793387750201 

1097 

1098 >>> try: 

1099 ... try_int_div(1.0, 2) 

1100 ... except TypeError as te: 

1101 ... print(te) 

1102 a should be an instance of int but is float, namely 1.0. 

1103 

1104 >>> try: 

1105 ... try_int_div(1, 2.0) 

1106 ... except TypeError as te: 

1107 ... print(te) 

1108 b should be an instance of int but is float, namely 2.0. 

1109 """ 

1110 if not isinstance(a, int): 

1111 raise type_error(a, "a", int) 

1112 if not isinstance(b, int): 

1113 raise type_error(b, "b", int) 

1114 minus: bool = False 

1115 if a < 0: 

1116 minus = True 

1117 a = -a 

1118 if b < 0: 

1119 minus = not minus 

1120 b = -b 

1121 

1122 # Let's say a = 762 and b = 204. 

1123 # We first compute the GCD to reduce both sides of the equation. 

1124 the_gcd: Final[int] = gcd(a, b) # == 6 in the example 

1125 a //= the_gcd # == 127 in the example 

1126 b //= the_gcd # == 34 in the example 

1127 

1128 # First, let's compute the result of the pure integer division. 

1129 int_res_1: Final[int] = a // b # == 3 in our example 

1130 int_mult_1: Final[int] = int_res_1 * b # == 102 in the example 

1131 if int_mult_1 == a: # if there is no rest, then we can stop here 

1132 return -int_res_1 if minus else int_res_1 

1133 

1134 int_frac_1: Final[int] = a - int_mult_1 # == 25 in the example 

1135 int_res_2: Final[int] = int_res_1 + 1 # rounding up, == 4 in the example 

1136 # Compute int_frac_2 == (int_res_2 * b - a, but simplified: 

1137 int_frac_2: Final[int] = b - int_frac_1 # == 9 in the example 

1138 

1139 # OK, there may be a loss of precision if we do the floating point 

1140 # computation. But we should try it now anyway. 

1141 # if `a` and `b` can exactly be represented as floats (by being not more 

1142 # than `__DBL_INT_LIMIT_P_I`, then we are OK and can directly use the 

1143 # result. Otherwise, if the result is between the lower and the upper 

1144 # limit, then we will also take it. This would mean to basically default 

1145 # to the normal division in Python in cases where it falls into the 

1146 # expected range of possible results. 

1147 with suppress(ArithmeticError): 

1148 float_res = __try_int(a / b) # == 3.5588235294117645 in the example 

1149 if ((a <= __DBL_INT_LIMIT_P_I) and (b <= __DBL_INT_LIMIT_P_I)) or ( 

1150 int_res_1 < float_res < int_res_2): 

1151 return -float_res if minus else float_res 

1152 

1153 best_result: Final[int] = \ 

1154 int_res_2 if int_frac_2 <= int_frac_1 else int_res_1 

1155 return -best_result if minus else best_result # fix sign of result 

1156 

1157 

1158def try_float_int_div(a: int | float, b: int) -> int | float: 

1159 """ 

1160 Try to divide a float by an int at best precision. 

1161 

1162 :param a: the first number, which is either a float or an int 

1163 :param b: the second number, which must be an int 

1164 :returns: `a/b`, but always finite 

1165 

1166 :raises ValueError: if either one of the arguments or the final result 

1167 would not be finite 

1168 :raises TypeError: if either one of `a` or `b` is neither an integer nor 

1169 a float 

1170 

1171 >>> try_float_int_div(10, 2) 

1172 5 

1173 

1174 >>> try_float_int_div(10.0, 2) 

1175 5 

1176 

1177 >>> try_float_int_div(10, 3) 

1178 3.3333333333333335 

1179 

1180 >>> try_float_int_div(-10, 2) 

1181 -5 

1182 

1183 >>> try_float_int_div(-10.2, 2) 

1184 -5.1 

1185 

1186 >>> try_float_int_div(-10.0, 2) 

1187 -5 

1188 

1189 >>> try_float_int_div(-10, 3) 

1190 -3.3333333333333335 

1191 

1192 >>> print(type(try_float_int_div(10.0, 2))) 

1193 <class 'int'> 

1194 

1195 >>> print(type(try_float_int_div(10.0, 3))) 

1196 <class 'float'> 

1197 

1198 >>> try: 

1199 ... try_float_int_div(10, 0.5) 

1200 ... except TypeError as te: 

1201 ... print(te) 

1202 b should be an instance of int but is float, namely 0.5. 

1203 

1204 >>> from math import inf, nan 

1205 >>> try: 

1206 ... try_float_int_div(1.0, 0) 

1207 ... except ZeroDivisionError as zde: 

1208 ... print("by zero" in str(zde)) 

1209 True 

1210 

1211 >>> try: 

1212 ... try_float_int_div(inf, 0) 

1213 ... except ValueError as ve: 

1214 ... print(ve) 

1215 Value must be finite, but is inf. 

1216 

1217 >>> try: 

1218 ... try_float_int_div(-inf, 0) 

1219 ... except ValueError as ve: 

1220 ... print(ve) 

1221 Value must be finite, but is -inf. 

1222 

1223 >>> try: 

1224 ... try_float_int_div(nan, 0) 

1225 ... except ValueError as ve: 

1226 ... print(ve) 

1227 Value must be finite, but is nan. 

1228 

1229 >>> try: 

1230 ... try_float_int_div(1, inf) 

1231 ... except TypeError as te: 

1232 ... print(te) 

1233 b should be an instance of int but is float, namely inf. 

1234 

1235 >>> try: 

1236 ... try_float_int_div("y", 1) 

1237 ... except TypeError as te: 

1238 ... print(te)