Estou estudando uma linguagem de assembly de aprendizado. Nela tenho duas implementações de função fatorial que gostaria de saber se podem ser consideradas basicamente equivalentes.
O contexto das implementações
Ela é para uma máquina de dezesseis registros (r0
a r15
).
As duas implementações que vou mostrar usando essa linguagem não empilham dados (isto é, não usam stack). (Obs.: qual palavra estou querendo usar no lugar de dados? Seria estado de execução, contexto de execução?)
Em vez disso usam o registro r1
para o parâmetro de entrada e r2
para a saída (resultado do fatorial).
Por simplicidade ela não faz nenhum tipo de tratamento de exceções, como por exemplo argumentos negativos.
Também, exceto pela comparação com zero (jeqzn
), não existe opcode para comparação de igualdade.
O registro de retorno das funções fica em r14
.
As duas implementações
A implementação-exemplo é assim (junto com um "pseudo-C" que fiz nos comentários para auxiliar a compreensão):
0 read r1
1 calln r14, 4
2 write r2
3 halt
# Início da função fatorial
4 setn r2, 1 # 4: r2 = 1;
5 jeqzn r1, 9 # 5: if (r1 == 0) goto 9;
6 mul r2, r1, r2 # 6: r2 = r1 * r2;
7 addn r1, -1 # 7: r1--;
8 jumpn 5 # 8: goto 5;
9 jumpr r14 # 9: return r2;
Esta é minha implementação:
0 read r1
1 calln r14, 4
2 write r2
3 halt
# Início da função fatorial
4 copy r2, r1 # 3: r2 = r1;
5 addn r1, -1 # 4: r1--;
6 jeqzn r1, 9 # 5: if (r1 == 0) goto 9;
7 mul r2, r1, r2 # 6: r2 = r1 * r2;
8 jumpn 5 # 7: goto 5;
9 jumpr r14 # 8: return r2;
O princípio das duas é quase igual: se N = 3, multiplica-se 3 * 2 * 1 (isto é, vai-se decrementando o N) e quando este chega a 0 retorna o resultado sem fazer nova multiplicação. Não deveria haver grande diferença entre elas, em princípio.
Elas podem ser consideradas equivalentes em princípio?
Instrução por instrução parece que sim, com uma (supostamente) negligível diferença entre setn r2, 1
e copy r2, r1
.
A diferença entre elas é que uma começa com um resultado 1
e vai multiplicando por N
e decrementando este N
até ele chegar a zero, quando então o resultado é retornado.
Na outra começa com um valor N
que é multiplicado por N - 1
, decrementa-se N
, multiplica-se o resultado por N - 2
, e assim por diante, também até chegar a zero, momento em que o resultado é retornado.
Guiando as respostas, pt. 1
Como elas se comparam? Eu testei os algoritmos e ambos dão o mesmo resultado. Se isso fosse em assembly normal, eles poderiam ser considerados basicamente equivalentes (descontando diferenças como a que foi citada entre os semelhantes setn
e copy
)? O segundo algoritmo foi uma implementação que fiz que me pareceu mais intuitiva que o primeiro (no sentido de partir de um algoritmo imaginado e seguir com sua implentação conforme vai pensando nas instruções). A implementação mais eficiente tende a ser intuitiva ou contra-intuitiva? Ou não há uma regra? Quando você busca uma ou outra, a diferença em eficiência pode ser significativa? Ou, dado meu conhecimento precário em assembly, estou perguntando isso cedo demais para ter ideia de como isso funciona na prática?
Guiando as respostas, pt. 2
Outra forma de perguntar: a dúvida é sobre uma ser melhor que a outra em termos de desempenho e outros aspectos não citados (preferência de qual adotar), sobre equivalência, sobre diferenças entre as instruções.
Teste de mesa
Para N = 3, isso é o que o primeiro código faz (estou ignorando o custo dos jumps, deveria?):
r1 = 3;
r2 = 1;
r2 = (r1 * r2) = (3 * 1) = 3;
r1 = 2;
r2 = (2 * 3) = 6;
r1 = 1;
r2 = (1 * 6) = 6;
r1 = 0;
return 6;
E isso é o que o segundo código faz:
r1 = 3;
r2 = 3;
r1 = 2;
r2 = (r1 * r2) = (2 * 3) = 6;
r1 = 1;
r2 = (r1 * r2) = (1 * 6) = 6;
r1 = 0;
return 6;
Guiando as respostas, pt. 3
Não ficou muito clara para mim a diferença no teste de mesa. Fiquei em dúvida sobre qual é mais performático, qual é mais didático, qual é mais intuitivo, e o que esperar da eficiência quando se opta por uma dessas últimas duas qualidades.
Resumindo: Deve-se esperar grandes diferenças se o "algoritmo" idealizado é basicamente muito parecido?