Главная

Контакты

Случайная статья

• Автоматизация
• Антропология
• Археология
• Архитектура
• Биология
• Ботаника
• Бухгалтерия
• Военная наука
• Генетика
• География
• Геология
• Демография
• Деревообработка
• Журналистика
• Зоология
• Изобретательство
• Информатика
• Искусство
• История
• Кинематография
• Компьютеризация
• Косметика
• Кулинария
• Культура
• Лексикология
• Лингвистика
• Литература
• Логика
• Маркетинг
• Математика
• Материаловедение
• Медицина
• Менеджмент
• Металлургия
• Метрология
• Механика
• Музыка
• Науковедение
• Образование
• Охрана Труда
• Педагогика
• Полиграфия
• Политология
• Право
• Предпринимательство
• Приборостроение
• Программирование
• Производство
• Промышленность
• Психология
• Радиосвязь
• Религия
• Риторика
• Социология
• Спорт
• Стандартизация
• Статистика
• Строительство
• Технологии
• Торговля
• Транспорт
• Фармакология
• Физика
• Физиология
• Философия
• Финансы
• Химия
• Хозяйство
• Черчение
• Экология
• Экономика
• Электроника
• Электротехника
• Энергетика

19. Karatsuba

На вход в rax и rbx получает указатели на сегменты, в которых находятся числа, которые необходимо перемножить.

На выходе ничего не возвращает, результаты работы складывает в сегментированный буфер P, по адресу, вычисляемому на основе текущей глубины рекурсии.

Описание работы:

В отдельные регистры сохраняются ссылки, после чего вычисляется длина пришедших на вход число-строк. Выясняется, какая длиннее и в зависимости от этого производится либо вычисление напрямую, либо методом Карацубы.

В случае с прямыми вычислениями, обе число-строки выгружаются в соответствующие регистры, и отправляются на умножение написаннойранее функции. После чего результат записывается в P[recursion_depth] и метод завершает работу.

При непрямых вычислениях, сначала вычисляется ⌊ n / 2⌋, потом на основании этого числа происходит разбивка входных число-строк на «левые» и «правые» части. Перед каждым подобным разбиением происходит очистка всех использующихся буферов. После разбиения происходит три последовательных рекурсивных вызова, в соответствии с псевдокодом. Далее считается разность в скобках, после чего происходит её «умножение» на степень десятки, которую мы посчитали ранее. После идёт рассчёт P1 + P2 с учётом всех сдвигов и умножений. На последнем шаге просиходит итоговое складывание или вычитание: в зависимости от результата разности в P3. После чего число-строка упаковывается в P[recursion_depth], метод завершает работу.

; | input

; rax = pointer on cell of segment-buffer, x

; rbx = pointer on cell of segment-buffer, y

; | output

; | P[recursion_depth]

Karatsuba:

push rcx

push rdx

push r8

push r9

push r10

push r11

push rsi

push rdi

mov r10, rax; r10 - x

mov r11, rbx; r11 - y

xor rbx, rbx

call get_length_number

mov r8, rax

mov rax, r11

call get_length_number

mov r9, rax

cmp r8, r9

jge. checking_for_simple

mov rax, r8

mov r8, r9

mov r9, r8

. checking_for_simple:

cmp r8, 3

jle. just_multiply

jmp. basic_method

. basic_method:

xor rdx, rdx

mov r9, 2

mov rax, r8

div r9

mov r8, rax; r8 - хранит нижнее неполное частное n / 2

add rax, rdx

mov r9, rax; r9 - хранит n/2

. create_vaues:

mov rax, P1_x

call decide_pointer

call clean_buffer

mov rbx, rax

mov rax, r10

mov rcx, r9

call cut_left

mov rax, P2_x

call decide_pointer

call clean_buffer

mov rbx, rax

mov rax, r10

mov rcx, r9

call cut_right

mov rax, P1_y

call decide_pointer

call clean_buffer

mov rbx, rax

mov rax, r11

mov rcx, r9

call cut_left

mov rax, P2_y

call decide_pointer

call clean_buffer

mov rbx, rax

mov rax, r11

mov rcx, r9

call cut_right

xor rbx, rbx

. create_P3:

mov rax, P3_x; clean

call decide_pointer

call clean_buffer

mov rax, first_number

call clean_buffer

mov rax, second_number

call clean_buffer

mov rax, computation_result

call clean_buffer

mov rax, P1_x; P1_x -> first_number

call decide_pointer

mov rsi, rax

call get_length_number

mov rcx, rax

mov rdi, first_number

rep movsb

mov rax, P2_x; P2_x -> second_number

call decide_pointer

mov rsi, rax

call get_length_number

mov rcx, rax

mov rdi, second_number

rep movsb

call add_string; -> computation_result

mov rsi, computation_result; computation_result -> P3_x

mov rax, computation_result

call get_length_number

mov rcx, rax

mov rax, P3_x

call decide_pointer

mov rdi, rax

rep movsb

mov rax, P3_y; clean

call decide_pointer

call clean_buffer

mov rax, first_number

call clean_buffer

mov rax, second_number

call clean_buffer

mov rax, computation_result

call clean_buffer

mov rax, P1_y; P1_y -> first_number

call decide_pointer

mov rsi, rax

call get_length_number

mov rcx, rax

mov rdi, first_number

rep movsb

mov rax, P2_y; P2_y -> second_number

call decide_pointer

mov rsi, rax

call get_length_number

mov rcx, rax

mov rdi, second_number

rep movsb

call add_string; -> computation_result

mov rsi, computation_result; computation_result -> P3_y

mov rax, computation_result

call get_length_number

mov rcx, rax

mov rax, P3_y

call decide_pointer

mov rdi, rax

rep movsb

. deciding:

. solve_P1:

mov rax, P1

call decide_pointer

call clean_buffer

mov rax, P1_y; new y

call decide_pointer

mov rbx, rax

mov rax, P1_x; new x

call decide_pointer

push rax

mov rsi, recursion_depth; change recursion_depth

lodsq

inc rax

mov rdi, recursion_depth

stosq

pop rax

call Karatsuba; OMG!!!

xor rbx, rbx

mov rax, P; Save result in P1[recursion_depth] (ATTENTION! rd > current rd)

call decide_pointer

mov rsi, rax

call get_length_number

mov rcx, rax

push rsi; change recursion_depth on current value

mov rsi, recursion_depth

lodsq

dec rax

mov rdi, recursion_depth

stosq

pop rsi

mov rax, P1; P1[recursion_depth] -> rdi

call decide_pointer

mov rdi, rax

rep movsb

. solve_P2:

mov rax, P2

call decide_pointer

call clean_buffer

mov rax, P2_y; new y

call decide_pointer

mov rbx, rax

mov rax, P2_x; new x

call decide_pointer

push rax

mov rsi, recursion_depth; change recursion_depth

lodsq

inc rax

mov rdi, recursion_depth

stosq

pop rax

call Karatsuba; OMG!!!

xor rbx, rbx

mov rax, P; Save result in P2[recursion_depth] (ATTENTION! rd > current rd)

call decide_pointer

mov rsi, rax

call get_length_number

mov rcx, rax

push rsi; change recursion_depth on current value

mov rsi, recursion_depth

lodsq

dec rax

mov rdi, recursion_depth

stosq

pop rsi

mov rax, P2; P2[recursion_depth] -> rdi

call decide_pointer

mov rdi, rax

rep movsb

. solve_P3:

mov rax, P3

call decide_pointer

call clean_buffer

mov rax, P3_y; new y

call decide_pointer

mov rbx, rax

mov rax, P3_x; new x

call decide_pointer

push rax

mov rsi, recursion_depth; change recursion_depth

lodsq

inc rax

mov rdi, recursion_depth

stosq

pop rax

call Karatsuba; OMG!!!

xor rbx, rbx

mov rax, P; Save result in P3[recursion_depth] (ATTENTION! rd > current rd)

call decide_pointer

mov rsi, rax

call get_length_number

mov rcx, rax

push rsi; change recursion_depth on current value

mov rsi, recursion_depth

lodsq

dec rax

mov rdi, recursion_depth

stosq

pop rsi

mov rax, P3; P3[recursion_depth] -> rdi

call decide_pointer

mov rdi, rax

rep movsb

. solve_result:

. solve_P3_with_shift:

mov rax, first_number; clean

call clean_buffer

mov rax, second_number

call clean_buffer

mov rax, computation_result

call clean_buffer

mov rax, P3; P3 -> first_number

call decide_pointer

mov rsi, rax

call get_length_number

mov rcx, rax

mov rdi, first_number

rep movsb

mov rax, P2; P2 -> second_number

call decide_pointer

mov rsi, rax

call get_length_number

mov rcx, rax

mov rdi, second_number

rep movsb

call substract_string; (P3 - P2) -> computation_result

mov rax, P3

call decide_pointer

call clean_buffer

mov rsi, computation_result; computation_result -> P3

mov rax, computation_result

call get_length_number

mov rcx, rax

mov rax, P3

call decide_pointer

mov rdi, rax

rep movsb

mov rax, first_number; clean

call clean_buffer

mov rax, second_number

call clean_buffer

mov rax, computation_result

call clean_buffer

mov rax, P3; P3 -> first_number

call decide_pointer

mov rsi, rax

call get_length_number

mov rcx, rax

mov rdi, first_number

rep movsb

mov rax, P1; P1 -> second_number

call decide_pointer

mov rsi, rax

call get_length_number

mov rcx, rax

mov rdi, second_number

rep movsb

cmp rdx, 1

je. adding

call substract_string; (P3 - P1) -> computation_result

jmp. next

. adding:

call add_string

. next:

mov rax, P3

call decide_pointer

call clean_buffer

mov rsi, computation_result; computation_result -> P3

mov rax, computation_result

call get_length_number

mov rcx, rax

mov rax, P3

call decide_pointer

mov rdi, rax

rep movsb

mov rbx, r9; P3 * 10^[n / 2]

mov rax, P3

call decide_pointer

call multiply_string

. solve_P1_with_shift:

mov rax, 2; 2 * [n / 2] -> rbx

mul r9

mov rbx, rax

mov rax, P1

call decide_pointer

call multiply_string; P1 * 10^(2*[n/2])

. solve_P1_P2_with_shift:

mov rax, first_number; clean

call clean_buffer

mov rax, second_number

call clean_buffer

mov rax, computation_result

call clean_buffer

xor rbx, rbx

mov rax, P1; P1 -> first_number

call decide_pointer

mov rsi, rax

call get_length_number

mov rcx, rax

mov rdi, first_number

rep movsb

mov rax, P2; P2 -> second_number

call decide_pointer

mov rsi, rax

call get_length_number

mov rcx, rax

mov rdi, second_number

rep movsb

call add_string; P1 + P2 -> computation_string

mov rax, P

call decide_pointer

call clean_buffer

mov rsi, computation_result; computation_result -> P

mov rax, computation_result

call get_length_number

mov rcx, rax

mov rax, P

call decide_pointer

mov rdi, rax

rep movsb

. solve:

mov rax, first_number; clean

call clean_buffer

mov rax, second_number

call clean_buffer

mov rax, computation_result

call clean_buffer

mov rax, P; P -> first_number

call decide_pointer

mov rsi, rax

call get_length_number

mov rcx, rax

mov rdi, first_number

rep movsb

mov rax, P3; P3 -> second_number

call decide_pointer

mov rsi, rax

call get_length_number

mov rcx, rax

mov rdi, second_number

rep movsb

cmp rdx, 1

je. substract_end

call add_string

jmp. get_result

. substract_end:

call substract_string

. get_result:

mov rax, P

call decide_pointer

call clean_buffer

mov rsi, computation_result; computation_result -> P

mov rax, computation_result

call get_length_number

mov rcx, rax

mov rax, P

call decide_pointer

mov rdi, rax

rep movsb

jmp. close

. just_multiply:

mov rsi, r10

xor rax, rax

lodsq

mov rbx, rax

mov rsi, r11

xor rax, rax

lodsq

call multiply_numbers

mov rbx, rax

mov rax, P

call decide_pointer

mov rdi, rax

mov rax, rbx

stosq

jmp. close

. close:

pop rdi

pop rsi

pop r11

pop r10

pop r9

pop r8

pop rdx

pop rcx

ret

7. Заключение

Если Вы дочитали до этого момента, значит, либо Вам стало скучно разбираться во всём этом счастье, либо вы познали дзен и у Вас получилось тоже написать эту небольшую программку по умножению тридцатизначных чисел на ассемблере. Спасибо, что читали эту статейку, желаю Вам удачи и счастья в личной жизни.