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

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

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-процессорах все регистры равноправны).