Useremo un metodo più veloce che usa la
rappresentazione binaria bk-1bk-2 …b1b0 di
N per scomporre la potenza come segue
X X
N
X
bk 1 2 k 1  bk 2 2 k 2 ...  b1 21  b0 20
bk 1 2 k 1
dove X
bi 2i
X
bk 2 2 k 2
1
  2i
X
 ...  X
b1 21
se bi  0
se bi  1
X
b0 20
Per calcolare:
X
N
X
bk 1 2 k 1
X
bk 2 2 k 2
 ...  X
R4  1.0
R4  X
R4  X
R4  X
b0 2 0
b1 21
b2 2 2
b1 21
X
R2  X
se b0  0
 R4

R4  R2 se b0  1
X
X
b0 20
b1 21
se b1  0
 R4

R4  R2 se b1  1
X
b0 20
20
b0 20
1
 X1  X
R2  X  X 2  R2  R2
21
R2  X
22
 X 4  R2  R2
se b2  0
 R4

R4  R2 se b2  1
R2  X  X 8  R2  R2
23
X: FLOAT ;
N: INT ;
Ris: FLOAT ;
Due : INT 2;
Unofl: FLOAT 1.0;
READ STINP X;
READ STINP N;
LOAD R0 Due;
SUB R0 R0;
LOAD R1 Due;
LOAD R2 X;
LOAD R3 N;
LOAD R4 Unofl;
LOAD R5 Due;
X:
N:
Ris:
Due:
Unofl:
3,0
?
?
5
?
2
1,0
R0:
R1:
R2:
R3:
R4:
R5:
2
?
0
?
2
RC:
3,0
?
?
5
1,0
?
?
2
?
Ciclo: COMP R3 R0;
BREQ Esci;
SUB R5 R5;
ADD R5 R3;
MOD R5 R1;
COMP R5 R0;
BREQ Pari;
FMULT R4 R2;
Pari: FMULT R2 R2;
DIV R3 R1;
BRANCH Ciclo;
X:
N:
Ris:
Due:
Unofl:
3,0
5
?
2
1,0
R0:
R1:
R2:
R3:
R4:
R5:
0
2
RC:
6561,0
81,0
3,0
9,0
5
2
1
0
243,0
1,0
3,0
5
2
1
0
?
1
0
Esci: STORE R4 Ris;
WRITE STOUT Ris;
STOP;
X:
N:
Ris:
Due:
Unofl:
3,0
5
243,0
?
2
1,0
R0:
R1:
R2:
R3:
R4:
R5:
0
2
RC:
6561,0
0
243,0
1
0
flowchart
READ STINP X;
READ STINP N;
LOAD R0 Due;
SUB R0 R0;
LOAD R1 Due;
LOAD R2 X;
LOAD R3 N;
LOAD R4 Unofl;
LOAD R5 Due;
R3 = R0?
NO
STORE R4 Ris;
WRITE STOUT Ris;
STOP;
SUB R5 R5;
ADD R5 R3;
MOD R5 R1;
R5 = R0?
NO
Quante volte
viene ripetuto
il ciclo?
SI
FMULT R4 R2;
FMULT R2 R2;
DIV R3 R1;
SI
All’inizio R3 = n (intero), ad ogni iterazione
R3 è diviso per 2 e ci si ferma quando R3 = 0,
ossia quando il un numero di iterazioni k
eseguite è tale che 2k  n ma 2k+1 > n.
Quindi il ciclo viene ripetuto k  log2 n volte.
Il tempo calcolo richiesto aumenterà
proporzionalmente a log2 n.
Diciamo che il programma ha complessità
tempo O(log2 n).
Come aumenta il tempo al variare di n.
(Processore a 1 Mips.)
Tabelle complessità
NumIstr(n)
n=10
n=100
n=1000
n=106
n=109
log2 n
3 s
6 s
9 s
18 s
27 s
n
10 s
100 s
1 ms
1s
17 m
n2
100 s
10 ms
1s
278 ore
>3·104
anni
n3
1 ms
1s
17 m
>3·107
anni
2n
1 ms
>1016
anni
10n
17 min
>1092
anni
Massimo N che richiede tempo  1 sec.
A = processore a 1 Mips
B = processore a 1 Gips
C = processore a 1 Tips
NumIstr(n)
A: 1 Mips
B: 1 Gips
C: 1 Tips
log2 n
N=21000000
N=21000000000
N=21000000000000
n
N=106
N=109
N=1012
n2
N=1000
N=31623
N=106
n3
N=100
N=1000
N=10000
2n
N=20
N=30
N=40
10n
N=6
N=9
N=12
La CPU non “capisce”
l’assembler !!
il programma assembler deve essere
tradotto in un programma macchina
programma
assembler
assemblatore
macchina
hardware
Assemblatore e caricatore
Programma assembler P
Assemblatore
Programma P in linguaggio
macchina (con indirizzi RAM
simbolici) su disco
Caricatore
Programma P in linguaggio
macchina con indirizzi in RAM
CPU
Risultati
Dati D
Programma assembler P
Dati D
interprete
Gli stessi risultati che si otterrebbero
eseguendo il programma P con i dati D
Siccome la CPU “MINIMA” è una CPU virtuale
noi usiamo un interprete per eseguire i programmi
assembler.
OSSERVAZIONE
Il programma assemblatore legge un programma
in assembler e il programma interprete legge sia
un programma che i dati per tale programma.
Esistono quindi programmi che hanno programmi
come dati.
Ha senso quindi cercare un programma Test che
sia in grado di leggere un qualsiasi programma P
e i relativi dati D e dire se, eseguendo il
programma P con i dati D, esso termina oppure
entra in un ciclo infinito e quindi non termina.
Test
READ INP P
READ INP D
P(D) termina?
WRITE OUT “SI”
WRITE OUT “NO”
Il programma Copia legge un programma P e
stampa due copie dello stesso programma P.
Componendolo con un interprete Iterpr
otteniamo il programma Riflex che con input
un programma P lo esegue con dati il
programma stesso P.
P
P
READ INP P
Copia
WRITE OUT P
WRITE OUT P
PP
Copia
Riflex
PP
Interpr
P(P)
Usando il programma ipotetico Test ed il
programma Riflex costruiamo un
programma Assurdo nel modo seguente.
P
Assurdo
READ INP P
Prefix
P
WRITE OUT Riflex
Prefix
WRITE OUT P
Riflex P
Si o No
Test
READ INP RISP
Invert
Riflex P
Si o No
Si
RISP?
No
Invert
Quindi il programma Assurdo, con input un
qualsiasi programma P, si comporta nel modo
seguente:
Se P con input P non termina allora Assurdo
con input P termina.
Se P con input P termina allora Assurdo con
input P non termina.
Se Assurdo con input Assurdo non termina
allora Assurdo con input Assurdo termina.
Se Assurdo con input Assurdo termina allora
Assurdo con input Assurdo non termina.