API tools faq
paste
Advertisement
FAR3L

Untitled

FAR3L
Dec 8th, 2019
1,851
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
MIX Assembler 17.85 KB | None | 0 0
raw download clone embed print report
  1. #
  2. # Karlsruher Institut fuer Technologie
  3. # Institut fuer Technische Informatik (ITEC)
  4. # Vorlesung Rechnerorganisation
  5. #
  6. # Autor(en): Johann Bonneau, Leo Garbe
  7. # Matrikelnummer: 2231658, ???????
  8. # Tutoriumsnummer: 9
  9. # Name des Tutors: Xu Fangyi
  10. #
  11.  
  12.  
  13.         .data
  14.        # space for the polynomials
  15.                        .align 3
  16. polynomial:             .space 40       # conventions: starting with a0 to a4                  
  17. derivedPoly:            .space 40       # for a0 + a1*x + a2*x^2 + a3*x^3 + a4*x^4
  18.        # the polynomial for which you have to find the null points for the given start values below
  19. testPoly:               .double 2, -0.5, -2.2, 0.0, 0.25
  20.  
  21.         # algorithm values
  22. maxRounds:              .word 30
  23. epsilon:                .double 0.00001
  24. # - ! - ! - ! - ! - ! - ! - ! - ! - ! - ! - ! - ! - ! - ! - ! - ! - ! - ! - ! - ! - ! -
  25. # write your found solutions for given start values here
  26. x0:                     .double -5.1    # found solution: -2.6216761331927914
  27. x1:                     .double -0.8    # found solution: -1.1837432144601066
  28. x2:                     .double 1       # found solution: 0.8816934297400127
  29. x3:                     .double 3.5     # found solution: 2.923728494996961
  30.  
  31.         # help values
  32. null:                   .double 0
  33. eins:                   .double 1
  34.  
  35.         # strings
  36. readFactorsPrompt:      .asciiz "Please insert polynomial factors for polynomial a0 + a1*x + a2*x^2 + a3*x^3 + a4*x^4."
  37. readNextFactor:         .asciiz "\nnext factor: "
  38. newLine:                .asciiz "\n"
  39. startValue:             .asciiz "\nStart newton's method with start value: "
  40. noSolutionFound:        .asciiz "Did not converge. No solution found."
  41. solutionFound:          .asciiz "The found solution is: "
  42. polyPrint:              .asciiz "\nPolynomial factors: "
  43. comma:          .asciiz ", "
  44.  
  45.         .text
  46.        .globl main
  47. # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
  48. #       MAIN            MAIN            MAIN            MAIN            MAIN            #
  49. # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
  50. main:           jal alignStackPointer   # align stackpointer to multiple of 8
  51.        # to read in a polynomial uncomment the polynomial lines and comment those with test polynomial
  52.                #la $a0, polynomial
  53.                #jal 0
  54.                
  55.         # print the polynomial
  56.                #la $a0, polynomial
  57.                 la $a0, testPoly
  58.                 jal printPolynomial
  59.                
  60.         # first we need to compute the derived polynomial, since we need it in the algorithm
  61.                #la $a0, polynomial
  62.                 la $a0, testPoly
  63.                 la $a1, derivedPoly
  64.                 jal derive                      # - ! - implement this subroutine              
  65.        # print the derived polynomial to see whether it was computed correctly
  66.                #la $a0, polynomial
  67.                 la $a0, derivedPoly
  68.                 jal printPolynomial
  69.                                
  70.         # now we can run the newton subroutine with our start values                    
  71.                 la $a2, x0
  72.                 la $a0, polynomial
  73.                 la $a0, testPoly
  74.                 la $a1, derivedPoly
  75.                 jal newtonsMethod               # - ! - implement this subroutine
  76.                
  77.                 la $a2, x1
  78.                 la $a0, polynomial
  79.                 la $a0, testPoly
  80.                 la $a1, derivedPoly
  81.                 jal newtonsMethod
  82.                
  83.                 la $a2, x2
  84.                 la $a0, polynomial
  85.                 la $a0, testPoly
  86.                 la $a1, derivedPoly
  87.                 jal newtonsMethod
  88.                
  89.                 la $a2, x3
  90.                 la $a0, polynomial
  91.                 la $a0, testPoly
  92.                 la $a1, derivedPoly
  93.                 jal newtonsMethod
  94.                                
  95.                 li $v0, 10
  96.                 syscall
  97.  
  98. # - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - #
  99. # Subroutine: newtonsMethod                                                             #
  100. #       The subroutine runs newton's method for given polynomial f and start value.     #
  101. #                                                                                       #
  102. # Parameters:                                                                           #
  103. #       $a0 - address of polynomial f                                                   #
  104. #       $a1 - address of derived polynomial f'                                          #
  105. #       $a2 - address of x_0, start value for algorithm                                 #
  106. # Output:                                                                               #
  107. #       $f0 - the solution of the algorithm, null point of given polynomial (hopefully) #
  108. # - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - #
  109. newtonsMethod:          # prepare a new stackframe for the subroutine
  110.                 subu $sp, $sp, 24
  111.                 sw $s0, 20($sp)
  112.                 sw $s1, 16($sp)
  113.                 sw $s2, 12($sp)
  114.                 sw $ra, 8($sp)
  115.                 sw $fp, 4($sp)
  116.                 addu $fp, $sp, 24
  117.  
  118.                 # store arguments in caller-save registers
  119.                 move $s0, $a0          
  120.                 move $s1, $a1
  121.                 move $s2, $a2
  122.  
  123.                 # possible register use:
  124.                # s0 = &f, s1 = &f', s2 = &x0
  125.                # f0 = x_n, f2= f(x_n), f4 = f'(x_n), $s3 = n, $s4 = maxRounds
  126.                 l.d $f0, ($s2)          # load x_0 in $f0
  127.                # print start value
  128.                 la $a0, startValue
  129.                 jal printString
  130.                 mov.d $f12, $f0
  131.                 jal printDouble
  132.                 la $a0, newLine
  133.                 jal printString
  134.                
  135. # - ! - ! - ! - ! - ! - ! - ! - ! - ! - ! - ! - ! - ! - ! - ! - ! - ! - ! - ! - ! - ! -
  136. # implement newton's method here. if it did not converge, abort with error message, else print out solution
  137. # (see predefined strings and helping methods at the end for easy printing)
  138. # use your implementation of the subroutine evalutePolynomial
  139.  
  140.         # you may implement the following version of newton's method
  141.        # while (|f(x_n)| > epsilon) {
  142.        #     x_(n+1) = x_n - f(x_n) / f'(x_n)
  143.        #     n++
  144.        #     if (n >= maxRounds) {
  145.        #       abort, did not converge
  146.        #     }
  147.        # }
  148.        # return x_(n)
  149.  
  150.         # YOUR CODE HERE
  151.             li $t7, 0 #initiates n to 0
  152. whileLoop:  move $a0, $s0 #$a0 contains address to f
  153.         jal evaluatePolynomial #returns f(x_n) at $f12
  154.         mov.d $f2, $f12  #stores returned value to register $f2
  155.         abs.d $f10, $f12    # stores absolute value of f(x_n) in $f1
  156.         l.d $f6, epsilon #loads value at epsilon in register $f6
  157.         c.lt.d $f10, $f6 #set FP condition flag true if |f(x_n)| <= epsilon
  158.         bc1t return #jumps to return if FP condition flag is true
  159.         move $a0, $s1 #$a0 contains address to f'              
  160.         jal evaluatePolynomial
  161.         mov.d $f4, $f12 # $f4 = f'(x_n)
  162.         div.d $f8, $f2, $f4 # $f8 = f(x_n) / f'(x_n)
  163.         sub.d $f0, $f0, $f8 # x_(n+1) = x_n - f(x_n) / f'(x_n)
  164.         addi $t7, $t7, 1 # n++
  165.         lw $t6, maxRounds
  166.         blt $t7, $t6, whileLoop # if n >= maxrounds continue, else abort
  167.         la $a0, noSolutionFound
  168.         jal printString # printing abort-string
  169.         lw $ra, 8($sp) #taking next instruction from stack
  170.         jr $ra # going back to next instruction
  171. return:     la $a0 solutionFound
  172.         jal printString
  173.         mov.d $f12, $f0
  174.         jal printDouble # printing solution
  175.         lw $ra, 8($sp) #taking next instruction from stack
  176.         jr $ra # going back to next instruction
  177.  
  178. # - ^ - ^ - ^ - ^ - ^ - ^ - ^ - ^ - ^ - ^ - ^ - ^ - ^ - ^ - ^ - ^ - ^ - ^ - ^ - ^ - ^ -
  179.                # restore the old stackframe and return to the calling function
  180.                 lw $s0, 20($sp)
  181.                 lw $s1, 16($sp)
  182.                 lw $s2, 12($sp)
  183.                 lw $ra, 8($sp)
  184.                 lw $fp, 4($sp)
  185.                 addu $sp, $sp, 24
  186.                 jr $ra
  187.                
  188. # - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - #
  189. # Subroutine: evaluatePolynomial                                                        #                                                                       #
  190. #       The subroutine evaluates the polynomial on the given x coordinate.              #
  191. #                                                                                       #
  192. # Parameters:                                                                           #
  193. #       $a0 - start address of polynomial factors                                       #
  194. #       $f0 - value x at which polynomial will be evaluated                             #
  195. # Output:                                                                               #
  196. #       $f12 - the computed value                                                       #
  197. # - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - #
  198. evaluatePolynomial:
  199.                # prepare a new stackframe for the subroutine
  200.                 subu $sp, $sp, 48
  201.                 s.d $f0, 48($sp)        # to make it easier for newton method
  202.                 s.d $f2, 40($sp)        # we store the floating point registers
  203.                 s.d $f4, 32($sp)        # to restore it after the evaluation
  204.                 s.d $f6, 24($sp)
  205.                 s.d $f8, 16($sp)
  206.                 sw $ra, 8($sp)
  207.                 sw $fp, 4($sp)
  208.                 addu $fp, $sp, 48
  209.  
  210. # - ! - ! - ! - ! - ! - ! - ! - ! - ! - ! - ! - ! - ! - ! - ! - ! - ! - ! - ! - ! - ! -
  211. # implement the evaluation of the polynomial given with address at $a0 at value in $f0
  212.        # for (i = 0; i <= 4; i++) {
  213.        #    f2 += a0[i] * (x^i);      
  214.        # }
  215.  
  216.         # YOUR CODE HERE
  217.                 li $t0, 0 # t0 = i (counter)
  218.             l.d $f12, null
  219.     addEval:    l.d $f2, eins # f2 is x^i
  220.             beq $t0, 0, doneMultEval
  221.             mul.d $f2, $f2, $f0 # x^1
  222.             beq $t0, 1, doneMultEval
  223.             mul.d $f2, $f2, $f0 # x^2
  224.             beq $t0, 2, doneMultEval
  225.             mul.d $f2, $f2, $f0 # x^3
  226.             beq $t0, 3, doneMultEval
  227.             mul.d $f2, $f2, $f0 # x^4
  228.     doneMultEval:   mul $t1, $t0, 8 # bit-offest for array
  229.             add $t1, $t1, $a0
  230.             l.d $f6, ($t1) # $f6 = a0[i]
  231.             mul.d $f4, $f2, $f6 # $f4 = a0[i] * (x^i);
  232.             add.d $f12, $f12, $f4 # $f12 += $f4
  233.             add $t0, $t0, 1
  234.             ble $t0, 4, addEval
  235.              
  236.  
  237.                
  238. # - ^ - ^ - ^ - ^ - ^ - ^ - ^ - ^ - ^ - ^ - ^ - ^ - ^ - ^ - ^ - ^ - ^ - ^ - ^ - ^ - ^ -                
  239.                # restore the old stackframe and return to the calling function
  240.                 l.d $f0, 48($sp)        
  241.                 l.d $f2, 40($sp)        # note that this restores the floating point registers
  242.                 l.d $f4, 32($sp)        # f0 - f9
  243.                 l.d $f6, 24($sp)        # return value has to be stored in f12
  244.                 l.d $f8, 16($sp)
  245.                 lw $ra, 8($sp)
  246.                 lw $fp, 4($sp)
  247.                 addu $sp, $sp, 48
  248.                 jr $ra            
  249.  
  250. # - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - #
  251. # Subroutine: derive                                                                    #                                                                       #
  252. #       The subroutine derives the polynomial of degree 4 at $a0.                       #
  253. #       Stores the derived polynomial at $a1.                                           #
  254. #                                                                                       #
  255. # Parameters:                                                                           #
  256. #       $a0 - address of polynomial f                                                   #
  257. #       $a1 - address where the derived polynomial f' will be stored                    #
  258. # - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - #
  259. derive:
  260.                # prepare a new stackframe for the subroutine
  261.                 subu $sp, $sp, 8
  262.                 sw $ra, 8($sp)
  263.                 sw $fp, 4($sp)
  264.                 addu $fp, $sp, 8
  265. # - ! - ! - ! - ! - ! - ! - ! - ! - ! - ! - ! - ! - ! - ! - ! - ! - ! - ! - ! - ! - ! -
  266. # implement the derive subroutine here
  267. # hint: you can use mtc1.d $t0, $f0 to move int at $t0 to double $f0/1
  268. # and then cvt.d.w $f0, $f0 to convert it to double
  269.        # for (i = 1; i <= 4; i++) {
  270.        #       b[i - 1] = (i) * a[i]
  271.        # }
  272.  
  273.  
  274.         # YOUR CODE HERE
  275.                 li $t0, 1 # t0 = i (counter)
  276.     addEval2:   mul $t2, $t0, 8 # bit-offest for array
  277.             add $t2, $t2, $a0
  278.             l.d $f2, ($t2) # $f2 = a0[i]
  279.            
  280.             mtc1.d $t0, $f4
  281.             cvt.d.w $f4, $f4 # $f4 = i
  282.            
  283.             mul.d $f6, $f2, $f4 # $f6 = i * a0[i];
  284.            
  285.             subi $t3, $t0, 1
  286.             mul $t3, $t3, 8
  287.             add $t3, $t3, $a1
  288.             s.d $f6, ($t3) # b[i - 1] = $f6
  289.             addi $t0, $t0, 1
  290.             ble $t0, 4, addEval2
  291.  
  292. # - ^ - ^ - ^ - ^ - ^ - ^ - ^ - ^ - ^ - ^ - ^ - ^ - ^ - ^ - ^ - ^ - ^ - ^ - ^ - ^ - ^ -
  293.  
  294.                 # restore the old stackframe and return to the calling function
  295.                 lw $ra, 8($sp)
  296.                 lw $fp, 4($sp)
  297.                 addu $sp, $sp, 8
  298.                 jr $ra
  299. # - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - #
  300. # Subroutine: readFactors                                                               #
  301. #       The subroutine asks for the polynomial factors and stores them at given address.#
  302. #                                                                                       #
  303. # Parameters:                                                                           #
  304. #       $a0 - start address of where to store the factors                               #
  305. # - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - #
  306. readFactors:
  307.                # prepare a new stackframe for the subroutine
  308.                 subu $sp, $sp, 8
  309.                 sw $ra, 8($sp)
  310.                 sw $fp, 4($sp)
  311.                 addu $fp, $sp, 8
  312.                
  313.                 move $s0, $a0
  314.                 la $a0, readFactorsPrompt
  315.                 jal printString
  316.                        
  317.         # for (i = 0; i <= 4; i++) {
  318.        #    a[i] =  readDouble
  319.        # }
  320.                 li $s1, 4               # 4
  321.                 li $s2, 0               # i = 0
  322.         loopR:  bgt $s2, $s1, outR      # i > 4 ? out : go on
  323.                
  324.                 la $a0, readNextFactor
  325.                 jal printString
  326.                
  327.                 mul $t3, $s2, 8         # i * 8 since we handle double
  328.                 add $a0, $t3, $s0       # &a[i]
  329.                 jal readAndStoreDouble
  330.                
  331.                 addi $s2, $s2, 1        # i++
  332.                 j loopR
  333.         outR:          
  334.  
  335.                 # restore the old stackframe and return to the calling function
  336.                 lw $ra, 8($sp)
  337.                 lw $fp, 4($sp)
  338.                 addu $sp, $sp, 8
  339.                 jr $ra
  340.                
  341. # - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - #
  342. # Subroutine: printPolynomial                                                           #                                                                       #
  343. #       The subroutine prints the factors of the polynomial given in $a0.               #
  344. #                                                                                       #
  345. # Parameters:                                                                           #
  346. #       $a0 - start address of polynomial factors                                       #
  347. # - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - #
  348. printPolynomial:
  349.                # prepare a new stackframe for the subroutine
  350.                 subu $sp, $sp, 20
  351.                 sw $s0, 20($sp)
  352.                 sw $s1, 16($sp)
  353.                 sw $s2, 12($sp)
  354.                 sw $ra, 8($sp)
  355.                 sw $fp, 4($sp)
  356.                 addu $fp, $sp, 20
  357.                
  358.                 move $s0, $a0           # save poly start address
  359.                
  360.                 la $a0, polyPrint       # print polynomial string
  361.                 jal printString
  362.                
  363.                 li $s1, 4               # 4
  364.                 li $s2, 0               # i = 0
  365.         ploop:  
  366.                 mul $t3, $s2, 8         # i * 8 since we handle double
  367.                 add $t3, $t3, $s0       # &a[i]
  368.                 l.d $f12, 0($t3)                # a[i]
  369.                 jal printDouble
  370.                
  371.                 beq $s2, $s1, pout      # i = 4 ? out : go on   to not print comma
  372.                 la $a0, comma           # print comma
  373.                 jal printString
  374.                
  375.                 addi $s2, $s2, 1        # i++
  376.                 ble $s2, $s1, ploop     # i <= 4 ? loop : go on
  377.                
  378.         pout:   # restore the old stackframe and return to the calling function
  379.                 lw $s0, 20($sp)
  380.                 lw $s1, 16($sp)
  381.                 lw $s2, 12($sp)
  382.                 lw $ra, 8($sp)
  383.                 lw $fp, 4($sp)
  384.                 addu $sp, $sp, 20
  385.                 jr $ra
  386.  
  387. # - - some more little helping subroutines  - - - - - - - - - - - - - - - - - - - - - - #
  388. # prints string with start address in $a0
  389. printString:    li $v0, 4
  390.                 syscall
  391.                 jr $ra
  392.                
  393. # prints double at $f12
  394. printDouble:    li $v0, 3
  395.                 syscall
  396.                 jr $ra
  397.  
  398. # reads double and stores it at $a0    
  399. readAndStoreDouble:
  400.                 li $v0, 7
  401.                 syscall
  402.                 s.d $f0, 0($a0)
  403.                 jr $ra
  404.  
  405. # aligns stack pointer to multiple of 8
  406. alignStackPointer:
  407.                 li $t0, 8
  408.                 div $sp, $t0
  409.                 mfhi $t0
  410.                 sub $sp, $sp, $t0
  411.                 jr $ra
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!