Base de Resíduos e Números Afortunados

Já investiguei vários tipos de sistemas numéricos, mas há um que é bastante diferente dos outros, porque não há uma maneira direta para converter para outras bases.

Uma consequência do Teorema Chinês dos Restos é que podemos representar um número como um conjunto de restos. A única exigência é a de que os números da nossa base sejam primos entre si.

Por exemplo, se eu usar 2 e 3 como uma base, posso representar todos os números até 6. O 1 eu represento com a tupla (1,1), o 2 com (0,2), o 3 com (1,0), o quatro com (0,1), o 5 com (1,2).

Seu eu usar apenas números primos até 8 bits (são 53 primos), posso representar números até o seguinte:

64266330917908644872330635228106713310880186591609208114244758680898150367880703152525200743234420230.

Esse monstro de 101 dígitos necessitaria 334 bits para ser representado num computador. Entretanto, com o uso da aritmética modular, posso fazer muitas operações de apenas 1 byte. Repare que 53*8=424 bits, então não é espaço que é economizado, mas sim complexidade das operações.

Claro que produzir o resultado no final exige uma complicação adicional.

Adição e subtração são definidos assim:

(A + B) mod C = (A mod C + B mod C) mod C
(A - B) mod C = (A mod C - B mod C) mod C

Então, podemos ir somando números aos poucos e por partes até chegar a uma soma realmente grande sem nunca ter que operar com um número grande. Infelizmente, em algum momento será preciso converter para uma base mais prática para visualizar o resultado. Um algoritmo relativamente eficiente é o de Algoritmo de Garner, mas eu vou descrever uma forma de reconstruir o resultado que também nos ensina um pouco sobre esse tipo de base.

Dada uma base formada por (3,11,17), que podemos usar para representar números de 0 até 561 (3*11*17), e um número representado pelos restos (2,4,1), vamos procurar começando pelo primeiro número a satisfazer x%17=1, que é 1 (ou 18). Se formos somando 17, em algum momento vamos encontrar um número que, além de ter resto 1 para 17, terá resto 4 para 11. Ou seja, queremos resolver (18+(x*17))%11=4. Este número é 103. A partir de 103, precisamos encontrar um número que também tenha resto 2 para 3. Podemos pular de 187 em 187 (11*17). Ou seja, precisamos resolver (103+(x*187))%3=2. E isso nos leva a 290.

O que isso nos ensina? Os restos se repetem de 3 em 3, de 11 em 11, de 17 em 17, de 3*11 em 3*11, de 3*17 em 3*17, e de 11*17 em 11*17. E também de 3*11*17 em 3*11*17.

Agora vou introduzir os números afortunados. Um número afortunado é o menor inteiro maior que 1 que, somado a um primorial resulta num primo.

Se tivermos uma base de restos baseada em primos, sabemos que todos os casos em que nenhum dos restos for 0 é um candidato a primo. Por exemplo, vamos ver a base (2,3):

n	n%2	n%3
0	0	0
1	1	1
2	0	2
3	1	0
4	0	1
5	1	2

Os dois restos são diferentes de 0 com n=1 ou com n=5, que é primo. Claro que, numa base com mais elementos, um candidato a primo pode ser apenas um múltiplo de um primo que não está na base. O que é importante ressaltar é que o padrão de restos se repete. Então, quando estamos tratando de números maiores de 2*3, não temos como saber precisamente de qual número se trata: temos que viver dentro do universo de 0 a 5.

n	n%2	n%3
0	0	0
1	1	1
2	0	2
3	1	0
4	0	1
5	1	2
6	0	0
7	1	1
8	0	2
9	1	0
10	0	1
11	1	2

Se ignorarmos o 1, todos os casos em que nenhum dos restos é 0 representam primos.

O primeiro primo depois de 6 é 7, mas esse não conta, porque é necessário somar apenas 1 a 6. O próximo é 11 e o número afortunado, neste caso, é 5, que é primo. Dado que os restos da representação de 11 têm que ser iguais aos restos da representação de 5 (porque a diferença é 6), seria até surpreendente encontrar um caso em que o número afortunado não fosse primo.

Mas isso não é prova suficiente, porque poderia acontecer, numa base muito maior, que o número afortunado fosse múltiplo de um primo que não está no primorial (ou na base de resíduos, se preferir).

Conto de 3 Estrelas

Zed dorme profundamente quando uma música muito suave começa a soar pelo despertador digital sobre sua mesa de cabeceira. O volume cresce aos poucos e a música ganha intensidade.

Quando finalmente está desperto e ordena que a música seja encerrada, o despertador solicita que a seleção musical seja avaliada. Quatro estrelas.

Ainda claudicante, Zed tateia o balcão do banheiro à procura do remédio. Surge, então, no espelho, uma enquete: qual dessas marcas você conhece? Zed ignora e vai procurar a cafeteira na cozinha.

O aroma dos melhores grãos colombianos deixa a cozinha quase que encantada. A cafeteira indaga: quantas estrelas esse café merece? Quatro, porque não é hora de responder a enquentes idiotas.

Alimentado, Zed volta ao quarto para vestir um terno, qualquer terno. O espelho mostra comerciais relacionados a seus sapatos e a seu terno. Ele poderia evitá-los, se pagasse o plano Ouro do espelho.

Dentro do elevador, Zed continua a ser bombardeado por comerciais. Talvez o plano Platinum do condomínio valha a pena para ao menos ter um pouco de paz de manhã. Antes de abrir a porta, o elevador oferece uma enquente: qual dessas marcas você recomendaria?

Zed senta dentro do carro e fecha os olhos por uns segundos. Muitos segundos. Então, ele suspira profudamente e dá o comando para o veículo iniciar.

—Bom dia, Zed. Já completamos mil viagens. Como avalias o Toyota e-5000?
—Podemos simplesmente ir? Tenho uma reunião.
—Neste caso, tenho algumas sugestões de livros sobre como melhor conduzir reuniões corportativas. Todos eles foram avaliados com 5 estrelas.
—Não tenho tempo para isso.
—Se avaliares a última compra, terás direito a um desconto em qualquer um desses livros. Pense bem.
—Ao escritório, já!

O transporte estaciona na vaga a tempo para a reunião, mas Zed ainda precisa avaliar a viagem. Cinco estrelas, apenas para não ter que justificar a avaliação. Bela maneira de conseguir boas avaliações, Zed grunhe entre os dentes, encher a paciência de quem não conceder 5 estrelas.

Ao entrar no elevador, um comercial submersivo acende com luzes fortes as quatro paredes, o piso, e o teto. Zed está um pouco irritado e dá um soco na porta, mas não forte o suficiente, pensa ele, para disparar os sensores de segurança.

O elevador silencia e o restante da subida se dá em silêncio. Que estranho.

Quando as portas finalmente se abrem, elas revelam dois seguranças. Zed é escoltado até o Setor de Incidentes Anti-Corporativos.

A polícia chega meia hora mais tarde e o leva até a delegacia, onde ele é identificado.

Dentro da cela, Zed deita-se e fecha os olhos. Um zumbido conhecido se aproxima: é o robô-recepcionista que ele mesmo projetou e que rendeu trilhões ao seu empregador.

—Bom dia, Zed. Lamento encontrar-te aqui, mas preciso fazer umas perguntas a respeito da abordagem policial desta manhã: que nota darias à limpeza da viatura, de um a dez?; que nota darias à cortesia dos policiais, de nove a dez?; como avaliarias a cela, de um a dez?

Infelizmente, a delegacia não oferece um plano sem comerciais na cela.

Tampouco

Estou em campanha pela reabilitação da palavra "tampouco". Cada vez que escuto "eu também não", fico um pouco triste e irritado.

Não me parece certo usar um termo inclusivo para marcar uma negação.

Por acaso a minha linguagem de programação favorita, o Perl, tem unless e until para controle de fluxo e as linguagens mais populares não têm algo parecido. Os programadores são obrigados a usar negações nos ifs e whiles. Perde-se um pouco de expressividade e elegância.

Ademais, pode-se utilizá-los como modificadores de uma expressão, o que ajuda a traduzir diretamente um pensamento numa linha de código.

  my $count = 0;
  print "$count\n" until $count++ >= 10;

  print "On air\n" unless $status eq 'Off';

Taxonomia das Necessidades Humanas

Eu vinha observando que as coisas consideradas de luxo tinham, acima de quaisquer considerações práticas, a qualidade de serem usadas para exibição pública: ostentação. Muitas coisas de luxo sequer são práticas, como carros baixinhos de dois lugares que mal conseguem navegar as ruas acidentadas de nossas cidades.

Após várias discussões filosóficas em família, chegamos à seguinte classificação das coisas que usamos:

• Necessidade
• Conforto
• Privilégio
• Luxo

Necessidades são as coisas básicas da vida: comida, roupas, um lugar para dormir e tomar banho, etc.

Conforto são as coisas que tornam a vida mais confortável, como água quente, sapatos confortáveis, eletrodomésticos, chuveiro a gás, um carro (em lugares com transporte público insuficiente), etc.

Privilégios são coisas que têm um pouco mais de qualidade, como sabonetes perfumados, oléo de banho francês, um carro japonês confiável, chocolate suíço, etc. Elas nos trazem prazer, mas não chamam a atenção.

Finalmente, luxo são, como anteriormente apontado, objetos ou serviços comprados para serem ostentados: carros importados caros, hotéis de 5 estrelas, roupas de marca, etc. É possível que essas coisas nunca tenham sentido econômico. Os carros da Toyota são reconhecidamente os carros mais confiáveis; carros como Ferraris e Porsches, apesar de serem muito mais caros, não alcançam a longevidade dos Toyotas e, portanto, só têm sentido se usados para ostentação. Os carros da Mercedes igualam a taxa de falha dos Toyotas até 5 anos, depois os Toyotas reinam solitários no topo do ranking da confiabilidade.

Por isso, eu penso que os itens de luxo são mais uma falha ou fraqueza de caráter do que qualquer outra coisa; estão aí para confirmar o sucesso do dono, ou suprir sua necessidade de reconhecimento, ou tentar apagar suas falhas.

O interessante dessa característica definidora do luxo é que ela vale para empresas. Quando surge uma nova moda tecnológica, é comum que seja adotada sem que seja avaliada na escala das necessidades.

Assim entram para as empresas o Big Data e a IA. Ninguém mede a necessidade, mas todos correm para implementar algo para então exibir ao resto da sociedade. A característica mais relevante é que é preciso ter porque os outros têm; o custo e os possíveis benefícios não são avaliados.

Claro que essas exibições de riqueza funcionam em alguma dimensão. Elas criam uma imagem de poder ou de sucesso. Desde sempre os ricos usam o luxo para se diferenciarem. Mas o melhor que uma pessoa ou uma empresa podem fazer é aprender avaliar o que é luxo e o que é necessidade, conforto, ou privilégio. Recursos que sobram podem ser usados para suprir mais necessidades, e mais confortos, e mais privilégios.

Multiplicação com o Algoritmo de Booth

A multiplicação russa é conhecida no submundo do assembly para 6502 como "shift and add", porque ela reduz a multiplicação a essas duas operações.

Um cidadão inglês chamado Booth notou que quando há sequências de 1s no multiplicador pode-se reduzir o número de operações.

Em poucas palavras, multiplicar x por 15 é igual a multiplicar x por 16 e subtrair x.

1111 * x = x<<3 + x<<2 + x<<1 + x
1111 * x = x<<4 - x

Podem existir várias sequências de 1s no multiplicador.

1110111 * x = x<<6 + x<<5 + x<<4 + x<<2 + x<<1 + x
1110111 * x = (x<<7 - x<<4) + (x<<3 - x)

A implementação é ineficiente e não vale a pena no 6502, talvez porque ele só tenha instruções para fazer um shift por vez. É um milagre que alguém consiga fazer algo com esse processador, mas Turing garante que tudo é possível.

Deve ser por terem convivido com tantas limitações que os criadores do ARM criaram instruções condicionais que fazem aritmética e shifts ao mesmo tempo, tudo numa só instrução.

Mas o que achei curiosa é a possibilidade de usar isso com o sistema decimal.

993.006 * x = 900.000*x + 90.000*x + 3.000*x + 6*x
993.006 * x = (1.000.000*x - 7.000*x) + 6*x

Operando manualmente, o número de adições reduz bastante:

993.006*123 => 123000000
                  161000 -
                     738 +
               122139738 =
               

Esse algoritmo é muito mais interessante no binário, porque a probabilidade de um bit ser zero ou um é de 50%, e, portanto, só vai realmente ajudar com uma classe específica de números decimais, mas é uma maneira interessante de ver a multiplicação.

Panela de Arroz

Eu ando muito interessado no Japão ultimamente. Tenho lido Sayaka Murata e Haruki Murakami. Entretanto, não é a cultura japonesa que me atrai; os artefatos é que me fascinam.

Há muitos anos, eu tinha um toca-fitas portátil vermelho. Eu acredito que ele era da marca Sanyo, que nem existe mais.

E, se minha memória não falha, era como o da imagem abaixo.

Quando eu tinha uns 10 anos, comprei um metro de cabo estéreo e dois plugues machos, e liguei o toca-fitas ao três-em-um do pai para poder copiar fitas de jogos.

Tem algo no design dos eletrônicos japoneses dos anos 1980 que considero muito atraente. Por exemplo, o MSX Hitbit 101 vermelho é o micro mais bonito já produzido.

Para não passar a impressão que tenho fixação com objetos vermelhos, eis uma linda máquina de escrever Brother Deluxe dos anos 1960.

Os japoneses até hoje fabricam produtos muito bons, mas a evolução da TI acabou com a necessidade de termos aparelhos dedicados para atividades distintas: tudo foi para dentro do celular.

Algumas coisas sobrevivem. Os celulares ainda não cozinham arroz e, é claro, os japoneses, sendo grandes consumidores do grão, inventaram uma panela perfeita para cozinhá-lo.

A Philco é uma empresa estadounidense, mas o projeto original é da Toshiba, dos anos 1950.

O que torna esse objeto tão interessante, fora o design (e a cor) é o mecanismo completamente analógico. Ela não tem nenhum processador dentro. Ela depende de um imã que perde a função de imã quando aquecido acima de 100°C. Quando a água toda tiver evaporado, o arroz esquenta acima dessa temperatura, o imã deixa de funcionar e o circuito abre, desligando o cozimento. É um pouco mais complicado, porque ela continua aquecendo o arroz enquanto não for desconectada da tomada. O funcionamento básico, porém, depende apenas de dois fenômenos físicos: o arroz não esquenta além da temperatura de ebulição da água enquanto houver água no recipiente; e o imã deixa de funcionar acima da temperatura de ebulição da água (cada tipo de imã deixa de funcionar numa temperatura diferente, a qual é conhecida como temperatura de Curie).

Ou seja, não tem muito o que dar errado. É um aparelho analógico perfeito. Apenas lamento não ter comprado uma antes, porque facilita muito o preparo das refeições.

Acho que essa panela só é tão perfeita, porque foi inventada antes de ser prático usar uma CPU. Se uma equipe fosse começar do zero hoje a criação de uma panela de arroz, posso apostar que teria um painel digital, uma MCU, e um software com muitos bugs. Além disso, claro, a placa controladora estragaria devido à exposição ao calor.

Por sorte, ela foi inventada por japoneses nos anos 1950.

O Verdadeiro Futuro da IA na Programação

A IA está por todos os lados e as previsões mais fantásticas estão sendo repetidas ad nauseam.

Eu ainda não usei IA para programar. Restringi-me a gerar umas imagens engraçadinhas. Entretanto, a IA veio até mim através de artefatos produzidos por programadores.

Os dois primeiros eram programadores fracos, então eu compreendi a dificuldade deles. O primeiro até foi honesto sobre estar usando IA. O segundo escondeu o fato até que fosse incontornável: o código dele tentava invocar uma função que não existe, além de tentar recompilar a si próprio numa tentativa estranha de ser dinâmico.

O terceiro foi uma grande supresa, porque o programador é um sujeito realmente competente. Entretanto, ele estava se aventurando numa área que não domina.

Eu acho que com essa última experiência podemos aprender algo.

Um dos livros que eu mais gosto tem o curioso nome de Zen e a Arte da Manutenção de Motocicletas. É um livro estranho: mistura filosofia com problemas mentais e uma viagem de moto. Em um dado momento, o autor discorre sobre como ele enfrenta a manutenção da moto. A pessoa precisa tanto de um modelo mental de como a moto funciona, assim como observar, no mundo real, seu comportamento. As duas coisas são importantes: um modelo mental razoavelmente sólido e correto e uma observação atenta.

Uma pessoa que tem um bom modelo mental de como uma coisa funciona é um especialista: um mecânico, um médico, um engenheiro, um programador.

A programação hoje em dia tornou-se uma tarefa das mais complicadas, porque envolve muitas tecnologias. Há muito tempo ninguém lida apenas com uma tecnologia sobre uma plataforma bem definida (Turbo C num PC, por exemplo).

As aplicações possuem muitas camadas e muitas tecnologias distintas. Inevitavelmente, as equipes mais produtivas incluem pessoas com habilidades complementares: não é novidade que a especialização é o motor da produtividade.

Isso me leva a concluir que a IA só vai ser realmente útil quando usada para complementar a habilidade de um especialista.

Se as empresas continuarem a demitir, porque acreditam que podem substituir pessoas por LLMs, antevejo que logo teremos problemas por causa de código gerado por IA. Tanto problemas de segurança, como problemas de perda de dados.

Se a pessoa não domina uma tecnologia, ela primeiro precisa estudá-la a fim de adquirir um modelo mental sólido para depois aplicar uma LLM. A IA deve até ser evitada até que o programador tenha um pouco de experiência com a tecnologia.

A minha conclusão é que a IA tem que ser usada como uma ferramenta para especialistas, não como substituta de especialistas.