response for @tevko ~ "coding challenge - make this function perform well on the largest possible number"

get-factors-fast-fixed.js

// April 25, 2015

// response for @tevko:
// "coding challenge - make this function perform well on the largest possible number"
// tweet: <a href="https://twitter.com/Tevko/status/591417164969574400">April 24, 2015</a>
 
// The fixed version of get-factors-fast-original.js (see below):
// Believe it or not, the fix is to replace the semi-colon at upper = []; with a comma upper = [],
// so that `limit` and `i` are no longer accidental globals.

// The *modified* version of original get-factors-of.js ( below )
// uses Math.sqrt(num)--and rounds down--for the iteration limit rather than num -1.
// now manages input of 100 trillion in 372ms on my laptop, in Firefox 37.0.2 on Windows 8 with 2.40 GHz and 8GB RAM.

var getFactorsFast = function(num) {

  var start = Date.now(); // added for console profiling
  var lower = [], 
      upper = [], // fixed idiotic semi-colon instead of comma
      limit = Math.floor(Math.sqrt(num)),
      i = 2,
      result;
  
  while (i <= limit) {
    num % i === 0 
      && lower.push(i)
      && (i != limit && upper.unshift(num / i)); // <= de-dupe
    i++;
  }
  
  result = lower.concat(upper);
  console.log(Date.now() - start + "ms"); // profile
  
  console.log(result);
  return result;
};

getFactorsFast( 64 ); // [2, 4, 8, 16, 32] no dupes: 0ms
getFactorsFast( 11999999 ); // 12million - 1: 1ms
getFactorsFast( 119999999 ); // 120million - 1: 1ms
getFactorsFast( 1199999999 ); // 1.2billion - 1: 0ms
getFactorsFast( 119999999999 ); // 100billion: 11ms
getFactorsFast( 1199999999999 ); // 1.2trillion: 38ms
getFactorsFast( 119999999999999 ); // 100trillion 414ms
getFactorsFast( 12345678901234567 ); // 12 quadrillion-ish: 3914ms
// don't do this ~ long-running script alerts over 14 seconds
//getFactorsFast( 123456789012345678 ); // 123 quadrillion-ish: 14106ms

// first ten primes, 6,469,693,230 takes 4ms 
getFactorsFast( 2*3*5*7*11*13*17*19*23*29 ); // 12million - 1: 4ms

get-factors-fast-original.js

// April 24, 2015

// response for @tevko:
// "coding challenge - make this function perform well on the largest possible number"
// tweet: <a href="https://twitter.com/Tevko/status/591417164969574400">April 24, 2015</a>
 
// First version of get-factors-fast.js ( see above ):
// Uses sqare root of the input number as the uppermost iteration integer.
// NOTE:  contains an assignment error that slows down the algorithm inadvertently

var getFactorsFast = function(num) {
  
  var start = Date.now(); // added for console profiling
  var lower = [], 
      upper = []; /* <= ASSIGNMENT ERROR:  originally assigned by @dfkaye. 
        --note the semi-colon rather than a comma--
        which turned limit and i into globals, thus introducing var lookups 
        outside the local scope, thus slowing total processing time by an 
        order of magnitude times 2 or 3.      
      */
      limit = Math.floor(Math.sqrt(num)),
      i = 2;
  
  while (i <= limit) {
    num % i === 0 
      && lower.push(i)
      && (i != limit && upper.unshift(num / i)); // <= de-dupe
    i++;
  }
  
  console.log(Date.now() - start + "ms"); // profile
  console.log(lower.concat(upper));
};

getFactorsFast( 64 ); // [2, 4, 8, 16, 32] no dupes: 0ms
getFactorsFast( 11999999 ); // 12million - 1: 3ms
getFactorsFast( 119999999 ); // 120million - 1: 10ms
getFactorsFast( 1199999999 ); // 1.2billion - 1: 29ms
getFactorsFast( 100000000000 ); // 100billion: 274ms
getFactorsFast( 1200000000000 ); // 1.2trillion: 949ms
getFactorsFast( 100000000000000 ); // 100trillion 8668ms

get-factors-of.js

// @tevko's original version
// April 24, 2105
// Linear performance algorithm that iterates through all possible integers up to 
// the input number.

var getFactorsOf = function(num) {

  var start = Date.now(); // added for console profiling
  var ar = [], i = 2;
      
  while (i < num - 1) {
    if (i > num) {
      break;
    } else {
      num % i === 0 && ar.push(i);
      i++;
    }
  }
  
  console.log(Date.now() - start + "ms"); // profile
  console.log(ar);
};

getFactorsOf( 64 ); // [2, 4, 8, 16, 32] no dupes: 0ms
getFactorsOf( 11999999 ); // 12million - 1: 58ms 
getFactorsOf( 119999999 ); // 120million - 1: 576ms
getFactorsOf( 1199999999 ); // 1.2billion - 1: 5790ms

// quite a jump: (5 minutes?) with many long-running script alerts
getFactorsOf( 10000000000 ); // 10billion: 304681ms 

get-factors-recursive-WTF.js

// April 25, 2015
// This version removes the noDupes assignment and fixes the dedupe strategy,
// BUT hits recursive limit sooner (~= 50million instead of ~=1billion -- I don't understand that).

var getFactorsRecursive = function(num) {
  if (num > 1199999999) {
    return console.log('sorry, that number is too large :(');
  } else {

    var start = Date.now(); // added for console profiling
    var lower = [], 
        upper = [],
        //noDupes = []; // BY FIXING THIS, limit and i are no longer accidental globals...
        limit = Math.floor(Math.sqrt(num)), // HOWEVER,
        i = 2; // RATHER INCREDIBLY, MAKING `i` LOCAL RATHER THAN GLOBAL WE HIT RECURSION LIMIT SOONER!!!

    (function run(limit) { // modified to IIFE since only run calls run...
      if (limit < 0) {
        console.log(Date.now() - start + "ms"); // profile
        // no need to "return" here
      } else {
      
        num % i === 0
          && lower.push(i)
          && (i != limit && upper.unshift(num / i)); // <= fix de-dupe

        i++;
      
        run(limit - 1);
      }
    }(limit));

    // probably missed a step where i is equal to limit...
    //lower.concat(upper).map(function(num) {
    //  noDupes.indexOf(num) === -1 && noDupes.push(num);
    //});

    return lower.concat(upper) //noDupes;
  }
}

getFactorsRecursive( 64 ); // [2, 4, 8, 16, 32] no dupes: 0ms
getFactorsRecursive( 11999999 ); // 12million - 1: 0ms

// strangely we now hit "too much recursion" sooner than previously, around 50million
// 119999999 previously resolved in 7ms
getFactorsRecursive( 119999999 ); // 120million - 1: too much recursion (vs 7ms)

get-factors-recursive.js

// @tevko's modification using recursion
// http://codepen.io/tevko/pen/jPOXba

// April 25, 2015: @dfkaye modified a couple things (dedupe)
// While fast as get-factors-fast (above) it tops out near 1199999999,
// generating the "too much recursion" messages

var getFactorsRecursive = function(num) {
  if (num > 1199999999) {
    return console.log('sorry, that number is too large :(');
  } else {

    var start = Date.now(); // added for console profiling
    var lower = [], 
        upper = [],
        noDupes = []; // <= REPEATED THE ASSIGNMENT ERROR by @dfkaye makes limit and i into globals
        limit = Math.floor(Math.sqrt(num)),
        i = 2;

    (function run(limit) { // modified to IIFE since only run calls run...
      if (limit < 0) {
        console.log(Date.now() - start + "ms"); // profile
        // no need to "return" here
      } else {
      
        num % i === 0
          && lower.push(i)
          && (i != limit && upper.unshift(num / i)); // <= fix de-dupe

        i++;
      
        run(limit - 1);
      }
    }(limit));

    // probably missed a step where i is equal to limit...
    //lower.concat(upper).map(function(num) {
    //  noDupes.indexOf(num) === -1 && noDupes.push(num);
    //});

    return lower.concat(upper) //noDupes;
  }
}

getFactorsRecursive( 64 ); // [2, 4, 8, 16, 32] no dupes: 0ms
getFactorsRecursive( 11999999 ); // 12million - 1: 2ms
getFactorsRecursive( 119999999 ); // 120million - 1: 7ms

getFactorsRecursive( 1199999999 ); // 1.2billion - 1:  too much recursion

getFactorsRecursive( 100000000000 ); // 100billion: sorry, that number is too large :(
getFactorsRecursive( 1200000000000 ); // 1.2trillion: sorry, that number is too large :(
getFactorsRecursive( 100000000000000 ); // 100trillion sorry, that number is too large :(