Мобильная версияИ зачем мне много цифр? Вот почему я хочу вычислять трансцендентные математические константы с произвольной точностью. Сначала я реализую свой алгоритм на Python, потому что создаю прототип, а в конечном итоге я реализую алгоритм на C++, используя уже реализованное целое число произвольной точности в C++20.
В любом случае я обнаружил, что сложение нескольких дробей вместе с помощью Fractions.Fraction сделает код медленным из-за накладных расходов на объекты Python и сокращения дробей, использование math.gcd сделает код медленным, поскольку нам нужно сделать один дополнительный НОД и два дополнительных деления этажей. каждое сокращение, которое является медленным, использование math.lcm сделает код медленным, поскольку он вызывает GCD под капотом, использование функций Python сделает код медленным из-за накладных расходов на вызов функций Python, использование условий сделает код медленным из-за неправильного прогнозирования ветвей, а использование многопроцессорной обработки сделает код медленным из-за всех накладных расходов.
Самый быстрый способ сложения дробей — использовать a/b + c/d = (a * d + b * c)/(b * г) просто разделите числитель и знаменатель и никогда не делайте деления.
А чтобы сложить кучу дробей, мы можем складывать их линейно одну за другой. Или мы можем попытаться действовать умно: если у нас есть n дробей, у нас есть n//2 пар дробей, и каждую пару можно складывать независимо, и у нас остается одна оставшаяся дробь, которая непарна, если n нечетно. После этого у нас есть n//2 дробей и n//4 пар с потенциальной остаточной дробью. Мы можем просто добавить остатки обратно в список и использовать выходные данные первой итерации в качестве входных данных второй итерации, а выходные данные второй — в качестве входных данных третьей и так далее. Каждая итерация уменьшает количество дробей вдвое, пока в конечном итоге не останется только одна дробь, представляющая собой сумму всех дробей в списке.
И я обнаружил кое-что, что не могу объяснить:
Код: Выделить всё
from itertools import batched
from math import gcd
def arctan_derivative(x: int, y: int) -> tuple[int, int]:
return y * y, x * x + y * y
def primitive_rationals_simple(denominator: int) -> list[tuple[int, int]]:
assert isinstance(denominator, int) and denominator > 0
result = []
for numerator in range(denominator + 1):
common = gcd(numerator, denominator)
result.append((numerator // common, denominator // common))
return result
def make_test_case(n: int) -> list[tuple[int, int]]:
return [arctan_derivative(*frac) for frac in primitive_rationals_simple(n)]
def test1(fracs: list[tuple[int, int]]) -> tuple[int, int]:
num, den = 0, 1
for tnum, tden in fracs:
num, den = num * tden + tnum * den, den * tden
return num, den
def test2(fracs: list[tuple[int, int]]) -> tuple[int, int]:
while (length := len(fracs)) > 1:
carry = fracs.pop(-1) if length & 1 else None
fracs = [(a * d + b * c, b * d) for (a, b), (c, d) in batched(fracs, 2)]
if carry:
fracs.append(carry)
return fracs[0]
Код: Выделить всё
In [83]: data = make_test_case(360)
In [84]: test1(data) == test2(data)
Out[84]: True
In [85]: %timeit test1(data)
271 μs ± 9.95 μs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
In [86]: %timeit test2(data)
166 μs ± 948 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
In [87]: (271 - 166)/271
Out[87]: 0.3874538745387454
Но один значительно быстрее другого.
Я просто пытаюсь понять, почему второй метод здесь быстрее. Все эти описания — это всего лишь контекст, они объясняют, почему я использую дроби и почему я использую перекрестное умножение. Я не знаю, почему метод, который я разработал, может быть быстрее, чем грубая сила.
Подробнее здесь: https://stackoverflow.com/questions/798 ... n-the-same
