Exemplos de programas simples para Ramses

fibonacci.txt - escreve os primeiros 14 números da série de Fibonacci;

multiply.txt - faz a multiplicação simples e não otimizada de pares de números armazenados em um vetor; o tamanho do vetor deve ser informado no endereço 80h, e os números devem estar a partir da posição 82h em diante. O programa multiplica os dois primeiros números, depois os dois seguintes e assim por diante, sempre considerando o segundo como multiplicador. Ou seja, no caso do par [1,200] ele faz 200 somas do valor 1; o resultado de cada multiplicação será armazenado nas posições seguintes ao final do vetor de acordo com o tamanho especificado;

looper.txt - escreve o caractere 'o' (decimal 111 ou hex 6Fh) nas posições de 80h a 8Ah e de 8Bh a 81h, com incrementos de +2 e -2, de forma que se veja esse caractere em um laço cíclico no sentido anti-horário em ASCII na área de dados da tela no simulador PocketRamses;

is_prime.txt - verifica se o número dado na posição 128 (h80) é um número primo ou não (composto). Testa se é divisível por todos os números menores que ele, fazendo subtrações sucessivas e verificando se atinge 0 ou se se torna negativo, caso em que a divisão não é exata. O número dado deve estar entre 1 e 129. Ao terminar, escreve uma mensagem em ASCII a partir do endereço 130, informando se o número é primo ou composto;

bubbles.txt - ordena uma lista de números armazenados em um endereço indicado na variável "databegin" em 7Ch, com o algoritmo de BubbleSort; A quantidade de números está armazenada na variável "size" no endereço 7Dh, e você pode reduzir, ou ordenar até 128 números que já estão na memória a partir do endereço 80h;

histogram.txt - faz um histograma de caracteres em um texto; este programa varre uma mensagem de texto de até 110 caracteres armazenada entre os endereços 92h e FFh, conta o número de ocorrências das letras maiúsculas ou minúsculas de A a Z, armazenando em uma tabela entre os endereços 5Ch e 8Fh, onde cada entrada tem o código ascii maiúsculo e o número de ocorrências, e depois ordena a tabela por ordem decrescente de ocorrências, com uma versão simplificada e dedicada (endereços hardcoded) do mesmo algoritmo BubbleSort anterior; A maior parte do tempo é dedicada ao algoritmo de ordenamento;

Exemplos avançados para Ramses

slr1.txt - faz análise sintática (parsing), verificando se uma sequência de símbolos terminais pertence a uma linguagem, de acordo com uma GLC (gramática livre de contexto), com um algoritmo do tipo bottom-up, usando uma tabela que deve ter sido pré-calculada e armazenada na memória no formato correto. Teoricamente qualquer autômato para análise SLR1, LALR1 ou mesmo LR1 canônico podem ser executado, mas pela limitação de número de estados, entre outras, ele é adequado para os métodos mais simples SLR1 e LALR1 apenas. Para outros detalhes, verificar os comentários no código assembly;

placer5.txt - posicionamento de células lógicas para fabricação de um circuito é um problema NP-hard, o que significa que não existe algoritmo que possa encontrar a melhor solução em tempo polinomial. Este programa faz o posicionamento de células (nodos de um grafo) minimizando conexões (as arestas), usando o método estocástico de otimização chamado Threshold Accepting (G. Dueck and T. Scheuer, 1990), que é uma simplificação do mais conhecido Simulated Annealing (Kirkpatrick, Gelatt and Vecchi, 1983). O algoritmo seleciona duas células ao acaso, troca suas posições, e aceita a troca se o custo for reduzido ou se for pior mas dentro de uma pequena margem (threshold), que vai sendo reduzida ao longo do processo. Isso permite que ele busque soluções melhores mas mantendo a capacidade de escapar de mínimos locais. O código faz a minimização do somatório de comprimento de conexões em um grafo contendo exatamente 16 nodos e 32 conexões entre eles, dispostos em um quadrado de tamanho 4x4. O exemplo contido nos dados foi gerado com um método conhecido como PEKO - Placement Example with Known Optimal (Chang, Cong, Romesis and Xie, 2003), onde conexões são criadas apenas entre células vizinhas já posicionadas, e depois sua posição embaralhada, e neste exemplo é garantido então que existe solução com custo=32 (número de conexões de tamanho unitário), de um total de quase 21 trilhões de possibilidades (fatorial de 16). Este código consegue encontrar uma solução com custo=39 (hex 27) em cerca de 1 minuto e 15 segundos rodando no emulador em Arduino PocketRamses em modo dark, e em cerca de 30s em modo silencioso no simulador Ramses 2024 (tempos podem variar com navegador e processador). As coordenadas das células estão armazenadas nos vetores X e Y nos endereços 90h e A0h, respectivamente, e o custo final pode ser observado nas posições 8Ah e 8Bh;