Основы программирования



              

Вычисление наибольшего общего делителя


Реализуем функцию, вычисляющую наибольший общий делитель двух целых чисел. Мы уже записывали алгоритм вычисления НОД на псевдокоде. На языке Си эта функция выглядит следующим образом:

int gcd(int x, int y) { // цел алг. gcd(цел x, цел y) int a, b, r; // | цел a, b, r; a = x; b = y; // | a := x; b := y; while (b != 0) { // | цикл пока b != 0 r = a % b; // | | r := a % b; a = b; // | | a := b; b = r; // | | b := r; } // | конец цикла return a; // | ответ := a; } // конец алгоритма

Вместо НОД мы назвали функцию "gcd" (от слов greatest common divizor), поскольку в языке Си русские буквы в именах функций и переменных использовать нельзя. Запишем эту программу на языке RTL. Переменные a, b, r мы будем хранить в регистрах R0, R1, R2.

// Вход в функцию: push FP; // сохраним значение FP в стеке; FP := SP; // определим новое значение FP; push R1; // сохраним значения регистров R1 push R2; // и R2 // R0 := m[FP+8]; // a := x; R1 := m[FP+12]; // b := y; L1: // метка начала цикла CC0 := R1 - 0; // сравнить b с нулем if (eq) goto L2; // если результат равен нулю, // то перейти на метку L2 R2 := R0 % R1; // r := a % b; R0 := R1; // a := b; R1 := R2; // b := r; goto L1 // перейти на метку L1 L2: // метка конца цикла // ответ уже содержится в R0 // выход из функции: pop R2; // восстановим значения R2 pop R1; // и R1 pop FP; // восстановим значение FP return; // вернемся в вызывающую программу

Эту программу можно переписать на конкретный Ассемблер, например, на Ассемблер "Masm" фирмы Microsoft для процессоров Intel 80x86. Первое, что надо сделать при переводе с RTL на Ассемблер — это распределить регистры, т.е. задать отображение виртуальных регистров R0, R1, ... на конкретные регистры данного процессора. У процессоров серии Intel 80x86 есть всего 8 общих регистров: это регистры

EAX, EBX, ECX, EDX, ESI, EDI, EBP, ESP.

Процессор Intel сконструирован таким образом, что каждый регистр выполняет в определенных командах свою особую роль (Intel 80x86 — это CISC-процессор; в RISC-процессорах все регистры равноправны).


Содержание  Назад  Вперед