x86-64 Machine Code, 24 bytes
31 C0 8D 50 01 92 01 C2 39 FA 7E F9 89 D1 29 FA 29 C7 39 D7 0F 4F C1 C3
The above bytes of code define a function in 64-bit x86 machine code that finds the closest Fibonacci number to the specified input value,
The function follows the System V AMD64 calling convention (standard on Gnu/Unix systems), such that the sole parameter (
n) is passed in the
EDI register, and the result is returned in the
Ungolfed assembly mnemonics:
; unsigned int ClosestFibonacci(unsigned int n);
xor eax, eax ; initialize EAX to 0
lea edx, [rax+1] ; initialize EDX to 1
xchg eax, edx ; swap EAX and EDX
add edx, eax ; EDX += EAX
cmp edx, edi
jle CalcFib ; keep looping until we find a Fibonacci number > n
mov ecx, edx ; temporary copy of EDX, because we 'bout to clobber it
sub edx, edi
sub edi, eax
cmp edi, edx
cmovg eax, ecx ; EAX = (n-EAX > EDX-n) ? EDX : EAX
Try it online!
The code basically divides up into three parts:
- The first part is very simple: it just initializes our working registers.
EAX is set to 0, and
EDX is set to 1.
The next part is a loop that iteratively calculates the Fibonacci numbers on either side of the input value,
n. This code is based on my previous implementation of Fibonacci with subtraction, but…um…isn't with subtraction. :-) In particular, it uses the same trick of calculating the Fibonacci number using two variables—here, these are the
EDX registers. This approach is extremely convenient here, because it gives us adjacent Fibonacci numbers. The candidate potentially less than
n is held in
EAX, while the candidate potentially greater than
n is held in
EDX. I'm quite proud of how tight I was able to make the code inside of this loop (and even more tickled that I re-discovered it independently, and only later realized how similar it was to the subtraction answer linked above).
Once we have the candidate Fibonacci values available in
EDX, it is a conceptually simple matter of figuring out which one is closer (in terms of absolute value) to
n. Actually taking an absolute value would cost way too many bytes, so we just do a series of subtractions. The comment out to the right of the penultimate conditional-move instruction aptly explains the logic here. This either moves
EAX, or leaves
EAX alone, so that when the function
RETurns, the closest Fibonacci number is returned in
In the case of a tie, the smaller of the two candidate values is returned, since we've used
CMOVG instead of
CMOVGE to do the selection. It is a trivial change, if you'd prefer the other behavior. Returning both values is a non-starter, though; only one integer result, please!