Only the first 90ish fibonacci numbers fit in a 4 byte int. Use a lookup table, make it O(1).