Dado um sistema de aritmética de ponto flutuante \mathbb{F}(\beta, p, m, M), \beta \geq 2, demonstre que
a cardinalidade (isto é, o número total de elementos distintos) de \mathbb{F}(\beta, p, m, M) é
\operatorname{card} \mathbb{F}(\beta, p, m, M)=2(\beta-1) \beta^{p-1}(M-m+1)+1

Passo 1

O enunciado pede para demonstrar uma fórmula para a cardinalidade do conjunto de números de ponto flutuante \mathbb{F}(\beta,p,m,M). As informações que temos são:
  • A base é \beta, com \beta \ge 2.
  • A precisão (número de algarismos na mantissa) é p.
  • O expoente inteiro varia entre m e M (inclusive).
  • Queremos o número total de elementos distintos em \mathbb{F}(\beta,p,m,M), isto é, a cardinalidade \operatorname{card}\mathbb{F}(\beta,p,m,M).
Além disso, adotamos a definição padrão (implícita no enunciado) para números de ponto flutuante normalizados:
  • Cada número não nulo em \mathbb{F}(\beta,p,m,M) tem a forma
\pm (d_1.d_2d_3\ldots d_p)_\beta \,\beta^{e},
onde
d_1\in\{1,2,\dots,\beta-1\},
e para j=2,\dots,p
d_j\in\{0,1,\dots,\beta-1\},
e o expoente e satisfaz e\in\{m,m+1,\dots,M\}.
  • O número 0 está presente no conjunto e é representado separadamente (pois não tem representação normalizada com d_1\neq 0).

Passo 2

Vamos contar, de forma bem didática, todas as possibilidades para representar um número não nulo em \mathbb{F}(\beta,p,m,M). A ideia é multiplicar as opções independentes: sinal, mantissa (os dígitos) e expoente.
  1. Escolhas do sinal. Para o sinal temos exatamente duas opções:
\text{signo} \in \{+,-\},
logo há 2 escolhas.
  1. Escolhas da mantissa (os dígitos d_1,d_2,\dots,d_p).
  • O primeiro dígito d_1 é o dígito líder não nulo e pode assumir os valores 1,2,\dots,\beta-1. Então existem \beta-1 possibilidades para d_1.
  • Cada um dos p-1 dígitos restantes ( d_2,\dots,d_p) pode ser qualquer inteiro de 0 até \beta-1, ou seja, cada um tem \beta possibilidades.
  • Como as escolhas dos dígitos são independentes, o total de mantissas possíveis é
(\beta-1)\cdot \beta^{p-1}.
Aqui usei a regra do produto: se você tem a opções para uma coisa e b opções independentes para outra, há a\cdot b opções juntas.
  1. Escolhas do expoente e.
    O expoente pode ser qualquer inteiro no intervalo \{m,m+1,\dots,M\}, que contém exatamente
M-m+1
valores (contagem de termos consecutivos em um intervalo fechado). Portanto há M-m+1 escolhas para e.

Passo 3

Agora combinamos as três partes — sinal, mantissa e expoente — usando novamente a regra do produto (escolhas independentes): o número total de números não nulos em \mathbb{F}(\beta,p,m,M) é
2 \cdot (\beta-1)\cdot \beta^{p-1}\cdot (M-m+1).
Explicando em palavras: para cada uma das 2 escolhas de sinal, para cada uma das (\beta-1)\beta^{p-1} mantissas e para cada um dos M-m+1 expoentes, obtemos um número distinto.

Passo 4

Falta lembrar do zero. A contagem do passo anterior não inclui 0, porque a representação normalizada exige d_1\neq 0. O número 0 é um elemento adicional do conjunto \mathbb{F}(\beta,p,m,M). Assim, somamos 1 à contagem dos não nulos.
Portanto a cardinalidade total é
2(\beta-1)\beta^{p-1}(M-m+1)+1.
Como verificação rápida e concreta: se \beta=10, p=2, m=-1, M=1, então (\beta-1)\beta^{p-1}=9\cdot 10=90, M-m+1=3, logo não nulos =2\cdot 90\cdot 3=540 e total =540+1=541, o que bate com a fórmula acima.

Resposta

2(\beta-1)\beta^{p-1}(M-m+1)+1

Exercícios relacionados