Find the closest Fibonacci Number

We are all familiar with the famous Fibonacci sequence, that starts with 0 and 1, and each element is the sum of the previous two. Here are the first few terms (OEIS A000045):

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584


Given a positive integer, return the closest number of the Fibonacci sequence, under these rules:

• The closest Fibonacci number is defined as the Fibonacci number with the smallest absolute difference with the given integer. For example, 34 is the closest Fibonacci number to 30, because |34 - 30| = 4, which is smaller than the second closest one, 21, for which |21 - 30| = 9.

• If the given integer belongs to the Fibonacci sequence, the closest Fibonacci number is exactly itself. For example, the closest Fibonacci number to 13 is exactly 13.

• In case of a tie, you may choose to output either one of the Fibonacci numbers that are both closest to the input or just output them both. For instance, if the input is 17, all of the following are valid: 21, 13 or 21, 13. In case you return them both, please mention the format.

Default Loopholes apply. You can take input and provide output through any standard method. Your program / function must only handle values up to 108.

Test Cases

Input -> Output

1    -> 1
3    -> 3
4    -> 3 or 5 or 3, 5
6    -> 5
7    -> 8
11   -> 13
17   -> 13 or 21 or 13, 21
63   -> 55
101  -> 89
377  -> 377
467  -> 377
500  -> 610
1399 -> 1597


Scoring

This is , so the shortest code in bytes in every language wins!

• – Mr. Xcoder Jul 19 '17 at 15:01
• FWIW, here is some Python code on SO for doing this efficiently for large inputs, along with a script that can be used for timing various algorithms. – PM 2Ring Jul 20 '17 at 7:56
• Is 0 considered as a positive integer? – Alix Eisenhardt Jul 21 '17 at 12:53
• @AlixEisenhardt No. Positive integer n implies n ≥ 1. – Mr. Xcoder Jul 21 '17 at 12:56

Python 2, 43 bytes

f=lambda n,a=0,b=1:a*(2*n<a+b)or f(n,b,a+b)


Try it online!

Iterates through pairs of consecutive Fibonacci numbers (a,b) until it reaches one where the input n is less than their midpoint (a+b)/2, then returns a.

Written as a program (47 bytes):

n=input()
a=b=1
while 2*n>a+b:a,b=b,a+b
print a

f=lambda n,a=0,b=1:b/2/n*(b-a)or f(n,b,a+b)


Neim, 5 bytes

f𝐖𝕖S𝕔


Explanation:

f       Push infinite Fibonacci list
𝐖                     93
𝕖     Select the first ^ elements
This is the maximum amount of elements we can get before the values overflow
which means the largest value we support is 7,540,113,804,746,346,429
S𝕔   Closest value to the input in the list


In the newest version of Neim, this can be golfed to 3 bytes:

fS𝕔


As infinite lists have been reworked to only go up to their maximum value.

Try it online!

• How is this 5 bytes when there are 2 characters there? And what is the difference between the first and second solution? – caird coinheringaahing Jul 19 '17 at 23:32
• Are you counting bytes or characters? It appears the first is 15 bytes, and the second 7 bytes. – Nateowami Jul 20 '17 at 3:33
• This probably has some kind of own codepage in which each character is own byte meaning the first one is 5 bytes ans the second is 3 bytes. The difference between the two is that the first one selects the first 93 elements manual while the second snipet in a newer version automatically selects the highest possible value that the languages int size can handle – Roman Gräf Jul 20 '17 at 6:13
• @cairdcoinheringaahing I've often had issues with people not being able to see my programs. Screenshot – Okx Jul 20 '17 at 9:34
• @Okx Oh OK, interesting, I would not have guessed. – Nateowami Jul 20 '17 at 14:38

Python, 55 52 bytes

f=lambda x,a=1,b=1:[a,b][b-x<x-a]*(b>x)or f(x,b,a+b)


Try it online!

R, 70676462 60 bytes

-2 bytes thanks to djhurio!

-2 more bytes thanks to djhurio (boy can he golf!)

F=1:0;while(F<1e8)F=c(F[1]+F[2],F);F[order((F-scan())^2)][1]


Since we only have to handle values up to 10^8, this works.

Try it online!

Reads n from stdin. the while loop generates the fibonacci numbers in F (in decreasing order); in the event of a tie, the larger is returned. This will trigger a number of warnings because while(F<1e8) only evaluates the statement for the first element of F with a warning

Originally I used F[which.min(abs(F-n))], the naive approach, but @djhurio suggested (F-n)^2 since the ordering will be equivalent, and order instead of which.min. order returns a permutation of indices to put its input into increasing order, though, so we need [1] at the end to get only the first value.

faster version:

F=1:0;n=scan();while(n>F)F=c(sum(F),F[1]);F[order((F-n)^2)][‌​1]


only stores the last two fibonacci numbers

• Nice one. -2 bytes F=1:0;n=scan();while(n>F)F=c(F[1]+F[2],F);F[order((F-n)^2)][1] – djhurio Jul 19 '17 at 16:37
• And the fast version with the same number of bytes F=1:0;n=scan();while(n>F)F=c(sum(F),F[1]);F[order((F-n)^2)][1] – djhurio Jul 19 '17 at 16:47
• @djhurio nice! thank you very much. – Giuseppe Jul 19 '17 at 17:08
• I like this. -2 bytes again F=1:0;while(F<1e8)F=c(F[1]+F[2],F);F[order((F-scan())^2)][1] – djhurio Jul 19 '17 at 18:21
• Using a builtin to generate the fibnums is shorter: numbers::fibonacci(x<-scan(),T) – JAD Jul 20 '17 at 11:42

JavaScript (ES6), 41 bytes

f=(n,x=0,y=1)=>y<n?f(n,y,x+y):y-n>n-x?x:y
<input type=number min=0 value=0 oninput=o.textContent=f(this.value)><pre id=o>0

Rounds up by preference.

• Almost identical to the version I was working on. At least you didn't use the same variable names or I would have been freaked out. – Grax Jul 19 '17 at 16:37
• @Grax Huh, now you mention it, Business Cat beat me to it... – Neil Jul 19 '17 at 16:49
• (Well, almost... I made my version work with 0, because why not?) – Neil Jul 19 '17 at 16:50
• f=(n,x=0,y=1)=>x*(2*n<x+y)||f(n,y,x+y) Since you don't have to work with 0, you can golf a bit more. – Alix Eisenhardt Jul 21 '17 at 13:00

Jelly, 9 7 bytes

-2 bytes thanks to @EriktheOutgolfer

‘RÆḞạÐṂ


Try it online!

Golfing tips welcome :). Takes an int for input and returns an int-list.

            ' input -> 4
‘           ' increment -> 5
R          ' range -> [1,2,3,4,5]
ÆḞ        ' fibonacci (vectorizes) -> [1,1,2,3,5,8]
ÐṂ     ' filter and keep the minimum by:
ạ       ' absolute difference -> [3,3,2,1,1,4]
' after filter -> [3,5]

• You can remove µḢ. – Erik the Outgolfer Jul 19 '17 at 17:12
• @EriktheOutgolfer as in: "There is a way to do it if you think about it", or as in "If you literally just backspace them it still works"? – nmjcman101 Jul 19 '17 at 17:14
• As in "it's allowed by the rules". :P – Erik the Outgolfer Jul 19 '17 at 17:17
• Ah. Thank you! (Filler text) – nmjcman101 Jul 19 '17 at 17:18

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, n.

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 EAX register.

Ungolfed assembly mnemonics:

; unsigned int ClosestFibonacci(unsigned int n);
xor    eax, eax        ; initialize EAX to 0
lea    edx, [rax+1]    ; initialize EDX to 1

CalcFib:
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
ret


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 EAX and 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 EAX and 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 EDX into EAX, or leaves EAX alone, so that when the function RETurns, the closest Fibonacci number is returned in EAX.

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!

. 2 } + " .
| ' = = ' . @
. & } 1 . !
_ | . _ }
$_ } {  Broken down: start: ? { 2 ' * //set up 2*target number " ' 1 //initialize curr to 1 main loop: } = + //next + curr + last " - //test = next - (2*target) branch: <= 0 -> continue; > 0 -> return continue: { } = & //last = curr } = & //curr = next return: { } ! @ //print last  Like some other posters, I realized that when the midpoint of last and curr is greater than the target, the smaller of the two is the closest or tied for closest. The midpoint is at (last + curr)/2. We can shorten that because next is already last + curr, and if we instead multiply our target integer by 2, we only need to check that (next - 2*target) > 0, then return last. Common Lisp, 69 bytes (lambda(n)(do((x 0 y)(y 1(+ x y)))((< n y)(if(<(- n x)(- y n))x y))))  Try it online! Perl 6, 38 bytes {(0,1,*+*...*>$_).sort((*-$_).abs)[0]}  Test it { # bare block lambda with implicit parameter ｢$_｣

( # generate Fibonacci sequence

0, 1,  # seed the sequence
* + *  # WhateverCode lambda that generates the rest of the values
...    # keep generating until
* > $_ # it generates one larger than the original input # (that larger value is included in the sequence) ).sort( # sort it by ( * -$_ ).abs  # the absolute difference to the original input
)[0]              # get the first value from the sorted list
}


For a potential speed-up add .tail(2) before .sort(…).

In the case of a tie, it will always return the smaller of the two values, because sort is a stable sort. (two values which would sort the same keep their order)

Pyth, 27 bytes

J[Z1)WgQeJ=aJ+eJ@J_2)hoaNQJ


Test suite.

Python 3 translation:
Q=eval(input())
def a(x):
return abs(Q-x)
J=[0,1]
while Q>=J[-1]:
J.append(J[-1]+J[-2])
print(sorted(J,key=a)[0])


Pyth, 19 bytes

JU2VQ=+Js>2J)hoaNQJ


Try it here

Explanation

JU2VQ=+Js>2J)hoaNQJ
JU2                  Set J = [0, 1].
VQ=+Js>2J)        Add the next <input> Fibonacci numbers.
oaNQJ  Sort them by distance to <input>.
h       Take the first.


(%)a b x|abs(b-x)>abs(a-x)=a|1>0=b%(a+b)\$x