Timp estimat de citire: 12-13 minute
„Algoritmul etern”
După ce am vorbit atât despre limbaje, despre dump-uri, despre mape cu listinguri și despre șuruburi și chei, e timpul să arăt concret ce înseamnă „același lucru, spus în cinci feluri.”
Am ales un singur algoritm. L-am numit „algoritmul etern” pentru că este, probabil, cea mai veche idee din programare care funcționează neschimbată de peste șaizeci de ani: căutarea prin dihotomie — binary search.
Principiul e de o simplitate care te face să bănuiești că se ascunde ceva: împarte spațiul în două, elimină jumătatea greșită, repetă. Cu fiecare pas, problema se înjumătățește. Dintr-o tabelă de un milion de elemente, găsești ce cauți în cel mult douăzeci de pași. Nu e magie. E matematică, și e frumoasă.
Am scris aceeași rutină în cinci limbaje pe care le-am folosit de-a lungul anilor. Toate caută o cheie (KEY) într-o tabelă sortată crescător (TABLE) de N elemente întregi. Returnează indexul elementului găsit sau zero dacă nu există. Același adevăr, cinci gramatici.
1. FORTRAN IV (IBM, 1962)
FORTRAN a fost limba mea de debut serios. Era limbajul calculelor — conceput de ingineri, pentru ingineri. Numele variabilelor: maximum șase caractere. Tablourile indexate de la 1, nu de la 0. Nu exista DO WHILE; aveai IF și GO TO, singurele unelte pentru o buclă condiționată. Iar construcția emblematică era IF-ul aritmetic: o singură instrucțiune care evalua o expresie și sărea pe trei căi diferite — negativ, zero, pozitiv. Trei destine dintr-un singur rând. Elegant, criptic, eficient.
Apelul subrutinei: CALL BSRCH(TABLE, N, KEY, IPOS). Parametrii se transmit prin referință — adică adrese, nu valori.
C-------------------------------------------------------------
C BINARY SEARCH IN A SORTED INTEGER TABLE
C FORTRAN IV - IBM SYSTEM/360
C
C PARAMETERS:
C TABLE - SORTED INTEGER ARRAY (ASCENDING)
C N - NUMBER OF ELEMENTS
C KEY - VALUE TO SEARCH FOR
C IPOS - RESULT: INDEX (1..N) OR 0 IF NOT FOUND
C-------------------------------------------------------------
SUBROUTINE BSRCH(TABLE, N, KEY, IPOS)
INTEGER TABLE(N), N, KEY, IPOS
INTEGER LOW, IHI, MID
C
C INITIALIZE BOUNDS
C
LOW = 1
IHI = N
IPOS = 0
C
C MAIN SEARCH LOOP
C
10 IF (LOW .GT. IHI) GO TO 30
MID = (LOW + IHI) / 2
IF (KEY - TABLE(MID)) 20, 25, 22
C
C KEY < TABLE(MID): SEARCH LEFT HALF
C
20 IHI = MID - 1
GO TO 10
C
C KEY > TABLE(MID): SEARCH RIGHT HALF
C
22 LOW = MID + 1
GO TO 10
C
C KEY = TABLE(MID): FOUND
C
25 IPOS = MID
C
30 RETURN
END
2. COBOL (IBM, 1960)
COBOL era cealaltă lume. Dacă FORTRAN vorbea limba inginerilor, COBOL vorbea limba contabililor și a economiștilor. Verbos prin natură, dar perfect lizibil cincizeci de ani mai târziu — un auditor din 1975 putea citi programul fără pregătire de programare. Nu avea aritmetică pe indici în mod natural; totul trecea prin COMPUTE. Bucla era PERFORM ... UNTIL, iar echivalentul switch/case era EVALUATE TRUE, cu fiecare WHEN testând o condiție. Tablourile, ca și în FORTRAN, indexate de la 1. Datele se declarau în WORKING-STORAGE, cu tipuri descrise prin PIC — picture clause — de parcă fiecare câmp trebuia legitimat la intrare.
IDENTIFICATION DIVISION.
PROGRAM-ID. BSEARCH.
*---------------------------------------------------------
* BINARY SEARCH IN A SORTED TABLE
* COBOL-68 / IBM OS/360
*---------------------------------------------------------
DATA DIVISION.
WORKING-STORAGE SECTION.
01 WS-TABLE.
05 WS-ENTRY PIC 9(8)
OCCURS 1000 TIMES.
01 WS-TABLE-SIZE PIC 9(4).
01 WS-SEARCH-KEY PIC 9(8).
01 WS-RESULT-POS PIC S9(4) VALUE ZERO.
01 WS-FOUND-FLAG PIC X(1) VALUE 'N'.
01 WS-LOW PIC 9(4).
01 WS-HIGH PIC 9(4).
01 WS-MID PIC 9(4).
01 WS-DONE-FLAG PIC X(1) VALUE 'N'.
PROCEDURE DIVISION.
BINARY-SEARCH-PARA.
MOVE 1 TO WS-LOW
MOVE WS-TABLE-SIZE TO WS-HIGH
MOVE ZERO TO WS-RESULT-POS
MOVE 'N' TO WS-FOUND-FLAG
MOVE 'N' TO WS-DONE-FLAG
PERFORM SEARCH-LOOP
UNTIL WS-DONE-FLAG = 'Y'
STOP RUN.
SEARCH-LOOP.
IF WS-LOW > WS-HIGH
MOVE 'Y' TO WS-DONE-FLAG
ELSE
COMPUTE WS-MID =
(WS-LOW + WS-HIGH) / 2
EVALUATE TRUE
WHEN WS-SEARCH-KEY <
WS-ENTRY(WS-MID)
COMPUTE WS-HIGH =
WS-MID - 1
WHEN WS-SEARCH-KEY >
WS-ENTRY(WS-MID)
COMPUTE WS-LOW =
WS-MID + 1
WHEN WS-SEARCH-KEY =
WS-ENTRY(WS-MID)
MOVE WS-MID TO WS-RESULT-POS
MOVE 'Y' TO WS-FOUND-FLAG
MOVE 'Y' TO WS-DONE-FLAG
END-EVALUATE
END-IF.
3. ALGOL 60 (1960)
ALGOL a fost limbajul academic — publicat în articole, rareori compilat pe aceeași mașină de două ori la fel. Nu l-am folosit în producție, dar l-am studiat și respectat. Sintaxa cu begin/end și := a influențat Pascal, C, și tot ce a urmat. Operatorul ÷ era împărțirea întreagă. Distincția între atribuire (:=) și comparație (=) — pe care FORTRAN o ignora și care a generat bug-uri decenii la rând — era deja clară în ALGOL. Funcția returna valoarea prin numele procedurii: bsearch := mid. Eleganță matematică pură.
comment -------------------------------------------------
BINARY SEARCH IN A SORTED INTEGER ARRAY
ALGOL 60
Returns index (1..n) if found, 0 if not found
---------------------------------------------------------;
integer procedure bsearch(t, n, key);
value n, key;
integer array t;
integer n, key;
begin
integer low, high, mid;
low := 1;
high := n;
bsearch := 0;
while low <= high do
begin
mid := (low + high) ÷ 2;
if key < t[mid] then
high := mid - 1
else if key > t[mid] then
low := mid + 1
else
begin
bsearch := mid;
low := high + 1 comment force exit;
end
end
end bsearch;
4. ASSEMBLER IBM System/360 — Cu Linkage Standard OS/360
Aceasta este rutina centrală — cea de care vorbeam în capitolele anterioare. Scrisă în Assembler, apelabilă atât din FORTRAN cât și din COBOL, fără să știe și fără să-i pese cine o cheamă. Respectă doar convenția.
Convenția de linkage OS/360: la intrare, R1 pointează la lista de parametri (patru adrese consecutive), R13 la Save Area a apelantului, R14 e adresa de retur, R15 e adresa de intrare. La ieșire, R15 conține codul retur: 0 înseamnă găsit, 4 înseamnă negăsit. Rezultatul se depune direct în cuvântul pointat de al patrulea parametru. Ultimul pointer are bitul de semn setat — marca standard OS/360 pentru „ultimul parametru din listă.”
Instrucțiuni cheie: SRA R10,1 — shift right arithmetic cu un bit, adică împărțire la 2, mai rapidă decât instrucțiunea D (divide). BCTR R4,0 — decrementează R4 cu 1, fără salt. SLA R4,2 — shift left cu doi biți, adică înmulțire cu 4 (dimensiunea unui fullword). C R7,0(R4,R2) — compară R7 cu fullword-ul de la adresa R2+R4, adresare indexată.
BSRCH CSECT
*=======================================================
* BINARY SEARCH - SORTED FULLWORD TABLE
* IBM SYSTEM/360 ASSEMBLER - OS/360 STANDARD LINKAGE
*
* CALLABLE FROM FORTRAN IV AND COBOL
*
* PARAMETERS VIA R1 (STANDARD OS/360):
* +0 A(TABLE) - ADDRESS OF SORTED FULLWORD ARRAY
* +4 A(N) - ADDRESS OF FULLWORD: ELEMENT COUNT
* +8 A(KEY) - ADDRESS OF FULLWORD: SEARCH KEY
* +12 A(IPOS) - ADDRESS OF FULLWORD: RESULT INDEX
* (1..N IF FOUND, 0 IF NOT FOUND)
*
* RETURN CODE IN R15: 0=FOUND, 4=NOT FOUND
*=======================================================
*
*--- STANDARD ENTRY LINKAGE ---
*
STM R14,R12,12(R13) SAVE CALLER'S REGISTERS
LR R12,R15 ESTABLISH BASE REGISTER
USING BSRCH,R12
LA R11,SAVEAREA OUR SAVE AREA
ST R13,4(,R11) BACKWARD CHAIN
ST R11,8(,R13) FORWARD CHAIN
LR R13,R11 R13 -> OUR SAVE AREA
*
*--- LOAD PARAMETER ADDRESSES ---
*
L R2,0(,R1) R2 = A(TABLE)
L R3,4(,R1) R3 = A(N)
L R4,8(,R1) R4 = A(KEY)
L R5,12(,R1) R5 = A(IPOS) (HI BIT ON)
LA R5,0(,R5) CLEAR HIGH-ORDER BIT
*
*--- LOAD VALUES ---
*
L R6,0(,R3) R6 = N (ELEMENT COUNT)
L R7,0(,R4) R7 = KEY (SEARCH VALUE)
*
*--- INITIALIZE: LOW=1, HIGH=N ---
*
LA R8,1 R8 = LOW = 1
LR R9,R6 R9 = HIGH = N
*
*--- MAIN LOOP ---
*
LOOP CR R8,R9 LOW > HIGH?
BH NOTFND YES: NOT FOUND
*
* MID = (LOW + HIGH) / 2
*
LR R10,R8 R10 = LOW
AR R10,R9 R10 = LOW + HIGH
SRA R10,1 R10 = (LOW+HIGH)/2 = MID
*
* COMPUTE TABLE OFFSET: (MID-1)*4
*
LR R4,R10 R4 = MID
BCTR R4,0 R4 = MID - 1
SLA R4,2 R4 = (MID-1) * 4
*
* COMPARE KEY WITH TABLE(MID)
*
C R7,0(R4,R2) COMPARE KEY : TABLE(MID)
BL GOLEFT KEY < TABLE(MID)
BH GORIGHT KEY > TABLE(MID)
*
*--- FOUND: STORE MID IN IPOS, RC=0 ---
*
ST R10,0(,R5) IPOS = MID
SR R15,R15 RC = 0 (FOUND)
B RETURN
*
*--- KEY < TABLE(MID): HIGH = MID - 1 ---
*
GOLEFT LR R9,R10 HIGH = MID
BCTR R9,0 HIGH = MID - 1
B LOOP
*
*--- KEY > TABLE(MID): LOW = MID + 1 ---
*
GORIGHT LR R8,R10 LOW = MID
LA R8,1(,R8) LOW = MID + 1
B LOOP
*
*--- NOT FOUND: IPOS = 0, RC=4 ---
*
NOTFND SR R10,R10 R10 = 0
ST R10,0(,R5) IPOS = 0
LA R15,4 RC = 4 (NOT FOUND)
*
*--- STANDARD EXIT LINKAGE ---
*
RETURN L R13,4(,R13) RESTORE CALLER'S R13
L R14,12(,R13) RESTORE R14 (RETURN ADDR)
LM R0,R12,20(R13) RESTORE R0-R12
BR R14 RETURN TO CALLER
*
*--- CONSTANTS AND WORK AREAS ---
*
SAVEAREA DS 18F OUR SAVE AREA
*
*--- REGISTER EQUATES ---
*
R0 EQU 0
R1 EQU 1
R2 EQU 2
R3 EQU 3
R4 EQU 4
R5 EQU 5
R6 EQU 6
R7 EQU 7
R8 EQU 8
R9 EQU 9
R10 EQU 10
R11 EQU 11
R12 EQU 12
R13 EQU 13
R14 EQU 14
R15 EQU 15
END BSRCH
Apelul din FORTRAN:
INTEGER TABLE(1000), N, KEY, IPOS
EXTERNAL BSRCH
C ...
CALL BSRCH(TABLE, N, KEY, IPOS)
C IPOS = INDEX (1..N) SAU 0 DACA NU EXISTA
Apelul din COBOL:
01 WS-TABLE.
05 WS-ENTRY PIC S9(8) COMP
OCCURS 1000 TIMES.
01 WS-N PIC S9(8) COMP.
01 WS-KEY PIC S9(8) COMP.
01 WS-IPOS PIC S9(8) COMP.
*
PROCEDURE DIVISION.
CALL 'BSRCH' USING WS-TABLE
WS-N
WS-KEY
WS-IPOS.
* WS-IPOS = INDEX (1..N) OR 0
Observație critică pentru linkage-ul dual: COBOL PIC S9(8) COMP este identic cu INTEGER din FORTRAN — un fullword binar cu semn. Ambele limbaje transmit parametrii prin referință. Rutina Assembler nu știe și nu trebuie să știe cine o apelează.
5. MACRO-11 (DEC PDP-11, 1970)
Altă mașină, altă lume. PDP-11: arhitectură pe 16 biți, little-endian, opt registre (R0–R7, unde R6 e stack pointer-ul, R7 e program counter-ul). Instrucțiunile operează pe words de 2 bytes, nu fullwords de 4. Nu există Save Area ca pe /360 — se folosește stiva. Parametrii se transmit pe stivă, rezultatul se returnează în R0.
Instrucțiuni cheie: ASR — arithmetic shift right, echivalentul SRA de pe /360. ASL — shift left, înmulțire cu 2 (un word, nu 4 bytes). CMP R1,(R3) — compară R1 cu conținutul de la adresa din R3; parantezele înseamnă indirect, adică dereferențiere. MOV R3,-(SP) — push pe stivă cu auto-decrement. MOV (SP)+,R0 — pop cu auto-increment. Și un detaliu care te poate înnebuni dacă nu știi: numerele sunt în octal. 10(SP) înseamnă octal 10, adică zecimal 8.
Apelul tipic:
MOV #TABLE,-(SP) ; PUSH ADDRESS OF TABLE
MOV N,-(SP) ; PUSH ELEMENT COUNT
MOV KEY,-(SP) ; PUSH SEARCH KEY
JSR PC,BSRCH ; CALL
ADD #6,SP ; CLEAN STACK (3 PARAMS * 2)
; R0 = RESULT (INDEX OR 0)
;=======================================================
; BINARY SEARCH - SORTED WORD TABLE
; MACRO-11 / PDP-11 / RT-11
;
; STACK PARAMETERS (PUSHED RIGHT TO LEFT):
; 6(SP) = ADDRESS OF SORTED WORD ARRAY
; 4(SP) = N (ELEMENT COUNT)
; 2(SP) = KEY (SEARCH VALUE)
;
; RETURNS: R0 = INDEX (1..N) IF FOUND, 0 IF NOT
;=======================================================
BSRCH: MOV R1,-(SP) ; SAVE REGISTERS
MOV R2,-(SP)
MOV R3,-(SP)
MOV R4,-(SP)
;
; LOAD PARAMETERS (OFFSET ADJUSTED FOR 4 SAVED REGS)
;
MOV 14(SP),R4 ; R4 = ADDRESS OF TABLE
MOV 12(SP),R3 ; R3 = N
MOV 10(SP),R1 ; R1 = KEY
;
; INITIALIZE: LOW=1, HIGH=N
;
MOV #1,R0 ; R0 = LOW = 1
MOV R3,R2 ; R2 = HIGH = N
;
; MAIN LOOP
;
LOOP: CMP R0,R2 ; LOW > HIGH?
BGT NOTFND ; YES: NOT FOUND
;
; MID = (LOW + HIGH) / 2
;
MOV R0,R3 ; R3 = LOW
ADD R2,R3 ; R3 = LOW + HIGH
ASR R3 ; R3 = (LOW+HIGH)/2 = MID
;
; COMPUTE TABLE OFFSET: (MID-1)*2 (WORD SIZE)
;
MOV R3,-(SP) ; SAVE MID ON STACK
DEC R3 ; R3 = MID - 1
ASL R3 ; R3 = (MID-1) * 2
ADD R4,R3 ; R3 = ADDR OF TABLE(MID)
;
; COMPARE KEY WITH TABLE(MID)
;
CMP R1,(R3) ; KEY : TABLE(MID)
BLT GOLEFT
BGT GORIGHT
;
; FOUND: R0 = MID
;
MOV (SP)+,R0 ; R0 = MID (POP SAVED MID)
BR DONE
;
; KEY < TABLE(MID): HIGH = MID - 1
;
GOLEFT: MOV (SP)+,R2 ; R2 = MID (POP)
DEC R2 ; HIGH = MID - 1
BR LOOP
;
; KEY > TABLE(MID): LOW = MID + 1
;
GORIGHT:MOV (SP)+,R0 ; R0 = MID (POP)
INC R0 ; LOW = MID + 1
BR LOOP
;
; NOT FOUND: R0 = 0
;
NOTFND: CLR R0 ; R0 = 0
;
; RESTORE AND RETURN
;
DONE: MOV (SP)+,R4 ; RESTORE REGISTERS
MOV (SP)+,R3
MOV (SP)+,R2
MOV (SP)+,R1
RTS PC ; RETURN
;
.END
Același adevăr, cinci gramatici
Fiecare limbaj impune propriile constrângeri, dar algoritmul rămâne identic: inițializează limitele, calculează mijlocul, compară, ajustează, repetă. De la IF-ul aritmetic al FORTRAN-ului la SRA al /360, de la EVALUATE al COBOL-ului la ASR al PDP-11, aceeași logică traversează mașinile și deceniile neschimbată.
E, într-adevăr, un algoritm etern.