18 апреля 2012 г.

Длинная арифметика: Вычитание

Продолжим работу с длинными числами, в текущий момент мы можем складывать числа произвольной длинны, а теперь нам необходимо научиться вычитать эти числа.
Опять же вспоминаем 3ий класс и как производятся вычитание при помощи столбика:

Числа записываются друг по другом, например так:
 4321
-
 1234
=
 3087
1. Начинаем с самой младшей цифрой, тоесть с правой, от уменьшаемого отнимаем вычитаемое
 тоесть, от 1 - 4, но так как у нас десятичная система и вычесть от еденицы мы не можем, то приходится занимать у соседнего числа 2 еденицу, которое приписываем к правому, получается 11 - 4 = 7, в ответ в самую младшую цифру записываем 7
2. Сдвигаем позицию в лево, тут находится цифра 2, но так как мы в предыдущей операции заняли еденицу, то от этой цифры нада отнять 1, получится 1 от которой отнимаем 3 и снова получается, что число отрицательное, а это мы не можем себе позволить, необходимо занять еденицу у следующей цифры с лева, итого: 11 - 3 = 8, записываем в ответ с с лева от предыдущей 8, получаеся 87.
3. Снова сдвигаем позицию в лево, там у нас цифра 3, но мы у нее заняли еденицу в предыдущей операции, так что получается, что там 2, ну от 2 отнять 2 мы можем без проблем, минусовая операция не получится, так что отнимаем 2 - 2=0, записываем с лева от ответа 0, получается 087.
4. И снова сдвигаем позицию в лево, там у нас цифра 4, операций заимстования мы в предыдущий раз не делали, так что цифра так и остается 4, отнимаем от нее 1 и получем 3, записываем с лева от результата, получается 3087.


3087 - это и есть итог вычислений, так мы можем двигаться в лево пока число не кончится.
Но тут есть свои подводные камни, например уменьшаемое число может быть меньше чем вычитаемое, соответственно итог может получиться минусовой. Нужно делать все тоже самое, что и в первом случае, только необходимо прибавлять получившуюся цифру к минус 10(ну или отнимать цифру от 10 :) не забываем поставить минус перед циферкой ).
Пример:
 1234
-
 4321
=
7913
Теперь прибавим эту цифру к -10000 + 7913 и получим, -3087, по началу алгоритм выглядит немного странно, но в коде это просматривается достаточно четко, итак пример алгоритма на ассемблере:


minus proc uses ecx edx ebx esi edi cif1:DWORD, cif2:DWORD, out_place:DWORD, lenght1:DWORD, lenght2:DWORD
    mov        ebx, cif1 ; копируем в ebx адрес младшего регистра цифры1
    mov        edx, cif2 ; копируем в edx адрес младшего регистра цифры2
    mov        edi, out_place ; копируем в edx адрес младшего регистра цифры2
    mov        al, BYTE PTR [ebx] ; копируем в al младший байт цифры 1
    sub        al, BYTE PTR [edx] ; отнимаем от al младший байт цифры 2
    jae        over_minus_1 ; проверяем, а не получился ли у нас минус
    dec        BYTE PTR [edi+1] ; получился - занимаем еденицу у следующего младшего байта
over_minus_1:    
    mov        BYTE PTR [edi], al ; копируем в младший байт получившуюся разницу
    xor        esi, esi ; обнуляем позицию в числе
next_minus:
    dec        lenght1 ; уменьшаем длинну байт в цифре 1
    dec        lenght2 ; уменьшаем длинну байт в цифре 2
    inc        esi ; сдвигаем позицию на следующий младший байт
    mov        al, BYTE PTR [ebx + esi] ; копируем в al младший байт цифры 1
    sub        al, BYTE PTR [edx + esi] ; отнимаем от al младший байт цифры 2
    jae        over_minus_2 ; проверяем, а не получился ли у нас минус
    dec        BYTE PTR [edi + 1 + esi] ; получился - занимаем еденицу у следующего младшего байта
over_minus_2:    
    add        BYTE PTR [edi + esi], al ; прибавляем к текущему младшему байту в ответе al
    mov        eax, lenght1 ; копируем в eax длинну числа 1
    or        eax, eax ; проверяем, а не 0 ли он?
    jz         check_minus_zero; если 0 то прыгаем на проверку окончания цифры check_minus_zero
    mov        eax, lenght2 ; копируем в eax длинну числа 2
    or        eax, eax ; проверяем, а не 0 ли он?
    jz        check_minus_zero; если 0 то прыгаем на проверку окончания цифры check_minus_zero
    jmp        next_minus ; возвращаемся к следующему байту

check_minus_zero:
    mov        eax, lenght1 ; копируем в eax длинну числа 1
    or        eax, eax  ; проверяем, а не 0 ли он?
    jnz        vichit_minus ; прыгаем на обработку если число 1 меньше числа 2
    mov        eax, lenght2 ; копируем в eax длинну числа 2
    or        eax, eax ; проверяем, а не 0 ли он?
    jnz        umen_minus ; прыгаем на обработку если число 2 меньше числа 1
    cmp        BYTE PTR [edi + 1 + esi], 0FFh ; проверяем самый старший байт, не минус ли?
    jne        non_minus ; не минус, прыгаем на заврешение процедуры
    lahf ; копируем в ah состояние флагов
    or         ah,80h ; переводим флаг SF(знак минуса) в 1
    sahf ; заливаем состояние флагов обратно
non_minus:
    jmp        finish_minus ; прыгаем на заврешение процедуры


umen_minus: ; если у нас первое число меньше второго, то будет явный минус, так что тут колдуем это
    inc        esi ; сдвигаем позицию на следующий младший байт
    dec        lenght2 ; уменьшаем количество байт в цифре 2 
    mov        al, 0 ; обнуляем al(эстеты могут пользовать xor al,al но разницы никакой - 2байта)
    sub        al, BYTE PTR [edx + esi] ; отнимаем от al(которое 0) младший байт числа2
    add        BYTE PTR [edi + esi], al ; прибавляем(плюс, минус какая разница? :) ) к ответу al
    dec        BYTE PTR [edi + 1 + esi] ; так как мы заняли еденицу, то отнимаем от следующего байта ответа 1
    mov        eax, lenght2 ; копируем в eax длинну числа 2
    or        eax, eax ; проверяем, а не 0 ли он?
    jnz        umen_minus ; если не 0 то повторяем процесс, прыгаем на umen_minus
    lahf ; копируем в ah состояние флагов
    or         ah,80h ; переводим флаг SF(знак минуса) в 1
    sahf ; заливаем состояние флагов обратно
    jmp        finish_minus ; заканчиваем безобразия
vichit_minus:
    inc        esi ; сдвигаем позицию на следующий младший байт 
    dec        lenght1 ; уменьшаем количество байт в цифре 1
    mov        al, BYTE PTR [ebx+esi] ; копируем в al текущий младший байт цифры 1
    add        BYTE PTR [edi + esi], al ; прибавляем(минус, плюс - какая разница?:) ) к ответу al
    mov        eax, lenght1 ; копируем в eax длинну числа 1
    or        eax, eax ; проверяем, а не 0 ли он?
    jnz        vichit_minus ; нет? Повторяем процесс, прыгаем vichit_minus
finish_minus:
    mov        eax, edi ; копируем в eax адрес ответа
    Ret ; кончил... и закурил :)
minus EndP
Прототип процедуры получается следующий:
 minus PROTO:DWORD, :DWORD, :DWORD, :DWORD, :DWORD
Вызывается функция следующим образом:
 invoke minus, ADDR num1, ADDR num2, ADDR int128, 3, 3
Возвращает процедура в eax место где находиться младший байт ответа,  в флаге SF - знак.
Из текущих багов которые есть в этой процедуре - если число плюсовое, но имеет в старшем байте FF, то оно на выходе из процедуры получит минусовой флаг. В принципе это поправить можно, но в текущий момент ленива. :) Также алгоритм работает только для чисел больше 2х байт. Это в принципе тоже легко правиться, но лень переписывать кучу коментов, ну например можно в самом начале проверить длину обоих чисел, но лучше имхо переписать алгоритм целиком.

Комментариев нет:

Отправить комментарий