Fibonacci past the horizon

fib(93) is the last Fibonacci number that fits in 64 bits, read as unsigned. This program goes on to fib(186) by keeping each number in two registers, a high half and a low half: 128 bits together.

Adding two 128-bit numbers takes two instructions. addsRd = Rn + Rm/imm, and sets the NZCV condition flags. adds the low halves and sets the carry flag C when their sum does not fit in 64 bits. adcRd = Rn + Rm + C. No flags. (add with carry) then adds the high halves plus C. A plain addRd = Rn + Rm/imm. No flags. on the high halves would drop that carry.

The starter reads n (0 to 186) into nth_r and prints a as 32 hex digits, high half first. Write the loop: a starts at fib(0) = 0 and bUnconditional branch to label (±128 MiB). at fib(1) = 1, and each of the n steps makes a + b the new bUnconditional branch to label (±128 MiB). while a takes the old bUnconditional branch to label (±128 MiB).. When the loop ends, a is fib(n).

With the sample input 100 the program prints fib(100) = 0x000000000000001333db76a7c594bfc3.

What is checked

• the line for the sample input
• the program exits cleanly
• the 128-bit add uses addsRd = Rn + Rm/imm, and sets the NZCV condition flags. and adcRd = Rn + Rm + C. No flags.
• the right answer for other values of n, including 0, the first n whose answer needs the high half, and 186