Проблемы вычисления GCD с библиотекой GNU MP

У меня есть вопрос о GNU MP, не могли бы вы помочь мне, как это сделать. Я использовал "Арифметическую библиотеку GNU Multiple Precision" Edition 5.1.1 для Windows. (MinGW\gcc + MSYS)

Существует функция mpz_gcd для вычисления "gcd" из двух целых чисел.

void mpz_gcd (mpz_t rop, mpz_t op1, mpz_t op2);

Насколько я понимаю из документации, в GNU MP реализовано несколько алгоритмов для вычисления Greatest Common Divisor. Среди них:

  • Двоичный GCD
  • Алгоритм Лемера
  • Субквадратичный GCD

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

В настоящее время бинарный алгоритм используется для GCD только тогда, когда N < 3.

Для входных данных, больших GCD_DC_THRESHOLD, GCD вычисляется с помощью функции HGCD (Half GCD) в качестве обобщения алгоритма Лемера.

Итак, я думаю, что есть как минимум три разных подхода для получения gcd (a, b). Основная проблема для меня: я хочу уточнить, какой алгоритм использовать сам. Я бы сравнил время выполнения этих алгоритмов на случайном большом входном сигнале (то есть 10^5 бит), чтобы выяснить некоторые общие тенденции: что это за точка, где использование "двоичного GCD" становится хуже, чем "метод Лемера", это "HGCD-Lehmer" обобщение "действительно лучше, чем прямой Лемер и т. д.

Есть ли простой способ указать алгоритм, который вы хотите использовать? Любой способ извлечь этот алгоритм из библиотеки, любой способ изменить некоторые переменные "#define". Можно ли сделать что-то, как я хочу, без перекомпиляции библиотеки? Я просто новичок там, и я не чувствую, что могу понять все виды вещей в библиотеке.

PS Наверное, кому-то будет интересно, что из этого получится. У меня есть код на GitHub: https://github.com/int000h/gcd_gcc

Источник

1 ответ

Решение

Это хорошее время для чтения исходного кода. GMP с открытым исходным кодом - воспользуйтесь этим!

В mpn/generic/gcd.c вы найдете функцию, которая выбирает алгоритм GCD (на самом деле это публичная функция, она указана в документации):

mp_size_t
mpn_gcd (mp_ptr gp, mp_ptr up, mp_size_t usize, mp_ptr vp, mp_size_t n)
{
    ...
    if (ABOVE_THRESHOLD (n, GCD_DC_THRESHOLD)) {
        ...

Вы можете видеть, что есть три основных ветви функции, каждая из которых заканчивается return заявление. Каждая ветвь соответствует разному алгоритму GCD. Вы можете скопировать и вставить код в свое собственное приложение и изменить его, чтобы вы могли точно указать, какой алгоритм вы хотите. Подсказки:

  • Вы можете избавиться от #ifdefs, Предполагать TUNE_GCD_P не определено.

  • Это mpn_* функция вместо mpz_* функция. Это более низкий уровень: например, вы должны явно выделить место для выходных данных. Вы также можете скопировать код из функции более высокого уровня, mpz_gcd(),

  • Вам нужно будет извлечь прототипы для внутренних функций, таких как mpn_hgcd_matrix_adjust(), Просто скопируйте прототипы из исходного кода GMP. Не волнуйтесь, кажется, что внутренние функции экспортируются из общей библиотеки (как правило, они не должны быть, но они есть, так что все в порядке).

Не нужно перекомпилировать библиотеку, но вам нужно будет немного поработать здесь.

Источник
Другие вопросы по тегам