Умножение Биг-Интов в схеме-ракетке

Question

Я реализовал в схеме «big-int» в виде списка, поэтому первый элемент - это знак числа (+ или -), а следующие - это значение самого числа, сначала те, затемдесятки и т. д.

Например: (+ 0 0 1) для 100, (- 9 2 3 1) для -1329 и т. д.

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

Answer 1

Разбейте проблему на более мелкие части.Сначала напишите функцию, которая умножает Big-int на одну цифру.Затем расширите это (используя подсказку Грега Хьюгилла, что вы, вероятно, знаете, как это сделать на бумаге) до функции, которая умножает Big-int на список цифр.Наконец, оберните это в функцию, которая принимает два Big-ints, удаляет знак и затем вызывает вашу предыдущую функцию.

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

Answer 2

здесь хорошо известен подход «разделяй и властвуй» для умножения больших чисел:

http://ozark.hendrix.edu/~burch/csbsju/cs/160/notes/31/1.html

Этот подход разбивает два числа на две части и рекурсивно обрабатывает их.Это очень быстро, и его легко реализовать, несмотря на то, что это может показаться длинным объяснением.Я очень рекомендую это.Требуется всего около 10 строк кода на других языках, возможно, меньше в схеме:).