Escreva um programa de montagem GOLF que leia um número inteiro de stdin (seguido por uma nova linha à direita) e produz seus principais fatores separados por novas linhas, seguidos por uma nova linha à direita no stdout.
Os fatores principais não precisam estar em uma ordem específica. 1
não é um fator primordial.
Seu binário GOLF (após a montagem) deve caber em 8192 bytes.
Seu programa será pontuado executando-o 10 vezes, cada um com uma das seguintes entradas:
8831269065180497
2843901546547359024
6111061272747645669
11554045868611683619
6764921230558061729
16870180535862877896
3778974635503891117
204667546124958269
16927447722109721827
9929766466606501253
Esses números são classificados em termos de dificuldade. O primeiro deve ser facilmente solucionável pela divisão de teste.
A otimização em relação a esse conjunto de números é contrária ao espírito da pergunta; posso alterar o conjunto de números a qualquer momento. Seu programa deve funcionar para qualquer número de entrada positivo de 64 bits, não apenas esses.
Sua pontuação é a soma dos ciclos da CPU usados para fatorar os números acima.
Como o GOLF é muito novo, incluirei alguns indicadores aqui. Você deve ler a especificação GOLF com todas as instruções e custos de ciclo . No repositório Github, exemplos de programas podem ser encontrados. Em particular, observe o programa de exemplo fatorial , que demonstra entrada / saída.
Compile seu programa para um binário executando python3 assemble.py your_source.golf
. Em seguida, execute seu programa usando python3 golf.py your_source.bin
, isso também deve imprimir a contagem de ciclos. Veja os valores do conteúdo do registro na saída do programa com o -d
sinalizador - use --help
para ver todos os sinalizadores.
1
não é um fator primordial, ele deve imprimir apenas o número inteiro de entrada?Respostas:
2.279.635 ciclos - 7373 bytes (determinístico)
Um por um:
Resumo:
Utilizo uma combinação de divisão de teste e o algoritmo Brent-Pollard rho para fatoração e pesquisa de tabela mais Miller-Rabin para teste de primalidade. Vou adicionar mais algumas explicações amanhã.
Observe que, devido ao limite de caracteres no comprimento da postagem, a segunda tabela de dados está truncada. Esta essência inclui a tabela completa.
fonte
mov o, 42
é uma oferta inoperante.Total de 36.757.269.913 ciclos
830B montado
Fatoração por divisão de teste, com algumas otimizações. Provavelmente não é o mais rápido, mas como ninguém postou ainda, vou começar.
Saída total do meu loop de temporização, caso alguém queira verificar os resultados e / ou minha cópia e pasta e matemática.
fonte
divu
: stackoverflow.com/questions/5558492/… . Quanto à sua resposta - esta questão não foi resolvida usando a divisão de teste: Pfactor * factor < number
- nenhum número pode ter fatores maiores que a raiz quadrada.score = 378.867.816 ciclos
[randomizado - seus resultados podem variar]
Usa o teste de primalidade de Miller-Rabin (uma versão determinística que pode suportar até 2 ^ 64), um pouco de fatoração experimental e fatoração de ECM . Todas as operações algébricas estão lá, incluindo adição modular, subtração, multiplicação, exponenciação e inversão (mod n <2 ^ 64).
A multiplicação modular é abaixo do ideal - faz uma pesquisa binária pelo quociente. Computar o restante de uma divisão de 128 por 64 é difícil sem uma instrução interna correspondente. Acelere isso e tudo irá mais rápido.
2290 bytes compilados
Saída:
fonte