Индекс действительно большого числа Фибоначчи

Question

Мне нужно рассчитать индекс числа Фибоначчи с JavaScript в последовательности Фибоначчи. Мне нужно сделать это без использования рекурсии или цикла. Я нашел следующую формулу: in the Math forum

п = ⌊logφ (F⋅5√ + 12) ⌋

и закодированы его в JavaScript:

function fibIndex(fib) 
{ 
    fib = BigNumber(fib); 
    return logBasePhi(fib.times(Math.sqrt(5)).plus((1/2))); 
} 

function phi() 
{ 
    return (1 + Math.sqrt(5))/ 2; 
} 

function getBaseLog(x, y) { 
    return Math.log(y)/Math.log(x); 
} 

function logBasePhi(x) 
{ 
    return getBaseLog(phi(), x); 
} 

Обратите внимание на .times() и .plus() функции, которые являются частью this BigNumber Library, которая была чрезвычайно полезна до этого момента. Это прекрасно работает, пока номер Фибоначчи, который я хочу найти, для индекса действительно большой.

Проблема:

мне нужен другой способ вычислить логарифм с таким большим числом. Если у меня есть действительно большое число, например, Фибоначчи 2000 года, я получаю Infinity по понятным причинам. Сама библиотека не имеет методов для вычисления журнала, и я тоже не могу написать эту функцию.

Я бы никогда не думал, что логарифм любого числа с такой небольшой базой (phi) может быть больше, чем max для целых чисел JavaScript. Можете ли вы, ребята, указать мне в правильном направлении? Должен ли я просто оставить его при получении индекса для чисел меньше Fib (1500) и назвать его хорошим?

Answer 1

Вы можете использовать BigInteger. Вы можете увидеть пример того, как использовать его здесь: http://reallifejs.com/the-meat/calculators/big-number-calculator/

Answer 2

Вместо этого используйте эту формулу:

(Fn) = (Fn-1) + (Fn-2)

п является субиндекс, для понимания, что я говорю ...

Так давайте код: D

function fibonacci(n) { 
    var f = new Array(); 
    f[0] = 1; 
    f[1] = 1; 

    if(n == 1 && n == 2) { 
    return 1; 
    } 

    for(var i = 2; i < n; i++) { 
    f[i] = f[i - 1] + f[i - 2]; 
    } 

    return f[n - 1]; 
} 

Answer 3

для любого другого ищет для этой функции, здесь используется this BigInteger библиотека:

function fibIndex(fib) 
{ 
    fib = BigInteger(fib); 
    var x = fib.multiply(Math.sqrt(5)).add((1/2)); 

    return Math.round(x.log()/Math.log(phi())); 
} 

function phi() 
{ 
    return (1 + Math.sqrt(5))/ 2; 
} 

Я по-прежнему использую ту же формулу, что и в моем вопросе выше, и возвращает индекс Фибоначчи любого размера.

fibIndex("3552293879432171509127295399108887507366095067071187974339990032643625408342138037892775025752467531144728691561082086130290437115246618296826111100982439172563715086274550534213022058697951171925502389533510870952207531424826066448316647967058822158527706988787316819649096356121969451807786487910042178820551538538043454597566200172355534244039262180857976029564853114163882291359060753354005408745204170782615327118525910739419985236764961829851709311700945589491835350352507623012581954312377931916744082078962656445976472533968480829007375638549624814219584324013506450788535487729657202480440862427294175363981253803991314202865190303052987111679331778975789360655034146695132475652682589973766794581383385372226263043326278097491542500573286659181886817470554608702210612705287731084795157170758279482037612857978976772148510949254228776434861586872339572512481485641557776354065676559167316272414604833085278808143917828870688188950284393383938343796557289538544079296039170226898476935785968627126657463287172704602430318466391939540146580152872601590145633302557348124795910165220460298803514153249036124574213905081943307783370774224631283520843929346972577743794025481908687167214612897223832825141458954443443517026136782478215510365757819419627011174857003444929796461256445626689163549925718652020566200419017958146518485827359063469655706771966834456971677260449437926825641755900598919666406233994336742639226754967169609162070448333570523540102466897237705895901354870189923742316331760981348007590643882156750167802745398125587294016589676556290694827588868223302601839859156168396827925331181035298221644999060513884127947625899829155539311217167251224729954052827398530462805909334004955504798174190155311843699637256514343709216404050138512197908782686483600285244101329043545140581893696579183008859405799317480170155523983803382549110118230260469348392329715555273264666423033989938694924746966214660178379915953526566319279862251960008019929477826402193032780467440684539085868936118364513803602462299975918114937440986833905619035493076243801825318183972199864647391129916857702952066619978368119126871928838796962474565324078070831995093115932361611672575908463117986329672876621241559374808293055815110135007637670429536347280563781355935092589871511793848113874421288696597789251652513904086337687443825301561448512027730668192219672054189819370257035588554035266826775985082731202586967262120157501641620776047167454166829537632280941209558296827539644997022606450061878848010224399661443708527154616405033264104082930735466775367001224101531516001395280253550083862908664924825327167786571748233189360087112363402534860762354833139723959618075080909694639797423322341773579015817861274133174885562908834073270590055324604171074201616001830372551221150920403488075959677542799667537196446943171756705423410725251162535871548917157457847930477751789977472359887266599109153894548881161822243865172322446599216032744469655275931388127302148091940688797023850907410507180806682170311506683812602758520792225620518614192135288065775855196360250458726533494846896372579594361265906158173811892121790048035897999120914006198579446215249845856447336929507815356729620181825172028182296206293683157363165375152807422519011182325370235117761066480394034550369969920803709578487049578564694399723447425826256999860804124314024767407351332337419993606621894609872209226414009266975365782401763446176398152199711922621913650858420337568329295794856307363297593764258194776804237111747019835544459951771897915871378480447084934317351794380026977598879906520926372701675762098910064924927779013929006778968827048115753724725507785438842459688233736002623641676407303084520628213429430170160536945255560874984408988184015246468818541347116553134808345007193676780884717882850521254468144834685041242239258445779802356261750715654014303658666045509415066500324877858994363380423606186778725409246576189772109749870684830483808213015157383014628159890586208052875599925938644140629584421209395853268927733133957674547761309304884216287250624849387963198478727957709587546563501380396046901974369444199654691073693459072539012225218131056806286801561742277137542542220910646623259768946663678086166624520443073537555044497446695176288888164280133784070920239187643378676864714780788016247153433427220203409841101176829095748434542450712132746238844301461280057534842381"); 

вернет 25 001, что является показателем вышеприведенного фиб.