Вычисление многих остатков с остатками деревьев

Question

Я ищу быстрый способ вычисления n mod x1, n mod x2, n mod x3, ... Я нашел статью о " остаточных деревьях ", которая утверждает, что делает именно это .

Однако я не вижу, как вышеприведенный подход лучше, чем наивное вычисление каждого mod в отдельности (кажется, что именно последний шаг из вышеприведенного remaindersusingproducttree делает именно это). Я также тривиально протестировал приведенный выше код, и он, похоже, не работает быстрее.

Мой вопрос, я думаю, что "деревья остатков" как-то работают лучше, чем наивный подход, но я не понимаю как. Пожалуйста, кто-нибудь может пролить свет на это?

В качестве альтернативы, есть ли другой способ быстрого вычисления множества операций mod?

Answer 1

Ускорение этого алгоритма предполагает, что log(n) >> log(x[i]).Временная сложность деления двух чисел составляет O(b^2), где b - количество битов в дивиденде.Начальное деление (n mod x[0]x[1]) довольно дорого, если n очень большое, но следующие два деления выполняются на сравнительно небольшом остатке от первого деления.Таким образом, чтобы получить два остатка в базовом случае, алгоритм заменяет два очень дорогих деления на одно очень дорогое деление и два очень дешевых деления.