PDA

Просмотр полной версии : 100 факториал



sasadabest
15.10.2007, 01:59
666666666666

somewhere
15.10.2007, 13:36
Так как будем писать в текстовый файл, то простейший способ реализации - байтовые массивы, где каждый байт есть цифра. На таком множестве для N! достаточно реализовать только операцию сложения (проще, если скорость не критична) или умножения (сложнее, но быстрее). Этот метод расчета факториала будет зависеть только от размера свободной памяти и времени. В теории можно подсчитать сколь угодно большой факториал - например 1000000!

sasadabest
15.10.2007, 14:59
666666666666

somewhere
15.10.2007, 16:22
.model tiny
.code
.386

jmp @start

Num1 db 199 dup (0), 1
Num2 db 200 dup (0)
NFact dw 100 // N! you want to calc
fName db 'Result.txt',0 // Output file
hFile dw 0 // File handle

;//========================= Addition
;// Input:
;// SI - First number
;// DI - Second number
;//
;// Output:
;// SI - Result

Addition proc near
pusha
mov cx, 199
add di, cx
add si, cx
@add_1:
mov al, [si]
add al, [di]
add al, ah
daa
mov ah, al
shr ah, 4
and al,0Fh
mov [si], al
dec si
dec di
dec cx
jnz @add_1

popa
ret
Addition endp

;//================= Main code
@start:
push cs
pop ds
push ds
pop es
mov ah, 3Ch // Create file
xor cx, cx
lea dx, Fname
int 21h
mov hFile, ax

mov bx, 2
@fact:
lea si, Num1
lea di, Num2
cld
mov cx, 100
rep movsw // Num2 = Num1
lea si, Num1
lea di, Num2
mov cx, bx
dec cx
@fact1: // (Num1 = Num1 + Num2) * BX
call Addition
loop @fact1
inc bx
cmp bx, NFact
jle @fact

lea si, Num1 // Convert Num1 to ASCII
mov cx, 200
@toascii:
add byte ptr [si], '0'
inc si
loop @toascii

lea si, Num1 // Removes forward zeroes
mov cx, 200
xor di, di
@k1:
cmp byte ptr [si], '0'
jnz @k2
inc di
inc si
loop @k1
@k2:
mov ah, 40h // Write to file
mov bx, hFile
mov cx, 200
sub cx, di
mov dx, si
int 21h

mov ax, 4C00h
int 21h
end

sasadabest
15.10.2007, 20:50
666666666666

somewhere
16.10.2007, 08:54
Не компилит - очень размытое понятие, конкретно что, в какой строке, какая версия TASM(MASM), с какими параметрами и т.д.
Этот код компилился, линковался, запускался и работал на:

- TASM 4.0
- параметры
tasm %1.asm /la
tlink %1.obj

результат 100! в файле Result.txt
42077929000600528501510821802506191186411316662087 30663151040180005505559973158901799305787908399921 20903182245000000000000000000000000000000000000000 0000000

sasadabest
16.10.2007, 13:05
сматри :) скачал TASM 4.0 файл обозвал fakt.asm пишу:
...\tasm40\tasm fakt.asm /la

и вот что выкидывает:confused: ...такой же разультат и на TASM 4.1 ...ща попробую на 5-ом

Serge_Bliznykov
16.10.2007, 22:17
sasadabest
неверно задан комментарий!
замени все символы " //" на " ;"
(кавычки в поиске/замене набирать НЕ НАДО!!!)

sasadabest
17.10.2007, 02:22
666666666666

somewhere
17.10.2007, 13:17
<<ВАЖНО>>
В проге есть тупая ошибка, из-за которой факториал считается неверно. Необходимо дополнить


add al, [di]
add al, ah
daa
на следующий


add al, [di]
daa
add al, ah
daa

Кто знает, что такое daa, тот поймет почему.

sasadabest
17.10.2007, 16:01
ок,поменял... проста когда вычисляешь факториал больших чисел ошибки незаметно.. всё равно сенкс:)

Serge_Bliznykov
17.10.2007, 23:20
somewhere
тото, как я открыл файл Result.txt сразу увидел, что факториал не тот.... ;-)))))))))

sasadabest
31.10.2007, 15:22
Somewhere очень благодарен за помощь но не мог бы ты в общих чертах пояснить прогу. Хотелось бы въехать в ход мыслей и сам процесс подсчёта факториала. Было бы очень любезно с твоей стороны. :)

somewhere
31.10.2007, 16:58
В общих чертах:

Используется всего одна операция: сложение. Рассмотрим факториал какого-нибудь числа и приведем все операции к одной. Например 5!. Сначала имеем единицу, теперь складываем ее саму с собой 2 раза, получили 2. Теперь складываем двойку саму с собой 3 раза, получили 6. Теперь складываем 6-ку саму с собой 4 раза, получили 24 и наконец 5 раз по 24 = 120. Вот и результат. Всего одна операция - сложение. Сейчас подробно объяснять времени нет, если не понятно, то лучше задавайте вопросы исходя из текста программы, а я поясню что к чему.

sasadabest
01.11.2007, 16:06
именно из текста программы и есть вопросы... хорохо бы коментов добавить , если не трудно. Кстати спасиба за пояснение принципа работы програмы :)

somewhere
02.11.2007, 09:25
.model tiny
.code
.386

jmp @start

Num1 db 199 dup (0), 1 ; Каждое число из 200 цифр, в этом храним 1
Num2 db 200 dup (0) ; а этом 0
NFact dw 100 ; Задаем, какой нужен N!
fName db 'Result.txt' ; куда результат выводить
hFile dw 0 ; это хендл файла, задавать не надо, рассчитывается внутри проги

;//========================= Сложение
;// Input:
;// SI - Первое число
;// DI - Второе число
;//
;// Output:
;// SI - Результат сложения

Addition proc near
pusha
mov cx, 199
add di, cx
add si, cx ; начинаем с конца
xor ah, ah
@add_1:
mov al, [si] ; берем цифру из 1
add al, [di] ; складываем с цифрой 2-го
daa ; корректируем в BCD
add al, ah ; добавляем предыдущий разряд
daa ; корректируем
mov ah, al
shr ah, 4 ; старший разряд в старших 4 битах сохраняем в AH
and al,0Fh ; оставляем младший
mov [si], al ; и записываем
dec si ; переход к следущему
dec di
dec cx
jnz @add_1

popa
ret
Addition endp

;//================= Main code
@start:
push cs
pop ds
push ds
pop es ; es = ds = cs
mov ah, 3Ch ; Создаем файл
xor cx, cx
lea dx, Fname
int 21h
mov hFile, ax ; для работы с ним используем хендл

mov bx, 2 ; начинаем считать с двойки
@fact:
lea si, Num1
lea di, Num2
cld
mov cx, 100
rep movsw ; Num2 = Num1
lea si, Num1
lea di, Num2
mov cx, bx ; кол-во необходимых сложений - 1
dec cx
@fact1:
call Addition ; складываем
loop @fact1
inc bx ; переход к следущему множителю
cmp bx, NFact ; пока не достигли нужного
jle @fact

lea si, Num1 ; подсчитали факториал, теперь переводим в ASCII код
mov cx, 200
@toascii:
add byte ptr [si], '0' ; для этого добавим к каждой цифре код '0' или 30h
inc si
loop @toascii

lea si, Num1 ; но у нас остались нули в начале
mov cx, 200
xor di, di ; и их сейчас будем убирать
@k1:
cmp byte ptr [si], '0' ; если не встретили 0, то выход из цикла
jnz @k2
inc di
inc si
loop @k1
@k2:
mov ah, 40 ; теперь в DI - кол-во пропущенных нулей
mov bx, hFile ; а в SI - позиция в числе, с которой надо писать в файл
mov cx, 200
sub cx, di ; кол-во байт для записи = 200 - DI
mov dx, si
int 21h

mov ax, 4C00h ; выходим
int 21h
end

sasadabest
02.11.2007, 14:23
Щас буду сидеть разбираться... :) потом отпишусь если что ;)

ЗЫ:А тут нигде нелизя плюсик в репутацию поставить? :)

somewhere
02.11.2007, 16:02
над сообщением пользователя в правом углу есть типа весы, нажав на них можно добавить отзыв.

Voortex
08.12.2008, 14:00
Извините, что поднимаю эту тему, просто мне выпала в задании честь найти факториал на ассемблере, здесь код который выложили, как раз почти подходит. Кстати он не работал у меня пока я вначале не поставил begin и в конце закрыл его. Здесь факториал дается в коде, а мне надо, чтобы самому ввести число и он его вычислил, еще самому задать имя файла, куда записать. И еще чтобы можно было найти факториал 1000. В этом я помойму разобрался, просто вверху поставил
Num1 db 999 dup (0), 1
Num2 db 1000 dup (0)
Немного с глюками выдает.
Ну и вот проблема в том что не могу сделать ввод числа и имени файла....
Если можете, помогите пожалуйста, буду очень-очень благодарен!

somewhere
09.12.2008, 14:50
1) Num2 - это массив из десятичных цифр факториала, мне лично не известно количество цифр в числе 1000! но без сомнений их больше 1000.
2) Для ввода с клавиатуры строки используйте функцию MS-DOS, для преобразования введеной строки в число - поищите в разделе "Ассемблер", в некоторых темах алгоритм имеется.
3) Ввод имени файла - также через функцию MS-DOS в массив fName
4) ВНИМАТЕЛЬНО следите за размерами массивов при считывании с клавиатуры, дабы не перекрыть другой участок памяти.

Voortex
09.12.2008, 20:16
Спасибо!
Попробую сделать, хотя в ассемблере плохо шарю...
А так я правильно для цифр в числе в том месте где надо, 1000 поставил ?
---
Можно хотя бы вообще узнать, какой код для того чтобы вводить текст ?
И еще хотя бы код чтобы уже был размещенным текст, типа "Введите число". А я сам у себя попробую разобраться
Я думаю введеное число преобразовав в число сразу можно присвоить Nfact

somewhere
09.12.2008, 20:26
Повторю еще раз, что не мне, не вам - не известно количество десятичных знаков в числе 1000! Еще точно известно что их больше 1000. Попробуйте для начала тысяч 5 поставьте. Это замедлит расчет, зато потом когда найдете, можно определить границы поточнее. Для одноразового расчета можно и подождать несколько лишних секунд.
Еще можно извратиться и сделать проверку на переполнение сего массива цифр и динамически его расширять - только вот это весомо увеличит размер кода и добавит лишнего гемороя.

BBB
18.12.2008, 10:29
Повторю еще раз, что не мне, не вам - не известно количество десятичных знаков в числе 1000! Еще точно известно что их больше 1000.
Попробуйте для начала тысяч 5 поставьте. Несложно сделать оценку сверху количества цифр в числе 1000!
Другое дело, что Voortex пишет, что число будет вводиться с клавиатуры, так что оно может оказаться и больше 1000. Хотя, нижеприведенные рассужедния можно формализовать для произвольного натурального N. А массив символов, насколько я помню возможности ассемблера, можно выделять динамически.

Итак, оценка основана на том факте, что количество цифр в числе N (рассматриваем запись числа в десятичной системе счисления) равно 1 + [lg (N)]:

QG (N) = 1 + [lg (N)]
где QG (N) я обозначил "кол-во цифр в числе N", а [x] - целая часть числа x.

Будем использовать следующие очевидные равенства и неравенства:
lg (1) = 0
для 2 <= n < 10: lg (n) < 1
lg (10) = 1
для 11 <= n < 100: lg (n) < 2
lg (100) = 2
для 101 <= n < 1000: lg (n) < 3
lg (100) = 3

Проводим оценку:
lg (1000!) = lg (1 * 2 * ... * 1000) = lg(1) + lg(2) + .... + lg (1000) =
lg (1) + (lg (2) + ... + lg (9)) +
lg (10) + (lg (11) + ... + lg (99)) +
lg (100) + (lg (101) + ... + lg (999)) +
lg (1000) <
0 + 8 * 1 +
1 + 89 * 2 +
2 + 899 * 3 +
3 = 9 + 180 + 2700 = 2889

Таким образом:
QN (1000!) = 1 + [lg (N)] < 1 + [2889] = 2890

Т.е. в числе 1000! заведомо не более 2890 цифр.

Voortex
19.12.2008, 08:27
system architect
У меня 2600 цифр получилось, я для проверки поставил 2700, ответ факториала 1000 остался таким же, потом 3000 поставил, тоже не изменился. Сейчас поставил как ты задал 2890, тоже также, т.е. можно считать, что 2600 знаков нормально))...Осталось маленький штрих, чтобы вводить...Я вроде нашел команду...пока не разобрался,там AH=0ah - ввод строки в буфер, а преобразование в число - cwd

Voortex
25.12.2008, 14:40
Изменил некоторые данные:



msg1 db 'Vvedite chislo $' ;Добавил параметр вывода стоки
Num1 db 2599 dup (0), 1 ;Больше разрядов для вычисления 1000
Num2 db 2600 dup (0)
buf db 8,8 dup (0) ;для помещения введенной строки
NFact db ? ;
fName db 'Result.txt',0
hFile dw 0


И добавил:


;//================= Main code
@start:
mov AH, 09h
lea DX, msg1 ;для вывода строки
int 21h
mov ah,0Ah ; для ввода числа, к которому присвоится Nfact
mov dx, offset Nfact
int 21h

push cs
pop ds
push ds
pop es


При компиляции выводит ошибку


сmp bx, NFact
Operand types do not match


Может я не там поставил ввод числа или еще что забыл ?

BBB
25.12.2008, 15:43
Изменил некоторые данные:
При компиляции выводит ошибку

сmp bx, NFact
Operand types do not match Несоответствие типов операндов.
Регистр bx - это 16 бит, NFact объявлен как db, т.е. 8 бит.
Оператором cmp можно сравнивать или два 16-битных значения, или два 8-битных значения (регистр-регистр или регистр-память)

Voortex
28.12.2008, 10:45
Вот тут исправил:
NFact dw ? ;
Теперь запускается, можно ввести число, но вычисляет с глюками....это потому что кажись надо еще переводить строку в число ?
Кстати, когда он записывает результат, он записывает его в одной строке, т.е. большой хвост, а хотелось бы, чтобы был перенос по строке

Voortex
28.12.2008, 15:05
Помогите хотя бы сделать в старом коде, чтобы в файл записался от какого числа выведен факториал, например:
"Факториал 5 = 120"

Voortex
29.12.2008, 07:35
Все, ребята, откат...Я показал преподавателю работу, какая есть, и он мне засчитал ее на отлично, оказывается достаточно было просто чтоб смогла вычислить 1000, а я уж переволновался, что полностью оформить надо....
вот ниже код для будущих студентов, если кому-то когда-нибудь понадобиться вычислить факториал 1000!


model tiny
.386
masm
.code
assume cs:@code, ds:@code, ss:@code
org 100h

begin:

jmp @start
Num1 db 2599 dup (0), 1
Num2 db 2600 dup (0)
NFact dw 1000 ; // N! you want to calc
fName db 'Result.txt',0 ;// Output file
hFile dw 0 ; // File handle

;//========================= Addition
;// Input:
;// SI - First number
;// DI - Second number
;//
;// Output:
;// SI - Result

Addition proc near
pusha
mov cx, 2599
add di, cx
add si, cx
@add_1:
mov al, [si]
add al, [di]
daa
add al, ah
daa
mov ah, al
shr ah, 4
and al,0Fh
mov [si], al
dec si
dec di
dec cx
jnz @add_1
popa
ret
Addition endp

;//================= Main code

@start:
push cs
pop ds
push ds
pop es
mov ah, 3Ch ; // Create file
xor cx, cx
lea dx, Fname
int 21h
mov hFile, ax
mov bx, 2

@fact:
lea si, Num1
lea di, Num2
cld
mov cx, 1300
rep movsw ; // Num2 = Num1
lea si, Num1
lea di, Num2
mov cx, bx
dec cx

@fact1: ; // (Num1 = Num1 + Num2) * BX
call Addition
loop @fact1
inc bx
cmp bx, NFact
jle @fact
lea si, Num1 ; // Convert Num1 to ASCII
mov cx, 2600

@toascii:
add byte ptr [si], '0'
inc si
loop @toascii
lea si, Num1 ; // Removes forward zeroes
mov cx, 2600
xor di, di

@k1:
cmp byte ptr [si], '0'
jnz @k2
inc di
inc si
loop @k1

@k2:
mov ah, 40h ; // Write to file
mov bx, hFile
mov cx, 2600
sub cx, di
mov dx, si
int 21h

mov ax, 4C00h
int 21h

end begin