[Challenge] Fibonacci Finder

Hard, JavaScript.
Using a formula I found online,
F(n) = round( Phi^n / √5 ) provided n ≥ 0 and Phi = (√5 + 1)/2 or 1.61803…
https://repl.it/Iy4W/19

function fibonacciFinderN(n){
  var sqrtFive = Math.sqrt(5);
  var phi = (sqrtFive+1)/2;
  return Math.round((Math.pow(phi,n-1))/sqrtFive);
}
fibonacciFinderN(300);
4 Likes

Using the golden ratio makes fibonacciFinderN O(1) which is really cool. Why did you use Math.floor instead of Math.round?

2 Likes

I had changed it to Math.round before but i guess i might of copied the wrong code. Thanks for the catch :)!

This entry coincides with a sidebar concerning JS and its limited ability to print long integers.

[Challenge] Fibonacci Finder

F(n) is rightly a long integer, not a float.

Actual value for F(300):

137347080577163115432025771710279131845700275212767467264610201

Float value:

 > float(137347080577163115432025771710279131845700275212767467264610201)
=> 1.3734708057716312e+62

My value from above mock code:

300 1.3734708057716305e+62

Value returned from golden ratio function

1.3734708057716302e+62

> int(1.3734708057716302e+62)
=> 137347080577163024412621090256418501530196341877966003631030272

Clearly our JS values are not in agreement with the long integer of Python 3. This represents a whole new challenge, if this the language of choice.

Even Python has trouble converting a float back to the original int.

 > int(1.3734708057716312e+62)
=> 137347080577163115756473423437850889260498386645654732126814208
3 Likes

Wow, I failed haha…
Thanks for bringing this up, I will try fixing it by using strings.

2 Likes

Got it.

https://repl.it/IygS/1

function addStringInts(a, b) {
    "use strict";
    let output  = "",
        digit   = 0,
        carry   = 0;

    if (a.length < b.length) a = numStringPadder(a, b.length, "0");
    if (a.length > b.length) b = numStringPadder(b, a.length, "0");

    for (let i = 0; i < a.length; i--) {
        digit = carry + +a.charAt(i) + +b.charAt(i);

        if (digit > 9 && i > 0) {
            carry = 1;
            digit %= 10;
        } else {
            carry = 0;
        }

        output = digit.toString() + output;
    }

    return output;
}

function numStringPadder(numString, l, padder = " ") {

    while (numString.length < l) {
        numString = padder + numString;
    }

    return numString;
}

function fibonacciFinderN(n) {
    "use strict";
    let pre = "0",
        cur = "1",
        fib = "0";

    for (let i = 2; i < n; i++) {
        fib = addStringInts(pre, cur);
        pre = cur;
        cur = fib;
    }

    return fib;
}

console.log(fibonacciFinderN(300));

EDIT: Adding string ints digit by digit was suggested late last night and I emphatically proclaimed ‘screw that!’ and went to bed.

All day today at work I kept coming back to the idea though and after reading all the rah-rah-Python above I had to work on this.

Adding string-integers digit by digit is a lot like grade school math, add two digits, check for carry over, move from right to left. In order for this to work the strings needed to be the same length so I zero-filled the smaller of the two string integers.

Next was the actual digit-by-digit addition which, for right to left, required a descending for loop. Prefixing a string with a ‘+’ attempts to coerce that value into a number which was safe to do because at the digit level JavaScript is obviously accurate.

The one bug that came up was that I kept getting ‘1’ as my output for fibonacciFinderN(300). I was forgetting to keep my carry value if I was on the last iteration of the loop and thus never worked on numbers above 10 (5 + 8 = 13, carry = 1, output = 3).

All of this obviously moves us out of O(n) into… O(2n)? Not sure, but it feels good!

EDIT 2: Cleaned up dirty word…

EDIT 3: Utilized sneaky while loop for speed

EDIT 4: Reverted while loop. Was less easy to read and understand for what it provided.

3 Likes

I’m just beginning to code at all and this is how I did it in Python for both basic and intermediate difficulty: https://repl.it/Iyz6/0

# from sys import argv

# script, N = argv
# N = int(N)

def fibonacciFinder50():
    """Gibt die 50. Fibonacci-Zahl aus und nimmt keine Argumente entgegen"""
    a, b, i = 0, 1, 1

    while i != 50:
        a, b = b, a+b
        i += 1

    print "%i " % a
    # print "%i" % i

def fibonacciFinderN(n):
    """Gibt die n. Fibonacci-Zahl aus und nimmt als Argument n entgegen"""
    a, b, i = 0, 1, 1

    while i != n:
        a, b = b, a+b
        i += 1

    print "%i " % a
    # print "%i" % i

fibonacciFinder50()
fibonacciFinderN(300)

Hi @chrinkus,

O(2n) is actually O(n). When evaluating complexities of algorithms, you can remove coefficients that are constants.

3 Likes

Intermediate difficulty, Python3:
https://repl.it/IzO4/0

def fibonacciFinderN(n):
  # Start of sequence
  f1 = 0
  f2 = 1
  # Edge special cases
  if n<=1: return f1
  if n==2: return f2
  # Direct rush: BigO(n)
  for i in range(3, n+1):
    f1, f2 = f2, f1+f2
    
  return f2
    
print(fibonacciFinderN(300))

Basic Difficulty using Ruby:
https://repl.it/IzRX/0

Basic and intermediate on Javascript. Maybe a bit sneaky of me to include the first few fib numbers in an array? Well it works
https://repl.it/IyEP/7

Seems that these formula match the formula that derived from matrix form.
https://en.wikipedia.org/wiki/Fibonacci_number#Matrix_form

Intermediate Difficulty:

https://repl.it/JAOA/0



def fib():
    first, second = 0,1
    sequence = []
    while len(sequence) != 50:
        first,second = second, first+second
        sequence.append(str(first))
    print(sequence[-1])
print(fib())
1 Like

Basic / Intermediate / Hard Difficulty :
Python 3 -
I came up with this solution only to find I am late and someone(betamaster97156) had already submitted with nearly same algorithm. Anyway, my approach focus on speed and less on memory management.

https://repl.it/JAOU/8

from time import time

def fibonacciFinder(): # return 50th number of fibonacci
    a, b = 0, 1
    for x in range(48):
        a, b = b, a + b
    return b
    

def fibonacciFinderN(N):
    # A dictionary to store value of few particular numbers of the fibonacci series
    fibDict = {1:0, 2: 1, 3: 1, 4: 2, 5: 3, 6: 5, 7: 8, 8: 13, 9: 21, 10: 34,
               11: 55, 12: 89, 13: 144, 14: 233, 15: 377, 16: 610, 17: 987, 18: 1597, 19: 2584, 20: 4181,
               21: 6765, 22: 10946, 23: 17711, 24: 28657, 25: 46368, 26: 75025, 27: 121393,
               'f25': 46368,'f26': 75025,'f27': 121393,
               'f100': 218922995834555169026, 'f101': 354224848179261915075, 'f102': 573147844013817084101,
               'f500': 86168291600238450732788312165664788095941068326060883324529903470149056115823592713458328176574447204501, 'f501': 139423224561697880139724382870407283950070256587697307264108962948325571622863290691557658876222521294125, 'f502': 225591516161936330872512695036072072046011324913758190588638866418474627738686883405015987052796968498626,
               'f5000': 2397334346100631452333336800023778743396400988090212332865227234032387117767626167465060795065595580850691237390963845987165478074085124644348902530685083246709423858342692329718110162972268152200857232686119638781547238020078362945470777668711057069618425746387920931255084621360135655698456629322111614827324455767748623844363426260372374195153577101298837831208580530677289982029527164306876024342838547454228388796380077029917639469963653048076473269452943584037848773158456736367057460079075603072996653089318046279296240100777360367200040226807430924334616931577257195085793060133817911514540227011756335999604550121968663793604830945238116686325506344893928776515696088851468818023735825546502317562957459506612704850760351077006532507519813600498603205937022956740021970327599548184626715032015801445754074519753924901317605013561516613650173445818028242577356369143977719495739428130191089993769093308407443558168431535751910046557480949313497996285124526992631353143367314930548703966553707195171094152730704138121243470432644848607501, 'f5001': 3878968454388325633701916308325905312082127714646245106160597214895550139044037097010822916462210669479293452858882973813483102008954982940361430156911478938364216563944106910214505634133706558656238254656700712525929903854933813928836378347518908762970712033337052923107693008518093849801803847813996748881765554653788291644268912980384613778969021502293082475666346224923071883324803280375039130352903304505842701147635242270210934637699104006714174883298422891491273104054328753298044273676822977244987749874555691907703880637046832794811358973739993110106219308149018570815397854379195305617510761053075688783766033667355445258844886241619210553457493675897849027988234351023599844663934853256411952221859563060475364645470760330902420806382584929156452876291575759142343809142302917491088984155209854432486594079793571316841692868039545309545388698114665082066862897420639323438488465240988742395873801976993820317174208932265468879364002630797780058759129671389634214252579116872755600360311370547754724604639987588046985178408674382863125, 'f5002': 6276302800488957086035253108349684055478528702736457439025824448927937256811663264475883711527806250329984690249846819800648580083040107584710332687596562185073640422286799239932615797105974710857095487342820351307477141875012176874307156016229965832589137779724973854362777629878229505500260477136108363709090010421536915488632339240756987974122598603591920306874926755600361865354330444681915154695741851960071089944015319300128574107662757054790648152751366475529121877212785489665101733755898580317984402963873738187000120737824193162011399200547424034440836239726275765901190914513013217132050988064832024783370583789324109052449717186857327239783000020791777804503930439875068662687670678802914269784817022567088069496231111407908953313902398529655056082228598715882365779469902465675715699187225655878240668599547496218159297881601061923195562143932693324644219266564617042934227893371179832389642895285401263875342640468017378925921483580111278055044254198382265567395946431803304304326865077742925818757370691726168228648841319231470626}

    # return value from index using the dictionary
    if N < 25:
        return fibDict[N]
    N += 1
    a, b, count = 0, 1, 1
    # Every number in fibonacci is multiple addition of first two number 0 and 1
    # Using that reduce the two variables repeatedly
    # Formula - f(x+n) = f(x+1)*f(n-1) + f(x+2)*f(n)
    # Example - f10 = f9*f1 + f10*f2 = 21*f1 + 34*f2         here => x = 8, n = 2 and f1 = 0, f2 = 1
    
    while N - count > 25:
        if N - count > 5000:    # x = 5000
            count += 5000
            a, b = fibDict['f5000'] * a + fibDict['f5001'] * b, fibDict['f5001'] * a + fibDict['f5002'] * b
        elif N - count > 500:    # x = 500
            count += 500
            a, b = fibDict['f500'] * a + fibDict['f501'] * b, fibDict['f501'] * a + fibDict['f502'] * b
        elif N - count > 100:    # x = 100
            count += 100
            a, b = fibDict['f100'] * a + fibDict['f101'] * b, fibDict['f101'] * a + fibDict['f102'] * b
        else:    # x = 25
            count += 25
            a, b = fibDict['f25'] * a + fibDict['f26'] * b, fibDict['f26'] * a + fibDict['f27'] * b
            
    if N - count == 1:
        return a
    else:
        # Using the above formula
        return fibDict[N - count - 1] * a + fibDict[N - count] * b


print(f'fibonacciFinder() => {fibonacciFinder()}')
print(f'fibonacciFinderN(300) => {fibonacciFinderN(300)}')

t = 0

for x in range(10000):
    start =  time()
    fibonacciFinderN(x+1)
    end = time()
    t += end - start

print(f'Time taken to find first 10000 numbers in fibonacci is {t} seconds')

I also tried to solve this problem with golden ratio formula, but it was very slow, if I tried to get precise values(even though it’s time complexity is O(1)) compared to this solution.

A post was split to a new topic: Fibonacci Finder - Thought Experiment

Python 3:
Intermediate

https://repl.it/JCs0/2

Anna

I initially just used a recursive algorithm but it seemed a bit too easy for a challenge so I went online to search for efficient ways to generate the Fibonnacci sequence. Found the Matrix Exponentiation method which would be O(logn) if exponentiation by squaring is used. I would never have thought about this method if I didn’t search online though, so I included both my initial solution and the piece of code I wrote for matrix exponentiation for practice. It’s my first challenge and I haven’t used Python in a while so I hope to get some useful feedback :slight_smile:

import numpy as np

# Set our n here for both functions to use
n = 300

# Recursive algorithm, O(n^2)
def recursiveFinderN(n):
    previousFib, currentFib = 0, 1
    for i in range(n-2):
        previousFib, currentFib = currentFib, previousFib + currentFib
    return currentFib

print("Recursive algorithm: The %dth fibonnacci number is %d" % (n, recursiveFinderN(n)))

###############################################################################

# Matrix exponentiation, O(logn)
def fibonacciFinderN(n):
    # Build array containing first 2 values of the sequence
    initialArray = [0, 1] 

    # Build transformation matrix which transforms initialArray into an array V
    # of which V[1] is the next value in the sequence
    # Set dtype=object to take advantage of arbitrary precision integers
    # otherwise matrix_power will overflow for higher powers
    transform = np.array([0, 1, 1, 1], dtype=object).reshape(2, 2)
    
    # Use exponentiation by squaring to compute transform^n-1
    # and multiply with initialArray to get array of nth and n+1th value of sequence
    finalArray = np.dot(expoBySquaring(transform, n-1), initialArray)

    return finalArray[0]

def expoBySquaring(matrix, power):
    if power == 1:
        return matrix
    if power % 2:
        return np.dot(matrix, np.linalg.matrix_power(matrix, int(power-1)))

    mat = np.linalg.matrix_power(matrix, int(power/2))
    return np.dot(mat, mat)

print("Matrix exponentiation: The %dth fibonnacci number is %d" % (n, fibonacciFinderN(n)))

Apparently there’s an even faster way of computing called the Fast Doubling. A comparison between the difference methods can be found here: https://www.nayuki.io/page/fast-fibonacci-algorithms
It also includes a piece of Python code on fast doubling, which is why I didn’t include this method in my answer.

https://repl.it/JFBV/0

Only problem is we are advised to not use libraries, outside of the math realm, so this is not considered an entry. If any discussion evolves around it, it will be split off. That would not be a bad thing; it would just remove the discussion from this thread so as not to cause a dirsruption of the entry queue.

2 Likes

As a moderator, it follows this is not a submission, just a follow up on an earlier secondary challenge. Acknowledging that there is already a posted solution, this is one that is not intentionally derived from that one since this was found independent of any knowledge of it. In other words, I did not study that code but hammered out this version from scratch…

JS:

function matchStrings(m, n) {
  var order = n.length > m.length ? [m, n] : [n, m];
  while (order[0].length < order[1].length) {
    order[0] = '0' + order[0];
  }
  return order;
}
function add_abc(a, b, c) {
  var s = a + b + c;
  c = Math.floor(s / 10);
  s %= 10;
  return [s, c];
}
function $sum($a, $b) {
  var strs = matchStrings($a, $b);
  $a = strs[0];
  $b = strs[1];
  var a, b, r, s;
  var $c = [];
  var c = 0;
  for (var i = $b.length; i > 0; i--) {
    a = +$a[i-1];
    b = +$b[i-1];
    r = add_abc(a, b, c);
    s = r[0];
    c = r[1];
    $c.unshift(s.toString(10));
  }
  if (c) $c.unshift(c.toString(10));
  return $c.join('');
}
function fibonacciFinderN(n, list) {
  if (arguments.length < 2) {
    list = 0;
  }
  var a = '0';
  var b = '1';
  var i = 2;
  var c;
  while (i++ < n) {
    c = $sum(a, b);
    a = b;
    b = c;
    if (list) {
      console.log(i, c);
    }
  }
  return c;
}

https://repl.it/JE6H/2

As to time complexity, I am reaching out to the community to solve this. I only know that when n is 1001, the add_abc function is called 104_541 times.


Addendum

Way back when it was BASIC or Assembly the dollar sign symbolized a strng. $a was mentally read as, Eh string. That is how this code is meant to be interpreted. $ denotes string object, or content in the case of reference objects.

4 Likes

Not much room for creative thinking in this one, you either know your algorithms or you don’t. I don’t so intermediate is all I mustered up on my own:

def fibonacciFinderN(n):
    a, b = 0, 1
    for i in range(n-2):
        a, b = b, a+b
    return b

Same recipe as everyone else’s, appears to be a tad faster than most as many people tend to complicate things. repl.it

The below code would be my hard entry… if I had conceived it. Unfortunately I only translated pseudocode provided by someone else:

def fib(n):
    a, b, p, q = 1, 0, 0 ,1
    while n > 0:
        if n%2:
            x = a
            a = b*q + a*q + a*p
            b = b*p + x*q
            n -= 1
        else:
            x = p
            p = p*p + q*q
            q = 2*x*q + q*q
            n /= 2
    return b

Posting so you can benchmark your own solutions against this. Runs almost twice as fast against the fast doubling routine @megajumper52633 referred to (6.6s vs 10.2s for n = 10**6 on my old box). Also contains no floats/approximations like the sqrt(5) one.

2 Likes