Segunda-feira, 8 de Março de 2010

O regresso à memória novamente - Algoritmos - A multiplicação russa

Quando recuo no tempo e entro nas recordações da infância trago à memória figuras humanas que deixaram impressões que me acompanharam ao longo da minha existência.


A maior parte delas já não pertence ao número dos vivos. Algumas passaram pela vida e não construíram nada que perdurasse no tempo. Outros, pelo contrário, foram figuras cuja presença nunca foi indiferente aos que conviveram com eles.


A figura de que vou falar era um grande contador de histórias e essencialmente um criador de episódios biográficos inventados, mas de tal maneira convincentes que quem o ouvia era incapaz de duvidar da sua veracidade.
Eram famosos os episódios da sua vida no Brasil, onde nunca tinha estado, e que contava aos forasteiros que paravam na taberna onde passava as tardes depois de dormir a sesta, que fazia todo o ano. Os conterrâneos presentes e que já conheciam as histórias ouvidas noutras ocasiões tinham alguma dificuldade em conter o riso perante os pormenores da falsa autobiografia. É claro que o forasteiro não se manifestava, mas tudo indicava que “engolia” as patranhas pelas perguntas que de vez em quando fazia, o que animava ainda mais o ambiente. A gargalhada geral explodia no fim, depois da saída da “vítima”. As mentiras eram completamente inócuas e as histórias acabavam por preencher o tempo de forma agradável e não provocavam danos ou faziam mal a alguém.


Ainda estou a vê-lo, alto, bastante alto, magro, de bigode aparado, quase sempre sentado num batorel (assento de pedra) junto de uma porta, na estrada que atravessa a freguesia, com as pernas dobradas de tal maneira que um dos pés passava por trás da outra perna e para ser tirado era preciso levantar-se.
Foi caçador quase até ao fim da vida, só parando quando o reumatismo o impediu de se deslocar e lhe provocava dores de que se queixava.
Embora sem formação académica tinha conhecimentos de várias áreas, como geografia, história e também tinha alguns conhecimentos de matemática, apresentando, por vezes alguns problemas interessantes. Lembro-me de lhe ter ouvido falar que os camponeses russos no século XIX faziam a multiplicação utilizando uma maneira diferente da nossa. Só mais tarde descobri o famoso algoritmo que é deveras interessante e onde as potências de base dois mais uma vez têm o seu protagonismo.


Vejamos como os camponeses calculavam os produtos de que necessitavam no seu dia a dia. Imaginemos que um camponês vendeu 27 animais a 42 rublos cada um. Quanto realizou na venda?


Se fosse hoje utilizávamos uma máquina de calcular e obtínhamos o resultado imediatamente.


Se fosse nas décadas de 50 e 60 do século passado utilizávamos o algoritmo tradicional e demorávamos mais algum tempo, mas obtínhamos o resultado.


No entanto, os camponeses russos do século XIX faziam outras contas. Vejamos:
- Colocavam os números assim:

 

                                       

      
- O número 27 era dividido por 2 ignorando o resto e o 42 era duplicado.
- Continuando a dividir o número do lado esquerdo até obtermos 1 e a duplicar os números do lado direito.


Agora impõe-se uma pergunta: como é que chegamos ao resultado? Onde entram as potências de base dois?


O resultado obtém-se somando os números do lado direito que correspondem no lado esquerdo a números ímpares. Vejamos:


27 x 42 = 42 + 84 + 336 + 672 = 1 134


Utilizando uma calculadora rapidamente verificamos o resultado.


Temos de responder à segunda pergunta: “Onde entram as potências de base dois?”


- na coluna da esquerda, quando dividimos sucessivamente por dois(2) estamos a escrever o número 27 na base dois (2) ou seja:


27 ≡ 11011(2), ou seja se dividirmos 27 e os quocientes obtidos sucessivamente por 2 até obtermos quociente 1 teremos 27 na base 2:



                          

 



Tal como os números na base 10, também é possível decompor nas suas ordens os números escritos em qualquer base. Assim:


11011(2) = 1x24 + 1x23 + 0x22 + 1x21 + 1x20 ou


11011(2) = 24 + 23 + 21 + 1


Se efectuarmos as operações obteremos 27 que é o número original na base 10.


Do lado direito, o número 42 foi duplicado e seguidamente foram sendo feitas duplicações, o que corresponde a multiplicar o número 42 sucessivamente por 2, 22,  23, 24.
Com um pequeno raciocínio chegamos à seguinte conclusão:


27 x 42 = (24 + 23 + 21 + 1) x 42 ou


27 x 42 = 24 x 42 + 23 x 42 + 21 x 42 + 1 x 42 ou


27 x 42 = 16 x 42 + 8 x 42 + 2 x 42 + 1 x 42 ou


27 x 42 = 672 + 336 + 84 + 42 – os números da segunda coluna correspondentes aos números ímpares da primeira coluna, apresentados na ordem inversa, tendo em atenção as potências de base dois que foram crescendo.


27 x 42 = 1134 , tal como tínhamos concluido no início.


Agora para terminar um pequeno desafio:


Aplicando o algoritmo dos camponeses russos tente calcular:


23 x 57=
e
31 x 46 =


 

palavras-chave:
publicado por Frantuco às 11:59
link do artigo | comentar | ver comentários (1) | favorito

.mais sobre mim

.pesquisar

 

.Abril 2011

Dom
Seg
Ter
Qua
Qui
Sex
Sab
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

.artigos recentes

. O regresso à memória nova...

.arquivos

. Abril 2011

. Fevereiro 2011

. Janeiro 2011

. Novembro 2010

. Junho 2010

. Março 2010

. Fevereiro 2010

. Janeiro 2010

. Dezembro 2009

. Novembro 2009

. Outubro 2009

. Agosto 2009

. Julho 2009

. Junho 2009

. Maio 2009

. Abril 2009

. Março 2009

. Fevereiro 2009

. Janeiro 2009

. Dezembro 2008

. Novembro 2008

. Outubro 2008

. Setembro 2008

.palavras-chave

. todas as tags

.links

.Contador

Expedia
Expedia Discount Travel