VPF::НОД - Форум программистов

Chameleon

Дата 13.12.2005, 14:41 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 18
Регистрация: 27.11.2005
Где: moscow

Репутация: нет
Всего: нет

не получается написать программу для нахождения Наименьшего Общего Делителя.
НОД для больших чисел byte* gcd(byte *a, byte *b, byte *c, int sizea, int sizeb) длинна числа=MAX(sizea,sizeb), результат записать в c

Akina

Дата 13.12.2005, 16:37 (ссылка)

(нет голосов)

Загрузка ...

Советчик

Профиль
Группа: Модератор
Сообщений: 20581
Регистрация: 8.4.2004
Где: Зеленоград

Репутация: 1
Всего: 454

ну и? процедура деления с остатком либо вычитания есть?

или ты желаешь чтобы сделали ЗА ТЕБЯ?

--------------------

О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума.

Chameleon

Дата 13.12.2005, 16:46 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 18
Регистрация: 27.11.2005
Где: moscow

Репутация: нет
Всего: нет

код проги исеется но он не рабочий, почему не работает не пойму, мозг уже сплавился

Код


.intel_syntax noprefix
.globl nod
.type nod, @function
nod:    
    push eax
    push ebx
    push ecx
    push esi
    push edi
    push ebp
    mov eax, [esp+28]
    mov ebx, [esp+32]
    mov esi, [esp+36]
    cmp esi, 0        
    je endp            
    xor ecx, ecx        

test_a0:            
    inc ecx            
    cmp ecx, esi        
    jg  endp        
    cmp [eax + ecx*4 - 4], 0
    je test_a0        
    xor ecx, ecx

test_b0:    
    inc ecx
    cmp ecx, esi
    jg endp
    cmp [ebx + ecx*4 - 4], 0
    je test_b0

if0:                
        xor ecx, ecx        
    xor edi, edi        

if1:                
        inc ecx            
        cmp ecx, esi        
    jg endp            
    mov edi, [eax + ecx*4 - 4] 
    sub edi, [ebx + ecx*4 - 4] 
    cmp edi, 0        
    je if1            
    jg sub_ab        
    xchg eax, ebx        

sub_ab:                
    xor ecx, ecx
    xor edi, edi
    xor ebp, ebp
    mov ecx, esi        

sub_ab1:            
    dec ecx            
    cmp ecx, 0        
    jl if0            
    mov edi, [eax + ecx*4]    
    cmp ebp, 0        
                
                
    je sbb_ab1        
    xor ebp, ebp        
    sbb edi, 1        
    jnc sbb_ab1        
    btr edi, 31        
                
    mov ebp, 1        

sbb_ab1:            
                
    sbb edi, [ebx + ecx*4]    
    jnc sbb_ab2        
    btr edi, 31        
    mov ebp, 1        

sbb_ab2:            
    mov [eax + ecx*4], edi    
    jmp sub_ab1        

endp:
    pop ebp
    pop edi
    pop esi
    pop ecx
    pop ebx
    pop eax
    ret

это все гоняется под gcc для linux

Akina

Дата 13.12.2005, 17:30 (ссылка)

(нет голосов)

Загрузка ...

Советчик

Профиль
Группа: Модератор
Сообщений: 20581
Регистрация: 8.4.2004
Где: Зеленоград

Репутация: 1
Всего: 454

а комментировать Пушкин будет? кому надо в хламе копаться? где собсно идея и алгоритм?

делов-то:

Код


NOD=0
do
   с=a mod b
   if с=0 then 
      NOD = b
   else
      a=b
      b=с
   end if
loop while NOD=0

--------------------

Chameleon

Дата 14.12.2005, 16:30 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 18
Регистрация: 27.11.2005
Где: moscow

Репутация: нет
Всего: нет

вот короче код с коментариями.

Код


.intel_syntax noprefix
.globl nod
.type nod, @function
nod:
    push eax        ;Сохраняем значения регистров eax, ebx, ecx, esi, edi, ebp
    push ebx
    push ecx
    push esi
    push edi
    push ebp
    mov eax, [esp+28]    ; Значение первого эл-та массива "а"
    mov ebx, [esp+32]    ; Значение первого эл-та массива "b"
    mov esi, [esp+36]    ; size
    cmp esi, 0        ; граничное условие: сравниваем размер массивов с нулем    
    je endp            ; если ноль, то завершить программу
    xor ecx, ecx        ; обнулить ecx, т.к. он пригодится нам в последствии

test_a0:            ; метод проверяет наличие хотя бы одного ненулевого эл-та в "а"
    inc ecx            ; ecx используем как индекс - увеличиваем по 1
    cmp ecx, esi        ; граничное условие: прверяем, не вышли ли за границы массива
    jg  endp        ; если вышли, то закончить программу => все эл-ты нулевые
    cmp [eax + ecx*4 - 4], 0; сравниваем i-й эл-т с нулем
    je test_a0        ; если ноль - опять на сравнение
    xor ecx, ecx        ; дошли до этой строки - есть хоть один ненулевой элемент => обнуляем есх

test_b0:            ; аналогичный метод для "b"
    inc ecx
    cmp ecx, esi
    jg endp
    cmp [ebx + ecx*4 - 4], 0
    je test_b0

if0:                ; начинаем поиск нода
        xor ecx, ecx        ; обнуляем есх
    xor edi, edi        ; обнуляем edi

if1:                ; метод сравнивает два длинных числа, записанных в массивах "a" и "b"
        inc ecx            ; есх - счетчик, увеличиваем на единицу
        cmp ecx, esi        ; граничное условие: не вышли ли за границу массива
    jg endp            ; если да, то закончить (произойдет, когда "а" сравняется с "b")
    mov edi, [eax + ecx*4 - 4] ; кладем в edi i-й эл-т "а"
    sub edi, [ebx + ecx*4 - 4] ; вычитаем из edi значение i-го эл-та "b"
    cmp edi, 0        ; сравниваем с нулем
    je if1            ; если ноль => эл-ты равны => сравниваем дальше
    jg sub_ab        ; если больше => "прыгаем" на sub_ab
    xchg eax, ebx        ; иначе - поменять местами значения регистров eax и ebx 

sub_ab:                ; вычитаем из большего числа меньшее => отрицательное число не получится никогда
    xor ecx, ecx
    xor edi, edi
    xor ebp, ebp
    mov ecx, esi        ; кладем в есх size

sub_ab1:            ; вычитание начинается с последнего элемента (вспомни вычитание в столбик :=)
    dec ecx            ; вычитаем из size'а единицу
    cmp ecx, 0        ; граничное условие: не вышли ли за границу массива
    jl if0            ; если вышли => вычитание закончилось => возвращаемся к сравнению длинных чисел
    mov edi, [eax + ecx*4]    ; кладем в edi значение (начиная с последнего) i-го эл-та еах
    cmp ebp, 0        ; здесь ebp используется аналогично биту переноса. сам бит переноса использовать пытался, но 
                ; в ходе проверки программы увидел, что он изменяется некоторыми из команд
                ; поэтому пришлось прибегнуть к небольшой уловке
    je sbb_ab1        ; если ebp - ноль => переноса не было, переходим к вычитанию
    xor ebp, ebp        ; иначе обнуляем ebp (был перенос в вычислении разности i-1 -вых элементов)
    sbb edi, 1        ; предварительно вычитаем единицу из i-го эл-та
    jnc sbb_ab1        ; если нет переноса, переходим к вычитанию
    btr edi, 31        ; иначе сбрасываем знаковый бит. 
                ; а если все же интересно, почему, - вспомни как устроены числа в 2-ном исчислении
    mov ebp, 1        ; наш "бит переноса" устанавливаем в 1 для будущих операций

sbb_ab1:            ; метод выполняет "вычитание в столбик" (напомним, что значения наших регистров не изменялись 
                ; за исключением вычитания 1)
    sbb edi, [ebx + ecx*4]    ; из i-го эл-та еах (значение которого сейчас находится в edi) вычитаем ebx
    jnc sbb_ab2        ; если переноса не было => все нормально, переходим к следующей стадии
    btr edi, 31        ; если был перенос => обнуляем знаковый бит
    mov ebp, 1        ; в наш "бит переноса" кладем 1

sbb_ab2:            ; конечная стадия - возвращаем i-му эл-ту еах полученное значение
    mov [eax + ecx*4], edi    ; собст-но, здесь это и делается
    jmp sub_ab1        ; переходим к следующему такту вычитания 

endp:                ; ну и самый приятный метод - окончание работы программы
                ; мы здесь оказываемся, если:    
                ; 1. size == 0
                ; 2. a[i] == 0 or b[i] == 0 (для всех i)
                ; 3. нашли нод 2-х длинных чисел

    pop ebp            ; возвращаем исходные значения использовавшихся регистров 
                ; (обязательно в обратном порядке, т.к. их значения лежали в стеке)
    pop edi
    pop esi
    pop ecx
    pop ebx
    pop eax
    ret            ; конец программы

P.S. вся группа мучается с этим заданием, никто не доганяет как писать это

Akina

Дата 14.12.2005, 18:42 (ссылка)

(нет голосов)

Загрузка ...

Советчик

Профиль
Группа: Модератор
Сообщений: 20581
Регистрация: 8.4.2004
Где: Зеленоград

Репутация: 1
Всего: 454

навскидку (пишу на коленке, не проверял)

Код


test_zero:
                        ; Проверим, есть ли ненулевой элемент в числе "а"
   mov esi, [esp+28]    ; Значение первого эл-та массива "а"
   mov ecx, [esp+36]    ; size
   cld
   xor ax,ax
   rep scasd
   jz done
                        ; Проверим, есть ли ненулевой элемент в числе "b"
   mov esi, [esp+32]    ; Значение первого эл-та массива "b"
   mov ecx, [esp+36]    ; size
   rep scasd
   jz done
                        ; Убедились что оба числа больше нуля
                        ; Теперь будем сравнивать
compare_a_b:
   mov esi, [esp+28]    ; Значение первого эл-та массива "а"
   mov edi, [esp+32]    ; Значение первого эл-та массива "b"
   mov ecx, [esp+36]    ; size
   cmpsd                ; Сравниваем очередной элемент
   ja substract         ; "а" оказалось больше, можно вычитать
   jb swap              ; "а" оказалось меньше, обменять и вычитать
   dec ecx
   jecxz done           ; Числа равны - оба содержат NOD
   jmp compare_a_b      ; Пора сравнивать следующий элемент

swap:                   ; Обменяем указатели на "a" и "b" в стеке
   mov esi, [esp+28]    ; Значение первого эл-та массива "а"
   mov edi, [esp+32]    ; Значение первого эл-та массива "b"
   mov [esp+28], edi    ; 
   mov [esp+32], esi    ; 

substract:
                        
; Извиняй, пора домой...

done:

PS. не занимайся фигней с сохранением состояния переноса в ebp - есть такая штука как pushf/popf

--------------------

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Asm для начинающих \| Следующая тема »