# Category:Jq/fibonacci.jq

The following is slightly more verbose than it need be except for the sake of compatibility with jaq.

```
module {
"name": "fibonacci",
"description": "Fibonacci sequence and Fibonacci coding of positive integers",
"version": "0.0.1",
"homepage": "https://rosettacode.org/w/index.php?title=Category:Jq/fibonacci.jq",
"license": "MIT",
"author": "pkoppstein at gmail dot com",
};
# If $n is a non-negative integer, then
# fibonacci($n) generates the stream of integers F(0), F(1), F(2), ... F($n)
# where F(0) = 0, F(1) = F(2) = 1 and F(i) = F(i-1) + F(i-2) for i>1.
# Thus F(i) == [fibonacci($n)][i] if 0 <= i <= $n
def fibonacci($n):
# input: [f(i-2), f(i-1), countdown]
def fib: (.[0] + .[1]) as $sum
| if .[2] == 0 then $sum
else $sum, ([ .[1], $sum, .[2] - 1 ] | fib)
end;
[-1, 1, $n] | fib;
# Efficient Fibonacci-encoding as an array of 0s and 1s ending in [1,1].
# If n is a positive integer, then n|fibencode is the Fibonacci encoding of n as an array
# such that join("") yields the string representation of the encoding.
# E.g. 11 | fibencode | join("") #=> "001011"
# Note that there is no check that n is a positive integer, and in particular that
# 0 | fibencode #=> [1]
def fibencode:
# `n|fibs` returns an array of Fibonacci numbers [1, 2, 3, ... m] where m <= n.
def fibs:
. as $n
# input: [f(i-2), f(i-1)]
| [1,1]
| [recurse(select(.[1] < $n) | [.[1], add])
| .[1] | select(. <= $n)];
fibs as $fibs
# Traverse $fibs from right to left to avoid calling reverse
| [foreach range($fibs|length -1 ; -1; -1) as $ix ({n: .};
$fibs[$ix] as $fib
| if .n >= $fib then .n -= $fib | .out = 1
else .out = 0
end)
| .out]
| reverse + [1];
# Efficient Fibonacci-decoding of a Fibonacci-encoded number
# as produced by `fibencode` or `fibencode | join("")`.
# Input: a Fibonacci-encoded number as a 0-1 string ending in "11", or
# as the corresponding 0-1 array.
# So "11" | fibdecode #=> 1
def fibdecode:
if type == "string" then explode | map(. - 48) else . end
| length as $n
| . as $x
| reduce fibonacci($n) as $F ({i:-2, ans:0};
if .i < 0 then . else .ans += $F * $x[.i] end
| .i += 1)
| .ans ;
```

*This category currently contains no pages or media.*