Algoritmo Di Bombelli

[utente__medio11]

Ciao a tutti e scusate se ho sbagliato sezione.
Ricordavo dell'esistenza di un metodo per calcolare la radice quadrata di un intero con carta e penna, ma non mi era mai capitato di approfondire la questione, finché prima cercando in rete non mi sono imbattuto nell'algoritmo di Bombelli.
Innanzitutto, avendo provato a formalizzare l'algoritmo, volevo chiedervi se è corretto e se si può scrivere in modo ancora più semplice e chiaro (nello schema sottostante con $INT$ mi riferisco alla radice intera):

[size=120] \( \sqrt{\underbrace{xx}_{n_1}\ \underbrace{xx}_{n_2}\ ...\ \underbrace{xx}_{n_i}\ ...\ \underbrace{xx}_{n_m}}^{INT} = \underbrace{x}_{r_1}\ \underbrace{x}_{r_2} \ ...\ \underbrace{x}_{r_i}\ ...\ \underbrace{x}_{r_m} \) [/size]

$a_0=c_0=R_0=0$

$a_i=(a_(i-1)-c_(i-1))*b^2+n_i$
$c_i=r_i*(2*b*R_(i-1)+r_i)<=a_i$
$R_i=b*R_(i-1)+r_i$
Per $i=1,2,...,m$

Dove $b$ è la base numerica utilizzata, $r_i$ è l'$i$-esima cifra del risultato partendo da sinistra (che si ottiene risolvendo in $N$ la precedente disequazione nell'incognita $r_i$), $R_i$ è il risultato parziale allo step considerato.
E in definitiva il numero sotto radice sarà uguale a $R_m^2+(a_m-c_m)$.

Infine, anche se il procedimento mi è chiaro e ho anche afferrato qualcosina di quello che avviene dietro le quinte, non sono ancora riuscito ad ottenere una dimostrazione complessiva dell'algoritmo. Qualche idea? Per esempio quel $2*$ da dove salta fuori?

[Quinzio]

"utente__medio":Ciao a tutti e scusate se ho sbagliato sezione.
Ricordavo dell'esistenza di un metodo per calcolare la radice quadrata di un intero con carta e penna, ma non mi era mai capitato di approfondire la questione, finché prima cercando in rete non mi sono imbattuto nell'algoritmo di Bombelli.
Innanzitutto, avendo provato a formalizzare l'algoritmo, volevo chiedervi se è corretto e se si può scrivere in modo ancora più semplice e chiaro (nello schema sottostante con $INT$ mi riferisco alla radice intera):

[size=120] \( \sqrt{\underbrace{xx}_{n_1}\ \underbrace{xx}_{n_2}\ ...\ \underbrace{xx}_{n_i}\ ...\ \underbrace{xx}_{n_m}}^{INT} = \underbrace{x}_{r_1}\ \underbrace{x}_{r_2} \ ...\ \underbrace{x}_{r_i}\ ...\ \underbrace{x}_{r_m} \) [/size]


$a_0=c_0=R_0=0$

$a_i=(a_(i-1)-c_(i-1))*b^2+n_i$
$c_i=r_i*(2*b*R_(i-1)+r_i) $R_i=b*R_(i-1)+r_i$
Per $i=1,2,...,m$

Dove $b$ è la base numerica utilizzata, $r_i$ è l'$i$-esima cifra del risultato partendo da sinistra (che si ottiene risolvendo in $N$ la precedente disequazione nell'incognita $r_i$), $R_i$ è il risultato parziale allo step considerato.
E in definitiva il numero sotto radice sarà uguale a $R_m^2+(a_m-c_m)$.

Infine, anche se il procedimento mi è chiaro e ho anche afferrato qualcosina di quello che avviene dietro le quinte, non sono ancora riuscito ad ottenere una dimostrazione complessiva dell'algoritmo. Qualche idea? Per esempio quel $2*$ da dove salta fuori?

Riordino i pedici al contrario.

[size=120] \( \sqrt{\underbrace{xx}_{n_{m-1}}\ \underbrace{xx}_{n_{m-2}}\ ...\ \underbrace{xx}_{n_i}\ ...\ \underbrace{xx}_{n_0}}^{INT} = \underbrace{x}_{r_{m-1}}\ \underbrace{x}_{r_{m-2}} \ ...\ \underbrace{x}_{r_i}\ ...\ \underbrace{x}_{r_0} \) [/size]


$a_m=c_m=R_m=0$

1) $a_i=(a_(i+1)-c_(i+1))*b^2+n_i$
2) $c_i=r_i*(2*b*R_(i+1)+r_i) \le a_i$
3) $R_i=b*R_(i+1)+r_i$
Per $i=m-1,m-2,...,0$

Con la disequazione 2) e la 1)

$c_i < a_i$

$c_i < (a_(i+1)-c_(i+1))*b^2+n_i$

Usando di nuovo la definizione ricorsiva 1)

$c_i < (((a_(i+2)-c_(i+2))*b^2+n_{i+1}) -c_(i+1))*b^2+n_i$

Svolgendo tutta la ricorsione da $i=0$ fino a $i=m-1$

$c_{m-1}b^{2(m-1)} + ... + c_0 < n_{m-1} b^{2(m-1)} + ... + n_0$

La parte a destra la scriviamo semplicemente come $n$ e per la parte a sinistra usiamo l'equazione 2)

$r_{m-1}*(2*b*R_{m}+r_{m-1}) b^{2(m-1)} + ... + r_0^2 \le n$

Scriviamo anche il termine intermedio e ricordando che $R_m = 0$

$r_{m-1}*(2*b*R_{m}+r_{m-1}) b^{2(m-1)} + ... + r_{i}*(2*b*R_{i+1}+r_{i}) b^{2i} + ... + r_0^2 \le n$

$r_{m-1}^2 b^{2(m-1)} + ... + r_{i}*(2*b*R_{i+1}+r_{i}) b^{2i} + ... + r_0^2 \le n$

Per esplicitare la $R_i$ usiamo la 3)

$R_i=b*R_(i+1)+r_i$

che svolgiamo completamente

$R_i=b^{m-1-i}*r_{m-1}+...+ r_i$

e otteniamo

$r_{m-1}^2 b^{2(m-1)} + ... + r_{i}*(2*b*(b^{m-1-i}*r_{m-1}+...+ r_{i+1})+r_{i}) b^{2i} + ... + r_0^2 \le n$

raggruppiamo i termini in modo omogeneo e aggiustiamo gli esponenti

$r_{m-1}^2 b^{2(m-1)} +...+ r_{i}^2 b^{2i}+ ... + r_0^2 + ... +2 r_{i} b^i(b^{m-1}*r_{m-1}+r_{i+1}b^{i+1}) \le n$

L'espressione a sinistra puo' sembrare indecifrabile, ma altro non e' che il quadrato della radice

$(r_{m-1}b^{m-1}+...+r_0)^2 \le n$

oppure, come ci piacerebbe vederla

$r^2 \le n$

Chiaramente la disequazione va intesa nel senso che al passo 2) dell'algoritmo gli $r_i$ sono stati massimizzati in modo che sia vero che

$r^2 \le n < (r+1)^2$


Il 2 che compare nelle equazioni (per rispondere alla tua ultima domanda) e' il doppio prodotto che risulta facendo il quadrato di un polinomio:
$(a+b)^2 = a^2 + b^2 + 2ab$
$(a+b+c)^2 = a^2 + b^2 + c^2 + 2(ab + ac+bc)$

[utente__medio11]

@Quinzio, grazie, tutto chiaro!
All'inizio avevo tentato la strada della sostituzione, poi però mi sono demoralizzato e ho mollato.

"Quinzio":Il 2 che compare nelle equazioni (per rispondere alla tua ultima domanda) e' il doppio prodotto che risulta facendo il quadrato di un polinomio:

Lo avevo pensato, ma non riuscivo a capire precisamente da dove potesse saltare fuori questo quadrato di un polinomio.

Comunque ho provato a dimostrare il tutto seguendo una strada un po' diversa:

Nella seguente schematizzazione con $INT$ mi riferisco alla radice intera.

[size=120] \( \sqrt{N}^{INT} = \sqrt{\underbrace{xx}_{n_1}\ \underbrace{xx}_{n_2}\ ...\ \underbrace{xx}_{n_i}\ ...\ \underbrace{xx}_{n_m}}^{INT} = \underbrace{x}_{r_1}\ \underbrace{x}_{r_2} \ ...\ \underbrace{x}_{r_i}\ ...\ \underbrace{x}_{r_m} = R_m \) [/size]

Sia $b$ la base numerica utilizzata, $r_i$ l'$i$-esima cifra del risultato partendo da sinistra, $R_i$ il risultato parziale allo step considerato. Posto

1) $a_0=c_0=R_0=0$

i passi dell'algoritmo per $i=1,2,...,m$ sono:

2) $a_i=b^2(a_(i-1)-c_(i-1))+n_i$
3) $c_i=r_i(2bR_(i-1)+r_i)$
4) $c_i<=a_i$
5) $R_i=bR_(i-1)+r_i$

Dove la 4) costituisce una disequazione nell'incognita $r_i$ da risolvere nell'insieme $ℕ$, ossia $r_i$ rappresenta il massimo numero naturale che soddisfa la 4).
Vogliamo dimostrare che $N=R_m^2+(a_m-c_m)$ (ovviamente per la 4) sarà $a_m-c_m>=0$).

Dalla 5) si ricava:

6) $r_i=R_i-bR_(i-1)$

Sostituendo la 6) nella 3) si ricava:

7) $c_i=(R_i-bR_(i-1))(2bR_(i-1)+(R_i-bR_(i-1)))=R_i^2-b^2R_(i-1)^2$

Sostituendo la 7) nella 2) si ricava:

8) $a_i=b^2(a_(i-1)-(R_(i-1)^2-b^2R_(i-2)^2))+n_i=b^2a_(i-1)-b^2R_(i-1)^2+b^4R_(i-2)^2+n_i$

Dalla 7) e 8) si ricava:

9) $a_m-c_m=b^2a_(m-1)-b^2R_(m-1)^2+b^4R_(m-2)^2+n_m-(R_m^2-b^2R_(m-1)^2)=b^2a_(m-1)+b^4R_(m-2)^2+n_m-R_m^2$

Applicando ricorsivamente la 8) alla 9) da $i=m-1$ a $i=1$ si ottiene:

10) $a_m-c_m=[b^4R_(m-2)^2+...-b^(2(m-i+1))R_(i-1)^2+b^(2(m-i+2))R_(i-2)^2+...-b^(2m)R_0^2+b^(2(m+1))R_(-1)^2+b^(2m)a_0]+(n_m+...+b^(2(m-i))n_i+...+b^(2(m-1))n_1)-R_m^2$

Relativamente alla 10), essendo la quantità tra parentesi quadre uguale a zero (per la 1) e per il fatto che le coppie di termini successivi, partendo dall'inizio fino al terzultimo elemento, si annullano a vicenda), ed essendo quella tra parentesi tonde pari ad $N$, si dimostra che:

11) $a_m-c_m=N-R_m^2 \ \ \ => \ \ \ N=R_m^2+(a_m-c_m)$

Il tutto mi sembra abbastanza semplice e scorrevole, se non fosse per quel $b^(2(m+1))R_(-1)^2$ indefinito nella 10), che deriva dalla 8) per $i=1$.
Porre $R_(i<1)=0$ sarebbe barare? Dopotutto il risultato parziale $R_i$ inizia ad esistere solo per $i=1$.
Che ne pensate, la precedente dimostrazione è completamente da cestinare o no?

[utente__medio11]

UP

[Quinzio]

"utente__medio":
Il tutto mi sembra abbastanza semplice e scorrevole, se non fosse per quel $b^(2(m+1))R_(-1)^2$ indefinito nella 10), che deriva dalla 8) per $i=1$.
Porre $R_(i<1)=0$ sarebbe barare? Dopotutto il risultato parziale $R_i$ inizia ad esistere solo per $i=1$.
Che ne pensate, la precedente dimostrazione è completamente da cestinare o no?

Beh, no, ovviamente non e' da cestinare. Il metodo da seguire l'hai capito bene, si tratta di dipanare la matassa delle ricorsioni in modo da arrivare ad un'espressione esplicita, che sia comprensibile.
Lungi da me il voler dimostrare che la mia esposizione e' stata migliore della tua o che sia piu' comprensibile, ma vorrei fare alcune osservazioni.
Hai di nuovo invertito l'ordine dei pedici. Ora, uno e' libero di fare quello che vuole, ma non si capisce perche' voler tenere quell'ordine invertito. Rende tutto un po' piu' ostico da leggere.
Un numero decimale di $m$ cifre io l'ho sempre visto scritto cosi': $\sum_{i=0}^{m-1} n_i 10^i$.
Poi, mi sembra che la mia esposizione arrivi a far vedere che $r^2 < n$, che e' quello che si vuole.
Nella tua, mi sembra che la conclusione finale " la quantità tra parentesi quadre uguale a zero" lasci un po' a desiderare, nel senso che sembra che sia da dimostrare. (per il fatto che le coppie di termini successivi si annullano a vicenda).

Ripeto, non sto dicendo che la mia sia piu' bella della tua, non sto dicendo che la mia esposizione sia l'unica possibile.
Mi sembra che la mia esposizione alla fine faccia vedere che $r^2 < n$, che e' quello che si vuole, tutto qui.

Oppure, ad esempio, piuttosto che smacchinare con tutti quei pedici (che e' quello che ho fatto anche io), mi sembrerebbe piu' utile far vedere il meccanismo sottostante a quelle ricorsioni, proponendo un algoritmo piu' semplice, anche se piu' lento.
Ovvero si tratta di trovare la radice per tentativi.
Parto da $b_0 = 0$
Scelgo (a caso) $a_0 > 0$ in modo che $(b_0 + a_0) ^2 < n$
$b_1 = b_0 + a_0$.
Scelgo (a caso) $a_1 > 0$ in modo che $(b_1 + a_1) ^2 < n$
E cosi' via...

Adesso il passo:
Trovo $a_1 > 0$ in modo che $(b_1 + a_1) ^2 < n$
si puo' riarrangiare come:
Trovo $a_1 > 0$ in modo che $a_1(2b_1 + a_1) < n - b_1^2$
che molto simile a quel passo misterioso dell'algoritmo originale.
Mi sembra che questo modo piu' semplice renda pero' tutto piu' chiaro.

[utente__medio11]

"Quinzio":Oppure, ad esempio, piuttosto che smacchinare con tutti quei pedici (che e' quello che ho fatto anche io), mi sembrerebbe piu' utile far vedere il meccanismo sottostante a quelle ricorsioni, proponendo un algoritmo piu' semplice, anche se piu' lento.
Ovvero si tratta di trovare la radice per tentativi.
[...]

Spunto interessante, anche io all'inizio cercavo di capire cosa avveniva dietro le quinte ad ogni passo dell'algoritmo, poi però mi sono arreso e ho deciso di accontentarmi di una dimostrazione complessiva.

"Quinzio":Hai di nuovo invertito l'ordine dei pedici. Ora, uno e' libero di fare quello che vuole, ma non si capisce perche' voler tenere quell'ordine invertito. Rende tutto un po' piu' ostico da leggere.

Non essendo del "settore" non ho molta familiarità con certe convenzioni, alla fine ho utilizzato questa impostazione degli indici fin dall'inizio solo perché era quella più coerente col funzionamento dell'algoritmo, il quale avanza da sinistra verso destra.

"Quinzio":Poi, mi sembra che la mia esposizione arrivi a far vedere che $r^2
Dato per scontato che il tuo $r^2<=n$ equivale al mio $R_m^2<=N$ (dove $n$ e $N$ indicano il numero di cui voler calcolare la radice quadrata, mentre $r$ e $R_m$ indicano la radice intera del numero), anche se dimostrare (o far vedere) che $R_m^2<=N$ è sufficiente, penso che dimostrare che $N=R_m^2+(a_m-c_m)$ (dove $a_m-c_m$ è il "resto" della radice intera) sia più "completo", anche perché da quest'ultima, essendo per ipotesi $c_i<=a_i$, ne discende che $R_m^2<=N$.
E ciò a maggior ragione se si tiene conto del fatto che mostrare $R_m^2<=N$ o mostrare $N=R_m^2+(a_m-c_m)$ è praticamente indifferente dal punto di vista della dimostrazione, infatti tu applichi sostituzioni e ricorsioni per sviluppare la disequazione $c_m<=a_m$, io invece per calcolare la quantità $a_m-c_m$; le nostre dimostrazioni sembrano diverse, ma in realtà sono la stessa cosa, e le differenze dipendono solo dalle modalità di sostituzione.

In ogni caso rimane la questione che ho sollevato nel precedente post, ossia dalla

8) $a_i=b^2a_(i-1)-b^2R_(i-1)^2+b^4R_(i-2)^2+n_i$

per $i=1$ esce fuori il termine $b^4R_(-1)^2$, dove però $R_(-1)$ risulta non definito.
Per questo chiedevo se fosse barare porre $R_(<0)=0$. Secondo te?

[Quinzio]

"utente__medio":

In ogni caso rimane la questione che ho sollevato nel precedente post, ossia dalla

8) $a_i=b^2a_(i-1)-b^2R_(i-1)^2+b^4R_(i-2)^2+n_i$

per $i=1$ esce fuori il termine $b^4R_(-1)^2$, dove però $R_(-1)$ risulta non definito.
Per questo chiedevo se fosse barare porre $R_(<0)=0$. Secondo te?

E' del tutto lecito porre $R_(<0)=0$.
Va benissimo.

[utente__medio11]

"Quinzio":E' del tutto lecito porre $R_(<0)=0$.
Va benissimo.

Come detto in precedenza la cosa per me poteva aver senso in quanto il risultato parziale $R_i$ inizia ad esistere solo per $i=1$, ma visto che si tratta di una questione piuttosto "strana" è sempre meglio avere una conferma da qualcuno con più esperienza.
Grazie per tutto l'aiuto!