11const list = [ ]
2-
2+ // https://en.wikipedia.org/wiki/Generalizations_of_Fibonacci_numbers#Extension_to_negative_integers
33const FibonacciIterative = ( nth ) => {
4- const sequence = [ ]
4+ const sign = nth < 0
5+ if ( sign ) n = - n
6+ const sequence = [ 0 ]
57
68if ( nth >= 1 ) sequence . push ( 1 )
7- if ( nth >= 2 ) sequence . push ( 1 )
9+ if ( nth >= 2 ) sequence . push ( sign ? - 1 : 1 )
810
911for ( let i = 2 ; i < nth ; i ++ ) {
10- sequence . push ( sequence [ i - 1 ] + sequence [ i - 2 ] )
12+ sequence . push (
13+ sign ?
14+ sequence [ i - 2 ] - sequence [ i - 1 ]
15+ :
16+ sequence [ i - 1 ] + sequence [ i - 2 ]
17+ )
1118}
1219
1320return sequence
@@ -17,15 +24,21 @@ const FibonacciRecursive = (number) => {
1724return ( ( ) => {
1825switch ( list . length ) {
1926case 0 :
20- list . push ( 1 )
27+ list . push ( 0 )
2128return FibonacciRecursive ( number )
2229case 1 :
2330list . push ( 1 )
2431return FibonacciRecursive ( number )
2532case number :
2633return list
2734default :
28- list . push ( list [ list . length - 1 ] + list [ list . length - 2 ] )
35+ const sign = number < 0
36+ list . push (
37+ sign ?
38+ list . at ( - 2 ) - list . at ( - 1 )
39+ :
40+ list . at ( - 1 ) + list . at ( - 2 )
41+ )
2942return FibonacciRecursive ( number )
3043}
3144} ) ( )
@@ -34,14 +47,18 @@ const FibonacciRecursive = (number) => {
3447const dict = new Map ( )
3548
3649const FibonacciRecursiveDP = ( stairs ) => {
37- if ( stairs <= 0 ) return 0
50+ const sign = stairs < 0
51+ if ( sign ) stairs *= - 1
52+
53+ if ( stairs === 0 ) return 0
3854if ( stairs === 1 ) return 1
3955
4056// Memoize stair count
4157if ( dict . has ( stairs ) ) return dict . get ( stairs )
4258
43- const res =
44- FibonacciRecursiveDP ( stairs - 1 ) + FibonacciRecursiveDP ( stairs - 2 )
59+ const res = sign
60+ ?FibonacciRecursiveDP ( stairs - 2 ) - FibonacciRecursiveDP ( stairs - 1 )
61+ :FibonacciRecursiveDP ( stairs - 1 ) + FibonacciRecursiveDP ( stairs - 2 )
4562
4663dict . set ( stairs , res )
4764
@@ -60,11 +77,18 @@ const FibonacciRecursiveDP = (stairs) => {
6077//@Satzyakiz
6178
6279const FibonacciDpWithoutRecursion = ( number ) => {
63- const table = [ ]
64- table . push ( 1 )
80+ const sgn = number < 0
81+ if ( sgn ) number *= - 1
82+ const table = [ 0 ]
6583table . push ( 1 )
84+ table . push ( sgn ?- 1 :1 )
6685for ( let i = 2 ; i < number ; ++ i ) {
67- table . push ( table [ i - 1 ] + table [ i - 2 ] )
86+ table . push (
87+ sgn ?
88+ table [ i - 2 ] - table [ i - 1 ]
89+ :
90+ table [ i - 1 ] + table [ i - 2 ]
91+ )
6892}
6993return table
7094}
@@ -75,10 +99,11 @@ const copyMatrix = (A) => {
7599return A . map ( row => row . map ( cell => cell ) )
76100}
77101
78- // the 2nd param is to generate a "BigInt-safe" matrix
79- const Identity = ( size , bigint ) => {
80- const ZERO = bigint ?0n :0
81- const ONE = bigint ?1n :1
102+ const Identity = ( size ) => {
103+ const isBigInt = typeof size === 'bigint'
104+ const ZERO = isBigInt ?0n :0
105+ const ONE = isBigInt ?1n :1
106+ size = Number ( size )
82107const I = Array ( size ) . fill ( null ) . map ( ( ) => Array ( size ) . fill ( ) )
83108return I . map ( ( row , rowIdx ) => row . map ( ( _col , colIdx ) => {
84109return rowIdx === colIdx ?ONE :ZERO
@@ -164,7 +189,6 @@ const FibonacciMatrixExpo = (n) => {
164189[ ZERO ]
165190]
166191F = matrixMultiply ( poweredA , F )
167- // https://en.wikipedia.org/wiki/Generalizations_of_Fibonacci_numbers#Extension_to_negative_integers
168192return F [ 0 ] [ 0 ] * ( sign ?( - ONE ) ** ( n + ONE ) :ONE )
169193}
170194