Домашнее задание: как написать собственное умножение больших чисел?

Question

В моем проекте я имею дело с умножением больших чисел (больше, чем java.long) в моем собственном классе BigNumber на int[]. В основном мне нужно реализовать что-то вроде этого:

    157 x
    121 y
   ----
    157 result1
   314  + result2
  157   + result3
 ------
 18997  finalResult

Но как мне это реализовать?

Я думал о расширении результата 2,3 с нулями (3140, 15700) и их добавлении. Но сначала мне нужно как-то перемещаться между каждой цифрой y и умножать ее на каждую цифру x.

Answer 1

Вам нужно будет рассматривать каждое целое в массиве как одну «цифру». Вместо использования базы 10, где каждая цифра идет от 0 до 9, вам придется использовать базу 2 ^ 32 = 4294967296, где каждая цифра идет от 0 до 4294967295.

Сначала я бы реализовал сложение, поскольку ваш алгоритм умножения может использовать сложение в качестве вспомогательного.