Чудновское двоичное расщепление и факторинг

Ответ 1

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

Чтобы ответить на некоторые вопросы из вашего вопроса, сначала посмотрите на этот фрагмент кода:

typedef struct {
  unsigned long max_facs;
  unsigned long num_facs;
  unsigned long *fac;
  unsigned long *pow;
} fac_t[1];

Он определяет новый тип как структуру (если вы вообще не знаете C, допустим, что он похож на рудиментарный объект ввода объектов Pyhton, но без методов). Этот тип позволяет обрабатывать целые числа как два целых значения и два массива (скажем: два списка):

• наибольший фактор
• количество факторов
• список факторов
• список (соответствующих) полномочий для этих факторов

В то же время код сохраняет те же числа, что и большие целые числа из типа libgmp (это то, что подразумевается под mpz_t p и mpz_t g в аргументах функции).

Теперь, как насчет функции, которую вы показываете. Он называется fac_remove_gcd; начальная fac связана с именем ранее описанного типа; два следующих слова легко понять: разделите два целых числа типа fac на их gcd.

Код C выполняет итерацию по двум спискам факторов в обоих списках; легко синхронизировать оба списка, поскольку факторы упорядочены (раздел кода вокруг операторов else if и else); когда обнаруживаются два общих фактора (начальный оператор if), деление является вопросом простой подстановки: наименьшая мощность вычитается в обоих списках степеней для этого фактора (например, при a = 2 * 5 ^ 3 * 17 и b = 3 * 5 ^ 5 * 19, значение 3 будет вычитано в списках степеней для a и b в позиции, соответствующей фактору 5, приводящему к a = 2 * 5 ^ 0 * 17 и b = 3 * 5 ^ 2 * 19).

Во время этой операции создается номер (того же типа fac) и называется fmul; это, очевидно, gcd обоих чисел.

После этого шага gcd, называемый fmul, и тип fac преобразуется в большое целое число GMP с функцией (также в коде программы), называемой bs_mul. Это позволяет вычислить GCD как большое целое, чтобы синхронизировать новые значения разделенных чисел в обеих формах: большие целые числа и специальный тип fac. Когда GCD вычисляется как большое целое число, легко делить оба начальных числа на GCD.

Таким образом, функции действуют на две версии каждого начального числа.

Надеюсь, это поможет.

Ответ 2

Ключевыми являются следующие комментарии:

/*
    g(b-1,b) = (6b-5)(2b-1)(6b-1)
    p(b-1,b) = b^3 * C^3 / 24
    q(b-1,b) = (-1)^b*g(b-1,b)*(A+Bb).
*/

/*
    p(a,b) = p(a,m) * p(m,b)
    g(a,b) = g(a,m) * g(m,b)
    q(a,b) = q(a,m) * p(m,b) + q(m,b) * g(a,m)
*/

/*
          p*(C/D)*sqrt(C)
    pi = -----------------
             (q+A*p)
*/

Заметим:

• Если мы масштабируем как p, так и q в k в конечном делении, это не влияет на результат.
• При вычислении операции слияния, которая соответствует второму набору комментариев, если бы мы масштабировали каждый из p(a,m), g(a,m) и q(a,m) на k, то этот коэффициент просто переносится на p(a,b), g(a,b), q(a,b); аналогично, если бы мы масштабировали каждый из p(m,b), g(m,b) и q(m,b), то этот коэффициент несли бы.

• Линия

  fac_remove_gcd(p2, fp2, g1, fg1);
  

  эффективно

  k = gcd(p2, g1);
  p2 /= k; // p(m,b) /= k
  g1 /= k; // g(a,m) /= k
  

  Это имеет чистый эффект уменьшения масштаба p(a,b), g(a,b) и q(a,b) тем, что gcd. По предыдущим двум наблюдениям это масштабирование полностью переносится до конечного результата.

Postscript

Я пробовал три способа реализации факторинга в Python.

• Отслеживание факторизаций с использованием неизменяемых списков замедляет ситуацию ужасно, потому что слишком много занятой работы, поддерживающей списки.
• Использование gmpy gcd не дает ускорения
• Предварительный подсчет списка простых чисел до 6 * N (т.е. который может делить g), и тестирование каждого из этих простых чисел замедляет работу в 2 - 3 раза.

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