Question

LC3 stack (factorial)

I need help in writing factorial in Lc3 language by using stack..

; Begin reserved section: do not change ANYTHING in reserved section!

                .ORIG x3000
                BR Main
                
; Parameter and result
Param           .FILL x0004
Result          .BLKW 1

; Constants
Stack           .FILL x4000
One             .FILL #1
MinusOne        .FILL #-1

; End reserved section: do not change ANYTHING in reserved section!
;-------------------------------------------------------------------------------

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;
; int Factorial(int N)
; Returns N! (must be a recursive function)
;
Factorial       ;__________________ ; Step 3: allocate space for return value
                ;__________________ ; Step 4: push return address
                ;__________________ ; Step 5: push previous frame pointer
                ;__________________ ; Step 6: setup new frame pointer
                ;__________________ ; Step 7: allocate space for local variable
                
                ;;;;;;;;;;;;;;;;;;;;; Step 8: body of the function
                
Checkpoint1     LDR   R0, R5, #4    ; Load parameter N into a register
                
                LD    R1, MinusOne  ; Calculate N - 1
                ADD   R2, R0, R1    ; R2 will contain N - 1
                
                ;__________________ ; Store N - 1 in the local variable
                
                BRnz  BaseCase      ; Detect base case (N <= 1)
                
                ;;;; Start of the recursive call
                
                ;__________________ ; Step 1: push parameter N - 1
                ;__________________ ; Step 2: call Factorial(N - 1)
                ;__________________ ; Step 13: retrieve return value into R2
                ;__________________ ; Step 14: remove parameter from stack
                
                LDR   R0, R5, #4    ; Multiply N * Factorial(N - 1)
                .ZERO R3            ; R3 will contain the product
MultiplyLoop    ADD   R3, R3, R2    ; Notice that by this point, R0 > 1
                ADD   R0, R0, #-1   ;
                BRp   MultiplyLoop  ;
                
                ;__________________ ; Make return value = N * Factorial(N - 1)
                
                BR    Finish
                
                ;;;; End of the recursive call
                
                ;;;; Start of the base case
                
BaseCase        LD    R0, One       ; Make return value = 1
                STR   R0, R5, #3    ;
                
                ;;;; End of the base case
                
                ;;;;;;;;;;;;;;;;;;;;; End of the body of the function
                
Finish          ;__________________ ; Step 9: remove local variable from stack
                ;__________________ ; Step 10: restore previous frame pointer
                ;__________________ ; Step 11: restore return address
Checkpoint2     RET                 ; Step 12: return to calling subroutine

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;
; Entry point
; Calls Factorial(Param) and stores the return value in Result
;
Main            LD    R6, Stack     ; Initialize stack pointer
                LD    R5, Stack     ; Initialize frame pointer
                
                LD    R0, Param     ; Load parameter into a register
                
                ;__________________ ; Step 1: push parameter
                ;__________________ ; Step 2: call Factorial(Param)
                ;__________________ ; Step 13: retrieve return value
                ;__________________ ; Step 14: remove parameter from stack
                
                ;__________________ ; Store return value in Result
                
TheEnd          HALT
                
               .END
                

Here is a C implementation:

#include <stdio.h>

int Param = 0x0004;
int Result;
  
/** Compute N! recursively */
int Factorial(int N) {
  int Temp = N - 1;
  
  if (Temp > 0) { 
    // Recursive call
    return N * Factorial(Temp);
  } else {
    // Base case (N <= 1)
    return 1;
  }
}

/** Entry point */
int main() {
  Result = Factorial(Param);
  printf("Return value is x%04X\n", Result);
  return 0;
}

Thank you.

Answer 1

.ORIG x3000

AND R1,R1,#0

ADD R1,R1,x7 ; INPUT - DO FACTORIAL OF 7, STORE IT IN R2

AND R2,R2,#0 ; result store

ADD R2,R2,#1

DECR

AND R3,R3,#0

ADD R3,R3,R1 ; r3=r1

AND R4,R4,#0

MULT

ADD R4,R4,R2

ADD R3,R3,#-1

BRp MULT

AND R2,R2,#0

ADD R2,R2,R4 ; r2=r4

ADD R1,R1,#-1

BRp DECR

.END