Re: [obm-l] Conversão de Números em Base Negativa

["Henrique Rennó" <henrique.renno@xxxxxxxxx>]

Olá Ricardo!

Eu acredito que a função mod implementada em linguagens de programação podem diferir em resultado. Acredito que isso deva ser um assunto bem antigo, pois a função mod deve existir desde que as linguagens começaram a ser implementadas.

Digitando no google "1001 modulo -2" a resposta retornada é -1.
Digitando na calculadora no Windows 1001 mod -2 a resposta retornada é 1.
Digitando no MS Excel "=MOD(1001,-2)" a resposta retornada é -1.

Acredito que seja uma escolha do valor teto ou chão na divisão, ou seja, 1001/(-2) = -500,5.
O google e o Excel consideram o quociente da divisão como -501 de forma que 1001 = (-501)*(-2) -1 --> teto(-500,5) = -501
A calculadora do Windows considera o quociente da divisão como -500 de forma que 1001 = (-500)*(-2) +1 --> chão(-500,5) = -500

Por isso que fico em dúvida fico em dúvida com relação ao método de divisões sucessivas pelo valor da nova base. Mas para garantir que o valor da operação módulo seja sempre positivo é necessário somar o valor da base ao número e tirar novamente o módulo. No caso de um valor negativo como o -1 acima temos: (-1 + 2) mod 2 = 1. Os valores positivos não serão alterados: (1 + 2) mod 2 = 1.

O que gostaria de entender mais profundamente é o raciocínio entre conversões de números (que são apenas permutações de símbolos que representam certa quantidade nas várias "posições de grandeza" como unidades, dezenas, centenas,... na base 10 que comumente efetuamos nossos cálculos).

A conversão 1001(10) para base (-2) seria o problema de achar os valores de N e A[i] (0 <= i <= N) para os quais a seguinte igualdade seja verdadeira (na verdade termos com base elevada a valores > N seriam 0, ou seja, A[j] = 0 para j > N):

1*(10)^3 + 0.(10)^2 + 0.(10)^1 + 1.(10)^0 = A[N]*(-2)^N + A[N-1]*(-2)^(N-1) + A[N-2]*(-2)^(N-2) + ... + A[1]*(-2)^1 + A[0]*(-2)^0

Caso eu tenha cometido algum engano durante as passagens peço que corrijam.

Alguém teria a indicação de algum livro de teoria dos números que trata o assunto de bases numéricas com profundidade???

Grato pela atenção de todos!

Abraços!

On 4/18/07, Ricardo Bittencourt <ricbit@700km.com.br> wrote:

Henrique Rennó wrote:
> Olá Ricardo!
> Por acaso você é o ricbitbr no TopCoder???
Sou eu sim, sempre que dá eu faço uns SRMs por lá.

> Ainda estou em dúvida com relação a esse problema. Suponha a seguinte
> conversão:
>
> 1001(10) = n(-2)
>
> ou seja, passar o número 1001 na base 10 para n na base -2. (resposta:
> n = 10000111001)
>
> Qual seria o procedimento para efetuar essa conversão???

Converter de decimal pra binário você sabe né? Se for ímpar, subtrai 1 e
divide por 2; se for par, divide por 2; repete até chegar em zero. Com
base -2 é exatamente a mesma coisa, só que você divide por -2:

1001 (1)
1001-1=1000/-2=-500
-500 (0)
-500/-2=250
250 (0)
250/-2=-125
-125 (1)
-125-1=-126/-2=63
63 (1)
63-1=62/-2=-31
-31 (1)
-31-1=-32/-2=16
16 (0)
16/-2=-8
-8 (0)
-8/-2=4
4 (0)
4/-2=-2
-2 (0)
-2/-2 =1
1 (1)
1-1 =0

Lendo os restos de trás para frente, 10000111001. Agora é só generalizar
para outras bases (negativas ou complexas).

--
Ricardo Bittencourt
=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=========================================================================

-- 
Henrique