.
Fazendo história com 42 dígitos: Cientistas da Paderborn University e KU Leuven desvendaram um mistério matemático de décadas com o chamado nono número de Dedekind. Especialistas em todo o mundo procuram o valor desde 1991. Os cientistas de Paderborn chegaram à sequência exata de números com a ajuda do supercomputador Noctua localizado lá. Os resultados serão apresentados em setembro no International Workshop on Boolean Functions and their Applications (BFA) na Noruega.
O que começou como um projeto de tese de mestrado de Lennart Van Hirtum, então estudante de ciência da computação na KU Leuven e agora pesquisador associado da Universidade de Paderborn, tornou-se um grande sucesso. Os cientistas se juntam a um grupo ilustre com seu trabalho: os números anteriores da série foram encontrados pelo próprio matemático Richard Dedekind quando ele definiu o problema em 1897 e, posteriormente, por grandes nomes da ciência da computação, como Randolph Church e Morgan Ward. “Durante 32 anos, o cálculo de D(9) foi um desafio aberto, e era questionável se algum dia seria possível calcular esse número”, diz Van Hirtum.
O número anterior na sequência de Dedekind, o 8º número de Dedekind, foi encontrado em 1991 usando um Cray 2, o supercomputador mais poderoso da época. “Portanto, parecia concebível para nós que já fosse possível calcular o 9º número em um grande supercomputador”, diz Van Hirtum, descrevendo a motivação para o ambicioso projeto, que inicialmente implementou em conjunto com os orientadores de sua tese de mestrado na Ku Leuven.
Grãos de areia, xadrez e supercomputadores
O assunto principal dos números de Dedekind são as chamadas funções booleanas monótonas. Van Hirtum explica: “Basicamente, você pode pensar em uma função booleana monótona em duas, três e infinitas dimensões como um jogo com um cubo n-dimensional. Você equilibra o cubo em um canto e depois colore cada um dos cantos restantes de branco ou vermelho. Existe apenas uma regra: você nunca deve colocar um canto branco sobre um vermelho. Isso cria uma espécie de interseção vertical vermelho-branco. O objetivo do jogo é contar quantos cortes diferentes existem. Seu número é o que é definido como o número de Dedekind. Mesmo que não pareça, os números rapidamente se tornam gigantescos no processo: o 8º número de Dedekind já tem 23 dígitos.”
Números comparativamente grandes – mas incomparavelmente mais fáceis de calcular – são conhecidos por uma lenda sobre a invenção do jogo de xadrez. “Segundo esta lenda, o inventor do jogo de xadrez pediu ao rei apenas alguns grãos de arroz em cada casa do tabuleiro de xadrez como recompensa: um grão na primeira casa, dois grãos na segunda, quatro na terceira , e o dobro em cada uma das casas seguintes. O rei rapidamente percebeu que este pedido era impossível de cumprir, porque tanto arroz não existe em todo o mundo. O número de grãos de arroz no tabuleiro completo teria 20 dígitos – uma quantidade inimaginável, mas ainda menor que D(8). Quando você percebe essas ordens de magnitude, é óbvio que tanto um método computacional eficiente quanto um computador muito rápido seriam necessários para encontrar D(9)”, disse Van Hirtum .
Marco: os anos se tornam meses
Para calcular D(9), os cientistas usaram uma técnica desenvolvida pelo orientador de tese de mestrado Patrick De Causmaecker, conhecida como fórmula do coeficiente P. Ele fornece uma maneira de calcular os números de Dedekind não por contagem, mas por uma soma muito grande. Isso permite que D(8) seja decodificado em apenas oito minutos em um laptop normal. Mas, “O que leva oito minutos para D(8) torna-se centenas de milhares de anos para D(9). Mesmo se você usasse um grande supercomputador exclusivamente para esta tarefa, ainda levaria muitos anos para completar o cálculo”, Van Hirtum aponta. O principal problema é que o número de termos nessa fórmula cresce incrivelmente rápido. “No nosso caso, explorando simetrias na fórmula, conseguimos reduzir o número de termos para ‘apenas’ 5,5*10^18 – uma quantidade enorme. Em comparação, o número de grãos de areia na Terra é de cerca de 7,5* 10 ^ 18, o que não é nada desprezível, mas para um supercomputador moderno, as operações 5,5 * 10 ^ 18 são bastante gerenciáveis”, disse o cientista da computação. O problema: o cálculo desses termos em processadores normais é lento e também o uso de GPUs, pois atualmente a tecnologia de acelerador de hardware mais rápida para muitos aplicativos de IA não é eficiente para esse algoritmo.
A solução: hardware específico de aplicação usando unidades aritméticas altamente especializadas e paralelas – os chamados FPGAs (field programmable gate arrays). Van Hirtum desenvolveu um protótipo inicial para o acelerador de hardware e começou a procurar um supercomputador que tivesse as placas FPGA necessárias. No processo, ele tomou conhecimento do computador Noctua 2 no “Paderborn Center for Parallel Computing (PC2)” da Universidade de Paderborn, que possui um dos sistemas FPGA mais poderosos do mundo.
O Prof. Dr. Christian Plessl, chefe do PC2, explica: “Quando Lennart Van Hirtum e Patrick De Causmaeker nos contataram, ficou imediatamente claro para nós que queríamos apoiar este projeto extraordinário. Resolver problemas combinatórios difíceis com FPGAs é um campo promissor de aplicação e o Noctua 2 é um dos poucos supercomputadores em todo o mundo com os quais o experimento é viável. Os requisitos extremos de confiabilidade e estabilidade também representam um desafio e um teste para nossa infraestrutura. A equipe de consultoria especializada em FPGA trabalhou em estreita colaboração com a Lennart para adaptar e otimizar a aplicação para o nosso ambiente.”
Após vários anos de desenvolvimento, o programa funcionou no supercomputador por cerca de cinco meses. E então chegou a hora: em 8 de março, os cientistas encontraram o 9º número de Dedekind: 286386577668298411128469151667598498812366.
Hoje, três anos após o início do projeto Dedekind, Van Hirtum está trabalhando como membro da NHR Graduate School no Paderborn Center for Parallel Computing para desenvolver a próxima geração de ferramentas de hardware em seu doutorado. A Escola de Pós-Graduação NHR (National High Performance Computing) é a escola de pós-graduação conjunta dos centros NHR. Ele relatará seu extraordinário sucesso junto com Patrick De Causmaecker no dia 27 de junho às 14h no Lecture Hall O2 da Universidade de Paderborn. O público interessado está cordialmente convidado.
.
