Вспомним опять же 3ий класс и умножение столбиком.
Возьмем два числа, например 123 и 456, запишем их друг под другом так, чтобы правые цифры оказались друг под другом, например так:
123
х
456
-----------
738
615
492
-----------
56088
1. Начинаем умножать самую младшую цифру второго числа на младшую цифру первого числа, получившуюся цифру записываем под младшей цифрой второго числа, если получилось 2х значное число, то старшую цифру запоминаем, она нам пригодиться. В моем примере получается 3 х 6 = 18, из которых я записываю 8 под крайней правой цифрой числа два, а 1 запоминаю.
1а. Следующим ходом умножаем младшую цифру второго числа на следующую цифру первого числа. К получившемуся ответу прибавляем запомненную цифру в первом вычислении. В моем примере получается следующее: 6 * 2 = 12 + 1 = 13, с лева от 8ки которую мы уже записали, пишем 3 и запоминаем 1.
1б. Также делаем дальше, как в предыдущих примерах, 6 * 1 = 6 + 1 = 7, тут переполнения нет, по этому запоминать нечего и просто дописываем 7 с лева от 38 и получаем в итоге 738.
И так пока не кончатся цифры в первом числе.
2. Далее нам необходимо умножить следующую цифру второго числа, по той же схеме как с крайней правой цифрой в пункте 1. Только записывать надо начать под той цифрой которую умножаем, то есть сместить разряд в лево.
3. С третим числом производим теже самые манипуляции как первом и втором пункте. Если чисел больше, то продолжаем по тому же принципу, сдвигая каждый раз число на 1 позицию в лево.
4. Складываем все получившиеся цифры после умножения столбиком, цифры с пустым местом складываются как с нулем, тоесть крайняя 8 так и остается 8. Не забываем переносить переполнения.
В итоге можно умножить практически любое число, но эта манипуляция отъедает огромное количество усилий, сначала умножить, потом прибавить, так что это ужасно медленная операция.
Даже по размеру кода это видно:
mult proc uses ecx edx ebx esi edi cif1:DWORD, cif2:DWORD, out_place:DWORD, lenght1:DWORD, lenght2:DWORD mov edi, out_place ; копируем в edi адрес ответа mov eax, lenght1 ; копируем в eax длину числа 1 cmp eax, lenght2 ; сравниваем длину 1 числа с длиной второго jng cif2_bolsh ; если цифра 2 длиннее то прыгаем на cif2_bolsh mov edx, cif1 ; копируем в edx цифру 1 mov ebx, cif2 ; копируем в ebx цифру 2 mov ecx, lenght1 ; копируем в ecx длинну цифры 1 jmp mult_start ; прыгаем на начало алгоритма умножения cif2_bolsh: mov edx, cif2 ; копируем в edx цифру 2 mov ebx, cif1 ; копируем в ebx цифру 1 mov ecx, lenght2 ; копируем в ecx длинну цифры 2 mult_start: push ecx ; кладем в стек ecx, где находиться длинна обрабатываемой цифры mult_next: dec lenght1 ; уменьшаем длинну цифры 1 dec lenght2 ; уменьшаем длинну цифры 2 mov al, BYTE PTR [edx] ; копируем в al младший байт большей цифры mul BYTE PTR [ebx] ; умножаем на младший байт, получаем в ah произведение mult_num_end_1: add BYTE PTR [edi], al ; прибавляем к ответу младший байт al push edi ; запоминаем в стеке текущую позиции в ответе chk_one_1: jae mult_norm_al ; проверяем, после сложения нет ли переполнения inc edi ; переполнение есть, по этому увеличиваем позицию ответа на 1 add BYTE PTR [edi], 1 ; добавляем еденицу jmp chk_one_1 ; прыгаем обратно на проверку переполнения, так как 0ffh + 1h = 00h mult_norm_al: pop edi ; востанавливаем позицию курсора из стека add BYTE PTR [edi+1], ah ; прибавляем к ответу старший байт ah push edi ; запоминаем в стеке текущую позиции в ответе chk_one_2: jae mult_norm_ah ; проверяем, после сложения нет ли переполнения inc edi ; переполнение есть, по этому увеличиваем позицию ответа на 1 add BYTE PTR [edi+1],1 ; добавляем еденицу jmp chk_one_2 ; прыгаем обратно на проверку переполнения, так как 0ffh + 1h = 00h mult_norm_ah: pop edi ; востанавливаем позицию курсора из стека xor esi, esi ; зануляем esi pop ecx ; достаем из стека количество циферок push ecx ; положим обратно в стек количество циферок, оно пригодится дальше or ecx,ecx ; проверим количество циферок равно 0 jz mult_end ; если да, то все уже посчитали, пора на выход next_sub_mult: inc esi ; увеличиваем esi mov al, BYTE PTR [edx+esi] ; копируем в al младший байт большей цифры mul BYTE PTR [ebx] ; умножаем на младший байт, получаем в ah произведение add BYTE PTR [edi+esi], al ; прибавляем к ответу старший байт al push edi ; запоминаем в стеке текущую позиции в ответе mult_norm_next_al_1: jae mult_norm_next_al ; проверяем, после сложения нет ли переполнения inc edi ; переполнение есть, по этому увеличиваем позицию ответа на 1 add BYTE PTR [edi+esi],1 ; добавляем еденицу jmp mult_norm_next_al_1 ; прыгаем обратно на проверку переполнения, так как 0ffh + 1h = 00h mult_norm_next_al: pop edi ; востанавливаем позицию курсора из стека add BYTE PTR [edi+1+esi], ah ; прибавляем к ответу старший байт ah push edi ; запоминаем в стеке текущую позиции в ответе mult_norm_next_ah_2: jae mult_norm_next_ah ; проверяем, после сложения нет ли переполнения inc edi ; переполнение есть, по этому увеличиваем позицию ответа на 1 add BYTE PTR [edi+1+esi],1 ; добавляем еденицу jmp mult_norm_next_ah_2 ; прыгаем обратно на проверку переполнения, так как 0ffh + 1h = 00h mult_norm_next_ah: pop edi ; востанавливаем позицию курсора из стека dec ecx ; уменьшаем ecx cmp ecx, 0h ; сравниваем ecx с нулем jg next_sub_mult ; если больше - повторяем процесс умножения на следующую цифру cmp lenght1, 0 ; сравниваем длину 1 с 0 js mult_end ; если меньше 0, то дальше вычислять нет смысла - на выход cmp lenght2, 0 ; сравниваем длину 2 с 0 js mult_end ; если меньше 0, то дальше вычислять нет смысла - на выход mult_cont: inc ebx ; сдвигаем позицию меньшего числа на 1 inc edi ; сдвигаем позицию большего числа на 1 jmp mult_next ; повторяем все с начала со следующей цифрой большего числа mult_end: pop ecx ; приводим стек в исходную позицию mov eax, edi ; копируем адрес ответа в eax Ret mult EndPПроцедурка имеет прототип в виде:
mult PROTO:DWORD, :DWORD, :DWORD, :DWORD, :DWORD
И вызывается следующим образом:
invoke mult, ADDR num1, ADDR num2, ADDR int128, 3, 3
На выходе в eax лежит адрес произведения двух чисел.
Эта процедурка в принципе не должна иметь багов, кроме огромного колличества неоптимизированного кода и в ней нет фичи, что минимальное число которое можно умножить, должно быть 2байта.
"Длинная арифметика: Деление" будет?
ОтветитьУдалитьАвтор, ау!!!
ОтветитьУдалить