SICP – cap. 1 – Costruire astrazioni tramite procedure – esercizi – 20

3000

Continuo da qui, oggi esercizi, qui.

Exercise 1.16: Design a procedure that evolves an iterative exponentiation process that uses successive squaring and uses a logarithmic number of steps, as does fast-expt. (Hint: Using the observation that (bn/2)2 = (b2)n/2, keep, along with the exponent n and the base b, an additional state variable a, and define the state transformation in such a way that the product a bn is unchanged from state to state. At the beginning of the process a is taken to be 1, and the answer is given by the value of a at the end of the process. In general, the technique of defining an invariant quantity that remains unchanged from state to state is a powerful way to think about the design of iterative algorithms.)

Uh! 😳 non so voi ma che ne dite di sbirciare i nostri maestri?

Forse l’esercizio è troppo semplice (per i nerds), ecco la versione di Bill:

s31

e quella di Weiqun:

s32

Una piccola modifica per rendere perfetta quella di Weiqun (la mia preferita, tiene locali le procedure ausiliarie):

s33

OK 😀 sì, sono stato un pasticcione; inizialmente avevo dato per scontata square (come fa Weiqun), c’era nella sessione, quella definita da Bill e quindi girava; ma da dove viene il risultato reale? attenzione alle condizioni iniziali 😳

Pausa 😀

Aggiornamento: c’è uno script in JavaScript che Maurizio ha postato nei commenti. Purtroppo non viene visualizzato correttamente per cui lo metto qui.

/*
Calcolo espnenziale con la formula:
    b^n = (b^2)^(n/2)
*/
// versione ricorsiva
function exp1(b, n) {
    if (n < 1)
        return 1;
    if (n % 2)  // se dispari
        return b * exp(b, n - 1);
    return exp(b * b, n / 2);
}

// versione iterativa
function exp(b, n) {
    var a = 1;
    while (n > 0) {
        if (n % 2) {    // se n è dispari
            a *= b;
            n--;
        } else {
            b *= b;
            n /= 2; 
        }
    }
    return a;
}

function printExp(a, b) {
    document.write(
        "exp(" + a + ", " + b + ") = (iterativa): " + exp(a, b) 
        + " (ricorsiva: " + exp1(a, b) + ")<br>");
}


printExp(2, 10);
printExp(7, 7);
printExp(17, 17);

:mrgreen:

Posta un commento o usa questo indirizzo per il trackback.

Commenti

  • Maurizio.  Il 19 maggio 2016 alle 10:32

    Non capisco un tubo di Phyton, ma… è sicuro che le procedure siano iterative, come viene richiesto? A me sembrano ricorsive.

    • juhan  Il 19 maggio 2016 alle 10:39

      Credo che ci sia una correzione da apportare s/Python/Lisp/ dove in particolare Lisp è da intendersi come famiglia di linguaggi, in questo caso Scheme o, più in dettaglio, Racket.
      Poi sì expt-iter è iterativa come raccontato nel SICP.

  • Maurizio.  Il 19 maggio 2016 alle 11:19

    Con un linguaggetto semplice semplice come il javascript lo avrei fatto così:

    per qualche motivo il codice js non viene riportato giusto, ho messo lo script in fondo al post come aggiornamento.
    Juhan

  • Maurizio.  Il 19 maggio 2016 alle 11:27

    E il programmino è stato tagliato proprio nel mezzo oltre che modificato qua e là. Bah… vedi commento precedente

    • juhan  Il 19 maggio 2016 alle 11:36

      OOPS! sono stato io; se mi mandi una mail @ n1n0 [dot] aegis [at] gmail.com con il codice lo metto giusto. Altrimenti vedo se riesco a recuperare la versione originale. vedi commenti precedenti

Trackback

Rispondi

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione /  Modifica )

Google photo

Stai commentando usando il tuo account Google. Chiudi sessione /  Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione /  Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione /  Modifica )

Connessione a %s...

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d blogger hanno fatto clic su Mi Piace per questo: