Machine Learning & Javascript

Interlude 1: Fibonacci

In my quest of writing different machine learning and other algorithms in javascript, I have found that I should probably also include different known formulas and/or algorithms that are usually used very often in core computer science. That is why I will also include “interlude” articles like this one in which I will discuss these algorithms. In this article I will tackle 2 algorithms, one of which will have 2 approaches. Fibonacci: The Fibonacci sequence (and the resulting ‘Golden Spiral’) is one of the most studied sequences in mathematics, physics, computer science and in nature itself (see lotus flower, pine trees …). I will show 2 approaches to that algorithm in javascript. One approach is the traditional recursive approach that requires a polynomial processing time. The other is a bit different and unique to functional languages like javascript and it will be able to achieve the Fibonacci sequence in a linear processing time (which means we’ll be able to generate the sequence up to a much higher number in much less time O ).

jsML.FibRecursive = function(n){ return n == 0 ? 0 : n == 1 ? 1 : jsML.FibRecursive(n-1) + jsML.FibRecursive(n-2); };

This is simple recursion in javascript and it will result in the Fibonacci number of ‘n’. A linear approach, however, would be in this form.

jsML.FibLinear = function(n){ var f = []; f[0] = 0; f[1] = 1; for(var i=2; i<=n; i++){ f[i] = f[i-1] + f[i-2]; } return f[n]; };

Obviously, this approach has a higher space-complexity (dynamic array) whereas the one above has a higher time complexity (recursion). Go ahead and try to get the Fib(199) from both ☺ The second algorithm I will discuss is the ‘Sieve of Eratosthenes’. In mathematics, it is a simple, ancient algorithm for finding all prime numbers up to any given limit. It does so by iteratively marking -as composite (i.e. not prime)- the multiples of each prime, starting with the multiples of 2.

//the jsML.SoE function(finds all prime numbers from 2 to maxNumber) jsML.SoE = function(maxNumber){ var collection = []; var _fillCollection = function(max){ for(var i = 2; i <= max; i++){ collection.push(i); } }; var _removeMultiples = function(number, max){ var index = -1; for(var i = 2; true; i++){ index = collection.indexOf(number*i); if(index > -1){ collection.splice(index, 1); } if((number*i) > collection[collection.length-1]){ break; } } }; _fillCollection(maxNumber); for(var i=0; i<collection.length; i++){ _removeMultiples(collection[i], maxNumber); } return collection; };

As you can see, I’ve segregated the process into 2 private functions inside the main function. ‘_fillCollection’ function fills the collection with all numbers from 2 to ‘maxNumber’ which would be the range in which we want to find all prime numbers. Whereas the second function ‘_removeMultiples’ takes a number and the max number and then runs through the collection finding (and removing) the multiples of the number passed. Please note that there is no need to check if ‘number’ is prime as -obviously- we are starting off from 2 and later removing all it’s multiples leaving only the prime numbers in the collection. As ‘collection.length’ decreases and ‘i’ increases we will eventually obtain a collection having all prime numbers between 2 and ‘maxNumber’. You can find the jsML.js project on my GitHub here.

May the Code be with You!