(1) Il numero di operazioni richieste per l’intero calcolo sara’ dato dalla somma dei tempi impiegati per eseguire gli n prodotti di numeri naturali e del tempo successivamente impiegato per sommare gli n numeri ottenuti da tali prodotti. Per ciascun prodotto il tempo sara’ stimato da

O(log a_{i} log b_{i}) = O(n^{3} · n^{3}) = O(n^{6}).

Per eseguire gli n prodotti il tempo sará dunque

n · n^{6} = O(n^{7}).

Inoltre ciascun prodotto fornisce un numero minore di e^{n^{3}} e^{n^{3}} = e^{2n^{3}}. Per sommare n numeri minori di e^{2n^{3}} si impiegherá un tempo del tipo O(n^{3} log n). In tutto si sono avute O(n^{7}) operazioni bit.

(2) Il numero dato n ha 10 cifre binarie, ovvero risulta 2^{9} ⩽ n < 2^{10}, dunque si ha 2^{4} < ⌊\sqrt{n}⌋ < 2^{5}. Quindi ⌊\sqrt{n}⌋ ha 5 cifre decimali e la prima é 1. L’algoritmo consente di fare solo altri 4 controlli per determinare le altre 4 cifre (invece, con una strategia ingenua ”a tappeto” sarebbero necessari fino a 2^{4} controlli, ovvero tutti i casi possibili). Infatti si tratta di determinare le 4 cifre rimanenti, partendo da quella piú ”a sinistra”, verificando se il quadrato del numero binario 11000 supera o no n. Poiche’ non lo supera la seconda cifra é 1. Per trovare la terza si guarda se il quadrato di 11100 supera n. Dato che lo supera, la terza cifra e’ 0. Si prosegue in questo modo e si trova ⌊\sqrt{n}⌋ = 11000, in forma binaria.

(3) Visto che 16 = 2^{4}, basta scrivere in base 16 ciascun gruppetto di 4 cifre binarie del numero dato, a partire dalle unitá (ovvero ”da destra”). Dato che (1011)_{2} = (B)_{16} , (0010)_{2} = (2)_{16} e (1)_{2} = (1)_{16}, si ha che il numero in base 16 si scrive 12B.

(4) Si ha:

125 = 4 · 30 + 5
30 = 6 · 5 + 0,

quindi (125, 30) = 5. Per l’identitá di Bezout, ripercorrere a ritroso le uguaglianze trovate (esclusa l’ultima, che ha resto nullo), che esprimono il resto come combinazione lineare del dividendo e del divisore. In questo caso, si ha, al primo passo, 5 = 125−4·30.

Typeset by AMS-TEX