[Question]
  [
## Introduction
We all know and love our Fibonacci sequence and have seen a myriad of challenge on it here already. However, we're still lacking a very simple case which this answer is going to provide: Reversed fibonacci! **So given `F_n` your job is to find `n`.**
## Specification
### Input
Your input will be a non-negative integer, which is guaranteed to be part of the fibonacci sequence.
### Output
The output must be a non-negative integer as well.
### What to do?
The introduction already said: Given a fibonacci number, output its index. Fiboancci number hereby is defined as `F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2)` and you're given `F(n)` and must return `n`.
### Potential Corner Cases
0 is a valid in- and output.  
If given "1" as input you may either output "1" or "2", as you prefer.  
You may always assume that your input actually is a fibonacci number.  
You may assume that the input is representable as a 32-bit signed integer.
### Who wins?
This is code-golf so the shortest answer in bytes wins!  
Standard rules apply of course.
## Test-cases
```
0 -> 0
2 -> 3
3 -> 4
5 -> 5
8 -> 6
13 -> 7
1836311903 -> 46
```
  
[Answer]
## Actually, 1 byte
```
f
```
Yes, there's a builtin for this, [since November 16, 2015](https://github.com/Mego/Seriously/commit/239b5cc6b71b22e96e5ced7ac3ba34ee499ae3e3).
[Try it online](http://actually.tryitonline.net/#code=Zg&input=OA)
---
For fun, without the builtin, it's 9 bytes:
```
‚ïó1`F‚ïú=`‚ïìi
```
[Try it online!](http://actually.tryitonline.net/#code=4pWXMWBG4pWcPWDilZNp&input=OA)
Explanation:
```
‚ïó1`F‚ïú=`‚ïìi
‚ïó          push input to register 0
 1`F‚ïú=`‚ïì   push list containing first value x (starting with x = 0) where:
   F         fib(x)
    ‚ïú=       is equal to the input
        i  flatten the list
```
[Answer]
# Mathematica, 25 bytes
```
InverseFunction@Fibonacci
```
Function. Pretty self-explanatory if you ask me.
[Answer]
# Python, ~~36~~ ~~34~~ 32 bytes
```
lambda n:len(str(66*n**6))//1.24
```
### Previous versions:
```
f=lambda n:len(str(66*n**6))//1.24
f=lambda n:(n*n*7).bit_length()//1.4
```
## Explanation
The core idea is to invert the formula
```
fibonacci(n) ~ ( (1 + sqrt(5)) / 2)**n / sqrt(5)
```
which tells us that
```
log fibonacci(n) ~ n log((1 + sqrt(5)) / 2) - log(sqrt(5))
```
to get
```
f(n) ~ (log(n) + log(sqrt(5))) / log((1 + sqrt(5))/2)
```
The golfing optimizations are:
* Use `len(str(n))` to compute log base 10 without importing `log` (old version used `.bit_length()` to compute log base 2)
* Raise `n` to a power, so that the approximation of the logarithm can distinguish between successive Fibonacci numbers
* Multiplying by a constant scales up the values to get them in the correct range
Then the divisor was truncated to as little precision as I could manage and the multiplier chosen to give the correct results for all 32-bit fibonacci numbers.
[Answer]
# [05AB1E](http://github.com/Adriandmen/05AB1E), 3 bytes
Code:
```
√ÖFg
```
Explanation:
```
√ÖF   # Generate all Fibonacci numbers <= input.
  g  # Get the length of this list.
```
Uses the **CP-1252** encoding. [Try it online!](http://05ab1e.tryitonline.net/#code=w4VGZw&input=MTgzNjMxMTkwMw).
[Answer]
# Julia, ~~27~~ ~~26~~ 18 bytes
```
!n=log(3n+.7)√∑.48
```
This uses the inverse of [Binet's formula](https://en.wikipedia.org/wiki/Fibonacci_number#Computation_by_rounding), with just enough precision for 32-bit integers; it actually works up to **F(153) = 42,230,279,526,998,466,217,810,220,532,898 > 2105**.
[Try it online!](http://julia.tryitonline.net/#code=IW49bG9nKDNuKy43KcO3LjQ4Cgpmb3IgbiBpbiAoMCwgMSwgMiwgMywgNSwgOCwgMTMsIDE4MzYzMTE5MDMsIDQyMjMwMjc5NTI2OTk4NDY2MjE3ODEwMjIwNTMyODk4KQogICAgQHByaW50ZigiJTMydSAtPiAlM3VcbiIsIG4sICFuKQplbmQ&input=)
### How it works
Binet's formula states the following.
![Binet's formula](https://i.stack.imgur.com/2ONm9.png)
Restricting **F** to the set of Fibonacci, the map **n → Fn** has a [right inverse](https://en.wikipedia.org/wiki/Inverse_function#Left_and_right_inverses) **F → nF**.
We have that
![right inverse of Binet's formula](https://i.stack.imgur.com/HtjEn.png)
and all that is left to do is dealing with the edge case **0**.
Since the input is restricted to 32-bit integers, we can use short decimal literals instead of the constants in the formula.
* **log φ = 0.481211825059603447… ≈ 0.48**
Unfortunately, **0.5** isn't precise enough.
* **√5 = 2.2360679774997896964… ≈ 3**
That might seem like an awful approximation at first glance, but we're taking logarithms and since **log 3 - log √5 = 0.29389333245105…**, the result before rounding will be off by a small constant factor.
* **0.5 ≈ 0.7**
Because of the excess from the previous approximation, we could actually omit this term altogether and still get correct results for **F > 0**. However, if **F = 0**, the logarithm will be undefined. **0.7** turned out to be the shortest value that extends our formula to **F = 0**.
[Answer]
# Jelly, ~~14~~ 11 bytes
```
5¬Ω√ól√òp+.·∏û¬ª0
```
[Try it online!](http://jelly.tryitonline.net/#code=NcK9w5dsw5hwKy7huJ7CuzA&input=&args=OA)
This is my first ever Jelly answer! This uses the algorithm [from the MATL answer](https://codegolf.stackexchange.com/a/85573/31716). Thanks to Dennis for shaving off 3 bytes!
Explanation:
```
   l√òp      # Log Base phi
5¬Ω          # Of the square root of 5
  √ó         # Times the input
      +     # Plus
       .    # 0.5
        ·∏û   # Floored
```
This gets the right answer, now we just need to handle the special case of '0'. With '0' as an arg, we get `-infinity`, so we return
```
¬ª      # The maximum of 
 0     # Zero
       # And the previous calculated value.
```
[Answer]
# JavaScript, ~~54~~ ~~50~~ ~~69~~ ~~50~~ 42 bytes
```
b=>(j=>{for(i=c=0;b-i;c++)i=j+(j=i)})(1)|c
```
Surely it isn't going to win, just for fun :)
~~Ok, checking for zero consumes 19 bytes. WTF?~~ Stupid-me.
---
Demo! To see the last test case, you have to scroll the console a bit.
```
a=b=>(j=>{for(i=c=0;b-i;c++)i=j+(j=i)})(1)|c;
console.log('0: '+a(0));
console.log('2: '+a(2));
console.log('3: '+a(3));
console.log('5: '+a(5));
console.log('8: '+a(8));
console.log('13: '+a(13));
console.log('1836311903: '+a(1836311903));
```
Thanks @edc for shortening by 8 bytes.
[Answer]
# [Perl 6](http://perl6.org) ~~¬†33 30¬†~~ 27 bytes
```
~~{first \*==$\_,:k,(0,1,\*+\*...\*>$\_)}
{first \*==$\_,:k,(0,1,\*+\*...\*)}~~
{first $_,:k,(0,1,*+*...*)}
```
[Try it](https://tio.run/nexus/perl6#ZZDPboJAEMbvPMUcjIKuZGeBBTSanvoEvRnT4LpUggLKYjXGx@7Z7q6tbdPbb/58M/NN10o4cl9MnU7Ti2zV1HF2Z@jnxWpcVGt5ghncLnlxaBX0XsmkJC4lSIajoe/7Q@96081PSuta3eg6ABRmc6BEEzMUGAoMhYYiQ5GhxBA3hLYcW0wCHiCm9K64lxmjFDkNMUKGSczjwGpTOxrTOKQsDhmmCU8YC5DHtmrXBVHIWJiECcYp45hiRGN7AlJ9oqe9NtusgtGXgxGgTuX14dvSeK5NgwuTUp7dXlE1nfIITI7ZtpNuT54aKZRce@DBRW8Tu2Zcl/B43Y@iv5D745LAQ0LAfyta5Vwd55/qz4MX@lK6/DXCxAQG7/WhbKFrQNU2pTYgt3InKwV1Ds/Fqq4yIQpo5b6TlZCD20dVj0UmNvIT "Perl 6 ‚Äì TIO Nexus")
### Explanation:
```
# lambda with implicit ÔΩ¢$_ÔΩ£ parameter
{
  first           # find the first element
    $_,           # where something is equal to the block's argument
    :k,           # return the key rather than the value
    # of the Fibonacci sequence
    ( 0, 1, * + * ... * )
    # ^--^ first two values
    #       ^---^ lambda used to generate the next in the series
    #             ^-^ generate until
    #                 ^ Whatever
}
```
### Test:
```
#! /usr/bin/env perl6
use v6.c;
use Test;
# using the safer version that stops generating
# values bigger than the input
my &fib-index = {first $_,:k,(0,1,*+*...*>$_)}
my @tests = (
  0 => 0,
  2 => 3,
  3 => 4,
  5 => 5,
  8 => 6,
  13 => 7,
  1836311903 => 46,
  1836311904 => Nil, # this is why the safe version is used here
  12200160415121876738 => 93,
  19740274219868223167 => 94,
  354224848179261915075 => 100,
);
plan +@tests + 1;
for @tests -> $_ ( :key($input), :value($expected) ) {
  cmp-ok fib-index($input), &[eqv], $expected, .gist
}
cmp-ok fib-index((0,1,*+*...*)[1000]), &[eqv], 1000, 'works up to 1000th element of Fibonacci sequence'
```
```
1..13
ok 1 - 0 => 0
ok 2 - 2 => 3
ok 3 - 3 => 4
ok 4 - 5 => 5
ok 5 - 8 => 6
ok 6 - 13 => 7
ok 7 - 1836311903 => 46
ok 8 - 1836311904 => Nil
ok 9 - 12200160415121876738 => 93
ok 10 - 19740274219868223167 => 94
ok 11 - 354224848179261915075 => 100
ok 12 - works up to 1000th element of Fibonacci sequence
```
[Answer]
# [Jelly](http://github.com/DennisMitchell/jelly), 8 [bytes](https://github.com/DennisMitchell/jelly/wiki/Code-page)
```
1+√ê¬°0
¬¢i
```
[Try it online!](http://jelly.tryitonline.net/#code=MSvDkMKhMArComk&input=&args=MTM) Note that this approach is too inefficient for the last test case.
### How it works
```
¬¢i     Main link. Argument: n
¬¢      Call the helper link niladically (i.e., without arguments).
       This yields the sequence of the first n positive Fibonacci numbers, i.e.,
       [1, 1, 2, 3, 5, ...].
 i     Find the first index of n (1-based, 0 if not found).
1+√ê¬°0  Helper link. No arguments.
1      Set the left argument to 1.
    0  Yield 0.
 +√ê¬°   Add both arguments, replacing the left argument with the sum and the right
       argument with the previous value of the left argument.
       Yield the array of all intermediate values of the left argument.
```
[Answer]
## Pyke, 5 bytes
```
.f.bq
```
[Try it here!](http://pyke.catbus.co.uk/?code=.f.bq&input=8&warnings=0)
```
.f    - first number where
  .b  -  fib(n)
    q - ^ == input
```
[Answer]
## Python, 29 bytes
```
g=lambda n:n>.7and-~g(n/1.61)
```
Recursively divides the input by the golden-ratio approximation 1.61 until it's below 0.7, and outputs the number of divisions.
For 0, the code outputs `False`, [which equals 0 in Python](http://meta.codegolf.stackexchange.com/q/9064/20260). This can be avoided for 2 bytes
```
g=lambda n:n//.7and 1+g(n/1.61)
```
[Answer]
## JavaScript, 22 bytes
```
n=>Math.log(n)/.48+2|0
```
[Answer]
## JavaScript (ES6), ~~39~~ 33 bytes
```
f=(n,j=0,k=1)=>n>j?f(n,k,j+k)+1:0
```
Even with ES7, the inverse Binet formula takes 47 bytes:
```
x=>Math.log(x*5**.5)/Math.log(.5+1.25**.5)+.5|0
x=>Math.log(x*5**.5)/Math.log((1+5**.5)/2)+.5|0
x=>Math.log(x*(p=5**.5))/Math.log((1+p)/2)+.5|0
```
[Answer]
## Sage, 49 bytes
```
lambda x,s=sqrt(5):x and int(log(x*s,(1+s)/2)+.5)
```
Thanks to TuukkaX for the suggestion about saving `sqrt(5)` as `s` to shave off a few bytes.
[Try it online](http://sagecell.sagemath.org/?z=eJxLs81JzE1KSVSo0Cm2LS4sKtEw1bSqUEjMS1HIzCvRyMlP16jQKtbRMNQu1tQ30tTWM9Xk5eLlKigCyiqkaaRlJuXnJSYnZ2oYGhhoagIAwWAXHw==&lang=sage).
This approach using an inverse of Binet's formula offers several improvements over the previous approach: it's faster (constant-time versus quadratic time), it actually works for larger inputs, and it's shorter!
Python users may wonder why I'm using `sqrt(5)` instead of the shorter `5**.5` - it's because `5**.5` is computed with C's `pow` function, and loses precision due to floating point issues. Many mathematical functions (including `sqrt` and `log`) are overloaded in Sage to return an exact, symbolic value, which don't lose precision.
[Answer]
# [MATL](https://github.com/lmendo/MATL), 14 bytes
```
t?5X^*17L&YlYo
```
[**Try it online!**](http://matl.tryitonline.net/#code=dD81WF4qMTdMJllsWW8&input=MTgzNjMxMTkwMw)
This uses [an inverse of Binet's formula](https://mathoverflow.net/questions/39124/fibonacci-sequence-inversion), and so it's very fast.
Let *F* denote the *n*-th Fibonacci number, and *œÜ* the [golden ratio](https://en.wikipedia.org/wiki/Golden_ratio). Then
[![enter image description here](https://i.stack.imgur.com/jVhN5.png)](https://i.stack.imgur.com/jVhN5.png)
The code uses this formula with two modifications:
* Instead of adding 1/2 and then rounding down, the code simply rounds towards the nearest integer, which takes up fewer bytes.
* Input *F*=0 needs to be treated as a special case.
### How it's done
```
t         % Take input F implicitly. Make a copy
?         % If (copy of) F is positive
  5X^     %   Push sqrt(5)
  *       %   Multiply by F
  17L     %   Push phi (predefined literal)
  &Yl     %   Two-input logarithm: first input is argument, second is base
  Yo      %   Round towards nearest integer
          % Else the input, which is 0, is left on the stack
          % End if implicitly
          % Display implicitly
```
[Answer]
# [Prolog (SWI)](http://www.swi-prolog.org), 90 bytes
*Written in conversation with [flawr](https://codegolf.stackexchange.com/users/24877/flawr) in chat.*
```
F-N-A-B:-F=A;N>0,M is N-1,C is A+B,F-M-B-C.
F/N/I:-N=I,F-N-0-1;J is I+1,F/N/J.
F/N:-F/N/0.
```
[Try it online!](https://tio.run/##HYxLCoQwEAX3nsK9/ZI0gcEPERIhEMG@hAsRBhx04fGjmV3Bq3q/8/geG657zzlC4BF6ROcHGQ0t9X7VAqapgG8CRSwImFQVtejUQ1yikhnwMBcpNUxlm//Ke/WyUTlzaz@WuTNWi6rWBw "Prolog (SWI) ‚Äì Try It Online")
### Ungolfed
Here's a less-golfed version:
```
fib(F,0,F,_).
fib(F,N,A,B) :- N>0, M is N-1, C is A+B, fib(F,M,B,C).
fibindex(F,N,N) :- fib(F,N,0,1).
fibindex(F,N,I) :- J is I+1, fibindex(F,N,J).
fibindex(F,N) :- fibindex(F,N,0).
```
The `fib/4` predicate (`F-N-A-B` in the golfed version) takes a number `N` and two accumulators `A` and `B` (which should start at `0` and `1`) and unifies `F` with the `N`th Fibonacci number. If `N` is `0`, `F` is simply the current value of `A`, the smaller accumulator value. Otherwise, count `N` down by one and recurse with new accumulator values `B` and `A+B`.
`fibindex/3` (`F/N/I` in the golfed version) takes a Fibonacci number `F` and an index `I` (which should start at `0`) and unifies `N` with the Fibonacci index of `F`. Either `F` is the `I`th Fibonacci number, in which case `N=I` and we're done, or we count `I` up by one and recurse. Note that this approach leads to infinite recursion if given a non-Fibonacci number, but we don't have to handle that case for this challenge.
Finally, `fibindex/2` (`F/N`) just calls `fibindex/3` with an initial `I` value of `0`.
[Answer]
# Regex (.NET), ~~23~~ 19 bytes
```
(\2?(\1)|x$|^x|\b)*
```
[Try it online!](https://tio.run/##RY5BboMwFET3nOILfQk7FBRadRPLaqSue4KQSsb5CZYAIxsESsi2B@gRexHqtovOZkYzize9ncj5mppmRScPji40H3e7jia2T1ZWPr6wsuDLjMv7vJQV36zJ/iF@tW1vGjrFXOBVbkV0to4hQxUyVrIQaOSWC0CTNQRPzz8pTTncIgjCFiSgy9/UoGvyLJmTDSoufkdzZnjlt8mZgbLa@uEeCIWA/wKyzoZ/jekIYlTw9fEJgd3mF2fH3h@KY65VP4yOfK7t2A08/sNqiSo8URKrYFUqUYvovn4D "PowerShell ‚Äì Try It Online")
Takes its input in unary, as a string of `x` characters whose length represents the number. Returns its output as the capture count of group `\1`.
This is based on [Martin Ender's .NET regex for matching Fibonacci numbers](https://codegolf.stackexchange.com/questions/126373/am-i-a-fibonacci-number/126405#126405). The .NET feature of balanced groups is used to count the number of iterations taken by the loop.
* That regex is first initially translated to use `x` as its unary numeral, yielding `^$|^(^x|(?>\2?)(\1))*x$`.
* Then the `x$` at the end is moved inside as the extra alternative `|x$`, incrementing the loop count by \$1\$ for all \$n>0\$. This also allows us to remove the `^$|` at the beginning, because `^(^x|(?>\2?)(\1)|x$)*$` will now match \$n=0\$ on its own. (It will also now match numbers that are \$0\$ or \$1\$ less than a Fibonacci number, but we don't care because as specified by the challenge, all inputs will be Fibonacci numbers.)
* Then the extra alternative `|\b` is added to increment the loop count again for all \$n>0\$; `\b` cannot match on an input of \$n=0\$ because there is no word character (`[0-9A-Za-z_]`) to form a boundary with the absense of a word character, but it will always match at the end of a string of one or more `x`s. The match is zero-width, so the loop will then be terminated.
* Then we remove the `^` and `$` anchors sandwiching the regex, because we don't need to return a non-match for non-Fibonacci numbers.
* Then an optimization for speed, moving the `^x` alternative as far to the end as possible, because it only has to match once, and would add a failed match to every subsequent iteration if ordered as the first alternative.
* The `\2?` can lose the `(?>`...`)` atomic group around it, because we don't need to determine if a number is Fibonacci or not. Due to the lack of any assertions following the loop, it will simply keep the first match it finds at each iteration, not having any reason to backtrack.
**27 byte** version that matches iff the input is a Fibonacci number:
```
^((?>\2?)(\1)\B|x$|^x|\b)*$
```
[Try it online!](https://tio.run/##RY9BboMwEEWvYlkjYYcaQboLchO1654AiESJEyw5tmUbgQJse4AesRehpFHV5Zv5evPHml443wqlFnC8cOIihmq306Inh2g5ErJ/Kbd7SsqMlq/TANNxmMoPuoElOjzhN3O1UokTpjnceJqfjRN10xJQSGoEUtsu0BFqDop5q2TADOfyTKBOGtPpwFRA23sg5lAXaTWvAgKaF1KH6neSg2ZK/HF25zim491x5eCS9zo0rfAkGqINaPrY3OjYOxkEa40P89osy/8ZMW3W95TUAmHQ6PvzC8FqSy7OdNavN5KmtqFzwj9KUjzP85Ky7DlNfwA "PowerShell ‚Äì Try It Online")
The `\B` prevents numbers \$1\$ less than a Fibonacci number from being matched; in unary, `\B` matches at every place except the beginning and end in a non-zero number (and matches "everywhere" in an input of zero).
# Regex `üêá` (PCRE1 / PCRE2 v10.34 or earlier), 20 bytes
```
^(\2?(\1)|x$|^x)+|^x
```
[Try it online!](https://tio.run/##dVNtb9owEP7Or7hma4mJW0HRpongVlvXaR9YOyEqbQIaGeOEqMGJnGTQt6/7AfuJ@yFjlzihdC8RJOfz3XN3z2OLJDkMhNi8CJWI8rmEfiK0PFqcNMSCa/CS8RQYDK13q9XNrJt/vb39Mlq8Xi3szbU9OT61Jx3ysH75cL0mDr425M84i0IrYV7idNzGU400m4dxUWTXpUMVPPeFMXolX/4dd9IIVQYJmpkntY61LWKVZlA23VrKNOWBJPdYp9cTGAD9PlTewiz9Us0jF7TMcq2g4z42cpWGgZJziGIVmBdX6Upqt6y2vPUEj6I4z@yCo3rhzaJY3EBLELg34Y6zhW0jbJnLQ2VjQAPwScY4RCSVnZDDzpS1XTANmdEgEcyyT3uWi5bDEvOxiH16hv89gv4cIbvHXgZxkVzgB2iU2LtAoUryrEjXElpaurDLEZKSZNpka5nmUWbsgk3fT2VGAYfDLoNsYXbib1JksR53p6YUojIwTMTLJIwk0nIkPCxuEwqfz4bn3vvL0dvBAB7M6mr04Q2FA1PZGHWpNjGYoQ/2npak5s8vJfZtHAujKVgFUNmjBo4tlemwP@/BfjpReNh2ME2dCnhXMWz7SUuz7eMJKmbkrE1nrEMFvUMrLOnts@4r5I5xytmMzhwmaOg4tZh113cEkO2CW7s5UU3iwh3ruFD1b@3P4ef3H4Adctwy5wT7qFQrHiNLik4lV2Y15k5n6uLBXeJAdkqhuW4agHTMp2wn2ShY6yHXUthaUri4GgwoYCJHistfJSKFLnGf9W8Q@m04OKjR9pjR7Xw4vBx6F5ef3o7OPpJt1va4iYJTvFXWeaGL9YQro1T@P7wiob6OfpSni39MVE352ChV7xm5tJTYMdnes@oENx43v4Qf8SDdHEYFFb8B "C++ (gcc) ‚Äì Try It Online") - PCRE1  
[Try it online!](https://tio.run/##hVXvbtpIEP/OU0zcu2QXTA@IWkUYJ8oRpERqSUWJrldCrWW9BqvGtux1SdLmax/gHvEe5Ljx7gJOyOksMLOzM7@dP78deJo255yvX/kiCGMBH/qjQcfrX18MvJvh1dj74@pifAkntVdhzKPCF9BLeSY6rxenNb5gGXjpZAoujKzfV6uvs@Piz/v7T@PF29WCrL@Q284ZuW3TH3e//PhyRxv4WtPndpYN9dT10kbbqRySyyyM5@UpO12YoFaw5eme3WktjCWkKEpPZFmSEZ7EuQQVYX0p8pzNBYXvufS7XY4W0OuBUZei0ovYjxzIhCyyGNrO4x5mueaJL2yYJUkEiRuwKC9h1TEGbtJ583bq1ACfMACiiuXNhcHwjBXROERX@6Z/eT46qVOzaUMePogkINvAf9toKvaUUnVK@ZAEznQSPCkkdGGbKC3Ts5QbqAi6YD1LXjlbFnpZt7FFt/UIoiJf6Ey2Rak91oo4D@ex8CFK4rl@sThficxRBVvee5xFEYZhcjcrbxYl/CvUuQ3fktCHus8kw9qVRSpFcF0g5U6dHu4wqMFuNLadaZnOLFkYEwRQAaYTJEIkYpLSZnvqthydgmYHpNy1yFnXclBquKn@sSg56@P3gKK@QMTjjiexqehbws9RUNBVoDBOC1m6q8SwhVDPxGa9ZJIvPJVLfSdrtEzkRSRt3QLHXLKPV58HShMEucBNzBdTmMvFE4N68k1wiV6mE3jZNucv0zASxJDi44fxiKb8NfcwWEJtg/F5MLr2xoPR@6vh@XhwsVEPPo0Hw4tyfahiMr8mkhbdMfggQwKa2ldvg3obu0rq7l41PFwzKbwgS5ZeyqQUWUwyZPnw5t07A1D1wasrxZ3EIm4k96V9A0v2UDCDLQU3EHaFl/ZLPHsOoI@KwmVYBWm2qVMx8kUq/9coE7zI8jCJXzRUxwZmuDC3Zc/cts3tB5RCRcWee/zGAe4ym7kze9ZwuR02Ghveb5r0QAGZWc4hcnQbH2EAD27b0f0KiPWrD3///Atw1DLc0lcKq2oYXj56UuaojMVKryas0Z46OCmWmAbJbTi6O9IA@YRN3YqzZvfTNqkOV6mJAAyZpT47cqBs6kGdJxlpzF4LDg8N/oFrqDsaXY@84fX783H/cjcDVf8q/NxcOZkVooItcGQ/8dmNTRx8pjQvjMDy8UUkpAD8w8u18vG/yItkF4LsUtu/FNpgu6bVqaI38d5th55OBsfv@h8eRGyer5uRsm@e/As "C++ (gcc) ‚Äì Try It Online") - PCRE2 v10.33
Takes its input in unary, as the length of a string of `x`s. Returns its output as the number of ways the regex can match. (The rabbit emoji indicates this output method. It can yield outputs bigger than the input, and is really good at multiplying.)
This is a straight port of the .NET version to the `üêá` output format. It needs to be anchored, so that the only variation in how a match can happen is how many iterations the loop takes, not where in the string it starts. The `*` is changed to `+` because with the former, looping for 0 iterations would still be a match, and would result in a 1-indexed return value.
Moving the `|\b` alternative to the end as `|^x` is a minor speed optimization, at a zero-byte cost. As an added bonus, we can change this to `|^xx` to return \$1\$ (instead of \$2\$) for an input of \$1\$.
For PCRE1, and PCRE2 before v10.35, the atomic group is not needed even with `üêá`-output, because those versions automatically atomicize groups that contain a nested backreference (in this case, `\1`).
# Regex `üêá` (Perl / PCRE), 23 bytes
```
^(\2?+(\1)|^x)+|^x|^xxx
```
[Try it online!](https://tio.run/##HY1NCsIwEIWvEsJQElJqq7ixjkWqW1cuiyEtCoVqS3AR@@PSA3hELxJHYXiPx/fBdGfbLP31wcCmbGjayjQMZilNXO@2x@1mYpfWCjAYh1BiEkKNMeF6jYsldYVgQqJQElYIFQlKyQFy0gR33IGR@JyJbAVWiiwblII8jCf5e9IHQWfr250XN55Cj0nK/puBiTj7vN6MR5CTOBKatN4fdlr7kyjmmRJFIseTk4qCzjnvvw "Perl 5 ‚Äì Try It Online") - Perl v5.28.2 / [Attempt This Online!](https://ato.pxeger.com/run?1=LY09CsJAEIWvsiyD7LJRE0UQ4xgk2lpZBsMaFALxh0VhNcbSA9jaWGhp7VlsPYmjBob3eHwfzOW2npns-nosdgyMz_JsleiMQd2nid1Bf9zvFWy-MgI0ug5M0XMgRZdw2sVmizpB0A5RmBJWCAkJSskcQtIEt9yClnisi6ADRoogyJWC0HEL-X2yr1TWJl1ueLTkPuzR89lvM9A1zt6nM-M1CEk8ECrieDgaxPF9u5lX28-JiBqBEpEnDxMrFQWdtX96LavsDw "Perl - Attempt This Online") - Perl v5.36+  
[Try it online!](https://tio.run/##dVNtb9owEP7Or7hmarGJW0HRpomQVl3XaR9YOyEqbQIaBeOEqMGJ7GTQt6/7AfuJ@yFjlzihdC9RCOfz3XN3z2PzND0MOd@8iiSP87mAfsqVOFqcNPjCV@Cl4ym4MLTerVa3s27@9e7uy2jxZrUgmxsyOT61yaRDH2/W1MYPvuv1hv4ZajFopa6X2h2n8VxGZ/MoKersulQkw5e@KEGv8Jd/x500IplBimbmCaUSRXgidQZl362l0NoPBX3AOr0exwDo96HyFmbpF3IeO6BElisJHeepkUsdhVLMIU5kaD6@1CuhnLLa8s7jfhwneUYKmuqFN4sTfgstTuHBhNv2FraNsGWuH0mCAQ3AJx3jELGQJKWHnanbdsA0ZEaDlLsWOe1ZDlq2m5o/i5LTc/ztUfTnCNk99jJIiuQCP0SjxN4FimSaZ0W6EtBSwoFdjpCUNFMmWwmdx5mxCzaDQIuMAQ6HXYbZwuwk3wTPEjXuTk0pRHXBMJEs0ygWSMsR97A4oQw@nw8vvPdXo7PBAB7N6nr04S2DA1PZGHWpNjWYUQBkTwla8xeUEgcEx8JoBlYBVPaowMeWynTYn/dgX08kHrYdTFOnAt5VDNt@1tJsB3iCihl9t81mbodxdo9WVNLbd7uvkTvXZ747YzPb5Syy7VrMuut7Csh2wS1pTmSTOnDvdhyo@rf25/Dz@w/ADn3cMucE@6hUKx4ji0anFCuzGvt2Z@rgwV3iQEQzaK6bBkCP/am7k2wUrPUQa8GJEgwurwcDBpjoI8XlW4nIoEudF/0bhH4bDg5qtD3X6HYxHF4NvcurT2ej8490m7U9brzgFG@VdVHoYj3jiliL/4dXJNTXMYhzvfjHRNWUT41S9Z6RSwmBHdPtPatOcONp84sHsR/qzWFcUPEb "C++ (gcc) ‚Äì Try It Online") - PCRE1  
[Try it online!](https://tio.run/##hVXvbuJGEP/OU0x8arIL5gpEd4owTpQSpES6IyeOqNcjnLWs12CdsS17fZC0@doH6CP2QUrHuws4IVUtMLOzM7@dP78deJo255xv3vgiCGMBn/qjQcfr314NvLvhzdj79eZqfA1ntTdhzKPCF9BLeSY6bxfnNb5gGXjpZAoujKxfVqvvs9Pit4eHL@PF@9WCbL6R@85Fg9y36R/f1rSBL/ys1xv60tSyoZ66XtpoO5VzcpmF8bw8aK8LE9QKtjw/sDuvhbGEFEXpiSxLMsKTOJeggqwvRZ6zuaDwey79bpejBfR6YNSlqPQi9iMHMiGLLIa283SAWa554gsbZkkSQeIGLMpLWHWMgZt03r2fOjXAJwyAqHp5c2EwPGNFNA7RBb/rX1@OzurUbNqQh48iCcgu8J@3moo9pVSdUj4kgQudBE8KCV3YJUrL9CzlBiqCLlgvklfOloVe1n1s0V09gqjIFzqTXVFqT7UizsN5LHyIkniuXyzOVyJzVMGWDx5nUYRhmNzNyptFCf8OdW7DjyT0oe4zybB2ZZFKEVwXSLlTp8d7DGqwG41dZ1qmM0sWxgQBVIDpBIkQiZiktNmeui1Hp6DZASl3LXLRtRyUGm6qfyxKLvr4PaKoLxDxtONJbCr6lvBzFBR0FSiM00KW7ioxbCHUM7FdL5nkC0/lUt/LGi0TeRFJW7fAMffs883XgdIEQS5wE/PFFOZy8cygnvwQXKKX6QTet@35yzSMBDGk@PxpPKIpf8s9DJZQ22B8HYxuvfFg9PFmeDkeXG3Vgy/jwfCqXB@rmMyviaRF9ww@ypCApvbV26Dexq6SuntQDQ/XTAovyJKllzIpRRaTDFk@vPvwwQBUffDqSrGWWMSt5L62b2DJAQpmsKPgFsKu8NJ@jWcvAfRRUbgMqyDNNnUqRr5I5f8aZYIXWR4m8auG6tjADBfmtuyZ27a5/YhSqKjYc0/fOcBdZjN3Zs8aLrfDRmPL@22THikgM8s5RE7u4xMM4NFtO7pfAbF@8uHvP/8CHLUMt/SVwqoahpePnpQ5KmOx0qsJa7SnDk6KJaZBchtO1icaIJ@wqVtx1ux@3ibV4So1EYAhs9RnTw6UTT2o8ywjjdlrwfGxwT9yDXVHo9uRN7z9eDnuX@9noOpfhZ/bKyezQlSwBY7sZz77sYmDz5TmlRFYPr6IhBSA/3m5Vj79F3mR7EKQfWqHl0Ib7Na0OlX0Jt673dDTyeD43fzDg4jN800zUvbNs38B "C++ (gcc) ‚Äì Try It Online") - PCRE2 v10.33 / [Attempt This Online!](https://ato.pxeger.com/run?1=hVXNbttGED4W0FOMGdTelahUkpHAEEULjizABhI5YGQ0jawQ1HIpEaFIglxGshtf8wC99pJLjzn3Wdpjn6TD3ZVEWy5K8Gd2dubbnZlvh79_Z2lU5OXjzhn7PjGaUcoy3mmeGNO_nGc-D8KYw9uBM-y4g6vzoXs9uhy7P1-ejy_gpPYsjFlU-Bx60un54rTGFl4GbjqZgg2O8Wq1-jQ7Ln65vX0_XrxcLcgfhQiaJ39-JDedfoPctOmXj2vawBfe67Wa_fuHPn3saJhQT203bbStyqq5yMJ4Xi6704UJarm3PN2zO62FsYAUReHyLEsywpI4FyC3XF_yPPfmnMKvufC7XYYW0OuBVpei1PPYjyzIuCiyGNrW_R5mOWaJz02YJUkEiR14UV7CymU03KTz4uXUqgFeYQBEZs-dc43haiuicIhK__Xg4sw5qVM9aUIe3vEkINuN_7TRVOwppXKV8iIJ9FUQLCkEdGEbKC3DM6QbyB10wXgUvHQ2DPQybmKDbvMRIHUWKpJtUmr3tSLOw3nMfYiSeK5eXpyveGbJhC1vXeZFEW5Dx65H7ixK2CeoMxM-J6EPdd8THuauTFIpgm0DKWfq9HCHQTV2o7GtTEtXZumFMUEAucF0gkSIeExS2mxP7ZalQlDsgJTZBul3DQulhp2qj0FJf4DPAUV9gYjHHVdgUdG3hJ-jIKGrQGGcFqJ0l4FhCaGe8c146Qm2cGUs9Z2s0DKeF5EwVQksfereXX4YSk0Q5BwnMV4MYS4WDwzqyWfOBHrpSuDp26y_TMOIE02Kd2_HDk3Zc-biZgk1NcaHoXPljofOm8vR2Xh4vlEP34-Ho_NyfCj3pL96Jy26Y_BBhgTUua-eBvnWdpXQ7b1suDj2BHeDLFm6qScEz2KSIctH169fa4CqDx5dwdcCk7iR7KfmNSzZQ8EIthTcQJgVXppP8ewxgFoqCpdhFaTZplbFyOep-F-jjLMiy8MkftJQLhvo5uLZLXNmt01m3qEUSir27OMXFjDbMz17Zs4aNjPDRmPD-02R7iggM8s-RI5u4iPcwJ3dtlS9AmL86MM_X38DbLUeTqkjhVnVDC8v1SlzVMZ8pUYTr9GeWtgplhgGyU04Wh8pgHziTe2Ks2L3wzLJClepiQAeMkveO3KgrPNBrQcRKcxeCw4PNf6BranrOFeOO7p6czYeXOx6oKxfhZ-bIyeyglewObbsBz67tomNT6fmiRZYXj6PuOCAf8BcKe__i7xIds7JLrT9Q6EMtmNa7SpqEs_dtumpYLD9qv_ot2_q-y8 "C++ (GCC) - Attempt This Online") - PCRE2 v10.40+
[Try it online!](https://tio.run/##hVXvbuJGEP/OU0x8arIL5gpcG0UYJ0oJUiLdkRNH1OsRzlrWa7DO2Ja9PkjafO0D9BH7IKXj3QWckKoWmNnZmd/On98OPE2bc843b3wRhLGAj/3RoOP1b68G3t3wZuz9enM1voaz2psw5lHhC@ilPBOdt4vzGl@wDLx0MgUXRtYvq9W32bvit4eHz@PF6WpBNl/JfeeiQe7b9I@va9rAF37W6w19aWrZUE9dL220nco5uczCeF4etNeFCWoFW54f2J3XwlhCiqL0RJYlGeFJnEtQQdaXIs/ZXFD4PZd@t8vRAno9MOpSVHoR@5EDmZBFFkPbeTrALNc88YUNsySJIHEDFuUlrDrGwE06P59OnRrgEwZAVL28uTAYnrEiGofogt/1ry9HZ3VqNm3Iw0eRBGQX@I9bTcWeUqpOKR@SwIVOgieFhC7sEqVlepZyAxVBF6wXyStny0Iv6z626K4eQVTkC53Jrii1p1oR5@E8Fj5ESTzXLxbnK5E5qmDLB4@zKMIwTO5m5c2ihH@DOrfhexL6UPeZZFi7skilCK4LpNyp0@M9BjXYjcauMy3TmSULY4IAKsB0gkSIRExS2mxP3ZajU9DsgJS7FrnoWg5KDTfVPxYlF338HlHUF4j4ruNJbCr6lvBzFBR0FSiM00KW7ioxbCHUM7FdL5nkC0/lUt/LGi0TeRFJW7fAMffs082XgdIEQS5wE/PFFOZy8cygnnwXXKKX6QTet@35yzSMBDGk@PRxPKIpf8s9DJZQ22B8GYxuvfFg9OFmeDkeXG3Vg8/jwfCqXB@rmMyviaRF9ww@ypCApvbV26Dexq6SuntQDQ/XTAovyJKllzIpRRaTDFk@vHv/3gBUffDqSrGWWMSt5L62b2DJAQpmsKPgFsKu8NJ@jWcvAfRRUbgMqyDNNnUqRr5I5f8aZYIXWR4m8auG6tjADBfmtuyZ27a5/YhSqKjYc386dYC7zGbuzJ41XG6HjcaW99smPVJAZpZziJzcxycYwKPbdnS/AmL94MPff/4FOGoZbukrhVU1DC8fPSlzVMZipVcT1mhPHZwUS0yD5DacrE80QD5hU7firNn9vE2qw1VqIgBDZqnPnhwom3pQ51lGGrPXguNjg3/kGuqORrcjb3j74XLcv97PQNW/Cj@3V05mhahgCxzZz3z2YxMHnynNKyOwfHwRCSkA//NyrXz6L/Ii2YUg@9QOL4U22K1pdaroTbx3u6Gnk8Hxu/mHBxGb55tmpOybZ/8C "C++ (gcc) ‚Äì Try It Online") - PCRE2 - every Fibonacci number up to \$F\_{46}\$ in under 20 seconds
Instead of atomicizing the whole loop, as `^((?>\2?(\1)|x$|^x|\b))+`, we move all choices out of the loop, so there's only one thing it can do at any iteration. This saves 1 byte.
As in the PCRE1 version, we can change `|^x` to `|^xx` to return \$1\$ (instead of \$2\$) for an input of \$1\$.
An alternative 23 byte option would be `^(\2?+(\1)|x$|^x)+|^xxx`, but that'd be ever-so-slightly slower due to having an extra choice inside the loop.
# Regex (.NET), ~~33~~ 29 bytes
```
(?=(^(x)|\3?(\1)|)*)(?<-1>x)*
```
[Try it online!](https://tio.run/##RY5NboMwEIX3nGKERsIDBQHdxXWJ1HVPkKSSIQ5YAowMFSg/2x6gR@xFqNuqymzm6XuL9w1mVnZsVNuuaMXOqloth82mVzPbBisrBHtjC133jwXbZ3SlkFjxFGfPC4VrsH3wX0w36FYdfeJ4Fin3TsYyZChdxlJkHLVIiQPquFWQ5z8pigguHrjDDgSgTV7lVDVqZMEShCiJ/5b6xPBMl9nqScWNGaebW8g43AHEvXGmre4V@Cjh6@MT3HaX1Na8D@MuPSSt6uupie4s/2fk/ylUAqWzkgJL98pIYMW92/oN "PowerShell ‚Äì Try It Online")
Returns its output as the sum of the lengths of the match (group `\0`) and group `\2`. It is done as a sum because for inputs \$n=1,2,3\$ the Fibonacci index is \$n+1\$ and would not fit in a single capture group.
Group `\2`, which is `(x)` in this regex, is captured as \$1\$ iff the loop takes at least one iteration, which happens for all \$n>0\$. The loop count itself is also given an extra increment, as in the **23 byte** version above, by the addition of an empty alternative `|` inside the loop. This will result in a zero-width match being taken at the end, regardless of input; it even happens for \$n=0\$, but that doesn't matter, because the `(?<-1>x)*` will not have room to pop its capture, and the return match will be \$0\$ anyway.
Note that this regex would actually *not* be made shorter by returning its output as the sum of the lengths of `\0`, `\3`, and `\3`, as the shortest way I can think of to do that takes **34 bytes**:
```
(?=((?>\2?)(\1)|^x)*(x))?(?<-1>x)*
```
[Try it online!](https://tio.run/##RY5BboMwEEX3nMJCI2FDQUB3cR1H6ronSFLJkAlYMhgZKlDSbHuAHrEXoW6rKrOZP28W/w12Rje2aMwKTuwdNrgcN5seZ7qLVioFpXJ7KCWjh4K9vy4spgtjksqntNj6a412D@Gz7QZt8BQyDheR8@BsHQUKymeoRMFBi5xxAjo1SMryJyUJI9eA@IGOCAIue1FT3eJIoyWKQTH@@9RnChd2nZ2eMG3tON18Q8HJHZC0t17X6B5JCIp8fXwS391ljbNvw7jPj5nBvpna5M4e/1lcsvBPohagvJcSUPlVJQJqHtzWbw "PowerShell ‚Äì Try It Online")
**38 byte** version that matches iff the input is a Fibonacci number:
```
^(?=(^(x)|(?>\3?)(\1)|)*x$|$)(?<-1>x)*
```
[Try it online!](https://tio.run/##RY9BboMwEEWvYlkjYUONINmFOETquicgRELUAUuOjYwRKMC2B@gRexEKraIs35/Rm/mN6YVta6HUApZnVlRiyA8HLXpy9pYrSTm5koFOJD1d9ikll5hO1B9gAkrSI4tPA/UX7/yG3829kUp8YprAg0fJzVhRlDUBhaRGIHXTOTpCwUGxtlHSYYYTeSNQhKXptGPKod22EHAosiifVwEBzTOpXf6XJKCZEk@ONw4COm6OOwcbfhSurEVLvMHzQdP/yYOOvZVOsNq0bl4/i5MXI6bN2lRJLRAGjX6@vhGstrCypmva9WaohK5cHbyy3TOjeJ7nJWLxPop@AQ "PowerShell ‚Äì Try It Online")
# Regex (Perl / PCRE), 31 bytes
```
((?=(\2?x))(^x|\4?+(\3)))*(x|^)
```
[Try it online!](https://tio.run/##LYzLisJAEEX3fkUhhamyRWOPbmzLIDhbVy6DIQk@AjFK66LFx9IP8BPnR2JHZnMPBy7ntLHluD5cAa2BW3nM0xJwYLzKdDFfzWeP1vZoCc8S9jBtJpNhDwsJ/aeYykg3VIpvgLlg6i0VzDwyJZibFgAFLnCYszwHaJv0udM52aK6tOOqbXx5aODrvtAP4O/1hqBPhDoqN9Xuskc9CVnRv4y5q9k8kuR3uUiSmigSinXkmGnt7vEoUhT/MHOX3H3Ndf0B "Perl 5 ‚Äì Try It Online") - Perl  
[Try it online!](https://tio.run/##XY/BasMwDIbvfQoRBJEak7bpBgPX5LTBYKdd59akxm0CSWrcHALrrnuAPeJeJHPYYbCD@PUL6eOXr/20K33tAQMoSFYJ5OCDO5vgfFtZR@kqX5bG1FU7GHvpfNO6oEmz1K@rayogjXWKQ3N280I/uH64kjFPzy@PxrCADUdkBMvF6RIIK7UWeFQbgY1aS8Bmp7YPs2YZwzugVVhFWyk8RjlmCq1cwG@mrhpsTRjEdQhzQFcNlI6pQMsCO5bQnAgbdra@JLpPJMxdROYJfH9@QZJTPGxdT9i9FXvO/tz9npcFy49/jxLLiahUpItyZKbDeNN3ZUZ6y8xLGm8HnqYf "PHP ‚Äì Try It Online") - PCRE
Returns its output as the sum of the lengths of groups `\2`, `\5`, and `\5`. The regex saves 3 bytes just by using a possessive quantifier, replacing `(?>\4?)` with `\4?+`.
The Fibonacci index minus \$2\$ is built up in `\2` using the expression `(?=(\2?x))`. The first time this is hit, the `\2?` will evaluate to zero because `\2` isn't set yet, and `\2` will be given a value of \$1\$. On every subsequent iteration, it will be incremented. This is done in a lookahead to avoid influencing the running total Fibonacci match, and is safe because at every step, the index will be less than the amount added to the full match.
The `(x|^)` at the end serves to let `\5`\$=1\$ in all cases except \$n=0\$.
This regex does not work under Java; group `\2` just captures \$1\$ and stays there. This may be due to a bug in Java's regex engine.
**33 byte** version that matches iff the input is a Fibonacci number:
```
^((?=(\2?x))(^x|\4?+(\3)))*(x|^)$
```
[Try it online!](https://tio.run/##RU7BToNAFLz3KzbNS3dfgRZQEtNlC03q1ZM3KZtqqG6yUgRMMHQ9@gF@oj@CW9T4Di9vJjNvpipqHQ3PbwRqTnp9fNhrAktuoYi3m9vN2kwOx5pBI3werzn2RB0swr6qVdmSaVZOuSGpFk2lVcuoR93m9b5prUW6XuAGWLycRck/61seVyCRn381NnFfpzoOsU/1XbATdvs7biaEjMnqlwAVi1FgL8fB3noZ7WgHCsX7Euol9tDMZmOvsZbtHPCfmqAWlHx9fBK6YAzCRBflY/sE4cpHh0H0hyOL5yFyY4yU1zdbKYecsUSwLEw6RJZ3p@wycVh2gYhz1p1yhGHwvSvfzjc "Perl 5 ‚Äì Try It Online") - Perl  
[Try it online!](https://tio.run/##XVDBSsNAEL37FUNYyEyTpmm1F7chFxUK4kG9Ne1S47YpJJslSSHS9uoH@In@SJwURejCLjPz3puZtzaz3Sy2mQVRQQTOyIEAbKW3qtI2X6ca3VEwiJXK1nmj0rKwu1xXCSYkk@dR7frg8t1wUW11TzCNNk2NSj3MH@@VIh/GxC25sbzalBWKXRRKkUcbptf48no3fyJJB9htUOSLuqlybTii4XgZRU5iHGJyvX9jhMt@6A/H1Ot1a/PyXaMzdHymS9an5d40vXY2YdGCG/AbLuUVwHmy@c2FmUVnnCPPIx4NeLZcrJs0Q1H5PKz3r9cNuq3rC0O@KIjg0G@5I51mZb@aBHYzltDnIEzgwPfnFzgBoi5s84GiWEyWFIe3f7bOOXn/8PQC5pwGE5In3vl08elIslshxhEmk7glwlV7TG5iD5NrYhW2xxWJrguH05DPDw "PHP ‚Äì Try It Online") - PCRE
If the output specification must be simplified to sum only two groups, this would be the shortest way I can think of doing it (**39 bytes**, output is the sum of the lengths of groups `\0` and `\5`):
```
(?=((?=(\2?x))(^x|\4?+(\3)))*(x))?\2?x?
```
[Try it online!](https://tio.run/##HYzLbsJADEX3fIWFLGIzPBIKq8EMSLDtih1poyTiESkENLAIArrsB/CJ/ZEw04Xv1bGtc97actIcb4BWw7085WkJONQOZbpcrBezZ2t3soQXCXuY@sgk6mEhofsppjIe@VaK74C5YOooFcxcZUow1y0ACuqgxpzlZ4jWqy@dztkW1bUdV23tzJGGf3aGQQB/vy8IBkRztQm/@vO@S1blttpfDzhh/UyS1ecySRoyQn7ikamZ6bt@xGOjKP5g5i65lfEX0zRv "Perl 5 ‚Äì Try It Online") - Perl  
[Try it online!](https://tio.run/##XU9BTsMwELz3FatopawbK00pHMC1fAIJiRNXApZruU2kJLVcH4qAKw/giXwk2OKAxGE1O7s7o1nf@XmrfOcBA0goVgXU4IM76OD8YKyjclUvldadGaK2x9H3gwsttUy0j6tTyaFMtU9DfXD5YIpuiifS@u7@4VZrxmHNkmUyFov9MRAa2XDcyTXHXjYCsN/KzXXGqmLwBmglmkSNxF2CXSXRigX8ZhpNtB1h4KcYckBnIpXnkqNlHEcmoN8T9szZ7li0UyEgd8myLuD78wuKmpJwcBPh@NQ8s4rc6ONrZlfPTDU3f9vEGRMf//4mJmZSknK1F@rMGL2c39tLVVG7SYIlpZHKGzXPPw "PHP ‚Äì Try It Online") - PCRE
**42 byte** version that matches iff the input is a Fibonacci number:
```
^(?=((?=(\2?x))(^x|\4?+(\3)))*(x|^)$)\2?x?
```
[Try it online!](https://tio.run/##RU5dT4MwFH3fr2iWZu0VGGVKYla6smS@@uSbjGYapk0qQ8AE0@GjP8Cf6B/Bgibe5N7cc@7HOVVRm3h4eUe45sia0@PBIBxyB0Wy295tN/3seKopbgTjyYaDRfroENiq1mWL5lk55z1KjWgqo1tKAuI3bw9N606UH0R@BMXruCT/WeZ4WGMFfPzVOMVDnZpkBTY199FeuMr2vJ8hNCnrPwLrREwLrvM8sO6Wko50WIP4CHEdgsXNYjH5mmw5zxH/tYn1kqDvzy9ElpSmnnsXpIGr4FEcS1OUT@0zjtcMgPd9r9TN7U6pIadS0DGzlewAaN6dsyvp0ewSAC5od84BwziTw8CCa@biBw "Perl 5 ‚Äì Try It Online") - Perl  
[Try it online!](https://tio.run/##XVDBaoNAEL3nKwZZcCZRo2lz2oiXthAoPbS9xWSxdhMDZhU1ICS59gP6if0ROxtaCl2YZWbnvXnzti7qYZHURQ2igRicqQMB1I3eqUbXZZZrdKfBOFGqyMpO5dWh3pe6STElmT5PW9cDl2PLj2qnLcB02nQtKvWwfLxXijyIiEfyYDnaVg2KfRxKUcZbhrf48nq3fCJJJ9hvUZSrtmtKbTgjP1rHsZMahxjcHt@4w89e6PkRWb7u67J61@j4jsdwyfy8OprOchczJq14AN/hWo4ArsrmpxZmEV/7nE0mxNKAV8uHrMsLFI3HYta/zjp0e9cThjxxIIKT3XJPOi8qu5oEdhNJsDUIEzjw9fEJToC/Ng4sR5O/ar4mkhfe5/LvQ5HksMEkRhvpLOmJcNOf09tkgukNEY2xP29IkO0lwxD685DPNw "PHP ‚Äì Try It Online") - PCRE
[Answer]
# Python, 38 bytes
```
f=lambda n,a=0,b=1:n^a and-~f(n,b,a+b)
```
Test it on [Ideone](http://ideone.com/fAT2fL).
[Answer]
# C, 62 58 bytes
```
g(c,a,b){return c-a?g(c,b,a+b)+1:0;}f(c){return g(c,0,1);}
```
**Detailed**
```
int g(int c, int a, int b)
{
    if (c == a)
    {
        return 0;
    }
    else
    {
        return g(c, b, a+b) + 1;
    }
}
int f(c)
{
    return g(c, 0, 1);
}
```
[Answer]
# Java 7, 70 bytes
```
int c(int n){int a=0,b=1,c=0,t;while(a<n){c++;t=b;b+=a;a=t;}return c;}
```
<https://ideone.com/I4rUC5>
[Answer]
## TSQL, 143 bytes
Input goes in `@n` as in `DECLARE @n INT = 1836311903;`
```
DECLARE @O BIGINT=0;WITH F(R,P,N)AS(SELECT @O,@O,@O+1 UNION ALL SELECT R+1,N,P+N FROM F WHERE N<=@n)SELECT MAX(R)FROM F OPTION(MAXRECURSION 0);
```
[Answer]
## Haskell, 45 bytes
```
f x=round$log(sqrt 5*x+0.9)/log((sqrt 5+1)/2)
```
[Answer]
# [Sesos](https://github.com/DennisMitchell/sesos), 28 bytes
Hexdump:
```
0000000: 16f8be 766ef7 ae6d80 f90bde b563f0 7ded18 3ceffa  ...vn..m.....c.}..<..
0000015: b1c1bb af9f3f ff                                  .....?.
```
[Try it online!](http://sesos.tryitonline.net/#code=c2V0IG51bWluCnNldCBudW1vdXQKZ2V0CmptcApzdWIgMQpmd2QgMQphZGQgMQpmd2QgMQphZGQgMQpyd2QgMgpqbnogICAgO2EgYQpmd2QgNAphZGQgMSAgO2EgYSAwIDEKZndkIDIKYWRkIDEgIDthIGEgMCAxIDAgMQpyd2QgNApqbXAKam1wICAgIDthIGEtYiBiIGMgbgpzdWIgMQpqbnogICAgO2EgMCBiIGMgbgpmd2QgMwphZGQgMQpqbXAKc3ViIDEKZndkIDIKYWRkIDEKcndkIDIKam56ICAgIDthIDAgYiBjIDAgMCBuKzEKcndkIDEKam1wCnN1YiAxCmZ3ZCAxCmFkZCAxCmZ3ZCAxCmFkZCAxCnJ3ZCAyCmpueiAgICA7YSAwIGIgMCBjIGMgbisxCnJ3ZCAxCmptcApzdWIgMQpmd2QgMQpzdWIgMQpmd2QgMgphZGQgMQpyd2QgMwpqbnogICAgO2EgMCAwIC1iIGMgYitjIG4rMQpyd2QgMgpqbXAKc3ViIDEKZndkIDIKYWRkIDEKZndkIDEKYWRkIDEKcndkIDMKam56ICAgIDswIDAgYSBhLWIgYyBiK2MgbisxCmZ3ZCAzCmpuegpmd2QgMwpwdXQ&input=NQ&debug=on)
(Exponential time because in Sesos copying a number needs exponential time.)
Assembly used to generate the binary file:
```
set numin
set numout
get
jmp
sub 1
fwd 1
add 1
fwd 1
add 1
rwd 2
jnz    ;input input
fwd 4
add 1  ;input input 0 1
fwd 2
add 1  ;input input 0 1 0 1
rwd 4
jmp
jmp    ;input input-curr curr next iterations
sub 1
jnz    ;input 0 curr next iterations
fwd 3
add 1
jmp
sub 1
fwd 2
add 1
rwd 2
jnz    ;input 0 curr next 0 0 iterations+1
rwd 1
jmp
sub 1
fwd 1
add 1
fwd 1
add 1
rwd 2
jnz    ;input 0 curr 0 next next iterations+1
rwd 1
jmp
sub 1
fwd 1
sub 1
fwd 2
add 1
rwd 3
jnz    ;input 0 0 -curr next curr+next iterations+1
rwd 2
jmp
sub 1
fwd 2
add 1
fwd 1
add 1
rwd 3
jnz    ;0 0 input input-curr next curr+next iterations+1
fwd 3
jnz
fwd 3
put
```
[Answer]
# Java 8 61 bytes
Same as @dainichi answer only made shorter by using Java 8 lambdas. The answer is a valid rvalue expression.
```
n->{int a=0,b=1,c=0,t;while(a<n){c++;t=b;b+=a;a=t;}return c;}
```
Ungolfed:
```
interface F
{
    int c(int n);
}
public class Main
{
    public static void main(String[] args)
    {
        F f = n->{int a=0,b=1,c=0,t;while(a<n){c++;t=b;b+=a;a=t;}return c;};
    }
}
```
[Answer]
# [Brachylog](https://github.com/JCumin/Brachylog), 14 bytes
```
‚âú‚àß0;1‚ü®t‚â°+‚ü©‚Å±‚Üñ?h
```
[Try it online!](https://tio.run/##AVsApP9icmFjaHlsb2cy/3t3IiAtPiAidz9@4oaw4oKC4bqJfeG1kP/iiZziiKcwOzHin6h04omhK@KfqeKBseKGlj9o//9bMCwyLDMsNSw4LDEzLDE4MzYzMTE5MDNd "Brachylog ‚Äì Try It Online")
Takes input through the output variable and outputs through the input variable.
```
‚âú                 Label the input variable, trying 0, 1, -1, 2...,
  0               then starting with 0
 ‚àß                (which is not necessarily the input variable)
   ;1             paired with 1,
     ‚ü®t‚â° ‚ü©        replace the first element of the pair with the last element
     ‚ü® ‚â°+‚ü©        and the last element of the pair with the sum of the elements
          ‚Å±‚Üñ?     a number of times equal to the input variable,
             h    such that the first element of the pair is the output variable.
```
I'm not entirely sure why `‚âú` is necessary.
[Answer]
# [APL (Dyalog Extended)](https://github.com/abrudz/dyalog-apl-extended), 14 bytes
```
(+.!‚àò‚åΩ‚ç®‚àò‚ç≥¬®‚Ä¶)‚ç≥‚ä¢
```
Explanation soon (TM)
[Try it online!](https://tio.run/##SyzI0U2pTMzJT9dNrShJzUtJTfn/qG@qp/@jtgkG/9OApIa2nuKjjhmPevY@6l0BYvRuPrTiUcMyTSDjUdcikGqgqjQFU1MuGNMIzjL@DwA "APL (Dyalog Extended) ‚Äì Try It Online")
[Answer]
# [Vyxal](https://github.com/Vyxal/Vyxal), ~~6~~ 4 bytes
```
√ûF·∏ü‚Ä∫
```
[Try it Online!](https://vyxal.pythonanywhere.com/#WyJBIiwiIiwiw55G4bif4oC6IiwiIiwiMFxuMVxuMVxuMlxuM1xuNVxuOFxuMTNcbjIxXG4zNFxuNTVcbjg5XG4xNDRcbjIzM1xuMzc3XG42MTBcbjk4N1xuMTU5N1xuMjU4NFxuNDE4MVxuNjc2NVxuMTA5NDZcbjE3NzExXG4yODY1N1xuNDYzNjhcbjc1MDI1XG4xMjEzOTNcbjE5NjQxOFxuMzE3ODExXG41MTQyMjlcbjgzMjA0MFxuMTM0NjI2OVxuMjE3ODMwOVxuMzUyNDU3OFxuNTcwMjg4N1xuOTIyNzQ2NVxuMTQ5MzAzNTJcbjI0MTU3ODE3XG4zOTA4ODE2OVxuNjMyNDU5ODZcbjEwMjMzNDE1NVxuMTY1NTgwMTQxXG4yNjc5MTQyOTZcbjQzMzQ5NDQzN1xuNzAxNDA4NzMzIl0=)
-2 thanks to Deadcode
1 byte longer than it should be just because Vyxal's "Fibonacci sequence" builtin does not start with 0.
[Answer]
# [C89 (clang)](http://clang.llvm.org/), 54 bytes
```
a,b,r;g(f){for(a=r=0,b=1;a<f;++r)b+=a,a=b-a;return r;}
```
[Try it online!](https://tio.run/##XY9RT8MgFIWfx6@4ziwp6a2hq6szjP0SX2hLK0mlC6XGZO63VxgmBp@4fJx7zqEt2lGaYV0lNmj5kPX02k82k8IKho0ouTz1PM8tbXIhUYqmkNwqt1gDlt/WR23acekUnGbX6enp/UyINo44NbvMD6ANQjjV10W1jpIr2YSrVfMyOk42cQABg5dTDy7Wv/fZdtdBcYZd92a2eHeJSi8JS7FA3H0Qv@6c3GL6h9Qm@5x095fnE1iIg28B93IMgdGE7BGqlFQIzyk5IBxSckSoU1L6tZd/6FjVVVm@suBYJ3/wpdcf "C (clang) ‚Äì Try It Online")
[Answer]
# [Japt](https://github.com/ETHproductions/japt), 8 [bytes](https://en.wikipedia.org/wiki/ISO/IEC_8859-1)
```
√¥!gM √®<U
```
[Try it](https://petershaggynoble.github.io/Japt-Interpreter/?v=1.4.6&code=9CFnTSDoPFU&input=MTM)
## Original, 9 bytes
Can handle larger inputs than the version above.
```
nMgV¬∞)¬©√í√ü
```
[Try it](https://petershaggynoble.github.io/Japt-Interpreter/?v=1.4.6&code=bk1nVrApqdLf&input=MTgzNjMxMTkwMw)
[Answer]
# Pyth, 13 bytes
```
J1tf>=Z+~JZZQ
```
[Test suite.](http://pyth.herokuapp.com/?code=J1tf%3E%3DZ%2B~JZZQ&test_suite=1&test_suite_input=0%0A1%0A2%0A3%0A5%0A8%0A13%0A1836311903&debug=0)
Approximation in Python 2:
```
Z=0;J=1;T=1;Q=input()
while not J+Z>Q:
    temp=J
    J=Z
    Z=temp+J
    T += 1
print(T-1)
```
### alternative approach, 18 bytes
```
L?<b2bsyMtBtbs.IyG
```
[Test suite.](http://pyth.herokuapp.com/?code=L%3F%3Cb2bsyMtBtbs.IyG&test_suite=1&test_suite_input=0%0A1%0A2%0A3%0A5%0A8%0A13%0A1836311903&debug=0)
This uses `.I` for inverse.
]