Наивный рекурсивный алгоритм полиномиального умножения в Python - PullRequest
Новая
       39

Наивный рекурсивный алгоритм полиномиального умножения в Python

0 голосов
/ 16 сентября 2018

Я пытаюсь реализовать алгоритм «разделяй и властвуй» для умножения полиномов .Вот псевдокод, указанный в примечаниях к лекции: enter image description here

, где A, B - списки коэффициентов каждого полинома, n - размер задачи (степень - 1), а a_l, b_l -индексы коэффициентов интереса.

Вот моя попытка реализовать его с помощью Python3: 

def poly_mult_dc_naive(A, B, n, a, b):
  n = int(n)
  a = int(a)
  b = int(b)
  C = [None] * int(2*n - 1)

  if n == 1:
    C[0] = A[a] * B[b]
    return C[0]

  C[0:n-1] = poly_mult_dc_naive(A, B, n//2, a, b)
  C[n:2*n-1] = poly_mult_dc_naive(A, B, n//2, a + (n // 2), b + (n // 2))

  W = poly_mult_dc_naive(A, B, n/2, a, b + (n // 2))
  V = poly_mult_dc_naive(A, B, n/2, a + n/2, b)
  C[n // 2:n + (n // 2) - 1] += W + V
  return C

Однако я получаю странные результаты.Например, пусть A = [1,2,3,4] B = [4,3,2,1] Я получу:

[4, None, 8, 3, 6, 12, None, 16, 9, 12, 2, None, 4, 1, 2, None, 8, 3, 4, None, None]

Правильный ответ [4, 11, 20, 30, 20, 11, 4]

Может кто-нибудь указать, где я ошибся и как этоможно сделать?

Ответы [ 2 ]

0 голосов
/ 16 сентября 2018
  • Не нужно приводить n,a,b от float к int. Просто используйте // 2 целочисленное деление везде (т. Е. В строках W, V). Это будет "хранить" целые числа как целые.
  • Строка C[n // 2:n + (n // 2) - 1] крайне нуждается в скобках, очень легко неправильно читается. Я бы написал C[(n//2) : (3*n//2)-1]
  • Но я настоятельно рекомендую вам использовать простые векторы, а не списки Python. Добавление, умножение и т. Д. Векторизовано.
0 голосов
/ 16 сентября 2018

Быстрое обновление: я думаю, что мне удалось отладить мой код, используя пустой массив для C вместо списка. Вот обновленная версия: 

import numpy as np

def poly_mult_dc_naive(A, B, n: int, a: int, b: int):
  C = np.zeros(2*n - 1, dtype=int) # here I changed it from list to np array
  if n == 1:
    C[0] = A[a] * B[b]
    return C[0]
  C[0:n-1] = poly_mult_dc_naive(A, B, n//2, a, b)
  C[n:2*n-1] = poly_mult_dc_naive(A, B, n//2, a + (n // 2), b + (n // 2))
  W = poly_mult_dc_naive(A, B, n//2, a, b + (n // 2))
  V = poly_mult_dc_naive(A, B, n/2, a + (n//2), b)
  C[(n // 2) : (3*n // 2) - 1] += W + V
  return C

БОНУСНЫЙ ВОПРОС: Кто-нибудь знает, как лучше я могу сохранить аргументы n, a и b в виде типов int?

Мне просто нужно написать: 

n = int(n)
a = int(a)
b = int(b)

может быть не самый элегантный способ.

...