Умножение методом Карацубы на FASM

Умножение методом Карацубы на FASM

1. Цель

Написать реализацию алгоритма Карацубы по быстрому умножению n-битовых чисел для десятичных чисел, чья длина не превосходит 30 символов.

Описание алгоритма в псевдокоде:

Процедура Karatsuba(x, y)

{

ВХОД: положительные целые х, у

ВЫХОД: ху

n = max(размер х, размер у)

если n ≤ 3 — вернуть ху

P1_x, P2_x — левые ⌈ n/2⌉, правые ⌊ n/2⌋ разрядов числа х

P1_y, P2_y — левые ⌈ n/2⌉, правые ⌊ n/2⌋ разрядов числа y

P3_x = P1_x + P2_x

P3_y = P1_y + P2_y

P1 = Karatsuba(P1_x, P1_y)

P2 = Karatsuba(P2_x, P2_y)

P3 = Karatsuba(P3_x, P3_y)

Вернуть P1 * 10^{2⌊ n/2⌋} + P2 + (P3 — P2 — P1) * 10^{⌊ n/2⌋}

}

2. Используемые обозначения

Число-строка — десятичное число, хранимое в памяти как строка.

Сегментированный буфер — буфер, логически разделённый на ячейки одинакового размера.

3. Общее описание работы программы

Считывание строки в формате «< число_1> * < число_2> » из консоли.
Обработка входной строки: вычленение < число_1> и < число_2>
Вызов метода Karatsuba для произведения умножения < число_1> на < число_2>
Вывод полученного произведения на консоль

4. Используемые методы

input — чтение из строки
get_length_number — вычисление длины полученного числа в буфере
output — вывод результата на консоль
add_simple — сложение двух однострочных число-строк, с учётом переноса. Вспомогательный метод.
clean_buffer — принимает на вход указатель на буфер, который лежит в rax. Обнуляет первые 64 байта этого буфера.
add_string — сложение двух чисел из буфера
substract_simple - вычитание двух однострочных число строк, с учётом переноса. Вспомогательный метод.
building_ten_degree — строит число-строку, являющуюся степенью десятки по заданной степени.
buffer_equalizer — в результате вычитания число-строка может получиться по длине меньше, чем какая-либо из изначальных. Метод выравнивает число-строку слева.
subtract_string — вычитание из одного числа другого
cut_left — получение «левых разрядов» числа
cut_right — получение «правых разрядов» числа
multiply_string - «умножение» на степень десятки (сдвиг числа)
decide_pointer — высчитывает текущий указатель на буфер на данной итерации рекурсивного вызова.
parse_input — вытаскивает число-строки из введённых данных
to_string_converter — преобразует числа в число-строки. Вспомогательный метод.
to_number_converter — преобразует число-строки в числа. Вспомогательный метод.
multiply_numbers — переводит в числа число-строки и перемножает их.
Karatsuba — герой, что спасёт нас всех.

12 3 4 5 6 7 Следующая ⇒