GCD алгоритмы для арифметики произвольной точности

Question

Я полностью застрял в этом вопросе, поэтому я ищу любую помощь.

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

Мне нужно реализовать этот метод (на языке C) для чисел с множественной точностью (более 10^5 бит). Доступно несколько библиотек GNU (GNU MP, MPFR, MPIR), и они имеют средства для определения чисел с множественной точностью и выполнения действий над ними. Это выглядит как одно число с множественной точностью, хранящееся в памяти как пара частей с одинарной точностью, называемых "конечностями".

Есть несколько методов, реализованных для поиска gcd(a, b), но их, на самом деле, сложно использовать для моих нужд. Бинарный метод для вычисления GCD используется только тогда, когда a и b содержат ровно две конечности. Метод HGCD, используемый, когда min(a, b) содержит более (т.е. 630) конечностей и т. Д. Мне трудно понять, как любой из этих методов может быть расширен для использования с любой длиной a и b. Я также обнаружил, что разные версии библиотек GNU содержат разные версии и методы алгоритмов GCD.

Вопрос: Я хочу выяснить, возможно ли заставить двоичный алгоритм GCD работать с целыми числами с множественной точностью любой длины в терминах "конечностей", и, если это возможно, - получить какую-либо помощь или идеи, как реализовать его в C. У кого-нибудь есть идеи или части кода, как это реализовать?

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

Вот часть двоичного метода GCD GNU MP для (a = b = 2 конечностей), если кто-нибудь взглянет:

/* Use binary algorithm to compute G <-- GCD (U, V) for usize, vsize == 2.
   Both U and V must be odd. */
static inline mp_size_t
gcd_2 (mp_ptr gp, mp_srcptr up, mp_srcptr vp)
{
  printf("gcd_2 invoked\n");
  mp_limb_t u0, u1, v0, v1;
  mp_size_t gn;

  u0 = up[0];
  u1 = up[1];
  v0 = vp[0];
  v1 = vp[1];

  ASSERT (u0 & 1);
  ASSERT (v0 & 1);

  /* Check for u0 != v0 needed to ensure that argument to
   * count_trailing_zeros is non-zero. */
  while (u1 != v1 && u0 != v0)
    {
      unsigned long int r;
      if (u1 > v1)
  {
    sub_ddmmss (u1, u0, u1, u0, v1, v0);
    count_trailing_zeros (r, u0);
    u0 = ((u1 << (GMP_NUMB_BITS - r)) & GMP_NUMB_MASK) | (u0 >> r);
    u1 >>= r;
  }
      else  /* u1 < v1.  */
  {
    sub_ddmmss (v1, v0, v1, v0, u1, u0);
    count_trailing_zeros (r, v0);
    v0 = ((v1 << (GMP_NUMB_BITS - r)) & GMP_NUMB_MASK) | (v0 >> r);
    v1 >>= r;
  }
    }

  gp[0] = u0, gp[1] = u1, gn = 1 + (u1 != 0);

  /* If U == V == GCD, done.  Otherwise, compute GCD (V, |U - V|).  */
  if (u1 == v1 && u0 == v0)
    return gn;

  v0 = (u0 == v0) ? ((u1 > v1) ? u1-v1 : v1-u1) : ((u0 > v0) ? u0-v0 : v0-u0);
  gp[0] = mpn_gcd_1 (gp, gn, v0);

  return 1;
}

CodePaste из вышеперечисленного.

Answer 1

Просто накатайте свой код специально для этой проблемы, почему бы и нет? (10^9)^2 подходит для 64-битного int, так что вы можете работать с базовым (10^9) цифры, каждая из которых содержится в 64-битном int. Представлять 2^(10^5) -битные значения, 2^(10^5) ~= 10^30103, т.е. значения с ~ 30103 десятичных цифр, вам понадобится только 30103/9 ~= 3350 int, который представляет собой массив размером ~ 27 кБ в памяти для каждого из двух задействованных чисел.

Согласно WP, для двоичного алгоритма GCD вам нужно только minus а также /2 что тривиально реализовать путем деления пополам каждой цифры, со случайным переносом 5*10^8 в нижнюю цифру (94 / 2 = 47 = {4,5+2}), Окончательное умножение на 2 ^k можно сделать с помощью наивного алгоритма, поскольку это нужно сделать только один раз.

Печать в базе 10 будет тривиально. Если вам не нужна печать конечного результата, вам не понадобится окончательное умножение (или если вы сообщите свой результат как 2^k*x) и тогда вы могли бы работать с 10^18 цифры, вдвое уменьшая количество цифр для работы.

Вам понадобится только обычная целочисленная арифметика C для работы с цифрами.