O algoritmo mais rápido do oeste

Dia desses um amigo me passou um probleminha bem divertido. O enunciado é simples: dado um vetor ordenado, construa uma binary search tree, balanceada, com os mesmos elementos do vetor. Esse problema tem uma solução trivial em O(n log n) e uma solução esperta em O(n), mas eu acabei achando uma terceira solução, com o algoritmo mais rápido do oeste: ele roda em O(0)!

Vamos revisar as respostas tradicionais antes. A solução trivial é usar uma árvore binária auto-balanceante, como a AVL ou a Red-Black, e inserir os elementos nela, um por um. Como você vai inserir n elementos e o custo de inserção é O(log n), então o total desse algoritmo é O(n log n).

Mas fazendo dessa maneira, você não está usando a informação de que o vetor estava ordenado. Com uma recursão simples você consegue aproveitar esse fato, e construir a árvore em apenas O(n). Um exemplo em python é assim:

def build_tree(vector):
  def partition(start, end):
    if (end < start):
      return None
    middle = start + (end-start) / 2
    return (vector[middle], 
            partition(start, middle-1), 
            partition(middle+1, end))
  return partition(0, len(vector) - 1)

Aparentemente, essa solução é ótima. Se você vai criar uma estrutura de dados nova usando os dados da antiga, o mínimo de trabalho que você precisa é copiar os elementos de uma pra outra, e isso limita em O(n) certo? Quase! Você pode contornar essa limitação se usar uma estrutura de dados implícita, e é isso que vamos tentar fazer.

Para usar o vetor ordenado original como uma estrutura implícita, nós precisamos criar um isomorfismo entre o vetor ordenado e a binary search tree. Se for possivel criar esse isomorfismo, então na verdade eu não preciso fazer nada pra converter o vetor, ele já é equivalente à árvore. E um algoritmo que não faz nada é um algoritmo O(0)! Eu poderia chamar essa estrutura de dados nova de Implicit Balanced Binary Search Tree, mas é muito comprido, então vou chamá-la de Cactus Binário (apropriado, daqui em diante as coisas vão ficar espinhosas).

Mas vamos ao isomorfismo então. Como o vetor está ordenado, então os valores dos elementos em si não importam muito, e nós podemos trabalhar só com os índices, sem perda de generalidade. Além disso, para as demonstrações ficarem mais simples, vamos dividir em dois casos. Digamos que o tamanho do vetor é N, então o primeiro caso que vamos tratar é quando N pode ser escrito como 2^h-1 para algum h>0. Nesse caso, o Cactus Binário é uma árvore perfeita (todas as folhas estão no mesmo nível e todos os nós internos tem dois filhos):

Para criar o isomorfismo, eu preciso fornecer duas funções que, para um dado índice, me retornem o índice do filho à esquerda e do filho à direita. Depois de pensar um pouco, acabei chegando nas funções abaixo:

left(x) = x - (x & (-x)) / 2
right(x) = x + (x & (-x)) / 2

Isso é mágica? Não, é matemática! Para entender porque as expressões funcionam, é só olhar para a árvore anterior usando a visão além do alcance:

Olha só que bacana, quando você olha para os índices da árvore em binário, parece que o nível em que está o índice é igual ao número de zeros no final da representação binária dele. Na verdade, nós podemos provar isso, usando indução na altura da árvore.

Vejamos: para uma árvore de altura unitária, o único elemento é o 1, que está no nível zero e tem 0 bits zero no final, então a base de indução está ok. Se a árvore tem altura h, então ela tem 2^h-1 elementos. O elemento central é o 2^h-1, que tem h-1 zeros no final e está no nível h-1. A sub-árvore da esquerda é uma árvore balanceada de tamanho 2^h-1-1, que funciona pela hipótese de indução. A sub-árvore da direita é igual à da esquerda, se você ligar o bit mais significativo de cada índice. Setar o bit mais à esquerda não muda a quantidade de bits zero à direita, então podemos usar a hipótese de indução novamente, e pronto: QED.

Agora ficou fácil achar a fórmula né? Se você tem um índice x no nivel h, então o filho à esquerda é o maior número com h-1 zeros à direita que seja menor que x, e o análogo vale para o filho à direita. Ou seja, pra descer do nível h para o nível h-1 pela esquerda, basta subtrair 2^h-1  (ou somar, se for pela direita).

E computacionalmente como eu faço isso? Basta achar o bit 1 mais à direita do número, dividir isso por dois e subtrair do número original. Para achar o primeiro bit 1, o truque é calcular x & (-x). Vamos provar: pela definição de complemento de dois, negar é o mesmo que inverter e somar um. Se o número em binário for algo do tipo xxxx10000, negado ele fica yyyy01111, e quando você soma um, o carry propaga até bater no zero, ficando yyyy10000. Quando você faz o AND, os primeiros bits dão zero porque o AND de um bit e seu complemento é sempre zero, e os últimos bits dão zero porque o AND de qualquer bit com zero dá zero. Sobra só o primeiro bit 1 à direita, QED.

Juntando tudo agora as duas fórmulas são evidentes. Mas pra completar o isomorfismo eu ainda preciso de uma fórmula que me indique onde está a raiz da árvore. A fórmula em si é simples: a raiz é a maior potência de dois menor ou igual ao tamanho do vetor, ou seja, basta achar o primeiro bit 1 à esquerda do tamanho.

Para achar o primeiro bit 1 à esquerda não tem nenhum truque tão simples quanto à direita, mas felizmente existe uma alternativa: os processadores x86 possuem um opcode meio desconhecido chamado BSR (bit scan reverse), que retorna exatamente onde está esse bit à esquerda. Em processadores bons, como o Core 2 Duo, o BSR é uma operação O(1), mas isso não é verdade em todos os processadores (por exemplo, não é verdade nos AMDs). Se você não tiver o BSR por hardware, pode fazer uma busca binária nos bits do número, que é uma operação O(log log n).

Isso conclui o primeiro caso. Vamos ver agora o que acontece quando o tamanho é um número qualquer. O pior caso do algoritmo é quando o tamanho é uma potência de dois, e o Cactus Binário fica assim:

Uepa! Essa árvore está balanceada? Bem, depende da sua definição de balanceada. Nessa árvore, o maior caminho entre a raiz e uma folha é 4, o que parece muito. Mas, na verdade, não dá criar uma árvore que tenha um caminho máximo menor. Se o caminho máximo fosse 3, então a árvore poderia ter no máximo 7 elementos, e pelo princípio da casa dos pombos a árvore de tamanho 8 com caminho máximo 3 é impossível. De fato, se você tentar balancear mais a árvore, o melhor que você consegue é algo assim:

Logo, o caminho máximo do Cactus Binário é o mesmo caminho máximo da árvore balanceada. Note, entretanto, que isso é melhor que as árvores auto-balanceantes! O caminho máximo da AVL, no pior caso, é 1.44log(n), e o da Red-Black é 2log(n), ambos maiores que o Cactus Binário.

Com isso, nós provamos o isomorfismo para os dois casos, e o algoritmo O(0) realmente funciona! Mas a grande dúvida agora é: ele serve pra alguma coisa? Na verdade, a grande vantagem da árvore binária é que ela faz inserções em O(log n), enquanto que uma inserção no Cactus Binário é apenas O(n). Por isso, nas aplicações práticas da vida real a árvore binária ganha. Aparentemente, a única utilidade do Cactus Binário é para escrever blog posts :)

Mais mágicas com calculadoras

Quando eu era criança, a mágica que eu mais gostava era aquela onde o ilusionista serra a assistente ao meio. Acho que a graça era tentar entender como ele fazia aquilo, levei um tempão para descobrir o truque. Usando uma calculadora também temos um truque parecido, mas ao invés de serrar uma assistente, vamos cortar um número em dois!

Para começar essa mágica, peça para a criança digitar o número mágico 142857 na calculadora:

Agora peça para que ela multiplique esse número por dois:

Olha só! Você cortou o número ao meio e juntou as partes ao contrário, 14-2857 virou 2857-14!

Agora peça para ela digitar novamente o número mágico e multiplicar por três:

Ahá! Novamente você cortou o número ao meio, 1-42857 virou 42857-1.

Você pode continuar a mágica a partir daqui, esse truque funciona com todos os múltiplos até 6:

142857 * 1 = 142857

142857 * 2 = 285714

142857 * 3 = 428571

142857 * 4 = 571428

142857 * 5 = 714285

142857 * 6 = 857142

Aparentemente, a parte díficil desse truque é memorizar o número mágico. Quando você está cercado de crianças barulhentas, não é fácil lembrar 142857! Mas, felizmente, você não precisa decorar o número. É só lembrar que ele é a dizíma periódica de 1/7, e você pode usar a própria calculadora para calcular a dízima:

1/7 = 0.142857142857142857...

A pergunta natural é: tem outras dízimas com essa propriedade, ou o 142857 é especial? Espantosamente, existem sim outros números. Eles tem até nome: são os números cíclicos. Para achar esses outros números, vale a pena entender porque o 1/7 funciona, e para isso é só observar o comportamento da dízima no algoritmo de divisão longa:

Você começa dividindo o número 1, e sempre que o resto é menor que 7, coloca um zero atrás e continua. Note que, quando você divide por 7, só tem sete restos possíveis: 0, 1, 2, 3, 4, 5 e 6. Se o resto for zero em algum momento, a divisão acaba e o resultado é exato. Mas se em algum momento o resto repetir, ou seja, for igual a algum resto que já apareceu antes, então você tem uma dízima.

Os números cíclicos são formados por divisões de período máximo. Como você nunca pode ter um zero de resto, então no caso da dízima de 7, o maior período possível seria seis (felizmente é o caso). Você começa com o resto 1, e quando chega no 1 de novo começa a repetir, como no diagrama abaixo:

Veja como agora dá pra entender porque os números cíclicos funcionam: 142857 é a dízima de 1/7. Se a gente multiplicar 1/7 por dois, teremos 2/7, e a dízima tem que ser o dobro também. Mas se você olhar no diagrama, multiplicar por dois é a mesma coisa que começar a percorrer o diagrama a partir do 2, ao invés de começar no 1. Mas não importa de onde você começa, a seqüência será sempre a mesma, e daí o resultado vai ser uma rotação da dízima original!

Sabendo que os números cíclicos são as dízimas de período máximo, já dá pra começar a procurar propriedades desses números. Quais números, além do 7, geram dízimas de período máximo?

A primeira coisa que a gente nota é que esses números precisam ser primos. O raciocínio é relativamente simples. Vamos chamar esse número que procuramos de k, e fazer a divisão longa de 1 por k. Os restos da divisão longa formam uma recorrência, onde o primeiro termo é 1, e para os seguintes você coloca um zero no final e acha o resto da divisão por k:

R[0] = 1
R[n] = 10*R[n-1] (mod k)

Essa recorrência dá pra resolver de cabeça:

R[n] = 10ⁿ (mod k)

Para termos uma dízima de período máximo, o resto precisa ser 1 novamente quando n=k-1, ou seja:

R[k-1] = 10^k-1 = 1 (mod k)

Agora, do teorema de Euler-Fermat, nós sabemos que:

10^φ(k) = 1 (mod k)

Onde φ(k) é a função totiente. Ora, nós sabemos que, quando k é composto, o totiente é sempre menor que k-1, então k não pode ser composto, e portanto é primo.

Certo, então k precisa ser primo, mas qualquer primo serve? Nope. Tem alguns primos que não funcionam, como por exemplo onze. No caso do 11, é verdade que 10¹⁰ deixa resto 1, mas logo 10² já tem resto 1 também, então a dízima é muito mais curta que gostaríamos.

Na verdade, o segredo desses primos que funcionam é que... hum... ninguém sabe qual o segredo. Esse é um problema em aberto. Na verdade, a coisa é tão feia que ninguém sabe nem mesmo se esses primos são finitos ou infinitos. O melhor que podemos fazer é um script que ache os primeiros deles:

Script em python que acha os primeiros números cíclicos

Depois do sete, o primeiro primo que funciona é o 17, e o número cíclico associado é 0588235294117647. Note que esse é um caso onde o zero à esquerda faz diferença! Se a sua calculadora tiver um visor bem grande, dá pra divertir uma criança por um tempão com esse número :)

Mágicas com calculadoras

Tem um diálogo que sempre acontece quando vou visitar algum amigo que tenha filho pequeno. Eu sou apresentado pelo amigo como "o Ricbit, aquele amigo que gosta de Matemática". Aí a criança, espantada, responde "mas como assiiiiiim ele gosta de Matemática?!". E o amigo responde "ah, mas matemática com o tio Ricbit é divertida. Mostra pra ele, Ricbit!". E aí eu, que nem cheguei direito, já estou com a batata quente na mão!

Felizmente, eu já descobri alguns truques pra lidar com situações assim. Se a criança ainda está na fase de achar que matemática é aritmética, então uma abordagem que funciona bem é pedir uma calculadora emprestada,e falar que você vai usá-la pra fazer mágicas.

Uma das mágicas clássicas funciona assim:

1. Primeiro você pede pra criança digitar 13837, que é um número mágico.

2. Depois, você pergunta quantos anos tem o pai dela, e fala pra ela multiplicar aquele número mágico pela idade do pai. Digamos que o pai tem 42 anos, então o resultado será 581154.

3. Por fim, você fala pra criança multiplicar esse número que está no visor por outro número mágico, 73.

Surpresa! O resultado é 42424242, a idade do pai repetida até encher o visor da calculadora! Crianças adoram isso, eu imagino que o motivo é uma variação da Lei de Clarke. A criança não entende porque isso aconteceu, e qualquer conta suficientemente incompreensível é indistinguível de magia. (Pensando bem, isso funciona com estudantes de engenharia também).

O truque funciona com qualquer valor de idade, é claro. O motivo é simples: se você multiplicar os dois números mágicos, 13837*73 resulta em 1010101. Qualquer número de dois dígitos fica replicado quatro vezes quando você multiplica por 1010101. O ilusionismo do truque é que o par de números mágicos obfusca esse valor.

A pergunta natural nesse caso é: dá pra fazer a mágica com cinco repetições? Seis? Quantas eu quiser?

Isso só é possível se o número 101...01 não for primo. Sendo composto, você sempre pode separar os fatores em dois números mágicos. Vamos fazer um teste rápido. Para duas repetições não dá, 101 é primo. Para três repetições temos 259 e 39, para cinco temos 372731 e 271. Usando o Wolfram Alpha, dá pra checar manualmente que acima de duas repetições todos os números parecem compostos. Mas dá pra provar isso?

Eu achei que esse seria um problema complexo, mas acabou sendo mais fácil do que eu esperava! A prova pode ser feita só com matemática elementar. Suponha que o número que queremos fatorar gera n repetições, então ele pode ser escrito como a soma de uma progressão geométrica finita:



Se você notar que 100ⁿ é o mesmo que 10²ⁿ, então dá pra fatorar o numerador como diferença de quadrados:



Agora é só notar que, para n>2, os dois termos do numerador são bem maiores que 99, então nenhum deles simplifica completamente. Daí, o valor final sempre vai ter pelo menos dois fatores, o que completa a demonstração.

Ainda tem um monte de mágicas que podem ser feitas com calculadoras, mas essas ficam para posts futuros :)

(Obrigado ao Jacques Brancher e ao Fábio Moreira pelas idéias.)