SISTEMAS DE NUMERAÇÃO, UMA INTRODUÇÃO - ULLYSSES SODRÉ

Prévia do material em texto

Sistemas de Numerac¸a˜o: Uma introduc¸a˜o
Ulysses Sodre´
Londrina-PR, 17 de agosto de 2012
1 Sistema Bina´rio
O sistema bina´rio e´ um sistema posicional cuja base possui 2 sı´mbolos, que sa˜o os
nu´meros 0 e 1. Isto significa que todo nu´mero no sistema bina´rio e´ formado por zeros
e uns, a`s vezes tendo um ponto para separar a parte inteira da parte fraciona´ria.
Mecanismo pra´tico para obter a sequeˆncia de zeros e uns no sistema bina´rio:
Vamos considerar o nu´mero inteiro 109, visando obter a sua representac¸a˜o bina´ria.
1. Realizamos a divisa˜o inteira do dividendo 109 pelo divisor 2, para obter o quo-
ciente q0 = 54 e o resto r0 = 1:
109 2
[1] 54
2. Agora, realizamos a divisa˜o inteira do dividendo q0 = 54 pelo divisor 2, ob-
tendo o quociente q1 = 27 e o resto r1 = 0:
54 2
[0] 27
3. Depois, realizamos a divisa˜o inteira do dividendo q1 = 27 pelo divisor 2, ob-
tendo o quociente q2 = 13 e o resto r2 = 1:
27 2
[1] 13
4. Repetimos os passos anteriores, ate´ obter o u´ltimo quociente igual a zero, isto e´,
q6 = 0 e resto r6 = 1.
1 2
[1] 0
O quociente de cada divisa˜o e´ o dividendo na divisa˜o seguinte. Eis as sete diviso˜es:
109 2
[1] 54
↗ 54 2
[0] 27
↗ 27 2
[1] 13
↗ 13 2
[1] 6
↗ 6 2
[0] 3
↗ 3 2
[1] 1
↗ 1 2
[1] 0
1.1 Expansa˜o Bina´ria de um nu´mero inteiro maior ou igual a 1 2
Todas estas operac¸o˜es podem ser postas em um u´nico quadro:
109 2
[1] 54 2
[0] 27 2
[1] 13 2
[1] 6 2
[0] 3 2
[1] 1 2
[1] 0
1.1 Expansa˜o Bina´ria de um nu´mero inteiro maior ou igual a 1
Todo nu´mero inteiro na˜o negativo, pode ser escrito na base 2 como uma soma finita
de escalares multiplicados por poteˆncias na˜o negativas de 2.
Exemplo: O nu´mero 109 do sistema decimal, pode ser escrito como a soma:
109 = 1× 64 + 1× 32 + 0× 16 + 1× 8 + 1× 4 + 0× 2 + 1
= 1× 26 + 1× 25 + 0× 24 + 1× 23 + 1× 22 + 0× 21 + 1 = [1101101]2
Algoritmo gerador da sequeˆncia de zeros e uns no sistema bina´rio: Para o nu´mero
inteiro 109, tomaremos o divisor igual a 2 na tabela abaixo, dando destaque para os
quocientes e para os restos em cada divisa˜o.
Dividendo = 2 × Quociente + Resto Sentido Observac¸a˜o
109 = 2 × (54) + [1] ↑ quociente positivo
(54) = 2 × (27) + [0] ↑ quociente positivo
(27) = 2 × (13) + [1] ↑ quociente positivo
(13) = 2 × (6) + [1] ↑ quociente positivo
(6) = 2 × (3) + [0] ↑ quociente positivo
(3) = 2 × (1) + [1] ↑ quociente positivo
(1) = 2 × (0) + [1] ↑ quociente = zero
Este tipo de divisa˜o euclidiana e´ encerrado quando obtemos o quociente nulo. As
setas indicam que os restos das diviso˜es devem ser escritos de baixo para cima,
iniciando pelo u´ltimo resto obtido no processo.
ProfMat - Sistemas de Numerac¸a˜o: Uma introduc¸a˜o - Ulysses Sodre´ - Matema´tica - UEL - 2012
1.2 Expansa˜o Bina´ria de um nu´mero decimal menor que 1 3
1.2 Expansa˜o Bina´ria de um nu´mero decimal menor que 1
Todo nu´mero decimal menor que 1, pode ser escrito na base 2 como uma soma finita
de escalares multiplicados por poteˆncias negativas de 2.
Exemplo: O nu´mero decimal 0.78125, pode ser escrito como a soma:
0.78125 = 1× 0.50000 + 1× 0.25000 + 0× 0.12500 + 0× 0.06250 + 1× 0.03125
= 1× 2−1 + 1× 2−2 + 0× 2−3 + 0× 2−4 + 1× 2−5
= [0.11001]2 = [.11001]2
Agora, mostraremos como funciona o algoritmo para obter a sequeˆncia de zeros e
uns no sistema bina´rio, para o nu´mero decimal: 0.78125:
No. decimal × 2 = Produto Parte inteira Sentido
0.78125 × 2 = 1.56250 [1] ↓
0.56250 × 2 = 1.12500 [1] ↓
0.12500 × 2 = 0.25000 [0] ↓
0.25000 × 2 = 0.50000 [0] ↓
0.50000 × 2 = 1.00000 [1] ↓
Para representar o nu´mero real 109.78125, basta escrever:
109.78125 = [1101101.11001]2
Exercı´cio: Mostrar que 7.6 = [111.1001 1001 1001 1001 . . .]2.
1.3 Soma de nu´meros inteiros nas bases decimal e bina´ria
A soma dos sı´mbolos 0 e 1 no sistema bina´rio e´ obtida pela tabela cujos resultados
formam uma matriz sime´trica 2× 2 garantindo que a adic¸a˜o e´ comutativa:
+ 0 1
0 0 1
1 1 0
O zero que esta´ na u´ltima linha e u´ltima coluna da tabela de soma, representa o
nu´mero 10 na base 2, isto e´, a soma de 1 com 1 fornece 0, mas o 1 que sobra deve ser
adicionado aos valores localizados na coluna a` esquerda daquela que trabalhamos.
ProfMat - Sistemas de Numerac¸a˜o: Uma introduc¸a˜o - Ulysses Sodre´ - Matema´tica - UEL - 2012
1.4 Produto de nu´meros inteiros nas bases decimal e bina´ria 4
Comparativo entre a soma de nu´meros no sistema decimal e no sistema bina´rio
1 1 1
4 1 6 7
+ 9 7 7 6
1 3 9 4 3
1 1 1
1 0 0 1
+ 1 1 0 1
1 0 1 1 0
Exercı´cio: Mostrar que [11011.01]2 + [101.1101]2 = [100001.0001]2.
1.4 Produto de nu´meros inteiros nas bases decimal e bina´ria
O produto dos sı´mbolos 0 e 1 no sistema bina´rio e´ obtida pela tabela cujos resultados
formam uma matriz sime´trica 2× 2 garantindo que o produto e´ comutativo:
× 0 1
0 0 0
1 0 1
Comparativo entre o produto de nu´meros no sistema decimal e no sistema bina´rio
1 2 5
× 1 2 3
3 7 5
2 5 0
+ 1 2 5
1 5 3 7 5
1 0 0 1
× 1 0 1
1 0 0 1
0 0 0 0
+ 1 0 0 1
1 0 0 1 0 1
Exercı´cio: Mostrar que
1. [10]2 × [100]2 = [10000]2
2. [0.01]2 × [1.1]2 = [1.111]2
3. [11.01]2 × [101.1]2 = [10001.111]2
ProfMat - Sistemas de Numerac¸a˜o: Uma introduc¸a˜o - Ulysses Sodre´ - Matema´tica - UEL - 2012
Sec¸a˜o 2 Sistema de Numerac¸a˜o em uma base natural b > 1 5
2 Sistema de Numerac¸a˜o em uma base natural b > 1
Um sistema de numerac¸a˜o de base natural b > 1 e´ um sistema posicional em que os
nu´meros inteiros podem ser escritos em func¸a˜o de sı´mbolos, muitas vezes represen-
tados por nu´meros inteiros na˜o negativos, como 0, 1, 2, 3, 4, 5, . . . , b− 1.
Algoritmo gerador da sequeˆncia de restos na base b: Seja o dividendo a, o divisor
b > 1, os quocientes qj e os restos rj < b (j = 0, 1, 2, 3, 4).
dividendo = b · quociente + resto sentido
a = b · q0 + r0 ↑
q0 = b · q1 + r1 ↑
q1 = b · q2 + r2 ↑
q2 = b · q3 + r3 ↑
q3 = b · 0 + r4 ↑
A divisa˜o euclidiana termina quando obtemos o quociente nulo (q4 = 0, mas poderia
ter outro ı´ndice natural). As setas indicam que os restos das diviso˜es devem ser
escritos de baixo para cima, iniciando pelo u´ltimo resto obtido no processo. Assim,
a = b · q0 + r0 (1)
q0 = b · q1 + r1 (2)
q1 = b · q2 + r2 (3)
q2 = b · q3 + r3 (4)
q3 = b · 0 + r4 (5)
Reunindo todas estas igualdades, obtemos a expansa˜o de a na base b.
a = bq0 + r0 = b(bq1 + r1) + r0 Usar (2) em (1)
= b2 q1 + b r1 + r0 = b
2(bq2 + r2) + br1 + r0 Usar (3) em (2)
= b3q2 + b
2 r2 + b r1 + r0
= b3(bq3 + r3) + b
2r2 + br1 + r0 Usar (4) em (3)
= b4 q3 + b
3 r3 + b
2 r2 + b r1 + r0
Com q3 = r4 e os restos no sentido inverso obtemos a expnsa˜o na base b:
a = r4 b
4 + r3 b
3 + r2 b
2 + r1 b+ r0
ProfMat - Sistemas de Numerac¸a˜o: Uma introduc¸a˜o - Ulysses Sodre´ - Matema´tica - UEL - 2012
Sec¸a˜o 2 Sistema de Numerac¸a˜o em uma base natural b > 1 6
Os restos que aparecem na expansa˜o na base b obtidos na divisa˜o euclidiana, reali-
zam um papel importante na Matema´tica e na Matema´tica Computacional.
Detalhes interessantes:
1. Como a = bq0 + r0 e 0 ≤ r0, enta˜o bq0 ≤ a. Como 1 < b, enta˜o q0 < bq0, assim
q0 < a.
2. Como q0 = bq1 + r1 e 0 ≤ r1, enta˜o bq1 ≤ q0. Como 1 < b, enta˜o q1 < bq1, logo
q1 < q0.
3. Repetindo as ana´lise anteriores, obtemos a > q0 > q1 > q2 > q3 > q4 = 0.
Teorema 1: Dados a, b ∈ N, com b > 1, existem nu´meros naturais c0, c1, . . . , cn, deter-
minados de modo u´nico tal que
a = c0 + c1b+ c
2b2 + c3b3 + . . .+ cnb
n
Prova: A divisa˜o euclidiana garante que se a, b ∈ N e b > 1, existem q, r ∈ N tal que
a = bq + r
Desse modo, bq ≤ a. Como b > 1, enta˜o bq > q, assim q < bq < a e temos que q < a.
Usando o fato que q < a, faremos a demonstrac¸a˜o pelo Princı´pio de Induc¸a˜o Ma-
tema´tica completa, sobre o nu´mero natural a.
Se a= 0 ou a = 1, basta tomar c0 = a e n = 0, para que seja va´lida a expansa˜o.
A hipo´tese de induc¸a˜o completa, garante que para todo n natural com n < a, existem
m ∈ N e d0, d1, . . . , dm ∈ N tal que
q = d0 + d1b+ d2b
2 + d3b
3 + . . .+ dmb
m
Segue que
a = bq + r
= b(d0 + d1b+ d2b
2 + d3b
3 + . . .+ dmb
m) + r
= d0b+ d1b
2 + d2b
3 + d3b
3 + . . .+ dmb
m+1 + r
Tomando r = c0, d0 = c1, d1 = c2, e em geral, dj = cj−1 com n = m + 1, podemos
escrever
a = c0 + c1b+ c2b
2 + c3b
3 + c4b
3 + . . .+ cnb
n
A unicidade segue das construc¸o˜es u´nicas dos coeficientes.
ProfMat - Sistemas de Numerac¸a˜o: Uma introduc¸a˜o - Ulysses Sodre´ - Matema´tica - UEL - 2012
Sec¸a˜o 3 Explicando a multiplicac¸a˜o egı´pcia 7
3 Explicando a multiplicac¸a˜o egı´pcia
Para mostrar que a = 37×523 = 19351, construı´mos uma tabela com duas colunas e
va´rias linhas. O produto sera´ a soma dos valores da coluna da direita para os quais
os respectivos valores da esquerda (na mesma linha) sa˜o ı´mpares. A primeira linha
conte´m os multiplicandos. Os elementos seguintes da primeira coluna, sa˜o obtidos
por sucessivas diviso˜es inteiras de a por 2. Cada elemento seguinte da segunda
coluna, e´ o dobro da linha anterior na mesma coluna da direita.
Paridade Metades Dobros Somandos
ı´mpar 37 523 523
par 18 1046
ı´mpar 9 2092 2092
par 4 4184
par 2 8368
ı´mpar 1 16736 16736
Soma=19351
Explicac¸a˜o da tabela, com o uso da divisa˜o euclidiana: Com diviso˜es inteiras por
2, construı´mos a tabela, indicando os restos e quocientes dispostos na forma:
a = 37 r0 = 1 b = 523 r0 · b = 523
q1 = 18 r1 = 0 2
1b = 1046 r1 · 21b = 0
q2 = 9 r2 = 1 2
2b = 2092 r2 · 22b = 2092
q3 = 4 r3 = 0 2
3b = 4184 r3 · 23b = 0
q4 = 2 r4 = 0 2
4b = 8368 r4 · 24b = 0
q5 = 1 r5 = 1 2
5b = 16736 r5 · 25b = 16736
Soma = 19351
A tabela nos mostra todos os restos r0, r1, r2, r3, r4, r5 e podemos escrever:
a = r0 + 2 r1 + 2
2 r2 + 2
3 r3 + 2
4 r4 + 2
5 r5
a× b = r0(b) + r1(2b) + r2(22b) + r3(23b) + r4(24b) + r5(25b)
Como a = 37 e b = 523 e r0 = r2 = r5 = 1 e que r1 = r3 = r4 = 0, enta˜o:
37× 523 = 1(523) + 0(1046) + 1(2092) + 0(4184) + 0(8368) + 1(16736) = 19351
ProfMat - Sistemas de Numerac¸a˜o: Uma introduc¸a˜o - Ulysses Sodre´ - Matema´tica - UEL - 2012
	Sistema Binário
	Expansão Binária de um número inteiro maior ou igual a 1
	Expansão Binária de um número decimal menor que 1
	Soma de números inteiros nas bases decimal e binária
	Produto de números inteiros nas bases decimal e binária
	Sistema de Numeração em uma base natural b>1
	Explicando a multiplicação egípcia