Фантазии о Вселенной и мой личный сайт
Страница запроса

Точное значение факториала n! при больших n

model tiny
codeseg

startupcode

    mov     bx, 6542            ; исходные данные

    ; ----- установление указателей ----
    mov     ax, cs
    add     ah, 0x10
    mov     es, ax
    mov     ds, ax            ; рабочие сегменты

    ; ----- инициализация массива ----
    xor     ax, ax            ; AX = 0x0000
    xor     cx, cx            ; CX = 0x0000
    xor     di, di            ; DI = 0x0000
    dec     cx                ; CX = 0xFFFF
    rep     stosb             ; записать 65535 значений нуля
    inc     di                ; DI = 0, т.к. данее DI = 0xFFFF
    mov     [byte ptr di], 0x01        ; записать 1 как первый множитель

    ; ----- факториал -----
U:  xor     bp, bp            ; BP - это перенос при умножении
    mov     cx, 32764
    xor     si, si
    xor     di, di            ; новая итерация

    ; ----- умножение -----
R:  lodsw
    mul     bx                ; умножить AX на BX
    add     ax, bp            ; с учетом предыдущего переноса
    adc     dx, 0             ; корректировка нового переноса
    mov     bp, dx            ; установление значения переноса
    stosw                     ; запись нового значения
    loop    R                 ; повторить с 32764 разрядами

    dec     bx                ; следующее умножение
    jNE     U

    ; CALL ... печать 65536-байтного числа ...

    int     0x20
По правде говоря, эта программа представляет из себя более технический метод, рассказывающий как программировать на Ассемблере под ДОС, чем сам по себе метод вычисления факториала. Вначале задается параметр BX = любому числу от 1..65535 (хотя последние брать не следует из-за огромного результата, получающегося при возведении в факториал оного). После программа вычисляет последовательность: BX * (BX - 1) * (BX - 2) * ... * 1 и результат оказывается записанным в 65536-байтном буфере, в одной машинной странице.

Для выделения рабочего места в программе используется повышение сегмента на 4096 машинных параграфов, что составляет 65536 байт. Программа COM не может занимать в ДОС'е больше места, чем около одной машинной страницы, примерно около 65000 байт. Остальное выделяется под стек. ДОС так устроен, что программы "накладываются" снизу вверх, по все возрастающим адресам, потому над программой по сути, должно находится неиспользуемое место. Это место используется как свободное, для вычисления факториала, в данном случае. Потому нужно установить указатели в то место, откуда будет начинаться буфер. Это делается так:
    mov     ax, cs            ; взять текущий сегмент кода
    add     ah, 0x10            ; добавить страницу вверх
    mov     es, ax            ; ES = новая страница
    mov     ds, ax            ; DS = ES = AX
Потом происходит предварительная очистка массива, в котором будет совершаться последовательное умножение на 1, 2, 3.... BX-2, BX-1, BX. Далее программа очищает буфер и устанавливает его значение как 1.

По сути, этот буфер не более, чем сверхбольшое число, записанное в позиционной системе счисления (как обычная, 10-я система, но только с гораздо большей разрядностью, т.е. с 65536-й разрядностью. Возьмем любое число, и тогда оно будет записываться примерно так:
16383  16382 ....  ....  ....   2     1     0
------------------------------------------------------
  0      0    .............   1544  32553 65535
Верхняя строчка - это номер позиции. Самая младшая позиция - это 0, самая старшая - это 16383, хотя предел совершенно не ограничен. Я сейчас не буду выкладывать основы позицонной системы счисления, просто скажу, что если перевести это число в 10-ю систему, получится число

65535*655360 + 32553*655361 + 1544*655362 + .... + 0 = 6633562963967

Огроменное! У него в десятичной системе счисления задействовано 13 разрядов вместо 3. Выгода от этого есть большая, потому что если уж в 65536-й системе счисления получается число с 16384 знаками, то что получится в 10-й! Да, это будет число так число :-) а точнее, количество знаков у него будет примерно 78913. Такого числа и в природе нет, ведь даже количество атомов во Вселенной от силы еле достигнет 10100.

Программа работает так просто, что проще не придумаешь. Вначале берется, с помощью инструкции LODSW, нулевой разряд (автоматически устанавливая на 0 + 1 = 1, т.е. на 1-й), выбранное число умножается на BX. Если полученное число получилось больше 65535, то всё не вместившееся уходит в верхний разряд, в DX. Умножим, например, 0x8852 * 0xA826 = 0x598A:0C2C Нижняя часть этого числа уйдет в AX = 0x0C2C, а верхняя - в DX = 0x598A. Как раз DX будет значением переноса, как при умножении в столбик, и оно является переносом в старший разряд.

Но при умножении в столбик не следует забывать, что может существовать предыдущий перенос. В этой программе он представлен как BP. Так что складывая AX + BP, мы можем получить еще перенос, который, как известно, в процессоре записывается в CF (Carry Flag, флаг переноса). Если он есть, то инструкция ADC DX, 0 добавляет к DX единицу, если нет - то оставляет как есть. После этих всех операции DX переписывается в BP, и становится новым переносом для следующего разряда.
    add    ax, bp       ; сложение текущего разряда с учетом переноса
    adc    dx, 0        ; если есть перенос при сложении, добавить
                        ; 1 к переносу в старший разряд
    mov    bp, dx       ; теперь перенос становится переносом из
                        ; младшего разряда
Полученное значение текущего разряда, что сохранено в AX, переписывается в этот же рязряд и процесс идет дальше. И так до тех пор, пока не доберется до последнего разряда. Число разрядов было указано в регистре CX. В данном случае, в CX было 32764, значит, именно столько разрядов он и учтет, а остальные "отрежет".

P.S.Так что не надо страдать гигантоманией, и столько хватит для начала ;-)