README.md (5174B)
1 <!-- 2 3 @license Apache-2.0 4 5 Copyright (c) 2018 The Stdlib Authors. 6 7 Licensed under the Apache License, Version 2.0 (the "License"); 8 you may not use this file except in compliance with the License. 9 You may obtain a copy of the License at 10 11 http://www.apache.org/licenses/LICENSE-2.0 12 13 Unless required by applicable law or agreed to in writing, software 14 distributed under the License is distributed on an "AS IS" BASIS, 15 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 16 See the License for the specific language governing permissions and 17 limitations under the License. 18 19 --> 20 21 # Fibonacci Polynomial 22 23 > Evaluate a [Fibonacci polynomial][fibonacci-polynomials]. 24 25 <section class="intro"> 26 27 A [Fibonacci polynomial][fibonacci-polynomials] is expressed according to the following recurrence relation 28 29 <!-- <equation class="equation" label="eq:fibonacci_polynomial" align="center" raw="F_n(x) = \begin{cases}0 & \textrm{if}\ n = 0\\1 & \textrm{if}\ n = 1\\x \cdot F_{n-1}(x) + F_{n-2}(x) & \textrm{if}\ n \geq 2\end{cases}" alt="Fibonacci polynomial."> --> 30 31 <div class="equation" align="center" data-raw-text="F_n(x) = \begin{cases}0 & \textrm{if}\ n = 0\\1 & \textrm{if}\ n = 1\\x \cdot F_{n-1}(x) + F_{n-2}(x) & \textrm{if}\ n \geq 2\end{cases}" data-equation="eq:fibonacci_polynomial"> 32 <img src="https://cdn.jsdelivr.net/gh/stdlib-js/stdlib@7e0a95722efd9c771b129597380c63dc6715508b/lib/node_modules/@stdlib/math/base/tools/fibpoly/docs/img/equation_fibonacci_polynomial.svg" alt="Fibonacci polynomial."> 33 <br> 34 </div> 35 36 <!-- </equation> --> 37 38 Alternatively, if `F(n,k)` is the coefficient of `x^k` in `F_n(x)`, then 39 40 <!-- <equation class="equation" label="eq:fibonacci_polynomial_combinatoric" align="center" raw="F_n(x) = \sum_{k = 0}^n F(n,k) x^k" alt="Combinatoric interpretation of a Fibonacci polynomial."> --> 41 42 <div class="equation" align="center" data-raw-text="F_n(x) = \sum_{k = 0}^n F(n,k) x^k" data-equation="eq:fibonacci_polynomial_combinatoric"> 43 <img src="https://cdn.jsdelivr.net/gh/stdlib-js/stdlib@7e0a95722efd9c771b129597380c63dc6715508b/lib/node_modules/@stdlib/math/base/tools/fibpoly/docs/img/equation_fibonacci_polynomial_combinatoric.svg" alt="Combinatoric interpretation of a Fibonacci polynomial."> 44 <br> 45 </div> 46 47 <!-- </equation> --> 48 49 where 50 51 <!-- <equation class="equation" label="eq:fibonacci_polynomial_coefficients" align="center" raw="F(n,k) = {{\frac{n+k-1}{2}} \choose {k}}" alt="Fibonacci polynomial coefficients."> --> 52 53 <div class="equation" align="center" data-raw-text="F(n,k) = {{\frac{n+k-1}{2}} \choose {k}}" data-equation="eq:fibonacci_polynomial_coefficients"> 54 <img src="https://cdn.jsdelivr.net/gh/stdlib-js/stdlib@7e0a95722efd9c771b129597380c63dc6715508b/lib/node_modules/@stdlib/math/base/tools/fibpoly/docs/img/equation_fibonacci_polynomial_coefficients.svg" alt="Fibonacci polynomial coefficients."> 55 <br> 56 </div> 57 58 <!-- </equation> --> 59 60 We can extend [Fibonacci polynomials][fibonacci-polynomials] to negative `n` using the identity 61 62 <!-- <equation class="equation" label="eq:negafibonacci_polynomial" align="center" raw="F_{-n}(x) = (-1)^{n-1} F_n(x)" alt="NegaFibonacci polynomial."> --> 63 64 <div class="equation" align="center" data-raw-text="F_{-n}(x) = (-1)^{n-1} F_n(x)" data-equation="eq:negafibonacci_polynomial"> 65 <img src="https://cdn.jsdelivr.net/gh/stdlib-js/stdlib@7e0a95722efd9c771b129597380c63dc6715508b/lib/node_modules/@stdlib/math/base/tools/fibpoly/docs/img/equation_negafibonacci_polynomial.svg" alt="NegaFibonacci polynomial."> 66 <br> 67 </div> 68 69 <!-- </equation> --> 70 71 </section> 72 73 <!-- /.intro --> 74 75 <section class="usage"> 76 77 ## Usage 78 79 ```javascript 80 var fibpoly = require( '@stdlib/math/base/tools/fibpoly' ); 81 ``` 82 83 #### fibpoly( n, x ) 84 85 Evaluates a [Fibonacci polynomial][fibonacci-polynomials] at a value `x`. 86 87 ```javascript 88 var v = fibpoly( 5, 2.0 ); // => 2^4 + 3*2^2 + 1 89 // returns 29.0 90 ``` 91 92 #### fibpoly.factory( n ) 93 94 Uses code generation to generate a `function` for evaluating a [Fibonacci polynomial][fibonacci-polynomials]. 95 96 ```javascript 97 var polyval = fibpoly.factory( 5 ); 98 99 var v = polyval( 1.0 ); // => 1^4 + 3*1^2 + 1 100 // returns 5.0 101 102 v = polyval( 2.0 ); // => 2^4 + 3*2^2 + 1 103 // returns 29.0 104 ``` 105 106 </section> 107 108 <!-- /.usage --> 109 110 <section class="notes"> 111 112 ## Notes 113 114 - For hot code paths, a compiled function will be more performant than `fibpoly()`. 115 - While code generation can boost performance, its use may be problematic in browser contexts enforcing a strict [content security policy][mdn-csp] (CSP). If running in or targeting an environment with a CSP, avoid using code generation. 116 117 </section> 118 119 <!-- /.notes --> 120 121 <section class="examples"> 122 123 ## Examples 124 125 <!-- eslint no-undef: "error" --> 126 127 ```javascript 128 var fibpoly = require( '@stdlib/math/base/tools/fibpoly' ); 129 130 var i; 131 132 // Compute the negaFibonacci and Fibonacci numbers... 133 for ( i = -77; i < 78; i++ ) { 134 console.log( 'F_%d = %d', i, fibpoly( i, 1.0 ) ); 135 } 136 ``` 137 138 </section> 139 140 <!-- /.examples --> 141 142 <section class="links"> 143 144 [fibonacci-polynomials]: https://en.wikipedia.org/wiki/Fibonacci_polynomials 145 146 [mdn-csp]: https://developer.mozilla.org/en-US/docs/Web/HTTP/CSP 147 148 </section> 149 150 <!-- /.links -->