Implementing the fibonacci function using RISC - V, so that f(0) = 0 ,
f(1) = 1, ..., up to f(47).
My output matches everything up to 46. But when i try to calculate f(47) i get: -1323752223.
Here's the output:Output from Code below with n=47
Is there some sort of Overflow because i get a negative Integer value? Where should i look into to try and fix the error?
.data
n: .word 47
.text
.globl main
main:
li x2, 0 # Used to determine if n (x7) equals 0
li x3, 1 # Used to determine if n (x7) equals 1
li x5, 0 # First number
li x6, 1 # Second number
lw x7, n # Limit
li x8, 1 # Counter
beq x7, x2, DO # If n == 0 then jump to DO (Which shoud print 0). Implements f(0) = 0
beq x7, x3, WRITE # if n == 1 then jump to WRITE (Which should print 1). Implements f(1) = 1
LOOP: beq x8, x7, EXIT # Comparse the counter x8 which starts with 1 to n (limit). If x8 == x7 jump to EXIT
add x4, x5, x6 # Add x5 to x6 and store in x4
ori x5, x6, 0 # Assign the second number to my first number
ori x6, x4, 0 # Assign the sum of x5 and x6 to my second number
addi x8, x8, 1 # Add 1 to my counter
j LOOP # Jump to loop
EXIT:
li x17, 1 # Load constant 1 to x17
add x10,x4,x0 # Add x4 (which contains the result after the above coe) to x10
ecall # Issue an SystemCall which prints an integer (Because of the 1 in x17)
li x17, 5
ecall
li x17, 10
ecall # Reads an int from input console (Because of the 10 in x17)
DO:
li x4, 0 # load 0 in x10 (x10 will be used by the SysCall to print) and print
add x10,x4,x0
li x17, 1
ecall
li x17, 5
ecall
li x17, 10
ecall
WRITE: li x4, 1 # load 1 in x10 and print
add x10,x4,x0
li x17,1
ecall
li x17, 5
ecall
li x17, 10
ecall
Yes, you have found the boundary of what signed 32-bit integers can hold.
fib(47) = 2971215073 won't fit in 32-bit integers as signed, but will fit as unsigned — however, RARS does not have an "unsigned int" print function.
fib(48) = 4807526976 won't fit in 32-bit form, even as unsigned.
List of fibonacci numbers: https://www.math.net/list-of-fibonacci-numbers
If you want to represent larger numbers, you will need a strategy.
if precision is not important, you can switch to floating point, where the results with such large numbers will be inexact.
use two integers together for 64-bit arithmetic — you'll be good up to fib(92) = 7540113804746346429.
use variable length integers for precision limited only by computer memory and compute time
a complex combination of the above
And finally, you can detect and issue an error on overflow of your chosen arithmetic data type. Overflow detection on RISC V is somewhat simple but not really obvious.
Technically, addition of 2 arbitrary 32-bit numbers results in a 33 bit answer — but no more than 33 bits, so we can use that knowledge of math in detecting overflow.
First, in a 32-bit number the top bit is either the sign bit (when signed data type), or the magnitude bit (when unsigned data type).
If you add two positive numbers (as is the case with fib) and the sign bit is set, you have signed overflow — but a proper bit pattern, if interpreted as unsigned. However, you won't be able to print the number properly using the ecall #1, because it will print the number as signed and interpret as negative. You can write your own unsigned number print; you can also look for this case and simply stop the program from printing and issue an error instead.
Going beyond that you can check for overflow in 32-bit unsigned addition by seeing if the resulting value is less than one of the input operands.
The last approach is also used in multiword addition to make a carry from the lower word(s) to higher word(s).