; ЗОЛОТОЕ СЕЧЕНИЕ - 512 знаков при использовании регистров (R128 - R191 по 8 знаков) или 12288 знаков при использовании блокнота ; (записи 0 - 3 в группах 0 - 511 по 6 знаков) ; ; ; Для вычисления длинных квадратных корней используется метод Ньютона, а для реализации длинного умножения - ; быстрое преобразование Фурье ; --------- выбор блокнота или регистров ; LLEN .EQU 12 ; блокнот - конечная логдлина массивов (т.е. длина = 2^LLEN) ; DIG .EQU 3 ; кол-во целочисленных знаков в ячейке массива ; ^ ; | закомментировать две строки выше / раскомментировать две строки ниже (или наоборот) ; v LLEN .EQU 7 ; регистры - аналогично DIG .EQU 4 ; ========== TSTK .EQU 1000 ; нач. указатель вершины программного стека (номер регистра) LLEN0 .EQU 3 ; нач. логдлина массивов .ORG 0 ENT ; --------- выбор блокнота или регистров - разные по реализации подпрограммы WRITE и READ ; .NUM WRITEC1 PM40 .NUM READC1 PM41 .NUM WRITER1 PM42 .NUM READR1 PM43 .NUM ORD1 PM44 .NUM ARRNO1 PM24 9060 PM20 1 + PM21; блокнот ; ^ ; | закомментировать строку выше / раскомментировать строку ниже (или наоборот) ; v .NUM WRITEC2 PM40 .NUM READC2 PM41 .NUM WRITER2 PM42 .NUM READR2 PM43 .NUM ORD2 PM44 .NUM ARRNO2 PM24 256 PM20 2 / PM21 ; регистры ; R40 - R43 - адреса п/п WRITE и READ, R44 - адрес п/п для переупорядочения по записям 0 - 3 блокнота в конце работы ; R24 - адрес п/п для выбора массива по номеру 1, 2 или 3 ; R21 = 9061...9064 для текущей записи в блокнот или нач. регистр текущего массива 128, 384 или 640 ; =========================================================================== ; расположение МАССИВОВ по номерам: 1 - записи 0 в блокноте или R128 - R383 ; 2 - записи 1 в блокноте или R384 - R639, 3 - записи 2 в блокноте или R640 - R895 ; РЕГИСТРЫ ; R0 - R6 - локальные в подпрограммах, значения следует сохранять на прогр. стеке ; R7 и R8 - для возврата результатов работы п/п, значения на стеке не сохраняются ; R9 - для доступа к параметрам, передаваемым в п/п через стек ; RA, RB и RD - адреса п/п PUSH, POP и PARAM для работы со стеком ; RC - текущая вершина стека ; RE - текущая длина массивов, R15 - текущая логдлина массивов ; R25 - макс. целочисленное значение в ячейке массива + 1 ; R37, R38 - комплексные корни из единицы, R30 - номер корня, R31 - угловое расстояние .NUM LLEN0 PM15 2 FX^Y ME ; инициализация регистров .NUM DIG ENT 10 FX^Y PM25 .NUM TSTK MC .NUM PUSH MA .NUM POP MB .NUM PARAM MD 1 PPM9045 ; радианы для тригонометрии PP RM9055 KMS->D M2 ; время запуска 5 KGSBA .NUM LLEN KGSBA PGSB SQROOT ; квадратный корень из пяти PGSB GOLD PGSB REORD ; золотое сечение PP RM9055 KMS->D RM2 - 3600 * ; тайминг R/S ; ======================= КОНЕЦ ОСНОВНОЙ ЧАСТИ ; --------- ПОДПРОГРАММЫ ; значение из RX на стек PUSH: RMC 1 - MC FR KMC RTN ; значение из стека в RX POP: KRMC RMC 1 + MC FR RTN ; получить параметр из стека с номером из RX и поместить в RX PARAM: RM9 + PM16 FR PKRM16 RTN ; выбрать массив с номером из RX ARRNO1: PRM20 + PM21 ; блокнот RTN ARRNO2: PRM20 * PRM20 2 / - PM21 ; регистры RTN ; реверсия битов целого числа, напр., 111010 -> 010111 ; на стек - число, рез-т в R7 BITR: RM9 KGSBA RMC M9 ; пролог RM0 KGSBA RM4 KGSBA RM6 KGSBA ; сохранение регистров на стеке 1 KGSBD M4 CX M7 PRM15 M0 RME M6 L_1: RM4 2 / ENT KINT M4 FR KFRAC 2 * RM6 2 / M6 * RM7 + M7 FL0 L_1 KGSBB M6 KGSBB M4 KGSBB M0 ; восстановление регистров из стека KGSBB M9 ; эпилог RMC 1 + MC RTN ; пролог типа PUSH EBP / MOV EBP, ESP, а эпилог - POP EBP / RET N на ассемблере ; т.е. R9 - аналог EBP, а RC - аналог ESP ; но на критических участках параметры передаем напрямую, без стека! ; запись комплексного числа в текущий массив ; индекс эл-та массива в RX, действ. часть в R7, мнимая - в R8 WRITEC: PKGSB40 RTN WRITEC1: PKM20 RM7 PKM21 <-> 1 + PKM20 RM8 PKM21 ; блокнот RTN WRITEC2: PRM21 + PM22 RM7 PKM22 PRM22 1 + PM22 RM8 PKM22 ; регистры RTN ; чтение комплексного числа из текущего массива ; индекс эл-та массива в RX, действ. часть сохраняется в R7, мнимая - в R8 READC: PKGSB41 RTN READC1: PKM20 PKRM21 M7 <-> 1 + PKM20 PKRM21 M8 ; блокнот RTN READC2: PRM21 + PM22 PKRM22 M7 PRM22 1 + PM22 PKRM22 M8 ; регистры RTN ; запись действ. числа в текущий массив ; индекс эл-та массива в RX, число - в RY WRITER: PKGSB42 RTN WRITER1: PKM20 <-> PKM21 ; блокнот RTN WRITER2: PM23 PRM21 + PM22 FR PRM23 <-> PKM22 ; регистры RTN ; чтение действ. числа из текущего массива ; индекс эл-та массива в RX, число возвращается в RX READR: PKGSB43 RTN READR1: PKM20 PKRM21 ; блокнот RTN READR2: PM23 PRM21 + PM22 FR PRM23 PKRM22 ; регистры RTN ; перестановка комплексных элементов текущего массива между собой ; на стек - 2) индекс1; 1) индекс2 EXCHG: RM9 KGSBA RMC M9 RM4 KGSBA RM6 KGSBA 1 KGSBD PGSB READC RM7 M4 RM8 M6 ; чтение и сохранение элемента по индексу2 (нумерация параметров справа налево!) 2 KGSBD PGSB READC 1 KGSBD PGSB WRITEC RM4 M7 RM6 M8 2 KGSBD PGSB WRITEC KGSBB M6 KGSBB M4 KGSBB M9 RMC 2 + MC RTN ; перестановка комплексных элементов текущего массива в соответствии с битовой реверсией индексов ; параметров на стек нет REVERS: RM4 KGSBA RM0 KGSBA CX M4 RME M0 L_3: RM4 KGSBA PGSB BITR RM4 RM7 - PX<0 L_2 RM4 2 * KGSBA RM7 2 * KGSBA PGSB EXCHG L_2: KRM4 PFL0 L_3 KGSBB M0 KGSBB M4 RTN ; перемножение комплексных чисел ; число1 - в RX, RY, число2 - в R7, R8, рез-т - в R7, R8 MULT: PM28 <-> PM27 RM7 * PRM28 RM8 * - PRM27 RM8 * PRM28 PRM7 * + M8 <-> M7 RTN ; инициализация тригонометрии ; угол в полуокружностях передается в RX, на выходе - угол в радианах в R31 ; корень0 (1, 0) из единицы в R37, R38, а R30 = 0 (номер корня) INTRIG: FPI * PM31 1 PM37 CX PM30 PM38 RTN ; получить следующий комплексный корень ; -> R37, R38 TRIG: PRM30 1 + PM30 PRM31 * FCOS PM37 FANS FSIN PM38 RTN ; рекурсивная реализация БПФ с комплексными отсчетами ; на стек - 3) индекс начального эл-та массива; 2) длина массива; 1) направление (1 - прямое, -1 - обратное) FFTC: RM9 KGSBA RMC M9 RM0 KGSBA RM1 KGSBA RM2 KGSBA RM3 KGSBA RM5 KGSBA RM6 KGSBA 3 KGSBD M3 2 KGSBD M1 2 - PX=0 L_4 RM3 2 + PGSB READC RM7 M0 RM8 M5 ; преобразование при длине = 2 и выход RM3 PGSB READC RM7 RM0 + RM7 RM0 - M0 <-> M7 RM8 RM5 + RM8 RM5 - M5 <-> M8 RM3 PGSB WRITEC RM0 M7 RM5 M8 RM3 2 + PGSB WRITEC PGOTO L_5 L_4: 1 KGSBD M2 RM3 RM1 + M6 RM1 2 / M1 RM3 KGSBA RM1 KGSBA RM2 KGSBA PGSB FFTC ; рекурсия на подмассивах половинной длины RM6 KGSBA RM1 KGSBA RM2 KGSBA PGSB FFTC RM2 RM1 / PGSB INTRIG L_6: RM6 PGSB READC ; преобразование бабочки PRM37 PRM38 PGSB MULT RM7 M0 RM8 M5 RM3 PGSB READC RM7 RM0 + RM7 RM0 - M0 <-> M7 RM8 RM5 + RM8 RM5 - M5 <-> M8 RM3 PGSB WRITEC RM0 M7 RM5 M8 RM6 PGSB WRITEC PGSB TRIG RM3 2 + M3 RM6 2 + M6 PFL1 L_6 L_5: KGSBB M6 KGSBB M5 KGSBB M3 KGSBB M2 KGSBB M1 KGSBB M0 KGSBB M9 RMC 3 + MC RTN ; дополнительная бабочка на массиве с действительными отсчетами ; на стек - направление (1 - прямое, -1 - обратное) FFTR: RM9 KGSBA RMC M9 RM0 KGSBA RM1 KGSBA RM2 KGSBA RM3 KGSBA RM5 KGSBA RM6 KGSBA RME 2 / 1 - M1 1 M6 KGSBD M3 RME / PGSB INTRIG PGSB TRIG L_7: RM6 2 * PGSB READC RM7 M0 RM8 M5 RM1 2 * RME + PGSB READC RM0 RM7 + RM7 RM0 - M2 <-> M0 RM5 RM8 - RM5 RM8 + M7 <-> M5 RM2 M8 PRM37 RM3 * PRM38 RM3 * PGSB MULT RM0 RM7 + 2 / RM0 RM7 - 2 / M7 <-> M0 RM5 RM8 + 2 / RM8 RM5 - 2 / M8 <-> M5 RM1 2 * RME + PGSB WRITEC RM0 M7 RM5 M8 RM6 2 * PGSB WRITEC PGSB TRIG KRM6 PFL1 L_7 RM3 3 + 4 / M3 0 PGSB READC RM7 RM8 + RM3 * RM7 RM8 - RM3 * M8 <-> M7 0 PGSB WRITEC KGSBB M6 KGSBB M5 KGSBB M3 KGSBB M2 KGSBB M1 KGSBB M0 KGSBB M9 RMC 1 + MC RTN ; окончательное БПФ на текущем массиве с действительными отсчетами ; на стек - направление (1 - прямое, -1 - обратное) ; на выходе усеченный массив с действительными (a_0, a_{N/2}) и комплексными a_1, a_2, ... a_{N/2-1} FFT: RM9 KGSBA RMC M9 RM3 KGSBA 1 KGSBD M3 FX<0 L_8 KGSBA PGSB FFTR L_8: PGSB REVERS 0 KGSBA RME KGSBA RM3 KGSBA PGSB FFTC RM3 FX>=0 L_9 RM3 KGSBA PGSB FFTR L_9: KGSBB M3 KGSBB M9 RMC 1 + MC RTN ; поэлементное произведение массивов ; на стек - 3) номер массива1; 2) номер массива2; 1) номер массива-результата CONVOL: RM9 KGSBA RMC M9 RM0 KGSBA RM1 KGSBA RM2 KGSBA RM3 KGSBA RM4 KGSBA RM5 KGSBA 3 KGSBD M1 2 KGSBD M2 1 KGSBD M3 RME 1 - M0 L_10: RM1 PKGSB24 RM0 2 * PGSB READC RM7 RME / M4 RM8 RME / M5 RM2 PKGSB24 RM0 2 * PGSB READC RM4 RM5 PGSB MULT RM3 PKGSB24 RM0 2 * PGSB WRITEC PFL0 L_10 RM1 PKGSB24 0 PGSB READC RM7 RME / M4 RM8 RME / M5 RM2 PKGSB24 0 PGSB READC RM7 RM4 * M7 RM8 RM5 * M8 RM3 PKGSB24 0 PGSB WRITEC KGSBB M5 KGSBB M4 KGSBB M3 KGSBB M2 KGSBB M1 KGSBB M0 KGSBB M9 RMC 3 + MC RTN ; округление к ближайшему целому ; число в RX, результат в RX ROUND: ENT KFRAC 2 F1/X - PX<0 L_11 FR KINT RTN L_11: FR KINT 1 + RTN ; округление всего текущего массива чисел ; параметров на стек нет ROUNDX: RM0 KGSBA RM4 KGSBA RME 2 * M0 CX M4 L_12: RM4 PGSB READR PGSB ROUND <-> PGSB WRITER KRM4 FL0 L_12 KGSBB M4 KGSBB M0 RTN ; нормализация текущего массива чисел - число целочисленных знаков в каждом эл-те не больше DIG ; параметров на стек нет NRML: RM0 KGSBA RM4 KGSBA RM5 KGSBA RME 2 * M0 CX M4 M5 L_13: RM4 PGSB READR RM5 + ENT PRM25 / KINT M5 PRM25 * - RM4 PGSB WRITER KRM4 FL0 L_13 KGSBB M5 KGSBB M4 KGSBB M0 RTN ; длинное перемножение массивов с помощью БПФ ; на стек - 3) номер массива1; 2) номер массива2; 1) номер массива-результата ; если номер массива1 или массива2 с отрицательным знаком, то для него БПФ не проводится (могло быть выполнено ранее) LMULT: RM9 KGSBA RMC M9 RM1 KGSBA RM2 KGSBA RM3 KGSBA 3 KGSBD M1 2 KGSBD M2 1 KGSBD M3 RM1 PX>=0 L_14 PKGSB24 1 KGSBA PGSB FFT GOTO L_15 ; БПФ для массива1 L_14: KABS M1 L_15: RM2 FX>=0 L_16 PKGSB24 1 KGSBA PGSB FFT GOTO L_17 ; БПФ для массива2 L_16: KABS M2 L_17: RM1 KGSBA RM2 KGSBA RM3 KGSBA PGSB CONVOL ; поэлементное произведение RM3 PKGSB24 1 +/- KGSBA PGSB FFT ; обратное БПФ PGSB ROUNDX PGSB NRML ; округление и нормализация KGSBB M3 KGSBB M2 KGSBB M1 KGSBB M9 RMC 3 + MC RTN ; очистка массива ; на стек - номер массива (с положительным знаком - очищается нижняя половина, с отрицательным - верхняя) CLEAR: RM9 KGSBA RMC M9 RM0 KGSBA RM4 KGSBA RME M0 CX M4 1 KGSBD M7 PX<0 L_18 KABS M7 RME M4 L_18: RM7 PKGSB24 L_19: 0 RM4 PGSB WRITER KRM4 PFL0 L_19 RM4 M7 KGSBB M4 KGSBB M0 KGSBB M9 RMC 1 + MC RTN ; копирование массива ; на стек - 2) номер массива-источника; 1) номер массива-назначения ; если номер массива-источника с отрицательным знаком, то копируется его верхняя половина в нижнюю половину назначения COPY: RM9 KGSBA RMC M9 RM0 KGSBA RM4 KGSBA RM5 KGSBA RME M0 CX M4 M5 2 KGSBD M7 FX<0 L_20 KABS M7 RME M4 L_20: 1 KGSBD M8 FX<0 L_21 KABS M8 RME M5 L_21: RM7 PKGSB24 RM4 PGSB READR RM8 PKGSB24 <-> RM5 PGSB WRITER KRM4 KRM5 FL0 L_21 RM4 M7 RM5 M8 KGSBB M5 KGSBB M4 KGSBB M0 KGSBB M9 RMC 2 + MC RTN ; затравка квадратного корня из целого числа n в массив 3 ; на стек - n INIT: RM9 KGSBA RMC M9 3 KGSBA PGSB CLEAR 1 KGSBD ENT FLG 2 / KINT 2 * F10^X / FSQRT PRM25 * 10 / KINT RM7 1 - PGSB WRITER KGSBB M9 RMC 1 + MC RTN ; деление на короткое число n ; на стек - 2) n; 1) номер массива DIV_N: RM9 KGSBA RMC M9 RM0 KGSBA RM4 KGSBA RM5 KGSBA RME M0 CX M4 2 KGSBD M5 1 KGSBD PKGSB24 L_22: RM0 1 - PGSB READR RM4 PRM25 * + ENT RM5 / KINT RM0 1 - PGSB WRITER <-> FR RM5 * - M4 FL0 L_22 KGSBB M5 KGSBB M4 KGSBB M0 KGSBB M9 RMC 2 + MC RTN ; умножение на короткое число n ; на стек - 2) n; 1) номер массива MUL_N: RM9 KGSBA RMC M9 RM0 KGSBA RM4 KGSBA RM5 KGSBA RM6 KGSBA RME M0 CX M4 M6 2 KGSBD M5 1 KGSBD PKGSB24 L_23: RM6 PGSB READR RM5 * RM4 + ENT PRM25 / KINT M4 PRM25 * - RM6 PGSB WRITER KRM6 FL0 L_23 KGSBB M6 KGSBB M5 KGSBB M4 KGSBB M0 KGSBB M9 RMC 2 + MC RTN ; вычитание из единицы ; на стек - номер массива SUB_1: RM9 KGSBA RMC M9 RM0 KGSBA RM4 KGSBA RM5 KGSBA RM6 KGSBA RME M0 CX M4 M5 M6 1 KGSBD PKGSB24 L_24: RM6 PGSB READR FX=0 L_25 RM5 PX!=0 L_26 FR L_25: +/- PRM25 + RM5 - 1 M5 FR L_26: RM6 PGSB WRITER KRM6 PFL0 L_24 KGSBB M6 KGSBB M5 KGSBB M4 KGSBB M0 KGSBB M9 RMC 1 + MC RTN ; длинное сложение ; на стек - 2) номер массива1; 1) номер массива2 (полож. знаки относятся к нижним половинам массивов, отриц. - к верхним) ; рез-т (сумма) в массиве2, см. также R7, R8 ; если R7 = 0, то добавлялся нулевой массив1, при R7 = 1 - нет ; если R8 = 0, то старший элемент массива1 нулевой LADD: RM9 KGSBA RMC M9 RM0 KGSBA RM2 KGSBA RM3 KGSBA RM4 KGSBA RM5 KGSBA RME M0 CX M2 M4 M5 2 KGSBD M7 FX<0 L_27 KABS M7 RME M4 L_27: 1 KGSBD M8 FX<0 L_28 KABS M8 RME M5 L_28: RM7 PKGSB24 RM4 PGSB READR M3 FX!=0 L_29 1 M2 L_29: RM8 PKGSB24 RM5 PGSB READR RM3 + RM5 PGSB WRITER KRM4 KRM5 PFL0 L_28 PGSB NRML ; нормализация RM2 M7 RM3 M8 KGSBB M5 KGSBB M4 KGSBB M3 KGSBB M2 KGSBB M0 KGSBB M9 RMC 2 + MC RTN ; итерация значения кв. корня x = n^{1/2} по формуле x_{i+1}= x_i + (1/2) x_i (1 - x_i^2 / n) ; на стек - n ; приближения - в массиве 3 ITERAT: RM9 KGSBA RMC M9 3 KGSBA 1 KGSBA PGSB COPY 1 +/- KGSBA PGSB CLEAR ; копия x_i из массива 3 в массив 1, очистка верхней половины массива 1 1 KGSBA PGSB FFT ; БПФ массива 1 1 KGSBA 2 KGSBA PGSB COPY 1 +/- KGSBA 2 +/- KGSBA PGSB COPY ; копия ПФ -> в массив 2 1 +/- KGSBA KGSBA 1 KGSBA PGSB LMULT ; в массиве 1 x_i^2 RME 2 * ME 1 KGSBD KGSBA 1 KGSBA PGSB DIV_N ; x_i^2 / n 100 KGSBA 1 KGSBA PGSB MUL_N ; перенос "запятой" на два знака 1 KGSBA PGSB SUB_1 ; 1 - x_i^2 / n RME 2 / ME 1 +/- KGSBA 1 KGSBA PGSB COPY 1 +/- KGSBA PGSB CLEAR ; не учитывается далее младшая половина массива 1 2 KGSBA 1 KGSBA PGSB DIV_N ; (1/2) (1 - x_i^2 / n) 1 KGSBA 2 +/- KGSBA 1 KGSBA PGSB LMULT ; (1/2) x_i (1 - x_i^2 / n) 1 +/- KGSBA 3 KGSBA PGSB LADD ; x_{i+1} - в массиве 3 KGSBB M9 RMC 1 + MC RTN ; длинный квадратный корень из n ; на стек - 2) n; 1) оконч. логдлина массива SQROOT: RM9 KGSBA RMC M9 RM1 KGSBA RM2 KGSBA 1 KGSBD M1 2 KGSBD M0 KGSBA PGSB INIT ; затравка кв. корня L_30: RME .NUM DIG * KSCR ; на экран - тек. число знаков RM0 KGSBA PGSB ITERAT ; итерации RM8 FX!=0 L_31 K- ; аварийный останов - что-то идет не так, если меняются старшие разряды x_i L_31: RM7 FX=0 L_30 PRM15 RM1 - PX!=0 L_32 3 KGSBA 3 +/- KGSBA PGSB COPY 3 KGSBA PGSB CLEAR RME 2 * ME PRM15 1 + PM15 ; если x_i при итерациях уже не меняется, то удвоить длины массивов! PGOTO L_30 L_32: KGSBB M2 KGSBB M1 KGSBB M9 RMC 2 + MC RTN ; золотое сечение ; параметров на стек нет GOLD: 2 KGSBA 3 KGSBA PGSB DIV_N ; поделить корень в массиве 3 на два RME 1 - PGSB READR PRM25 20 / + <-> PGSB WRITER ; и прибавить к старшей ячейке 1/2 RTN ; переупорядочение в конце работы ; параметров на стек нет REORD: RM0 KGSBA RM1 KGSBA RM4 KGSBA RM5 KGSBA RM6 KGSBA 1 KGSBA PGSB CLEAR 2 KGSBA PGSB CLEAR 2 +/- KGSBA PGSB CLEAR ; чистится всё, кроме массива 3 RME 1 - M0 8 ENT .NUM DIG / KINT M8 CX M6 ; теперь кол-во цифр в ячейке будет кратно DIG, но не больше восьми L_33: 3 PKGSB24 RM8 M1 CX M4 L_34: RM0 PX>=0 L_35 PGSB READR RM4 PRM25 * + M4 RM0 1 - M0 PFL1 L_34 1 PKGSB24 RM4 RM6 PGSB WRITER KRM6 ; рез-т переписывается в массив 1 - старшие разряды по младшим адресам PGOTO L_33 L_35: 3 KGSBA PGSB CLEAR ; очистка массива 3 GSB ORD ; дополнительно в случае блокнота KGSBB M6 KGSBB M5 KGSBB M4 KGSBB M1 KGSBB M0 RTN ; в случае блокнота рез-т из массива 1 (записи 0) распределяется по записям 0, 1, 2, 3 ORD: PKGSB44 RTN ORD1: RM6 M0 1 M5 CX M4 M6 ; блокнот L_36: 1 PKGSB24 RM6 PGSB READR M7 0 RM6 PGSB WRITER RM5 PKGSB24 RM7 RM4 PGSB WRITER KRM5 RM5 5 - FX=0 L_37 1 M5 KRM4 L_37: KRM6 FL0 L_36 ORD2: RTN ; заглушка, если регистры