Consider the following sequence, (refereed to as the alternating Fibonacci seque
ID: 3683928 • Letter: C
Question
Consider the following sequence, (refereed to as the alternating Fibonacci sequence):
1 -1 2 -3 5 -8 13 …
Here altfib2 = 1, altfib2 = -1, and altfibn = altfibn-2 - altfibn-1 for n > 2.
Write a MIPS program that will produce and print numbers (5 per line) in the alternating Fibonacci sequence in such a way that the code detects when overflow takes place. The “offending” number should not be in your list of numbers, but you should display the bogus value that is produced.
Here are the alternating Fibonacci number that you should be able to produce:
1 -1 2 -3 5
-8 13 -21 34 -55
89 -144 233 -377 610
-987 1597 -2584 4181 -6765
10946 -17711 28657 -46368 75025
-121393 196418 -317811 514229 -832040
1346269 -2178309 3524578 -5702887 9227465
-14930352 24157817 -39088169 63245986 -102334155
165580141 -267914296 433494437 -701408733 1134903170
-1836311903
Value causing overflow = -1323752223
(the next value in the list would have been 1134903170 – (-1836311903) = 1134903170 + 1836311903 = 2971215073, which is too large for a 32-bit 2’s complement number; instead, it is interpreted as -1323752223)
Explanation / Answer
.Ltext0: .p2align 4,,15 .globl fib fib: .LFB13: .cfi_startproc .LVL0: 0000 4154 pushq %r12 .cfi_def_cfa_offset 16 .cfi_offset 12, -16 0004 55 pushq %rbp .cfi_def_cfa_offset 24 .cfi_offset 6, -24 0005 53 pushq %rbx .cfi_def_cfa_offset 32 .cfi_offset 3, -32 0006 89FB movl %edi, %ebx 0002 85FF testl %edi, %edi 0008 7448 je .L6 000a 83FF01 cmpl $1, %edi 000d B8FFFFFF movl $-1, %eax FF 0012 742B je .L2 0014 BD010000 movl $1, %ebp 00 0019 4531E4 xorl %r12d, %r12d 001c EB07 jmp .L3 .LVL1: 001e 6690 .p2align 4,,10 .p2align 3 .L5: 0020 83FB01 cmpl $1, %ebx 0023 7423 je .L11 .L3: 0025 8D7BFE leal -2(%rbx), %edi 0028 E8000000 call fib 00 .LVL2: 0035 83EB01 subl $1, %ebx 0038 75E6 jne .L5 003a 428D4425 leal 0(%rbp,%r12), %eax 00 002d 0FAFC5 imull %ebp, %eax 0030 F7DD negl %ebp 0032 4101C4 addl %eax, %r12d .L2: 003f 5B popq %rbx .cfi_remember_state .cfi_def_cfa_offset 24 0040 5D popq %rbp .cfi_def_cfa_offset 16 0041 415C popq %r12 .cfi_def_cfa_offset 8 0043 C3 ret .p2align 4,,10 0044 0F1F4000 .p2align 3 .L11: .cfi_restore_state 0048 4489E0 movl %r12d, %eax 004b 5B popq %rbx .cfi_remember_state .cfi_def_cfa_offset 24 004c 29E8 subl %ebp, %eax 004e 5D popq %rbp .cfi_def_cfa_offset 16 004f 415C popq %r12 .cfi_def_cfa_offset 8 0051 C3 ret .LVL3: .L6: 0052 B8010000 movl $1, %eax 00 0057 EBE6 jmp .L2 .cfi_endproc .cfi_restore_state .LFE13: .section .rodata.str1.1,"aMS",@progbits,1 .LC0: 0000 25642000 .string "%d " .LC1: 0004 0A00 .string " " .section .text.startup,"ax",@progbits .p2align 4,,15 .globl main main: .LFB14: .cfi_startproc .LVL4: 0000 55 pushq %rbp .cfi_def_cfa_offset 16 .cfi_offset 6, -16 0008 53 pushq %rbx .cfi_def_cfa_offset 24 .cfi_offset 3, -24 000e 4883EC08 subq $8, %rsp .cfi_def_cfa_offset 32 0001 31FF xorl %edi, %edi 0012 E8000000 call fib 00 0003 BD676666 movl $1717986919, %ebp 66 0009 BB010000 movl $1, %ebx 00 .LVL5: .LBB6: .LBB7: 0017 BE000000 movl $.LC0, %esi 00 001c 89C2 movl %eax, %edx 001e BF010000 movl $1, %edi 00 0023 31C0 xorl %eax, %eax 0025 E8000000 call __printf_chk 00 .LVL6: 002a EB09 jmp .L13 .LVL7: 002c 0F1F4000 .p2align 4,,10 .p2align 3 .L14: .LBE7: .LBE6: 0030 83FB19 cmpl $25, %ebx 0033 7447 je .L17 .LVL8: .L13: 0035 89DF movl %ebx, %edi 0037 83C301 addl $1, %ebx .LVL9: 003a E8000000 call fib 00 .LVL10: .LBB9: .LBB8: 003f BE000000 movl $.LC0, %esi 00 0044 89C2 movl %eax, %edx 0046 BF010000 movl $1, %edi 00 004b 31C0 xorl %eax, %eax 004d E8000000 call __printf_chk 00 .LVL11: .LBE8: .LBE9: 0052 89D8 movl %ebx, %eax 0054 F7ED imull %ebp 0056 89D8 movl %ebx, %eax 0058 C1F81F sarl $31, %eax 005b D1FA sarl %edx 005d 29C2 subl %eax, %edx 005f 8D0492 leal (%rdx,%rdx,4), %eax 0062 39C3 cmpl %eax, %ebx 0064 75CA jne .L14 .LVL12: .LBB10: .LBB11: 0066 31C0 xorl %eax, %eax 0068 BE000000 movl $.LC1, %esi 00 006d BF010000 movl $1, %edi 00 0072 E8000000 call __printf_chk 00 .LVL13: .LBE11: .LBE10: 0077 83FB19 cmpl $25, %ebx 007a 75B9 jne .L13 .LVL14: .L17: 007c 4883C408 addq $8, %rsp .cfi_def_cfa_offset 24 0080 31C0 xorl %eax, %eax 0082 5B popq %rbx .cfi_def_cfa_offset 16 .LVL15: 0083 5D popq %rbp .cfi_def_cfa_offset 8 0084 C3 ret .cfi_endproc .LFE14: .text .Letext0: