[AN+] Radice Quadrata Intera

Vuoi proporre i tuoi esercizi? Qui puoi farlo!!

Moderatore: tutor

Bloccato
achillu
Messaggi: 114
Iscritto il: 01 gen 1970, 01:00
Località: Carpi è bella,ma Capri è più bella

Messaggio da achillu »

Non so se questo problema può entrarci o meno con le Olimpiadi così come sono strutturate adesso, però penso che alcuni di questi concetti dovreste averli comunque già assimilati (credo).
<BR>
<BR>Consideriamo questa successione di numeri REALI definita ricorsivamente:
<BR>
<BR>x<sub>0</sub> = B (dove B è una costante > 0)
<BR>x<sub>i+1</sub> = (x<sub>i</sub><sup>2</sup> + B) / (2 x<sub>i</sub>) (i >= 0)
<BR>
<BR>se negli ultimi 16 anni non sono rinco***onito, questa successione dovrebbe convergere alla radice quadrata di B (e magari qualcuno potrebbe già divertirsi a dimostrarlo, ma non è questo ciò che propongo).
<BR>
<BR>Supponiamo adesso di avere a disposizione una calcolatrice che opera solamente con i numeri INTERI NON NEGATIVI, e che quindi esegua correttamente addizioni, sottrazioni (con risultato non negativo) e moltiplicazioni, ma che prenda solamente la parte intera del risultato quando fa le divisioni. Tanto per dire, se provi a fare 17 / 3 ottieni 5.
<BR>
<BR>Problema 1: è possibile trovare un algoritmo che trovi la parte intera della radice quadrata di un numero intero positivo I utilizzando la calcolatrice e le quattro operazioni elementari dell\'aritmetica (vale a dire: radice quadrata intera di 17 = 4)? È possibile stimare in quanti passi si ottiene il risultato?
<BR>
<BR>Problema 2: supponendo che la calcolatrice sia limitata superiormente, vale a dire può effettuare le operazioni aritmetiche elementari sui numeri INTERI NON NEGATIVI purché gli operandi e il risultato non superino il limite M, per quali I compresi tra 0 ed M l\'algoritmo trovato con il problema 1 può trovare la radice quadrata intera di I? È possibile trovare un algoritmo che trovi la radice quadrata intera di tutti gli I compresi tra 0 ed M?
<BR>
<BR>EDIT: corretta una parentesi mancante e precistato il testo<BR><BR>[ Questo Messaggio è stato Modificato da: achillu il 31-01-2005 17:25 ]
MindFlyer

Messaggio da MindFlyer »

<!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE>
<BR>On 2005-01-31 17:20, achillu wrote:
<BR>È possibile trovare un algoritmo che trovi la radice quadrata intera di tutti gli I compresi tra 0 ed M?
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>Sì, c\'è l\'algoritmo banale che eleva al quadrato tutti gli interi a partire da 0 e li confronta con I. Appena supera I o sfora (i.e. supera M) sa di aver trovato la radice intera.
achillu
Messaggi: 114
Iscritto il: 01 gen 1970, 01:00
Località: Carpi è bella,ma Capri è più bella

Messaggio da achillu »

<!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE>
<BR>On 2005-01-31 18:24, MindFlyer wrote:
<BR><!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE>
<BR>On 2005-01-31 17:20, achillu wrote:
<BR>È possibile trovare un algoritmo che trovi la radice quadrata intera di tutti gli I compresi tra 0 ed M?
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>Sì, c\'è l\'algoritmo banale che eleva al quadrato tutti gli interi a partire da 0 e li confronta con I. Appena supera I o sfora (i.e. supera M) sa di aver trovato la radice intera.
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>Yep... <IMG SRC="images/forum/icons/icon_wink.gif"> hai ragione; io pensavo che questo algoritmo fosse ancora più banale: detta r la radice
<BR>
<BR>se I = 0 allora r = 0
<BR>se I = 1 allora r = 1
<BR>se I = 2 allora r = 1
<BR>se I = 3 allora r = 1
<BR>se I = 4 allora r = 2
<BR>...
<BR>
<BR>Forse dovevo specificare \"con un numero di passi paragonabile all\'algoritmo trovato col problema 1\"... in realtà è sempre difficile definire la complessità di un algoritmo porkapaletta <IMG SRC="images/forum/icons/icon27.gif">
Avatar utente
Boll
Messaggi: 1076
Iscritto il: 01 gen 1970, 01:00
Località: Piacenza

Messaggio da Boll »

bah, non è un algoritmo, fa schifo ed è lungo, ma, pensandoci poco io farei così:
<BR>dividiamo I per tutti i termini da 1 a I
<BR>I/k=j
<BR>quando |k-j| è minimo, la parte intera del minore dei due numeri è la stessa della radice.<font color=white><BR><BR>[ Questo Messaggio è stato Modificato da: Boll il 31-01-2005 19:19 ]
"Ma devo prendere una n-upla qualsiasi o una n-upla arbitraria?" (Lui)
MindFlyer

Messaggio da MindFlyer »

Boll, quello funziona, ma è ancor meno efficiente...
Avatar utente
Boll
Messaggi: 1076
Iscritto il: 01 gen 1970, 01:00
Località: Piacenza

Messaggio da Boll »

Ho premesso che fa schifo... <IMG SRC="images/forum/icons/icon_biggrin.gif"><IMG SRC="images/forum/icons/icon_biggrin.gif"> Comunque credo che il problema abbia poco senso poichè, avendo a disposizione un calcolatore veloce a piacere, può andare qualsiasi cosa (anche la mia <IMG SRC="images/forum/icons/icon_razz.gif">) sennò c\'è da limitare la velocità del calcolatore, il coefficeiente di \"velocità\" dell\'algoritmo, i byte che utilizzi per scriverlo ecc. ecc. e quindi non è più un problema di matematica... Almeno io la penso così, non insultarmi troppo Mind <IMG SRC="images/forum/icons/icon_biggrin.gif"><IMG SRC="images/forum/icons/icon_biggrin.gif">
"Ma devo prendere una n-upla qualsiasi o una n-upla arbitraria?" (Lui)
MindFlyer

Messaggio da MindFlyer »

Ok, non ti insulto troppo. <IMG SRC="images/forum/icons/icon_razz.gif">
<BR>Questo qui è un problema di algoritmica, non di matematica. Penso allora che l\'argomento che dice \"...altrimenti il problema non sarebbe di matematica\" sia un po\' debole.
<BR>La storia della velocità del calcolatore, dei byte, etc si può formalizzare, e la conclusione è che, in presenza di algoritmi di complessità esponenziale, un incremento di velocità del calcolatore di un certo fattore, si traduce in un incremento di prestazioni costante. Considera ad esempio un computer che con il tuo (o il mio) algoritmo calcola la radice di 100 in un secondo. Se prendiamo un altro computer con velocità doppia, in un secondo riuscirà a calcolare la radice di 101, e non di 200. Se quadruplichiamo la velocità, ci metterà un secondo a calcolare la radice di 102, etc.
<BR>Da qui il vantaggio di avere algoritmi polinomiali.
<BR>
<BR>Comunque Achillu, mi pare che l\'algoritmo che hai descritto tu (che poi dovrebbe essere quello di Newton) risolva perfettamente il Problema 1. A patto di fare la divisione intera, il che non è un danno, ma anzi accelera la convergenza.
achillu
Messaggi: 114
Iscritto il: 01 gen 1970, 01:00
Località: Carpi è bella,ma Capri è più bella

Messaggio da achillu »

<!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE>
<BR>On 2005-01-31 20:08, MindFlyer wrote:
<BR>Comunque Achillu, mi pare che l\'algoritmo che hai descritto tu (che poi dovrebbe essere quello di Newton) risolva perfettamente il Problema 1. A patto di fare la divisione intera, il che non è un danno, ma anzi accelera la convergenza.
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>Yesss.... infatti se mi dai un criterio per terminare l\'algoritmo forse riusciamo a stimare il numero di passi necessari.
Cu_Fa
Messaggi: 39
Iscritto il: 01 gen 1970, 01:00

Messaggio da Cu_Fa »

<!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE>
<BR>Problema 1: è possibile trovare un algoritmo che trovi la parte intera della radice quadrata di un numero intero positivo I utilizzando la calcolatrice e le quattro operazioni elementari dell\'aritmetica (vale a dire: radice quadrata intera di 17 = 4)? È possibile stimare in quanti passi si ottiene il risultato?
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>Forse ti può essere da aiuto questo:
<BR>1+3+5+7+...+2n+1=n<sup>2</sup>
<BR>Quindi basta sottrarre al numero di partenza una sequenza di numeri dispari crescenti, fino a che il risultato non diventa negativo.Il numero delle iterazioni necessarie è la parte intera della radice.
<BR>Esempio:
<BR>Radice di 17:
<BR>17-1=16
<BR>16-3=13
<BR>13-5=8
<BR>8-7=1 stop
<BR>La radice stroncata è quindi 4
Avatar utente
Marco
Site Admin
Messaggi: 1331
Iscritto il: 01 gen 1970, 01:00
Località: IMO '93

Messaggio da Marco »

Scusatemi, se mi intrometto senza far avanzare di un nanometro la discussione: si sono rincorse troppe cose e non ho capito bene. Posso provare a riformulare?, giusto per rimettere ordine...
<BR>
<BR>-----------------------------------
<BR>Sia B un intero positivo.
<BR>
<BR>Consideriamo questa successione di numeri INTERI definita ricorsivamente:
<BR>
<BR>y<sub>0</sub> = B
<BR>y<sub>i+1</sub> = [ (y<sub>i</sub><sup>2</sup> + B) / (2 y<sub>i</sub> ]
<BR>
<BR>[] è la parte intera, al solito.
<BR>
<BR>Dimostrare che
<BR>i) la successione si stabilizza (i.e. da un certo punto in poi è costante)
<BR>ii) si stabilizza a [sqrt(B)]
<BR>iii) si dica in quanti passi si stabilizza (basta stimare l\'ordine di crescita con B; Achillu, conferma s.v.p.)
<BR>-----------------------------------
<BR>E\' corretto?
<BR>
<BR>Ciao. M.
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."
MindFlyer

Messaggio da MindFlyer »

<!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE>
<BR>On 2005-02-01 09:16, marco wrote:
<BR>Dimostrare che
<BR>i) la successione si stabilizza (i.e. da un certo punto in poi è costante)
<BR>ii) si stabilizza a [sqrt(B)]
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>
<BR>Non è vero che la successione si stabilizza (si provi ad esempio con B=3, B=8, B=15, etc), ma si può comunque dare un criterio di terminazione che fornisce il risultato corretto [sqrt(B)].
<BR>
<BR>Siccome la disequazione
<BR>(x^2+B)/(2x) < sqrt(B)
<BR>non ha soluzione per x>0, questo implica che gli interi calcolati dall\'algoritmo non scendono mai sotto [sqrt(B)].
<BR>
<BR>Sia x>sqrt(B), poniamo
<BR>K = x - sqrt(B),
<BR>K\' = (x^2+B)/(2x) - sqrt(B),
<BR>e calcoliamo
<BR>K\'/K = (x-sqrt(B))/(2x) = 1/2 - sqrt(B)/(2x) < 1/2.
<BR>Quindi, se l\'algoritmo non facesse la divisione intera, ad ogni passo la distanza dalla radice quadrata dimezzerebbe (...).
<BR>Ma fare la divisione intera non peggiora la convergenza; anzi, la aiuta. Infatti sappiamo già che non possiamo scendere al di sotto di [sqrt(B)], e nel caso scendessimo sotto sqrt(B), avremmo già in mano il risultato.
<BR>
<BR>Quindi il criterio di terminazione consiste nel confrontare gli ultimi 2 interi della sequenza: se l\'ultimo non è minore del penultimo, allora l\'algoritmo termina restituendo il penultimo (in realtà si potrebbe fare in modo più efficiente, perché per calcolare l\'ultimo numero bisogna elevare il penultimo al quadrato, perciò basterebbe un confronto del quadrato con B prima di finire il calcolo...).
<BR>
<BR><!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE>
<BR>iii) si dica in quanti passi si stabilizza (basta stimare l\'ordine di crescita con B)
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>
<BR>Il fatto che, come detto sopra, K\'/K < 1/2, implica che, prima dell\'ultimo passo, la stessa disuguaglianza varrà anche tra gli interi calcolati dall\'algoritmo.
<BR>Infatti, sia X l\'ultimo intero trovato, e siano
<BR>Q = K = X - sqrt(B),
<BR>Q\' = [(X^2+B)/(2X)] - sqrt(B),
<BR>K\' = (X^2+B)/(2X) - sqrt(B).
<BR>Allora, se Q\' e Q sono positivi (ovvero se l\'algoritmo non deve terminare),
<BR>Q\'/Q <= K\'/K < 1/2.
<BR>
<BR>Giunto all\'ultimo passo, l\'algoritmo ugualierà o scenderà al di sotto di sqrt(B). La disuguaglianza di poco fa non varrà più, ma poco importa perché l\'algoritmo termina.
<BR>
<BR>In sostanza, l\'algoritmo ha ordine O(log(B-sqrt(B))) = O(log(B)).
MindFlyer

Messaggio da MindFlyer »

<!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE>
<BR>On 2005-02-01 07:07, Cu_Fa wrote:
<BR>Forse ti può essere da aiuto questo:
<BR>1+3+5+7+...+2n+1=n<sup>2</sup>
<BR>Quindi basta sottrarre al numero di partenza una sequenza di numeri dispari crescenti, fino a che il risultato non diventa negativo.Il numero delle iterazioni necessarie è la parte intera della radice.
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>Cu_Fa, il tuo algoritmo ha ordine O(sqrt(B)), che non è molto meglio di quello banale che ha ordine O(B).
<BR>Quello di Newton ha invece ordine O(log(B)), come dimostrai qui sopra.
<BR>Complimenti a Newton!!
MindFlyer

Messaggio da MindFlyer »

<!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE>
<BR>On 2005-02-01 11:50, MindFlyer wrote:
<BR>In sostanza, l\'algoritmo ha ordine O(log(B-sqrt(B))) = O(log(B)).
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>Per la verità questo non l\'ho dimostrato come si deve.
<BR>
<BR>Noi sappiamo che
<BR>X<sub>n</sub> < (X<sub>n-1</sub>- sqrt(B))/2 + sqrt(B).
<BR>Ora, se
<BR>X<sub>n</sub>- sqrt(B) <= 1,
<BR>l\'algoritmo termina al passo successivo (dimostrazione ovvia).
<BR>
<BR>Quindi basta calcolare dopo quanti passi ciò avviene, ed è presto fatto:
<BR>X<sub>n</sub>- sqrt(B) < (X<sub>0</sub>- sqrt(B))/2<sup>n</sup> = (B - sqrt(B))/2<sup>n</sup>,
<BR>e ponendo
<BR>(B - sqrt(B))/2<sup>n</sup> <= 1
<BR>si ottiene
<BR>n >= log<sub>2</sub>(B - sqrt(B)).
<BR>
<BR>Perciò, è dimostrato che l\'algoritmo ha ordine O(log(B - sqrt(B))) = O(log(B)).
achillu
Messaggi: 114
Iscritto il: 01 gen 1970, 01:00
Località: Carpi è bella,ma Capri è più bella

Messaggio da achillu »

<!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE>
<BR>On 2005-02-01 09:16, marco wrote:
<BR>Dimostrare che
<BR>i) la successione si stabilizza (i.e. da un certo punto in poi è costante)
<BR>ii) si stabilizza a [sqrt(B)]
<BR>iii) si dica in quanti passi si stabilizza (basta stimare l\'ordine di crescita con B; Achillu, conferma s.v.p.)
<BR>-----------------------------------
<BR>E\' corretto?
<BR>
<BR>Ciao. M.
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>MindFlyer mi ha preceduto, e infatti la successione in alcuni casi non si stabilizza, però si può stabilire un criterio di terminazione, che si può esprimere per l\'appunto con x<sub>a+1</sub> >= x<sub>a</sub> come fatto notare da MindFlyer, e la soluzione è [sqrt(B)] = x<sub>a</sub>.
Bloccato