Разделяй и властвуй подход для алгоритма Карацубы - PullRequest
Новая
       29

Разделяй и властвуй подход для алгоритма Карацубы

0 голосов
/ 09 ноября 2018

Я пытаюсь написать алгоритм Карацубы, используя подход «разделяй и властвуй» в Haskell.Я сделал это с помощью алгоритма сортировки слиянием, но не могу понять это здесь, и это немного смущает.

Моя основная функция выглядит так: 

dz test end divide combine x = 
   if test x then end x
   else combine(map(dz test end divide combine) (divide x))

Я проверяю этодля значений 1234 и 5678: dz test end divide combine [1234, 5678,2].

Поэтому мне нужно написать test, end, divide и combine функции. 

lengthNumb x = length . show $ x
test (x:x1:xs) = (lengthNumb x) < 4 || (lengthNumb x1) < 4
end (x:y:z:xs) = [x * y, z]

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

divide [] = []
divide (x:x1:x2:xs) = 
   let y1 = x `div` 10^x2
     y2 = x `mod` 10^x2
     y3 = x2 `div` 2
     z1 = x1 `div` 10^x2
     z2 = x1 `mod` 10^x2
   in [[y1,y2,y3],[z1,z2,y3],[y1+y2, z1+z2, y3]]

combine [[x, x1],[y,y1],[z,z1]] = x * 10^(2*x1) + y + (z - x - y) * 10^x1

Мне сказали, что функция combine должна выполнять только окончательное умножение.Поэтому я думаю, что он должен получить три числа в качестве входных данных (каждое со своим значением m), а затем также выполнить необходимое вычитание (z-x-y), потому что я не смог сделать это в divide.

Но это неправильно.Я получаю сообщение об ошибке: 

Occurs check: cannot construct the infinite type: a ~ [a]
  Expected type: [[a]] -> [a]

  Actual type: [[[a]]] -> [a]

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

...