Trade-off de espaço-tempo

RKA10GM Tenho uma novidade. Entrei em contato com a engenharia na NASA e descobri que o novo rover está usando a mesma plataforma de memória utilizada no Curiosity. E o rover Curiosity foi equipado com dois computadores, mas apenas um ficava ativo de cada vez, e ele tinha as seguintes especificações: 2 gigabytes de memória flash, 256 megabytes de memória de acesso aleatório (RAM) e 256 kilobytes de memória somente de leitura (ROM), que continha as rotinas principais do sistema. Queremos armazenar todo o nosso programa na RAM, mas como temos que compartilhar esse espaço com outros programas, estamos com 5% de RAM alocados, que é o máximo que podemos usar, isso é cerca 12,8 megabytes no total. Mencionei isso porque quero apresentar a ideia de trade-off de tempo-espaço ou trade-off de espaço-tempo, um termo comumente utilizado em ciência da computação. Eu estava olhando para um programa feito por IV42, e ele tinha um vetor de milhões de números primos para que o algoritmo dele pudesse avançar apenas pelos números primos, na medida do possível, ao fazer um teste de primalidade com divisão por tentativa. Por que não armazenar todos os números primos que precisamos até o limite em um vetor, ao invés de calculá-los em tempo real? Mencionamos em um vídeo anterior que isso seria o ideal para um algoritmo de divisão por tentativa. Embora você possa ver que o algoritmo dele não use muitas etapas, ele começou a rodar lentamente e, então, parou de funcionar antes de atingir o limite da etapa. Portanto, não foi capaz de resolver rapidamente o problema para os tamanhos que defini anteriormente. Neste caso, eles foram trocados por tempo sob a forma de testes de divisibilidade repetidos à custa de espaço, que é a memória para armazenar o vetor. E por que isso não funciona? Vamos fazer um cálculo aproximado usando o que aprendemos para descobrir se este método é possível usando o nosso limite de memória. Lembre-se, temos que poder lidar com números até pouco mais de 9 quatrilhões. E o nosso algoritmo de divisão por tentativa só precisa verificar para fatores até a raiz quadrada de um número, e se ela atingir este ponto sem fatores encontrados, pode-se dizer 100% se um número é primo ou não. Quantos números primos existem até a raiz quadrada desse limite, onde a raiz quadrada de 9 quatrilhões é 94,9 milhões? Quantos números primos são menores que 95 milhões? Felizmente, aprendemos uma solução matemática para ter uma resposta aproximada usando o teorema de número primo. Quantos números primos são menores do que "x"? É "x" dividido pelo logaritmo natural de "x". E se "x" é um pouco maior do que 94,9 milhões, nós encontramos a quantidade de números primos que é, aproximadamente, de 5,1 milhões. Como estamos armazenando esses números primos, precisamos saber o tamanho do maior número primo ou, neste caso, o 5,1 milionésimo, aproximadamente. E sabemos que ele será um número menor do que 94,9 milhões. Verifique a tabela com atenção e o valor real desse número primo, o maior primo que precisamos armazenar na raiz quadrada do nosso limite, é 89.078.611 milhões. Quanta memória este único e grande número primo exige? Para descobrir, vamos converter o número para notação binária, que é a forma como o computador armazenará um número usando apenas chaves na memória. Aprendemos sobre isso no vídeo sobre memória do computador. Em bits, o maior número primo se parece com isto, que é 24 bits, ou 3 bytes necessários para armazenar este único número. Digamos que queremos armazenar cada número na memória, e já que sabemos que o maior número requer 24 bits, podemos imaginar uma longa lista de blocos de 24 bits armazenando cada número primo. Quantos bits são necessários para essa lista inteira? A memória necessária é o número de valores ou o número de números primos vezes o espaço de cada valor. Portanto, temos cerca de 5,1 milhões de valores vezes 24 bits para cada valor, que é um pouco mais de 124 milhões de bits. Ou se convertermos em bytes, é cerca de 14,7 milhões de bytes. Pode-se dizer que são quase 15 megabytes. Logo, não é possível nem mesmo armazenar a lista desses números na memória usando o nosso limite. Este é apenas um exemplo de brincadeira. É, na verdade, uma subestimação do que realmente se precisa. Por exemplo, um vetor precisa de espaço para um ponteiro de cada item, e cada ponteiro em uma máquina de 32 bits é 4 bytes. Portanto, a quantidade real de memória necessária é muito mais do que 15 megabytes. Dito isso, sabemos que armazenar todos os números primos até a raiz quadrada de nosso limite relativamente pequeno não é nem mesmo possível com o nosso limite de memória. Não podemos fazer isso dessa forma. E o que dizer quando os valores caem por um fator de 1.000 ou 10.000? Os sistemas de criptografia usam 512 bits ou números ainda maiores, que tornam a pesquisa e a enumeração impossíveis. Por exemplo, se alguém te pedisse para fazer uma lista de todos os números primos até os números primos com 200 dígitos de comprimento, você nem deveria considerar tentar. Isso porque o disco rígido necessário para armazenar todos esses números primos seria mais pesado do que a massa do universo observável. Vou deixar os cálculos para você tentar na próxima vez que estiver em um restaurante com giz de cera e papéis espalhados pela mesa. Mas lembre-se, há cerca de 10⁸⁰ átomos no universo observável. Este é um número de 80 dígitos. Perceba que há um limite fundamental para a quantidade de espaço ou memória a que temos acesso. Não importa quanto tempo levaria, mas é sempre um "empurra e puxa" entre usar espaço ou tempo para resolver nossos problemas. Logo, para resolver este problema de testes para primalidade rapidamente, utilizando uma pequena quantidade de espaço e uma pequena quantidade de tempo, vamos ter que abordá-lo de uma maneira totalmente nova.