[Question]
  [
## Background
We've had challenges before on [Fibonacci
coding](https://en.wikipedia.org/wiki/Fibonacci_coding) and Zeckendorf
representation. These representations follow naturally from [Zeckendorf's
theorem](https://en.wikipedia.org/wiki/Zeckendorf%27s_theorem), which states
that every positive integer can be represented uniquely as the sum of one
or more distinct, non-consecutive Fibonacci numbers. For example:
$$
\begin{aligned}
64 &= 55 + 8 + 1 \\
 &= F\_{10} + F\_6 + F\_2 \\ 
171 &= 144 + 21 + 5 + 1 \\
 &= F\_{12} + F\_8 + F\_5 + F\_2 \\ 
\end{aligned}
$$
where \$F\_i\$ is the \$i\$-th Fibonacci number.
## What is Fibonacci multiplication?
Extending this concept, Donald Knuth defined "circle multiplication" (the Fibonacci product) on two
postive integers \$a\$ and \$b\$ as follows. First assume
$$
\begin{align}
a &= \sum\_{i=0}^n F\_{c\_i} \text{ where } c\_i \ge 2 \\
b &= \sum\_{i=0}^m F\_{d\_i} \text{ where } d\_i \ge 2
\end{align}
$$
Then we define the Fibonacci product like so:
$$
a \circ b = \sum\_{i=0}^n \sum\_{j=0}^m F\_{c\_i + d\_j}
$$
See [Knuth's original
article](http://www.cs.umb.edu/%7Ervetro/vetroBioComp/compression/FIBO/KnuthFibb.pdf)
(pdf) or the [Wikipedia
entry](https://en.wikipedia.org/wiki/Zeckendorf%27s_theorem#Fibonacci_multiplication)
for more.
Here is a worked example from the Wikipedia page:
$$
\begin{align}
2 &= F\_3 \\
4 &= F\_4 + F\_2 \\
2 \circ 4 &= F\_{3 + 4} + F\_{3 + 2} \\
 &= F\_7 + F\_5 \\
 &= 13 + 5 \\
 &= 18
\end{align}
$$
As an interesting aside not directly related to the challenge, it [has been
shown](https://www.sciencedirect.com/science/article/pii/0893965989900785) that
the Fibonacci product:
> 
> can be interpreted as the usual multiplication in a multiplicatively closed subset of the ring \$\mathbb{Z}[\phi]\$ of algebraic integers generated by the "golden ratio".
> 
> 
> 
## Task
Given two positive integers as input, return their Fibonacci product as
defined in the section above.
This is code-golf and standard site rules apply.
## Test Cases
```
1 1 -> 3
1 2 -> 5
1 5 -> 13
2 1 -> 5
2 4 -> 18
4 1 -> 11
4 4 -> 40
4 9 -> 87
7 1 -> 18 
7 2 -> 29
7 9 -> 141
9 9 -> 189
```
  
[Answer]
# [Wolfram Language (Mathematica)](https://www.wolfram.com/wolframscript/), ~~39~~ ~~34~~ 33 bytes
```
1##+{#2,#}.⌊+++{##}2/++√5⌋&
```
[Try it online!](https://tio.run/##y00syUjNTSzJTE78n2b731BZWbta2UhHuVbvUU@XtjaQo1xrpK@t/ahjlumjnm61/4GlmaklDgFFmXkl0cq6dmkODsqxanXByYl5ddVc1YY6hrU6IMoIQpmCKCOIoJGOCYgygfBMYDxLEGUOETSH6DOHCFoCKa7a/wA "Wolfram Language (Mathematica) – Try It Online")
Uses the formula in the [linked Arnoux paper](https://www.sciencedirect.com/science/article/pii/0893965989900785): \$m\circ n=m n+p\_m n+m p\_n\$, where \$p\_x\$ is defined as the integer such that \$p\_x-\frac x\phi\in(\frac1\phi-1,\frac1\phi)\$. A little bit of manipulation gets us \$p\_x=\left\lfloor\frac{x+1}\phi\right\rfloor\$.
```
1##                         m n
   +{#2,#}.                 + (n,m) .
           ⌊+++{##}2/++√5⌋  ⌊(1+(m,n)) / ϕ⌋
```
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), ~~9~~ 8 bytes
A port of [att's answer](https://codegolf.stackexchange.com/a/230974/64121) and -1 byte thanks to them. Takes input as a pair of integers `[a, b]`.
```
‘:ØpḋṚ+P
```
[Try it online!](https://tio.run/##y0rNyan8//9RwwyrwzMKHu7ofrhzlnbA/6N7Drc/alrjBsTu//9HG@oYxuoASSMwaQokjcAiRjomQNIEzDaBsi2BpDlYxBys3hwsYgkkAQ "Jelly – Try It Online")
```
‘          increment each value          [a+1, b+1]
 :Øp       integer divide by phi         [(a+1):phi, (b+1):phi]
    ḋṚ     dot product with the reverse  (a+1):phi×b + (b+1):phi×a
       +P  add the product of the input  (a+1):phi×b + (b+1):phi×a + a×b 
```
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), 18 bytes
```
ŒP‘ÆḞS=ɗƇ¹Ḣ)p/§ÆḞS
```
[Try it online!](https://tio.run/##y0rNyan8///opIBHDTMOtz3cMS/Y9uT0Y@2Hdj7csUizQP/Qcojg////zXUULAE "Jelly – Try It Online")
-1 byte thanks to caird coinheringaahing
---
I have posted a video explanation of this answer and how to approach this problem as well as the mathematical observation below to [my YouTube channel](https://www.youtube.com/channel/UCjWrRy5b2fntu1-u5EiFNtw). You can see the video [here](https://www.youtube.com/watch?v=IRJqGcYsKlc).
---
Assume that there is a sequence of Fibonacci numbers where two are consecutive. Select the largest two such terms and them be \$F\_n\$ and \$F\_{n+1}\$. Then, \$F\_{n+2}\$ cannot be in the sequence because then it would be consecutive with \$F\_{n+1}\$ and thus contradict the definition. Therefore, we replace \$F\_n,F\_{n+1}\$ with \$F\_{n+2}\$ in the sequence and we now have a shorter sequence that sums to the same value.
Keep repeating this process indefinitely, and we can see that the shortest sequence of Fibonacci numbers that sums to \$N\$ has to be the unique one containing no consecutive terms, otherwise we can reduce it to something shorter, which would be a contradiction.
Thus, we only need to find the *shortest* sequence. Here follows the explanation of the Jelly code itself:
```
ŒP‘ÆḞS=ɗƇ¹Ḣ)p/§ÆḞS    Main Link; accept a list [x, y]
           )          For each k of x and y
ŒP                    Take the powerset of [1, 2, ..., k], shortest & lexicographically least first
  ‘                   Add one (now we have the powerset of [2, 3, ..., k + 1])
        Ƈ             Filter; keep terms where
   ÆḞ                 Taking the Nth fibonacci number
     S                and summing
      =               is equal to
         ¹            k itself
          Ḣ           And take the first (thus shortest) such subset
            p/        Take the cartesian product of the two codings
              §       Sum each pair
               ÆḞ     Get the Nth fibonacci number for each
                 S    and sum
```
[Answer]
# [J](http://jsoftware.com/), 70 bytes
```
+/@,@(1{:@F@++/)&(F i.2-/\[(0>.]-(<:@I.>:){[)^:a:~F=:_2&(],+/@{.)&1 2)
```
[Try it online!](https://tio.run/##Tc7RCoIwFAbge5/i0IXb0E23ZupIGQSDoKtuzSIiqW56AKFXN6dONhic8@3843yGDUMdVAoQxJCCGi9lcDifzBAlOtaY90obHUUJCbGBNxM0uTQ4rVlL8V7pI6sV6RtyVXf1M5W6iRC38RjtGQk5CDKQ4Pl4fUFAB3Iud3KseZ7PHaL2oGDuMLdvBCrYeiAsZB5kFrgbES6TeSCnkWIR6UY492SakaknpZViWQ3na6oAj6Z1ROnJFOPS/V2uVJTDHw "J – Try It Online")
* `F=:_2&(],+/@{.)&1 2)` `F_1, F_2 … F_n`.
* `[(0>.]-(<:@I.>:){[)^:a:~` starting with `n`, greedily find the highest Fibonacci number (with binary search with adjusted indices `<:@I.>:`), subtract from `n` and repeat until we hit `0`. Return the intermediate results.
* `F i.2-/\` From the intermediate results get the Fibonacci numbers, and then their indices.
* `…&…` do this for both results, then for both Fibonacci index lists do …
* `1{:@F@++/` addition table, get the last `F_i` for each sum.
* `+/@,@` … and sum it again
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), 25 bytes
```
¹©R‘U;ṖÆḞS>®Ʋ¡¥ƒ“”)p/§ÆḞS
```
[Try it online!](https://tio.run/##y0rNyan8///QzkMrgx41zAi1frhz2uG2hzvmBdsdWnds06GFh5Yem/SoYc6jhrmaBfqHlkPk/v//b66jYAkA "Jelly – Try It Online")
-4 bytes thanks to caird coinheringaahing
Non-brute force answer that should run in \$O(N^2)\$ time. Still trying to figure out how to remove the register usage.
Basically, constructs the Fibonacci coding by starting from an upper bound and counting down, adding in the largest Fibonacci number that can fit each time. Since I am summing the accumulating list each time, and I think the output list is roughly \$O(\log N)\$ in size, I *believe* this is \$O(N \log N)\$, but I'm not sure, so I'll just put down \$O(N^2)\$ for now.
```
¹©R‘U;ṖÆḞS>®Ʋ¡¥ƒ“”)p/§ÆḞS        Main Link (monadic): accept [x, y]
                  )              For each k in [x, y]
¹©                               Save it to the register
  R                              Range; [1, 2, ..., k]
   ‘                             Increment; [2, 3, ..., k + 1]
    U                            Reverse; [k + 1, k, ..., 2]
     ;ṖÆḞS>®Ʋ¡¥ƒ“”               Reduce this list starting from []:
     -========¥                  Last two as a dyad:
     ;                           - append the new value to the list
             ¡                   - then, N times (if statement for boolean values)
       ÆḞS>®Ʋ                      - if the sum of those Fibonacci numbers exceeds the desired value
      Ṗ                            - pop the last addition back off
                   p/            Cartesian product of the results
                     §           Sum of each; get the indexes
                      ÆḞ         Convert to Fibonacci numbers
                        S        Sum
```
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), 22 bytes
```
ŒP‘I’ẠƊƇÆḞS=ɗƇ)p"/§ÆḞ§
```
[Try it online!](https://tio.run/##y0rNyan8///opIBHDTM8HzXMfLhrwbGuY@2H2x7umBdse3L6sXbNAiX9Q8vBAoeW/3@4Y9PDHYuNwh41rTnc/nDHoqOTHu6cwfVw95bD7UChyP//DRUMFXTtFIy5DBWMQAxTIMMUxDA05jKCyJkCGSZgIQsuE4iQoSGQBRYzMQCyLEEsC3Muc6ishQKQCTbOyBLIAksbmhhyWUKZFpYA "Jelly – Try It Online")
This feels grossly long.
Returns `[x]` where `x` is the expected output. This is [allowed by default](https://codegolf.meta.stackexchange.com/questions/2447/default-for-code-golf-input-output-methods/11884#11884)
-1 byte thanks to [hyper-neutrino](https://codegolf.stackexchange.com/users/68942/hyper-neutrino)
---
## How it works
```
ŒP‘I’ẠƊƇÆḞS=ɗƇ)p"/§ÆḞ§ - Main link. Takes [a, b] on the left
              )        - For each input:
ŒP                     -   Cast to range, then powerset
  ‘                    -   Increment each one
      ƊƇ               -   Keep those for which the following is true:
   I                   -     Forward differences
    ’                  -     Decrement
     Ạ                       Are all non-zero?
                             This removes all lists with any consecutive indices
            ɗƇ         -   Keep those for which the following is true:
        ÆḞ             -     Convert each index to its Fibonacci number
          S=           -     Does the sum equal the input?
               p"/     - Get the Cartesian product of the indices
                          The " (vectorise) quick allows us to avoid extracting the
                          first element, instead we operate with everything
                          wrapped to an additional depth
                  §    - Sums
                   ÆḞ  - Fibonacci number of each
                     § - Sum
```
[Answer]
# [Vyxal](https://github.com/Lyxal/Vyxal) `as`, 11 bytes
```
›5√›½ḭṘ*⁰ΠJ
```
[Try it Online!](https://lyxal.pythonanywhere.com?flags=as&code=%E2%80%BA5%E2%88%9A%E2%80%BA%C2%BD%E1%B8%AD%E1%B9%98*%E2%81%B0%CE%A0J&inputs=1%0A2&header=&footer=)
A port of the other ones. No, there isn't a phi builtin.
[Answer]
# [Ruby](https://www.ruby-lang.org/), 56 bytes
```
->a,b{g=->z{(2*z/=1+5**0.5).to_i};a*b+a*g[b+1]+b*g[a+1]}
```
[Try it online!](https://tio.run/##KypNqvyfZvtf1y5RJ6k63VbXrqpaw0irSt/WUNtUS8tAz1RTryQ/PrPWOlErSTtRKz06SdswVjsJyEgEMmr/FyikRRvqGMZygRiWOpax/wE "Ruby – Try It Online")
Same formula as almost everybody else.
[Answer]
# JavaScript (ES6), ~~98~~ 90 bytes
A full implementation.
Expects `(a)(b)`.
```
a=>g=(x,k,n)=>(F=n=>n<3||F(n-1)+F(n-2))(-~n)>x?x&&(k?F(k+n):g(a,n))+g(x-F(n),k):g(x,k,-~n)
```
[Try it online!](https://tio.run/##Zc9BCoMwEAXQfU/hSmZQaxMVTWniznuIVWmVpNRSXEivnioGBQOBQN78z@RZfsuhej9en0Cqe60brksuWg6j3/kSuYCCSy7kLZqmAmRA0FsuigjBT6IY89F1ocsL6DyJ1xbKOYVeC2Mwz6HfLW9L1zKtKyUH1dfnXrXQAMH5oBOGTnSyhK6S2JKsQo4hutUltsQmlB0o3kKE2GRS8cUmtlKWHijdCzPHNvMtymwyjSQ@LsJ2y5j@Aw "JavaScript (Node.js) – Try It Online")
### Commented
The helper function \$F\$ just computes the \$n\$-th Fibonacci term, 1-indexed.
```
F = n => n < 3 || F(n - 1) + F(n - 2)
```
Main function:
```
a =>               // outer function taking a
g = (              // the inner function g first takes x = b and later
  x,               // invokes itself for the 2nd pass with x = a
  k,               // k is undefined during the 1st pass, then set to
                   // a positive integer
  n                // n is the Fibonacci term index
) =>               //
  F(-~n) > x ?     // if F(n + 1) is greater than x:
    x && (         //   stop if x = 0, otherwise:
      k ?          //     if k is defined:
        F(k + n)   //       compute F(k + n)
      :            //     else:
        g(a, n)    //       process the 2nd pass with x = a and k = n
    ) +            //
    g(x - F(n), k) //   add the result of a recursive call with F(n)
                   //   subtracted from x and k unchanged
  :                // else:
    g(x, k, -~n)   //   try again with n + 1
```
---
# JavaScript (ES7), 42 bytes
Using [@att's closed-form formula](https://codegolf.stackexchange.com/a/230974/58563) is, obviously, significantly shorter.
Expects `(a)(b)`.
```
a=>b=>~~(p=.5+5**.5/2,b-~b/p)*a-~~(~a/p)*b
```
[Try it online!](https://tio.run/##Zc9BCsMgEAXQfU@RpbE1VqtEF@YumialJURpSpde3aZEEnBgFgOP/5l52a9d@vczfMjs70MaTbKmc6aLEQXTyLPEuJGUXxyJjoYaW7JKtP/Vpd7Pi5@GZvIPNCJWr1NXlFa3ExC@iYQiN2FliO91EorIIVWQ2EOMQcopcYWkN1JtQe1RqCpo@S2uIeVGJspD9GFKpx8 "JavaScript (Node.js) – Try It Online")
[Answer]
# [Japt](https://github.com/ETHproductions/japt), ~~19~~ 18 [bytes](https://en.wikipedia.org/wiki/ISO/IEC_8859-1)
Far too long but just can't seem to do any better. There's gotta be a shorter way to get Phi!
```
×+UËÄ z5¬Ä ÑÃx_*Uo
```
[Try it](https://petershaggynoble.github.io/Japt-Interpreter/?v=1.4.6&code=1ytVy8QgejWsxCDRw3hfKlVv&input=WzcgOV0)
[Answer]
# [Retina 0.8.2](https://github.com/m-ender/retina/wiki/The-Language/a950ad7d925ec9316e3e2fb2cf5d49fd15d23e3d), 123 bytes
```
.+
$*
(\G1|(?>\2?)(\1))*1
$#1$*01¶
%)+`^(.*).(.*¶)(\1.)¶
$3$2
+`^(0*)1(.*¶¶)(.+)
0$1$2$3¶00$1$3
3A`
0?
;
+`;(1*);1
1;1$1;
1
```
[Try it online!](https://tio.run/##HYoxDsIwDEX3fw1cKU6jKE6KqioSFVMPwFqhMDCwMCBGztUD9GLB6WD/Z7//eX5f70ftzK04mKVU34MszLrIz8yXNc5sVmG2AjoJ2SD7ho77cjfeste1b63hWf@UKKKpYFkO1aTvGYGEIqV9C40S0rUgzMjazkYsZ4FkIcmQWsXp5aLOGVE5ugGD5nDkhFF5VD8qT276Aw "Retina 0.8.2 – Try It Online") Takes newline-separated inputs but link is to test suite that splits on comma for convenience. Explanation:
```
.+
$*
(\G1|(?>\2?)(\1))*1
$#1$*01¶
+`^(.*).(.*¶)(\1.)¶
$3$2
```
Convert the input to its Zeckendorf representation. This is based on my answer to [Fibonacci Encoding](https://codegolf.stackexchange.com/questions/222676) but without the trailing `1` of course.
```
%)`
```
Apply the above to each input separately.
```
+`^(0*)1(.*¶¶)(.+)
0$1$2$3¶00$1$3
3A`
```
Long multiply the two inputs. (The final addition is implicitly accomplished after the conversion back to decimal.) Additionally, since the Zeckendorf representation starts at F₂, prefix an additional two zeros to adjust for the 2-indexing.
```
0?
;
+`;(1*);1
1;1$1;
```
Convert each Zeckendorf representation back to unary. This is based on my answer to [Converting a number from Zeckendorf Representation to Decimal](https://codegolf.stackexchange.com/questions/173601).
```
1
```
Sum the unary values and convert to decimal.
[Answer]
# [C (gcc)](https://gcc.gnu.org/), ~~77~~ ~~62~~ 53 bytes
```
g(m){m=~m*(1-sqrt(5))/2;}f(m,n){m=m*n+g(m)*n+g(n)*m;}
```
[Try it online!](https://tio.run/##hY/LTsMwEEXXyVeMipDsPKDOgyZKWz6DBVQoch5Yip0Su2yq8OmEcbwBsUAaec7cOyNd87jnfLkRig@XpoW9No0Y796OS08kvcrDpwwIi/X7ZEhO6X1SzR2RkbKWDFRot9amaCCreRHKgGm1eeW1bvXzCQ5w9T0WAVYarZREkDvKUbZistq5owyHAjFbRcYc2to6LCModog7t1A4xMukdIgLLLN3peOi9OfKt8lkLRT5GEVDbapunMhFadGrtgFrC0y7rbDtIX2wPTxASn3PO09od2Rz2wBWfLTvIz4vahP9/K44/R4hBPZXSlDqyH9nlFb@vHzxbqh7vcRPaoyFPA@CCxNjmm8 "C (gcc) – Try It Online")
-15 bytes thanks to [ovs](https://codegolf.stackexchange.com/questions/230967/compute-the-fibonacci-product#comment529696_231040)  
-9 bytes thanks to [att](https://codegolf.stackexchange.com/questions/230967/compute-the-fibonacci-product/231040?noredirect=1#comment529745_231040)
[Original submission:](https://tio.run/##hY/dasMwDIWv66cQLQM7cbc6P2tC2u41ClsZJXY6w@JssbObkmfP5HgXG70YCOnTkQ5I9fpS19NKm/p9kAp21knd3b8dppVUjTYKjrTlhkFMtXGM0jYWLEoeqP3sHc0ZdiwypJmXrr1yQ2@gjcyP7UgNb1k1TmgGp6x7rc9W2ecT7OFKFoIDRspnSjjkgXKUvZjM4zxQhk2BmM2iEAF9bAKWHIot4jYsFAHRmZQBcUFk3lcGLkoyVsRf1p61oV@dlsxf1XQ9HYzVF6Mk@LHGazcVlh2kj77Ge0gZWSw@ehw3dHknAWN98PkJ04tZ8t/v6tPfFmIQt1KCUkP/szFWkXH6Bg "C (gcc) – Try It Online")
```
#define X(m,n) +(int)((m+1)*2/(sqrt(5)+1))*n
f(m,n){return m*n X(m,n)X(n,m);}
```
Basically an adaptation of [att's excellent answer](https://codegolf.stackexchange.com/a/230974/56453).
Thanks to the power of ~~the preprocessor~~ *undefined behavior* this is way shorter than an equivalent Java version I tried.
[Answer]
# Python 2, ~~68~~ *61* bytes
-7 bytes thanks to ovs, and based on att's [answer](https://codegolf.stackexchange.com/a/230974/83082):
```
def f(x,y):p=lambda a:~a*(1-5**.5)//2;print x*y+x*p(x)+y*p(y)
```
[Try it online!](https://tio.run/##K6gsycjPM/r/PyU1TSFNo0KnUtOqwDYnMTcpJVEh0aouUUvDUNdUS0vPVFNf38i6oCgzr0ShQqtSu0KrQKNCU7sSSFVq/k/TsNSx1OQCURYgyljHVPM/AA)
As my first golfing experience with python, there might be room for improvement. Suggestions are welcome.
[Answer]
# [MathGolf](https://github.com/maxbergmark/mathgolf/blob/master/math_golf.txt), 16 [bytes](https://github.com/maxbergmark/mathgolf/blob/master/code_page.py)
```
ê)φ/iêx^~êßmÅε*Σ
```
MathGolf has a builtin for the golden ratio / phi, but unfortunately it's not too good at taking the product of inner lists..
[Try it online.](https://tio.run/##y00syUjPz0n7///wKs3zbfqZh1dVxNUdXnV4fu7h1nNbtc4t/v/fUMGQy1DBCIhNuYyAbCMFEy4TIG0Cpi25zIFsc6C8OZBtqWAJAA)
**Explanation:**
```
ê                # Push the input as integer-array: [a,b]
 )               # Increase both values by 1: [a+1,b+1]
  φ/             # Divide both by phi: [(a+1)/phi,(b+1)/phi]
    i            # Floor the decimals to an integer: [(a+1)//phi,(b+1)//phi]
     êx          # Push the input-array again, and reverse it: [b,a]
       ^         # Zip the two lists together: [[(a+1)//phi,b],[(b+1)//phi,a]]
                 # Append the input-pair to this list, by:
        ~        #  Dumping both pairs onto the stack
         ê       #  Push the input-array again
          ß      #  Wrap all three pairs into a list: [[(a+1)//phi,b],[(b+1)//phi,a],[a,b]]
           m     # Map over the inner lists,
            Å    # using the following two characters as inner code-block:
             ε*  #  Take the product of this inner pair: [(a+1)//phi*b,(b+1)//phi*a,a*b]
               Σ # Sum all three values together: (a+1)//phi*b+(b+1)//phi*a+a*b
                 # (after which the entire stack is output implicitly as result)
```
]