# 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",
"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.