 |
 |
 |
 |
 |
 |
 |
 |
| Os números 687 e 1000 apresentam a mesma seqüência |
[ Anterior | Índice | Seguinte ]
Para calcular as representações MOF, NAF, wMOF e wNAF de quaisquer números inteiros positivos no intervalo ]0, 1024[, foi feito um programa, cuja manipulação será explicada nesta seção.
Primeiramente, obtenha o código fonte do programa em C que encontra-se aqui. Descompacte o arquivo no diretório de sua preferência. Entre no diretório mac499/ e siga as instruções que estão no arquivo Readme.txt para compilar e executar o programa. (Observação: as instruções para compilar e executar o programa devem ser realizadas no Linux. Para o Windows, utilize os comandos próprios do compilador utilizado)
Ao executar o programa, será pedido para o usuário entrar com um número inteiro positivo no intervalo ]0, 1024[. Em seguida, será pedido o tamanho da janela w utilizada nos cálculos de wMOF e wNAF. Após isso, serão mostrados na tela as representações MOF, NAF, wMOF e wNAF.
Caso queira continuar calculando as representações para outros números inteiros positivos no intervalo ]0, 1024[, repita o processo descrito no parágrafo anterior. Caso contrário, ou seja, não queira calcular essas representações para outros números, digite 0 (zero) para sair do programa.
Abaixo estão os códigos que geram as formas MOF, NAF, wMOF e wNAF e suas respectivas análises. Como pode ser visto em [ 2 ], há outro modo de se calcular essas formas. Os algoritmos abaixo implementam a explicação dada anteriormente sobre cada representação:
/************************************ MOF *************************************/
/* Função que calcula o MOF de um string binário */
/* Recebe: */
/* - um inteiro n --> o número de iterações */
/* - um vetor de inteiros b --> a representação binária do número */
/* - um vetor de inteiros mof, onde vai ser "devolvida" a forma MOF de d */
01 void MOF (int n, int b[], int mof[]) {
02 int i, j;
03 mof[n] = b[n - 1];
04 for (i = n - 1; i > 0; i--) mof[i] = b[i - 1] - b[i];
05 mof[0] = - b[0];
06 }/* MOF -------------------------------------------------------------------*/
|
Nas linha 03 é atribuído o valor do bit mais a esquerda (mais significativo) como sendo o do primeiro bit da representação binária usual. Isso garante: O maior bit não nulo é 1.
Na linha 04 é feita a subtração bit a bit das representações binárias do número nas formas d e 2d. Isso garante: Os sinais dos bits adjacentes não nulos (sem considerar os bits nulos) são opostos.
Na linha 05 é atribuído o valor do bit mais a direita (menos significativo) como sendo o do último bit da representação binária usual, com o sinal negativo. Isso garante: O menor bit não nulo é -1.
/************************************ NAF *************************************/
/* Função que calcula o NAF de um string binário */
/* Recebe: */
/* - um inteiro n --> o número de iterações */
/* - um vetor de inteiros b --> a representação binária do número */
/* - um vetor de inteiros naf, onde vai ser "devolvida" a forma NAF de d */
01 void NAF (int n, int b[], int naf[]) {
02 int i, j;
03 for(i = 0; i < n ; i++) naf[i] = b[i];
04 naf[n] = 0;
05 i = 0;
06 while ((i + 2) <= n) {
07 if (naf[i] == 1 && naf[i + 1] == 1) {
/* transformação NAF */
08 naf[i] = -1;
09 naf[i + 1] = 0;
10 naf[i + 2] = 1;
11 i += 2;
12 }
13 else i++;
14 }
15 }/* NAF -------------------------------------------------------------------*/
|
Nas linha 03 e 04, o algoritmo faz uma cópia da representação binária do número no vetor naf, acrescentando um zero a esquerda.
Da linha 05 em diante, o algoritmo funciona da seguinte maneira:
- Começando pelo bit mais a direita (menos significativo), são verificados esse bit e o próximo bit a esquerda.
- Se ambos forem iguais a 1, esse 11 é substituído por 01 e o próximo bit a esquerda desse 11 recebe -1.
- Caso contrário, verificam-se os próximos 2 bits a esquerda e o processo se repete.
/*********************************** wMOF *************************************/
/* Função que calcula o wMOF de um string binário */
/* Recebe: */
/* - um inteiro n --> o número de iterações */
/* - um vetor de inteiros b --> a representação binária do número */
/* - um vetor de inteiros wmof, onde vai ser "devolvida" a forma wMOF de d */
01 void wMOF (int n, int w, int b[], int wmof[]) {
02 int i, j, num, potencia, aux, aux1[NMAX + 1], aux2[NMAX];
03 if (w == 1) {
04 for (i = 0; i < n; i++) wmof[i] = b[i];
05 wmof[n] = 0;
06 }
07 else {
08 MOF(n, b, aux1);
09 i = n;
10 while ((i - w) > 0) {
11 num = 0;
12 potencia = pot (2, w - 1);
13 for (j = i; j > (i - w); j--) {
14 wmof[j] = 0;
15 num += aux1[j] * potencia;
16 potencia /= 2;
17 }
18 potencia = pot (2, w);
19 aux = num;
20 if (aux % 2 != 0) {
21 if (aux < pot (2 , (w - 1))) wmof[i - w + 1] = aux;
22 else wmof[i - w + 1] = aux - potencia;
23 }
24 else {
25 for(j = 0; j < w; j++) aux2[j] = 0;
26 if (aux < 0) {
27 num = converte (-aux, aux2);
28 for (j = i, num = w - 1; j > i - w; j--) wmof[j] = - aux2[num--];
29 }
30 else {
31 num = converte (aux, aux2);
32 for (j = i, num = w - 1; j > i - w; j--) wmof[j] = aux2[num--];
33 }
34 }
35 }
36 }
37 }/* wMOF-------------------------------------------------------------------*/
|
Das linhas 03 a 06 é tratado o caso em que w = 1.
Na linha 08, o algoritmo transforma a representação binária do número para a forma MOF. Ao fazer a função receber como argumento o número já na forma MOF ao invés de recebê-lo na representação binária usual, estaríamos economizando tempo e retiraríamos a linha 08.
Da linha 09 em diante, o algoritmo funciona da seguinte maneira:
- Começando pelo bit mais a esquerda (mais significativo), são selecionados w bits. Esses w bits representam algum número na representação binária (potência 2) e são transformados na representação decimal (potência 10) (linhas 10 a 17).
- Como na forma wMOF cada dígito não nulo é ímpar e menor que 2w - 1 em valor absoluto, temos 2 casos:
* Caso o número obtido seja ímpar e:
- menor que 2w - 1 em valor absoluto, a linha 21 é executada.
- não seja menor que 2w - 1 em valor absoluto, a linha 22 é executada.
* Caso o número obtido seja par, transformamos esse número para a forma binária e :
- caso o número seja negativo, executamos as linhas 26 a 29.
- caso contrário, executamos as linhas 30 a 33.
- Em seguida, o processo se repete.
/*********************************** wNAF *************************************/
/* Função que calcula o wNAF de um string binário */
/* Recebe: */
/* - um inteiro n --> o número de iterações */
/* - um inteiro w --> a largura da janela usada pelo wNAF */
/* - um vetor de inteiros b --> a representação binária do número */
/* - um vetor de inteiros wnaf, onde vai ser "devolvida" a forma wNAF de d */
01 void wNAF (int n, int w, int b[], int wnaf[]) {
02 int i, j, num, potencia, aux[NMAX + 1];
03 if (w == 1) {
04 for (i = 0; i < n; i++) wnaf[i] = b[i];
05 wnaf[n] = 0;
06 }
07 else {
08 MOF(n, b, aux);
09 i = 0;
10 while ((w + i) < n) {
11 num = 0;
12 potencia = 1;
13 if (aux[i] != 0) {
14 for (j = i; j < (w + i); j++) {
15 num += aux[j] * potencia;
16 potencia *= 2;
17 }
18 potencia = pot (2, w);
19 if (num < pot (2 , (w - 1))) wnaf[i] = num;
20 else wnaf[i] = num - potencia;
21 i += w;
22 }
23 else {
24 wnaf[i] = 0;
25 i++;
26 }
27 }
28 }
29 }/* wNAF ------------------------------------------------------------------*/
|
Das linhas 03 a 06 é tratado o caso em que w = 1.
Na linha 08, o algoritmo transforma a representação binária usual do número para a forma MOF. Ao fazer a função receber como argumento o número já na forma MOF ao invés de recebê-lo na representação binária usual, estaríamos economizando tempo e retiraríamos a linha 08.
Da linha 09 em diante, o algoritmo funciona da seguinte maneira:
- Começando pelo bit mais a direita (menos significativo), é verificado se esse bit é nulo ou não. Caso o bit seja igual a 0, são executadas as linhas 23 a 26. Caso contrário, são selecionados w bits. Esses w bits representam algum número na representação binária (potência 2) e são transformados na representação decimal (potência 10) (linhas 14 a 17). Isso garante: Dentre quaisquer w dígitos consecutivos, ao menos um é não nulo.
- Caso o número obtido não seja menor que 2w - 1 em valor absoluto, a linha 20 é executada. Caso contrário, a linha 19 é executada. Isso garante: Cada dígito não nulo é ímpar e menor que 2w -1 em valor absoluto.
- Em seguida, o processo se repete. Assim que o algoritmo termina, o bit mais significativo não nulo é positivo.
Os gráficos abaixo demonstram a quantidade de vezes em que o vetor com a representação binária inicial é modificado até se obter a forma de representação binária com sinal, de acordo com o tamanho de w :
|
|
|
|
|
|
|
|
| Os números 687 e 1000 apresentam a mesma seqüência |
Dos gráficos apresentados, podemos notar que a forma wMOF executa menos modificações no vetor do que a forma wNAF, dependendo do número a ser calculado e do tamanho da janela w.
|
|