Pseudokod programa

Ideja ovog programa je da se izvede celobrojno deljenje na način blizak samom hardveru.

Ovaj algoritam se, između ostalog, zasniva na tome da je operacija šiftovanja (pomeranja) datog broja udesno za n mesta ekvivalentna celobrojnom deljenju tog broja sa n-tim stepenom dvojke, a šiftovanje ulevo za n mesta ekvivalentna množenju sa n-tim stepenom dvojke, pri čemu je ta operacija efikasnija od drugih operacija.

Algoritam se sastoji iz dva dela:

• U prvom delu se određuje n takvo da je y*2ⁿ najmanji broj veći od ili jednak x.

• U drugom delu se vrši brojanje koliko puta se y sadrži u x. Umesto da se to čini tako što se x svaki put umanjuje za y, x se svaki put umanjuje za y*2ⁿ za, u tom trenutku, najveće moguće n za koje je y*2ⁿ manje od ili jednako x. Na taj način, umesto da se 2ⁿ puta od x oduzima y, samo jednom se od x oduzme y*2ⁿ, čime se dobija na efikasnosti. Pri tome se počinje od onog n koje je dobijeno u prvom delu programa. Vrednost n se u svakom koraku umanjuje za jedan, ispituje se da li je y*2ⁿ manje ili jednako od x i ako jeste onda se x umanjuje za tu vrednost. Postupak se ponavlja sve dok n ne dobije vrednost 0, to jest sve dok y*2ⁿ ne dobije vrednost y. Kako je operacija šiftovanja brža od operacije oduzimanja, u svakom koraku, umesto da se n smanjuje za jedan dok ne dobije vrednost 0, vrednost 2ⁿ se deli sa dva, tj. šiftuje udesno za jedan, sve dok ne dobije vrednost 1.

Imajući ovo u vidu, program treba da prođe sledeće korake tokom izvršavanja:

{x ≥ 0, y > 0}
Korak 1: Promenljivu q inicijalno postaviti na 0,
         promenljivu r inicijalno postaviti na x,
         promenljivu z1 inicijalno postaviti na y,
         promenljivu z2 inicijalno postaviti na 1.
Korak 2: Ukoliko je z1 < r,
         preći na korak 3,
         inače preći na korak 4.
Korak 3: Promenljivu z1 postaviti na 2 * z1,
         promenljivu z2 postaviti na 2 * z2.
         Vratiti se na korak 2.
Korak 4: Ukoliko je z1 ≤ r, odnosno z1 = r,
         preći na korak 5,
         inače preći na korak 6. 
Korak 5: Promenljivu r postaviti na r - z1,
         promenljivu q postaviti na q + z2.
         Preći na korak 6.
Korak 6: Ukoliko je z2 različito od 1,
         preći na korak 7,
         inače preći na korak 8.
Korak 7: Promenljivu z1 postaviti na z1 / 2,
         promenljivu z2 postaviti na z2 / 2.
         Preći na korak 4.
Korak 8: Kraj
{x = q * y + r, 0 ≤ r < y}

{x ≥ 0, y > 0}
q = 0;
r = x;
z1 = y;
z2 = 1;
while (z1 < r) do   
  begin
    z1 = 2 * z1;
    z2 = 2 * z2;
  end
if(z1 ≤ r)
  begin
    r = r - z1;
    q = q + z2;
  end
while (z2 ≠ 1) do
  begin
    z1 = z1 / 2;
    z2 = z2 / 2;
    if(z1 ≤ r)
      begin
        r = r - z1;
        q = q + z2;
      end
  end	
{x = q * y + r, 0 ≤ r < y}

Kao i u prethodnim primerima, postavlja se pitanje ispravnosti ovog programa. Da li će ovaj program zaista izračunati vrednosti celobrojnog deljenja dva prirodna broja x i y zadatih na ulazu?

Naredna: Invarijanta petlje (izvođenje iz brojača) Gore: Hardverdsko celobrojno deljenje Prethodna: Specifikacija   Sadržaj