Radice quadrata di un numero

Il linguaggio C non fornisce operazioni per il calcolo della radice quadrata di un numero. Esiste pero' una libreria di funzioni (la libreria matematica libm) che fornisce una funzione sqrt() per il calcolo della radice quadrata.

Per poter utilizzare funzioni della libreria matematica, bisogna includere math.h ed aggiungere -lm alla fine della riga di comando per compilare.

Calcolo della radice quadrata

Problema: e' possibile calcolare la radice quadrata di un numero senza utilizzare la libreria matematica?

Si puo' utilizzare l'algoritmo cosiddetto babilonese. Il problema e' allora scrivere un programma che codifichi tale algoritmo usando il linguaggio C.

L'algoritmo Babilonese

L'algoritmo babilonese funziona come segue:

  Variabili:
      guess (numero reale)	// Rappresenta la stima della radice quadrata
      epsilon (numero reale)	// Rappresenta l'approssimazione che vogliamo per la stima

  guess = 1
  mentre guess * guess non in (x - epsilon, x + epsilon) ripeti
      guess = (guess + x / guess) / 2

  guess e' la stima della radice quadrata di x
       

Questo algoritmo funziona quindi in modo iterativo, partendo da una prima stima della radice quadrata di x e "raffinandola" fino a che la differenza fra il quadrato della stima ed x non e' abbastanza piccola.

Ci sono vari modi per interpretare l'algoritmo babilonese. Una spiegazione completa e rigorosa non spetta a questo corso, ma si possono considerare alcune spiegazioni intuitive. Per esempio:

• Se guess e' una stima della radice quadrata di x e chiamiamo radice la radice quadrata esatta, allora radice=guess+errore, quindi

    radice * radice = x => (guess + errore) * (guess + errore) = x =>
    guess * guess + 2 * guess * errore + errore * errore = x =>
    2 * guess * errore + errore * errore = x - guess * guess =>
    errore = (x - guess * guess) / (2 * guess + errore)
               

  approssimando questa espressione a (x - guess * guess) / (2 * guess), si ottiene

    guess + errore = (2 * guess * guess + x - guess * guess) / (2 * guess) =
    = (guess * guess + x) / (2 * guess) = (guess + x / guess) / 2
               

  che e' proprio la regola di aggiornamento di guess prescritta dal metodo babilonese
• Approssimare la radice quadrata di x equivale a trovare la soluzione approssimata di radice * radice = x che e' scrivibile come radice * radice - x = 0. Se guess e' una soluzione approssimata di tale equazione, si puo' raffinare la soluzione approssimando la parabola con la retta tangente nel punto di ascissa guess (che ha pendenza 2 * guess). Chiamando g' il punto in cui la retta tangente interseca l'asse delle ascisse, si ha:

    0 = 2 * guess * (g' - guess) + guess * guess - x =>
    2 * guess * g' - 2 * guess * guess + guess * guess - x = 0 =>
    2 * guess * g' = x + guess * guess =>
    g' = (x + guess * guess) / (2 * guess) = (x / guess + guess) / 2
               

  che ancora una volta e' l'aggiornamento della soluzione approssimata prescritto dal metodo babilonese

Implementazione in C

Una possibile implementazione dell'algoritmo babilonese citato qui sopra si puo' scaricare dal sito del corso. Provate ad implementare l'algoritmo da soli prima di controllare la soluzione.

Esercizi

Ora che si ha una implementazione funzionante della funzione che calcola la radice quadrata, e' possibile scrivere un programma che chiede in ingresso un numero reale e ne stampa la radice quadrata (usare scanf() per chiedere il numero in ingresso).

Si puo' anche modificare il programma che calcola le soluzioni di equazioni di secondo grado per usare la nostra implementazione invece della funzione standard sqrt().