Самый быстрый алгоритм для нахождения множителей 2 и 5

После разговора я действительно думаю, что ваша идея — самый быстрый путь, за одним исключением:

Дивизия (в большинстве случаев) стоит дорого. С другой стороны, проверка последней цифры числа (обычно?) выполняется быстрее, поэтому перед делением я бы проверил последнюю цифру (0/5 и 0/2/4/6/8).

Я основываю это на этом комментарии ОП:

моя библиотека написана на PHP, и число на самом деле хранится в виде строки с основанием 10. Это действительно не самый эффективный способ, но это то, что лучше всего работает в рамках технических ограничений языка.

Если вы привержены strings-in-php, то следующий псевдокод ускорит работу по сравнению с фактическим повторяющимся модулем и делением общего назначения:

while the string ends in 0, but is not 0
  chop a zero off the end,
  increment ctr2 and ctr5
switch repeatedly depending on the last digit:
  if it is a 5,
     divide it by 5
     increment ctr5
  if it is 2, 4, 6, 8,
     divide it by 2
     increment ctr2
  otherwise
     you have finished

Это не требует никаких операций с модулем, и вы можете реализовать деление на 5 и деление на 2 дешевле, чем деление длинных чисел общего назначения.

С другой стороны, если вам нужна производительность, использование строковых представлений для целых чисел неограниченного размера равносильно самоубийству. Используйте gmp (с библиотекой php) для вашу математику и конвертировать в строки только при необходимости.

изменить:

вы можете повысить эффективность (и упростить свои операции), используя следующий псевдокод:

if the string is zero, terminate early
while the last non-zero character of the string is a '5',
   add the string to itself
   decrement ctr2
count the '0's at the end of the string into a ctr0
chop off ctr0 zeros from the string
ctr2 += ctr0
ctr5 += ctr0
while the last digit is 2, 4, 6, 8
   divide the string by 2
   increment ctr2

Вырезать сразу много нулей лучше, чем зацикливаться. А mul2 выигрывает у div5 по скорости (это можно реализовать, добавив число один раз).

Я думаю, что ваш алгоритм будет самым быстрым. Но у меня есть пара предложений.

Одна альтернатива основана на наибольшем общем делителе. Возьмите gcd вашего входного числа с наименьшей степенью 2 больше, чем ваше входное число; это даст вам все множители 2. Разделите на gcd, затем повторите ту же операцию с 5; это даст вам все множители числа 5. Разделите снова на НОД, и остаток скажет вам, есть ли какие-либо другие множители.

Другая альтернатива основана на бинарном поиске. Разделите двоичное представление вашего входного числа пополам; если правая половина равна 0, двигайтесь влево, иначе двигайтесь вправо. Получив множители 2, разделите, а затем примените тот же алгоритм к остатку, используя степени 5.

Я оставлю вам реализовать и рассчитать время этих алгоритмов. Но мое внутреннее чувство состоит в том, что повторное деление будет трудно превзойти.

Я только что прочитал ваш комментарий о том, что ваш входной номер хранится в базе 10. В этом случае многократно делите на 10, пока остаток равен 0; это дает коэффициенты как 2, так и 5. Затем примените свой алгоритм к уменьшенному числу.

Если у вас есть миллиардное число, вы не хотите делать на нем деления, если это действительно необходимо. Если у вас нет оснований полагать, что это 1/2 ^ 1000 чисел, делящихся на 2 ^ 1000, то имеет смысл использовать гораздо более быстрые тесты, которые рассматривают только последние несколько цифр. Вы можете определить, делится ли число на 2, взглянув на последнюю цифру, делится ли оно на 4, взглянув на последние 2 цифры, и на 2^n, взглянув на последние n цифр. Точно так же вы можете определить, делится ли число на 5, взглянув на последнюю цифру, делится ли оно на 25, взглянув на последние 2 цифры, и на 5^n, взглянув на последние n цифр.

Я предлагаю вам сначала подсчитать и удалить конечные 0, а затем решить по последней цифре, проверяете ли вы степени двойки (последняя цифра 2, 4, 6 или 8) или степени 5 (последняя цифра 5).

Если вы проверяете степень двойки, возьмите последние 2, 4, 8, 16,... 2^i цифры и умножьте их на 25, 625,... 5^2^i, считая конечные 0 до 2^i (но не более). Если вы получаете меньше 2 ^ i завершающих нулей, остановитесь.

Если вы проверяете степень числа 5, возьмите последние 2, 4, 8, 16,... 2^i цифры и умножьте их на 4, 16,... 2^2^i, считая конечные 0 до 2^i (но не более). Если вы получаете меньше 2 ^ i завершающих нулей, остановитесь.

Например, предположим, что число, которое вы анализируете, равно 283 795 456. Умножьте 56 на 25, вы получите 1400 с 2 конечными нулями, продолжайте. Умножьте 5 456 на 625, вы получите 3 410 000 с 4 нулями в конце, продолжайте. Умножьте 83 795 456 на 5 ^ 8 = 390 625, вы получите 32 732 600 000 000, в котором 8 завершающих нулей, продолжайте. Умножьте 283 795 456 на 5 ^ 16, чтобы получить 43 303 750 000 000 000 000, в котором всего 13 завершающих нулей. Это меньше 16, так что стоп, степень двойки в простой факторизации равна 2^13.

Я надеюсь, что для больших умножений вы реализуете алгоритм n log n для умножения n-значных чисел, но даже если это не так, этот метод должен превзойти все, что связано с делением типичных больших чисел.

Давайте посмотрим на среднюю временную сложность различных алгоритмов, предполагая, что каждое n-значное число равновероятно.

Сложение или вычитание двух n-значных чисел занимает тета(n) шагов.

Деление n-значного числа на небольшое число, например 5, требует тета(n) шагов. Деление по основанию равно O(1).

Деление n-значного числа на другое большое число требует шагов тета (n log n) с использованием БПФ или тета (n ^ 2) с помощью наивного алгоритма. То же верно и для умножения.

Алгоритм многократного деления числа с основанием 10 на 2 имеет среднюю временную сложность тета(n): для первого деления требуется тета(n) время, и в среднем вам нужно сделать только O(1) делений.

Вычисление большой степени 2 по крайней мере с n цифрами требует тета (n log n) путем повторного возведения в квадрат или тета (n ^ 2) с помощью простого умножения. Выполнение алгоритма Евклида для вычисления НОД занимает в среднем тета(n) шагов. Хотя деление занимает тета(n log n) время, большинство шагов можно выполнить как повторяющиеся вычитания, и для их выполнения требуется только тета(n) время. Для выполнения алгоритма Евклида таким образом требуется O(n^2 log log n). Другие улучшения могут снизить это значение до тета(n^2).

Проверка последней цифры на делимость на 2 или 5 перед выполнением более дорогостоящих расчетов — это хорошо, но это приводит только к постоянному улучшению коэффициента. Применение исходного алгоритма после этого по-прежнему требует в среднем тета(n) шагов.

Проверка последних d цифр на делимость на 2 ^ d или 5 ^ d занимает время O (d ^ 2), O (d log d) с помощью БПФ. Очень вероятно, что нам нужно сделать это только тогда, когда d мало. Доля n-значных чисел, делящихся на 2^d, равна 1/2^d. Таким образом, среднее время, затрачиваемое на эти проверки, равно O(sum(d^2 / 2^d)) и эта сумма ограничена и не зависит от n, поэтому в среднем требуется тета(1) время. Когда вы используете последние цифры для проверки на делимость, вам обычно не нужно выполнять какие-либо операции над цифрами, близкими к n.