4

Tenho que criar um programa com a linguagem assembly K & S Model 2 que multiplique um numero por outro, o problema é que esta linguagem não fornece uma operação de multiplicação. Pensei então fazer multiplicações com adições, por exemplo:

3 x 5 = 5 + 5 + 5 (3 vezes o 5) = 15

Esta linguagem também não fornece uma maneira direta de fazer um ciclo (ou loop), nem uma instrução de comparação de registros, por exemple para ver se são iguais, ou seja se tem o mesmo numero.

Esta linguagem assembly fornece só operadores de bitwise com os quais não tenho muita familiaridade. Sei que fazendo o AND bit a bit é como fazer uma multiplicação dos números mas convertidos em binários, por exemplo:

3 & 2

Primeiro temos que convertir em binário:

  11 (3)
& 10 (2)
==== 
  10 (2)

Sinceramente não estou a ver como poderei fazer uma multiplicação usando so esta operações, se pelo menos pudesse fazer um loop de qualquer maneira...

7
  • 1
    Que tipos de desvio condicional essa linguagem tem? É possível por exemplo você dizer: "desvie se tal registro for zero"? Muito provavelmente a solução do seu problema estará aí, e não nos operadores bitwise.
    – mgibsonbr
    Commented 21/09/2014 às 17:21
  • Isso! Como falei na resposta, não sei exatamente como esses comandos funcionam. Presumo que "ALU RESULT" se refira ao "resultado da última operação aritmética e lógica realizada", e escrevi o pseudo-código baseado nessa premissa. Até seria possível se adaptar o algoritmo pra uma linguagem sem desvio condicional, desde que o desvio incondicional permitisse usar um valor da memória ou dos registradores como ponto de chegada, mas vejo que no seu caso não é assim que o BRANCH funciona (ele pede um endereço hardcoded). De modo que a saída é usar BNEG ou BZERO mesmo (no meu código, BNEG)
    – mgibsonbr
    Commented 21/09/2014 às 18:00
  • 2
    Você pode usar o algoritmo de multiplicação da 4a série para fazer a conta de forma mais eficiente do simplesmente fazer um monte de somas.
    – hugomg
    Commented 21/09/2014 às 18:44
  • 1
    Esse algoritmo é a versão em base 2 do algoritmo da escola (que usa base 10)
    – hugomg
    Commented 21/09/2014 às 19:29
  • 1
    aaaah, agora tudo faz sentido! :D Na verdade até pensei [subconscientemente] em sugerir uma variação dele a princípio, mas como essa arquitetura não dá suporte pra shift left ia ser um pouquinho mais complicado... Preferi manter a resposta simples mesmo, afinal "first make it work, then make it fast" :P
    – mgibsonbr
    Commented 21/09/2014 às 20:42

2 Respostas 2

5

Pode-se fazer uma multiplicação [inteira] usando somente a soma (+), desde que você tenha acesso a um operador de desvio condicional que desvie se tal registro for zero. Pelo seu link, há dois operadores assim: BZERO (desvia se o resultado na ALU for zero) e BNEG (desvia se o resultado na ALU for menor que zero).

Eu não entendi muito bem como essa sua arquitetura funciona (nem tenho intenção de me aprofundar nela), de modo que vou responder com pseudo-código:

  1. Guarde -1 no registro A;
  2. Guarde o multiplicador no registro B;
  3. Guarde o multiplicando no registro C;
  4. Guarde 0 no registro D;
  5. Some os registros A com B e guarde o resultado em B; (i.e. decremente o multiplicador)
  6. Se o resultado for menor que zero, vá para 9;
  7. Some os registros C e D e guarde o resultado em D;
  8. Volte para 5;
  9. Fim do programa. (D contém o resultado da multiplicação)

Ou seja, cada vez que você decrementar o multiplicador, você soma o multiplicando ao resultado. Você estará então calculando n x m somando m n vezes.

Nota: esse algoritmo funciona inclusive quando m for negativo, mas não quando n é negativo - ele vai entrar num loop infinito. A solução nesse caso seria ter dois algoritmos: um que decrementa até chegar a zero, e um que incrementa até chegar a zero, e escolher entre um e outro dependendo se n é positivo ou negativo.

1

Eu fiz da seguinte forma e funcionou:

1)LOAD R1 22
2)LOAD R2 23
3)LOAD R3 24
4)ADD R0 R0 R3
5)STORE 21 R0
6)ADD R2 R2 R1
7)STORE 23 R2
8)BZERO 9
9)BRANCH 4
10) HALT

0

Você deve fazer log-in para responder a esta pergunta.