algoritmo del contadino russo

[F.]

Non riesco a trovare ne a fare la dimostrazione dell'algoritmo del
contadino russo:

r(a,1) = a
r(a,b) =r(2·a,b/2) se b è pari,
r(a,b) =r(2·a,(b-1)/2) + a se b è dispari.

Dimostrare per induzione che r(a,b) = a·b per ogni a, b >1.

Alla base ci sono arrivata: r(2,2)=r(2*2,2/2)=r(4,1)=4 cioè 2*2
poi sono partita dicendo che vale P(m,n)=m*n e
r(m,n)=r(2·m,n/2) se n è pari
r(m,n)=r(2·m,(n-1)/2) +n se n è dispari

Devo dimostrare che vale
P(m+1,n+1)=(m+1)*(n+1)=m*n+m*1+n*1+1=r(m,n)+r(m,1)+r(n,1)+r(1,1)

ma questo non mi porta da nessuna parte.....

C'è qualcuno che ha un'idea su come proseguire?

Ciao
F.

[marcofuics]

Post by F.
Non riesco a trovare ne a fare la dimostrazione dell'algoritmo del
r(a,1) = a
r(a,b) =r(2·a,b/2) se b è pari,
r(a,b) =r(2·a,(b-1)/2) + a se b è dispari.
Dimostrare per induzione che r(a,b) = a·b per ogni a, b >1.

se b e' pari allora b=2 k (intero) e 2a = n (intero)
r(a,b) =r(2·a,b/2) = r(2a,k) --- ora k puo' essere pari o dispari --
se e' pari k = 2 k_1, cioe'
r(2a,k) = r(2 a,2 k_1 ) = r(4 a, k_1).... e cosi' via.

se b e' dispari allora b = 2 k + 1, cioe'
r(a,b) =r(2·a,(b-1)/2) = r(2a,k) , ed ancora k puo' essere pari o
dispari, se ad ex e' dispari
k = 2 k_1 + 1
riottieni:
r(2a,k) = r(2 a,((2 k_1 + 1)-1)/2 ) = r(4 a, k_1 ) = .... e cosi' via.

Come vedi nell'uno o nell'altro caso la discesa e' tale da condurti
alla fine con un espressione irriducibile

r(n a, 1) che equivale a sommare n volte il termine iniziale b....
quindi aXb.

[marcofuics]

On 15 Mar, 16:58, "F." <***@aby.it> wrote:

hmmmmmm... ma perche' in russia si piantano algoritmi?

[fm2766]

Post by F.
Non riesco a trovare ne a fare la dimostrazione dell'algoritmo del
r(a,1) = a
r(a,b) =r(2·a,b/2) se b è pari,
r(a,b) =r(2·a,(b-1)/2) + a se b è dispari.
Dimostrare per induzione che r(a,b) = a·b per ogni a, b >1.
Alla base ci sono arrivata: r(2,2)=r(2*2,2/2)=r(4,1)=4 cioè 2*2
poi sono partita dicendo che vale P(m,n)=m*n e
r(m,n)=r(2·m,n/2) se n è pari
r(m,n)=r(2·m,(n-1)/2) +n se n è dispari
Devo dimostrare che vale
P(m+1,n+1)=(m+1)*(n+1)=m*n+m*1+n*1+1=r(m,n)+r(m,1)+r(n,1)+r(1,1)
ma questo non mi porta da nessuna parte.....
C'è qualcuno che ha un'idea su come proseguire?
Ciao
F.

Se non erro, non è un metodo esatto. Nel senso che si lavora con numeri
interi ed approssimazioni.
Correggimi *se sbaglio* , ma mi pare che nel metodo originario, il "+a"
se b è dispari non ci sia.
Nel caso b dispari, si ha
1) a·b=(2·a)·(b-1)/2,
che si alterna a
2) a·b=(2·a)·(b+1)/2.
Il calcolo si fa a mente. Per es:

15x22=7x44=4x88=2x176=352 (invece di 330, se inizio con 1) )
oppure
15x22=8x44=4x88=2x176=352 (invece di 330, se inizio con 2) )

Tu dici che
a·b=(2·a)·(b-1)/2 + a se b dispari,
ma questo, anche se è un calcolo esatto, non aiuta a fare i calcoli a mente.

[F.]

Post by fm2766
Se non erro, non è un metodo esatto. Nel senso che si lavora con numeri
interi ed approssimazioni.
Correggimi *se sbaglio* , ma mi pare che nel metodo originario, il "+a"
se b è dispari non ci sia.
Nel caso b dispari, si ha
1) a·b=(2·a)·(b-1)/2,
che si alterna a
2) a·b=(2·a)·(b+1)/2.
15x22=7x44=4x88=2x176=352 (invece di 330, se inizio con 1) )
oppure
15x22=8x44=4x88=2x176=352 (invece di 330, se inizio con 2) )
Tu dici che
a·b=(2·a)·(b-1)/2 + a se b dispari,
ma questo, anche se è un calcolo esatto, non aiuta a fare i calcoli a mente.

Hai perfettamente ragione, ma CHI ci ha dato un esercizio simile, non
l'ha fatto perchè così poi insegnamo ai nostri alunni il metodo più
efficace e utile, l'hanno fatto solo per complicarci la vita!!

Scusa lo sfogo, ma hai toccato un tasto .....

Ciao
F.

[g***@gmail.com]

una curiosita': mi sembra che da un punto di vista computazionale
questo algoritmo sia molto veloce.

Moltiplicare e dividere per 2 sono operazioni che un calcolatore
esegue in tempo costante (basta uno shift); percio' la complessita'
dovrebbe essere O(log b) e quindi, detto N il numero di cifre di b (in
una qualunque rappresentazione),
O(N). Mi sbaglio?

[A. Caranti]

Post by fm2766
ma questo, anche se è un calcolo esatto, non aiuta a fare i calcoli a mente.

Hai perfettamente ragione, ma CHI ci ha dato un esercizio simile,
non l'ha fatto perchè così poi insegnamo ai nostri alunni il metodo
più efficace e utile, l'hanno fatto solo per complicarci la vita!!
Scusa lo sfogo, ma hai toccato un tasto .....

Come ti e' stato gia' fatto notare, il valore di questo metodo e' che
e' piuttosto efficiente dal punto di vista computazionale, quindi
altro che complicare la vita, insegnare a valutare la bonta' degli
algoritmi (chiamala complessita' computazionale algebrica se vuoi) e'
una cosa oramai essenziale, no?

In quanto alla dimostrazione, come forse hai gia' visto, e' una
induzione sul solo b. Infatti la base e'

r(a,1) = a.

In effetti a * 1 = a.

Poi nel primo caso:

r(a,b) =r(2·a,b/2) se b è pari,

hai per ipotesi induttiva

r(2·a,b/2) = 2 * a * b/2 = a * b,

OK.

Nel secondo caso

r(a,b) =r(2·a,(b-1)/2) + a se b è dispari

hai per ipotesi induttiva

r(2·a,(b-1)/2) = 2 * a * (b-1)/2 = a*b - a,

e tutto torna anche qui.

Andreas

[F.]

Post by A. Caranti
Come ti e' stato gia' fatto notare, il valore di questo metodo e' che
e' piuttosto efficiente dal punto di vista computazionale, quindi
altro che complicare la vita, insegnare a valutare la bonta' degli
algoritmi (chiamala complessita' computazionale algebrica se vuoi) e'
una cosa oramai essenziale, no?

Si certo, sono un'informatica e so quanto è importante la complessità
computazionale, ma qui si
parlava di un metodo (sempre chiamato del contadino russo) però più
facile da memorizzare e da applicare per calcoli a mente; almeno io ho
capito così.

Post by A. Caranti
In quanto alla dimostrazione, come forse hai gia' visto, e' una
induzione sul solo b. Infatti la base e'
r(a,1) = a.
In effetti a * 1 = a.
Poi nel primo caso: r(a,b) =r(2·a,b/2) se b è pari,
hai per ipotesi induttiva r(2·a,b/2) = 2 * a * b/2 = a * b,
OK.
Nel secondo caso r(a,b) =r(2·a,(b-1)/2) + a se b è dispari
hai per ipotesi induttiva r(2·a,(b-1)/2) = 2 * a * (b-1)/2 = a*b - a,
e tutto torna anche qui.

Questo si, che sembra più semplice, ma è ugualmente corretto?

Francesca

[Tetis]

Post by F.
Non riesco a trovare ne a fare la dimostrazione dell'algoritmo del
r(a,1) = a
r(a,b) =r(2·a,b/2) se b è pari,
r(a,b) =r(2·a,(b-1)/2) + a se b è dispari.
Dimostrare per induzione che r(a,b) = a·b per ogni a, b >1.
Alla base ci sono arrivata: r(2,2)=r(2*2,2/2)=r(4,1)=4 cioè 2*2
poi sono partita dicendo che vale P(m,n)=m*n e
r(m,n)=r(2·m,n/2) se n è pari
r(m,n)=r(2·m,(n-1)/2) +n se n è dispari

Proposta alternativa: considera la proposizione seguente
P(m,k) == {per ogni 1<=l <= k r(m,l) = m x l }
ora e' facile mostrare per induzione, distinguendo i
due casi, k pari e k dispari, che P(m,k) => P(m,k+1).
P(m,1) e' ovviamente verificato per l'ipotesi che r(a,1)=a.
Ne segue, d'induzione, che per ogni dato m e per ogni 1 <= k
r(m,k) = m x k. Che e' un'estensione della tesi e quindi
implica la tesi nel suo caso particolare che 1 < k . Nota
che k ed a sono intercambiali.

Esempio di applicazione:

13 x 15

13 15
6 30
3 60
1 120

risultato 195 Ovvero se il numero a sinistra
e' pari non entra nella somma
come diceva Levin.

--------------------------------
Inviato via http://arianna.libero.it/usenet/

[Tetis]

Riscrivo l'esempio dato che sono andati perduti
13 x 15
13 15
6 ///////// 30
3 60
1 120
risultato 195 Ovvero se il numero a sinistra
e' pari non entra nella somma
come diceva Levin.
--------------------------------
Inviato via http://arianna.libero.it/usenet/

--------------------------------
Inviato via http://arianna.libero.it/usenet/

[fm2766]

Post by Tetis

Riscrivo l'esempio dato che sono andati perduti
13 x 15
13 15
6 ///////// 30
3 60
1 120
risultato 195 Ovvero se il numero a sinistra
e' pari non entra nella somma
come diceva Levin.
--------------------------------
Inviato via http://arianna.libero.it/usenet/

--------------------------------
Inviato via http://arianna.libero.it/usenet/

Ma questo è un altro algoritmo ancora per la moltiplicazione, non quello
del contadino russo. Diciamo che è un algoritmo vecchio e caduto in
disuso. Ma esteticamente affascinante.

[Tetis]

Post by fm2766

Riscrivo l'esempio dato che sono andati perduti
13 x 15
13 15
6 ///////// 30
3 60
1 120
risultato 195 Ovvero se il numero a sinistra
e' pari non entra nella somma
come diceva Levin.

Ma questo è un altro algoritmo ancora per la moltiplicazione, non quello
del contadino russo. Diciamo che è un algoritmo vecchio e caduto in
disuso. Ma esteticamente affascinante.

Prova ad applicare la regola che abbiamo dimostrato
per induzione:

r(15,13) =
r(30,6) + 15 =
r(60,3) + 15 =
r(120,1) + 60 +15 =
120 +60 +15 .

Tradotto: a destra di r(120,1) devi aggiungere tutti quegli "a"
che durante la strada risultavano associati ad un valore dispari
di a. D'altra parte non e' altro che la classica regola della
moltiplicazione che si impara alla scuola elementare, solo
applicata alle espressioni binarie dei numeri.

--------------------------------
Inviato via http://arianna.libero.it/usenet/

[fm2766]

Post by Tetis

Post by fm2766

Riscrivo l'esempio dato che sono andati perduti
13 x 15
13 15
6 ///////// 30
3 60
1 120
risultato 195 Ovvero se il numero a sinistra
e' pari non entra nella somma
come diceva Levin.

Ma questo è un altro algoritmo ancora per la moltiplicazione, non quello
del contadino russo. Diciamo che è un algoritmo vecchio e caduto in
disuso. Ma esteticamente affascinante.

Prova ad applicare la regola che abbiamo dimostrato
r(15,13) =
r(30,6) + 15 =
r(60,3) + 15 =
r(120,1) + 60 +15 =
120 +60 +15 .
Tradotto: a destra di r(120,1) devi aggiungere tutti quegli "a"
che durante la strada risultavano associati ad un valore dispari
di a. D'altra parte non e' altro che la classica regola della
moltiplicazione che si impara alla scuola elementare, solo
applicata alle espressioni binarie dei numeri.
--------------------------------
Inviato via http://arianna.libero.it/usenet/

Posso tradurlo?

15*13=
=15*12+15=
=30*6+15=
=60*3+15=
=60*2+60+15=
=120*1+60+15=
=120+60+15=195

OK, funge. Ma non mi pare sia il metodo del contadino russo, che implica
calcoli fatti a mente, e risultati approssimati. Se non erro, il metodo
darebbe:

15*13=(circa)
=30*6=180
(errore relativo: 15/195=8%)


oppure

15*13=(circa)
=30*7=210
(errore relativo: 15/195=8%)

oppure

15*13=(circa)
=7*26=
=3*52=156
(errore relativo: 39/195=20%)

oppure

15*13=(circa)
=8*26=
=4*52=208
(errore relativo: 13/195=7%)


Nel metodo del contadino che io conosco, non è necessario portare uno
dei fattori ad 1. Basta ridursi ad un calcolo con un fattore ad una
cifra, fattibile a mente.

[Dalet]

Post by fm2766
OK, funge. Ma non mi pare sia il metodo del contadino russo, che implica
calcoli fatti a mente, e risultati approssimati. Se non erro, il metodo
15*13=(circa)
=30*6=180
(errore relativo: 15/195=8%)

Non ho letto nessun'altro post del 3d, ma questo contadino
russo non finisce mai... ti dico come lo conosco io.
Da fare: 15*13.

15 13
7 26
3 52
1 104
-----------
195

Ma con pari a sn si escludono, e poi il mugico e' furbissimo!
mette sempre il maggiore a destra:

13 15
6 30
3 60
1 120
------------
195

[fm2766]

Post by Dalet

Post by fm2766
OK, funge. Ma non mi pare sia il metodo del contadino russo, che implica
calcoli fatti a mente, e risultati approssimati. Se non erro, il metodo
15*13=(circa)
=30*6=180
(errore relativo: 15/195=8%)

Non ho letto nessun'altro post del 3d, ma questo contadino
russo non finisce mai...

Va bè, mica è un male!

Post by Dalet
ti dico come lo conosco io.

Lo conosciamo diverso. Ma siccome sono in minoranza, avrete sicuramente
ragione voi. :-)

Post by Dalet
Da fare: 15*13.
15 13
7 26
3 52
1 104
-----------
195
Ma con pari a sn si escludono, e poi il mugico e' furbissimo!

mugico??

Post by Dalet
13 15
6 30
3 60
1 120
------------
195

Questo pure lo conoscevo, ma con un altro nome. Vabbè, ricorderò male. :-(
Spero non me ne vorrai a male se ho allungato il 3d. :-D

[Tetis]

Post by fm2766
Lo conosciamo diverso. Ma siccome sono in minoranza, avrete sicuramente
ragione voi. :-)

Se ti puo' essere di conforto io ho qualche reminiscenza
di un algoritmo per la moltiplicazione in base ottale
che anche quello non richiedeva di ricordarsi le
tabelline, e permetteva di tenere a mente meno numeri
da sommare, ma e' da anni che non ne sento piu' parlare,
quello era l'algoritmo di un contadino siciliano.

Post by fm2766

Post by Dalet
Da fare: 15*13.
15 13
7 26
3 52
1 104
-----------
195
Ma con pari a sn si escludono, e poi il mugico e' furbissimo!

mugico??

E' una parola di origine francese particolarmente diffusa in
Piemonte e nel genovese, per via della storia che Genova
aveva gli empori in Crimea. Significa, a secondo dei contesti
paisa' oppure poveraccio, o semplicemente contadino, per
l'appunto.

Post by fm2766

Post by Dalet
13 15
6 30
3 60
1 120
------------
195

Questo pure lo conoscevo, ma con un altro nome. Vabbè, ricorderò male. :-(
Spero non me ne vorrai a male se ho allungato il 3d. :-D

--------------------------------
Inviato via http://arianna.libero.it/usenet/

[Festen]

Post by Tetis
Se ti puo' essere di conforto io ho qualche reminiscenza
di un algoritmo per la moltiplicazione in base ottale
che anche quello non richiedeva di ricordarsi le
tabelline, e permetteva di tenere a mente meno numeri
da sommare, ma e' da anni che non ne sento piu' parlare,
quello era l'algoritmo di un contadino siciliano.

Me lo puoi indicare? grazie.

[Tetis]

Post by Festen

Post by Tetis
Se ti puo' essere di conforto io ho qualche reminiscenza
di un algoritmo per la moltiplicazione in base ottale
che anche quello non richiedeva di ricordarsi le
tabelline, e permetteva di tenere a mente meno numeri
da sommare, ma e' da anni che non ne sento piu' parlare,
quello era l'algoritmo di un contadino siciliano.

Me lo puoi indicare? grazie.

Come dicevo e' da tanti anni, ero piccolo ed e' rimasta
appena una reminiscenza. Funzionava usando otto dita
a tenere le cifre ed il pollice per appuntarle. Ero piccolo,
ma provavo a fare il conto a mente, usando tutti i trucchi
che mi venissero a mente, ma perdevo sempre la gara :-)


--------------------------------
Inviato via http://arianna.libero.it/usenet/

[fm2766]

Post by Tetis

Post by Festen

Post by Tetis
Se ti puo' essere di conforto io ho qualche reminiscenza
di un algoritmo per la moltiplicazione in base ottale
che anche quello non richiedeva di ricordarsi le
tabelline, e permetteva di tenere a mente meno numeri
da sommare, ma e' da anni che non ne sento piu' parlare,
quello era l'algoritmo di un contadino siciliano.

Me lo puoi indicare? grazie.

Come dicevo e' da tanti anni, ero piccolo ed e' rimasta
appena una reminiscenza. Funzionava usando otto dita
a tenere le cifre ed il pollice per appuntarle. Ero piccolo,
ma provavo a fare il conto a mente, usando tutti i trucchi
che mi venissero a mente, ma perdevo sempre la gara :-)
--------------------------------
Inviato via http://arianna.libero.it/usenet/

Non è che era in base dodici e contavi falangi, falangine e falangette
delle altre quattro dita col pollice? Perché ci sono popolazioni che
contano così! La moltiplicazione potrebbe essere uno sviluppo di quel
modo di contare.

[Tetis]

Post by fm2766

Post by Tetis

Post by Festen
Me lo puoi indicare? grazie.

Come dicevo e' da tanti anni, ero piccolo ed e' rimasta
appena una reminiscenza. Funzionava usando otto dita
a tenere le cifre ed il pollice per appuntarle. Ero piccolo,
ma provavo a fare il conto a mente, usando tutti i trucchi
che mi venissero a mente, ma perdevo sempre la gara :-)
--------------------------------
Inviato via http://arianna.libero.it/usenet/

Non è che era in base dodici e contavi falangi, falangine e falangette
delle altre quattro dita col pollice? Perché ci sono popolazioni che
contano così! La moltiplicazione potrebbe essere uno sviluppo di quel
modo di contare.

Chissà, forse un giorno mi ricorderò i dettagli e magari è proprio
come dici, avevo riportato questo per dire che condivido il disagio
di non ricordare un metodo di calcolo veloce. Fra l'altro, nel frattempo
ho comprato Le Scienze ed ho trovato che in inghilterra un contabile
Fowler sviluppò un metodo di calcolo in base ternaria, la particolarità
è che è un metodo che fa uso della somma, ma anche della sottrazione
di potenze di tre, si chiama base ternaria compensata. Questo metodo
è stato in seguito adottato dai ricercatori russi ed è stato dimostrato
anche
che è il sistema numerico di maggiore efficienza computazionale, entro
una larga classe di sistemi considerati che include il binario ed il
decimale.

Riflettendo sulla base otto consideravo che i resti delle potenze di dieci
sono 2, 4, 8, 0, e poi ancora 2. Ma va anche notato che 8 in base 8 è 10
Questo significa che la conversione in
base ottale di un numero richiede di saper solo fare le moltiplicazioni
per due. Per esempio 24 = 4 + 20 + 10 = 34. Poi si potrebbe provare
a guardare se le tabelline in base otto hanno qualche semplificazione
particolare.

1 2 3 4 5 6 7
2 4 6 10 12 14 16
3 6 11 14 ....

ma non mi sembrano più facili di quelle in base dieci a prima vista,
a meno che non
ci sia qualche proprietà, che si può sfruttare, del fatto che 8 = 2^3 per
ottenere i prodotti in base otto dai resti delle cifre in base 2.
Ad ogni modo se ti risulta che il metodo in base 12 è particolarmente
efficace potrebbe essere che fosse quello.

--------------------------------
Inviato via http://arianna.libero.it/usenet/

[Dalet]

Post by fm2766

Post by Dalet
Ma con pari a sn si escludono, e poi il mugico e' furbissimo!

mugico??

Anche col De Mauro online: contadino russo.