Python custom class takes 23 times as much as the time direct application of formula takes to execute. How to optimize?
This isn't homework or job-related. And I wrote all the code completely by myself.
So I have been using basic algebra to calculate many things using only integer arithmetic by separating the parts. Like (a + b sqrt(N))(c + d sqrt(N)) = (ac + Nbd) + (ad + bc)sqrt(N), and (a + bi)(c + di) = (ac - bd) + (ad + bc)i.
Now I have decided to wrap things in classes to make code cleaner, I tried to do this with fractions first, and I have done it, but somehow the class is much slower than direct calculation.
The core idea of my class is extremely simple, I just used a/b + c/d = (ad + bc)/(bd) and derived a bunch of formulas from it. I have implemented __add__, __sub__, __mul__, __truediv__, __divmod__, __floordiv__, __mod__, __neg__, __pow__, __eq__, __ne__, __lt__, __le__, __gt__, __ge__ operators, as the algorithm is self-evident I won't bother to explain my code. All of them work, I have tested thoroughly.
Now before you ask why I don't use fractions.Fraction, look at this:
In [6]: from fractions import Fraction
In [7]: Fraction(50, 100)
Out[7]: Fraction(1, 2)
It is evident that fractions.Fraction class does fraction reduction every step and so it uses one GCD and two floor divisions every single step, so it will be very time-consuming if I add a bunch of fractions together, and power series need many many terms.
Here is the code:
import math
import operator
from typing import Self
class Fraction:
__slots__ = ("numerator", "denominator", "reduced")
def __init__(self, numerator: int, denominator: int) -> None:
if (
notint := not (isinstance(numerator, int) and isinstance(denominator, int))
) or (divby0 := not denominator):
raise (
TypeError("both numerator and denominator must be integers"),
ValueError("denominator cannot be zero"),
)[divby0 > notint]
neg_num = numerator < 0
neg_den = denominator < 0
self.denominator = (denominator, -denominator)[neg_den]
self.numerator = (numerator, -numerator)[neg_num ^ (neg_num ^ neg_den)]
self.reduced = False
def reduce(self) -> None:
if not self.reduced:
common = math.gcd(self.numerator, self.denominator)
self.numerator //= common
self.denominator //= common
self.reduced = True
def __repr__(self) -> str:
return f"Fraction({self.numerator}, {self.denominator})"
def __str__(self) -> str:
return f"{self.numerator}/{self.denominator}"
def _special_fraction_addition(self, other: Self) -> Self:
return Fraction(self.numerator + other.numerator, self.denominator)
def _general_fraction_addition(self, other: Self) -> Self:
return Fraction(
self.numerator * other.denominator + self.denominator * other.numerator,
self.denominator * other.denominator,
)
def _integer_fraction_addition(self, other: int) -> Self:
return Fraction(self.numerator + other * self.denominator, self.denominator)
def _special_fraction_subtraction(self, other: Self) -> Self:
return Fraction(self.numerator - other.numerator, self.denominator)
def _general_fraction_subtraction(self, other: Self) -> Self:
return Fraction(
self.numerator * other.denominator - self.denominator * other.numerator,
self.denominator * other.denominator,
)
def _integer_fraction_subtraction(self, other: int) -> Self:
return Fraction(self.numerator - other * self.denominator, self.denominator)
def _general_fraction_multiplication(self, other: Self) -> Self:
return Fraction(
self.numerator * other.numerator, self.denominator * other.denominator
)
def _integer_fraction_multiplication(self, other: int) -> Self:
return Fraction(self.numerator * other, self.denominator)
def _general_fraction_division(self, other: Self) -> Self:
return Fraction(
self.numerator * other.denominator, self.denominator * other.numerator
)
def _integer_fraction_division(self, other: int) -> Self:
if not other:
raise ValueError("division by zero")
return Fraction(self.numerator, self.denominator * other)
def _general_fraction_equality(self, other: Self) -> bool:
return (
(
self.denominator == other.denominator
and self.numerator == other.numerator
)
or self.numerator * other.denominator == self.denominator * other.numerator
)
def _integer_fraction_equality(self, other: int) -> bool:
return self.numerator == self.denominator * other
def _general_fraction_less_than(self, other: Self) -> bool:
return (
self.denominator == other.denominator and self.numerator < other.numerator
) or self.numerator * other.denominator < self.denominator * other.numerator
def _integer_fraction_less_than(self, other: int) -> bool:
return self.numerator < self.denominator * other
def _general_fraction_greater_than(self, other: Self) -> bool:
return (
self.denominator == other.denominator and self.numerator > other.numerator
) or self.numerator * other.denominator > self.denominator * other.numerator
def _integer_fraction_greater_than(self, other: int) -> bool:
return self.numerator > self.denominator * other
def _general_fraction_floor_division(self, other: Self) -> tuple[int, Self]:
div, mod = divmod(
self.numerator * other.denominator, self.denominator * other.numerator
)
return (div, Fraction(mod, self.denominator * other.denominator))
def _special_fraction_floor_division(self, other: Self) -> tuple[int, Self]:
div, mod = divmod(self.numerator, other.numerator)
return (div, Fraction(mod, self.denominator))
def _integer_fraction_floor_division(self, other: int) -> tuple[int, Self]:
div, mod = divmod(self.numerator, self.denominator * other)
return (div, Fraction(mod, self.denominator))
def __neg__(self) -> Self:
return Fraction(-self.numerator, self.denominator)
def __add__(self, other: int | Self) -> Self:
if not ((isfrac := isinstance(other, Fraction)) or isinstance(other, int)):
raise TypeError("argument must be either int or Fraction")
return (
self._integer_fraction_addition,
self._general_fraction_addition,
self._special_fraction_addition,
)[isfrac + (isfrac and self.denominator == other.denominator)](other)
def __sub__(self, other: int | Self) -> Self:
if not ((isfrac := isinstance(other, Fraction)) or isinstance(other, int)):
raise TypeError("argument must be either int or Fraction")
return (
self._integer_fraction_subtraction,
self._general_fraction_subtraction,
self._special_fraction_subtraction,
)[isfrac + (isfrac and self.denominator == other.denominator)](other)
def __mul__(self, other: int | Self) -> Self:
if not ((isfrac := isinstance(other, Fraction)) or isinstance(other, int)):
raise TypeError("argument must be either int or Fraction")
return (
self._integer_fraction_multiplication,
self._general_fraction_multiplication,
)[isfrac](other)
def __truediv__(self, other: int | Self) -> Self:
if not ((isfrac := isinstance(other, Fraction)) or isinstance(other, int)):
raise TypeError("argument must be either int or Fraction")
return (self._integer_fraction_division, self._general_fraction_division)[
isfrac
](other)
def __lt__(self, other: int | Self) -> bool:
if not ((isfrac := isinstance(other, Fraction)) or isinstance(other, int)):
raise TypeError("argument must be either int or Fraction")
return (self._integer_fraction_less_than, self._general_fraction_less_than)[
isfrac
](other)
def __eq__(self, other: int | Self) -> bool:
if not ((isfrac := isinstance(other, Fraction)) or isinstance(other, int)):
raise TypeError("argument must be either int or Fraction")
return (self._integer_fraction_equality, self._general_fraction_equality)[
isfrac
](other)
def __gt__(self, other: int | Self) -> bool:
if not ((isfrac := isinstance(other, Fraction)) or isinstance(other, int)):
raise TypeError("argument must be either int or Fraction")
return (
self._integer_fraction_greater_than,
self._general_fraction_greater_than,
)[isfrac](other)
def __le__(self, other: int | Self) -> bool:
return not self > other
def __ne__(self, other: int | Self) -> bool:
return not self == other
def __ge__(self, other: int | Self) -> bool:
return not self < other
def __divmod__(self, other: int | Self) -> tuple[int, Self]:
if not ((isfrac := isinstance(other, Fraction)) or isinstance(other, int)):
raise TypeError("argument must be either int or Fraction")
return (
self._integer_fraction_floor_division,
self._general_fraction_floor_division,
self._special_fraction_floor_division,
)[isfrac + (isfrac and self.denominator == other.denominator)](other)
def __floordiv__(self, other: int | Self) -> int:
return divmod(self, other)[0]
def __mod__(self, other: int | Self) -> Self:
return divmod(self, other)[1]
def __pow__(self, other: int) -> Self:
if not isinstance(other, int):
raise TypeError("only integer exponents are supported")
if not other:
return Fraction(1, 1)
negative = other < 0
other = (other, -other)[negative]
pair = (self.numerator, self.denominator)
numerator = pair[0 ^ negative]
denominator = pair[1 ^ negative]
return Fraction(pow(numerator, other), pow(denominator, other))
As I have said, it works:
In [190]: ARITHMETIC_OPS = ("add", "sub", "mul", "truediv")
...: COMPARISON_OPS = ("eq", "ne", "lt", "le", "gt", "ge")
...: denominators = list(range(-10, 0)) + list(range(1, 11))
...: for num_1 in denominators:
...: for den_1 in denominators:
...: float1 = num_1 / den_1
...: frac1 = Fraction(num_1, den_1)
...: for num_2 in denominators:
...: for den_2 in denominators:
...: float2 = num_2 / den_2
...: frac2 = Fraction(num_2, den_2)
...: for op in ARITHMETIC_OPS:
...: func = getattr(operator, op)
...: frac3 = func(frac2, num_1)
...: frac4 = func(frac1, frac2)
...: assert math.isclose(
...: func(float2, num_1),
...: frac3.numerator / frac3.denominator,
...: )
...: assert math.isclose(
...: func(float1, float2),
...: frac4.numerator / frac4.denominator,
...: )
...:
...: for op in COMPARISON_OPS:
...: func = getattr(operator, op)
...: assert func(float2, num_1) == func(frac2, num_1)
...: assert func(float1, float2) == func(frac1, frac2)
...:
...: div, mod = divmod(frac2, num_1)
...: assert math.isclose(
...: num_1 * div + mod.numerator / mod.denominator, float2
...: )
...: div, mod = divmod(frac1, frac2)
...: assert math.isclose(
...: float2 * div + mod.numerator / mod.denominator, float1
...: )
But it is ridiculously slow:
In [191]: a, b, c, d = 1, 2, 3, 5
In [192]: %timeit a * d + b * c, b * d
99 ns ± 1.02 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
In [193]: %timeit Fraction(1, 2) + Fraction(3, 5)
2.31 μs ± 98 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
How can I optimize this class?