CODEWITHSUNDEEP
javascriptmath
zahabba
zahabba

Reputation: 3231

How to minimize Math calls? (Javascript)

I'm doing a Codewars challenge in which I have to create a function with the parameters a, b & c corresponding to the quadratic equation ax^2 + bx + c = 0 and solve for x. The goal is not only to solve for x, but to minimize the number of spendy Math.sqrt calls. (You also have to return an array with the unique solution(s)).

I came up with a solution:

function solveQuadratic(a, b, c) {
  if ((4*a*c > b*b) || ((a === 0) && (b === 0))) { return undefined;}
  else if (a === 0) {return [-c/b];}
  else {
   var xVals = [];
   var sqrt = Math.sqrt(b*b - 4*a*c);
   xVals.push((-b - sqrt)/2*a);
   xVals.push((-b + sqrt)/2*a);
   if (xVals[0] === xVals[1]) {xVals.pop();}
   return xVals;
  }
}

I got the error message:

You passed the tests using 6 Math.sqrt calls. You should be able to pass these tests with 4 Math.sqrt calls or less.

I thought storing the result of the square root part of the expression in a variable (sqrt) would prevent it from being called more than that one time to evaluate the expression and assign a value to the variable. But that's not the case.

So I have a couple of questions:

Upvotes: 1

Views: 223

Answers (4)

jfriend00
jfriend00

Reputation: 707396

The key is to avoid Math.sqrt(x) when x === 0 and when x === b^2 since the answer is already known. These two situations occur when b^2 === 4ac and when 4ac === 0, so the code needs to short circuit those two cases to avoid the extra Math.sqrt() calls.

So, all the special cases are:

  • When b^2 - 4ac < 0 or a === 0 && b === 0 which make the answer undefined.
  • When a === 0 (in which case the equation is linear, not quadratic) so the answer is -c / b.
  • When c === 0 which makes 4ac === 0 so it's just -b / a and 0.
  • When b^2 - 4ac === 0 in which case the answer is just -b / (2 * a)

Using a combination of Ruud's suggestion and a fixed version of Joanvo's suggestion, it will pass with only 4 Math.sqrt() calls with this:

function solveQuadratic(a, b, c) {
    var delta = (b * b) - (4 * a * c), sqrt;
    if ((delta < 0) || ((a === 0) && (b === 0))) {
        return undefined;
    } else if (a === 0) {
        return [-c / b];
    } else if (c === 0) {
        return b === 0 ? [0] : [-b / a, 0];
    } else if (delta == 0) {
        return [-b / (2 * a)];
    } else {
        sqrt = Math.sqrt(delta);
        return [(-b - sqrt) / (2 * a), (-b + sqrt) / (2 * a)];
    }
}

Here's a version that builds on the above version and adds the cache from Juan's answer. In the initial standard test, this reports only one Math.sqrt() operation.

function solveQuadratic(a, b, c) {
    var delta = (b * b) - (4 * a * c), sqrt;
    if ((delta < 0) || ((a === 0) && (b === 0))) {
        return undefined;
    } else if (a === 0) {
        return [-c / b];
    } else if (c === 0) {
        return b === 0 ? [0] : [-b / a, 0];
    } else if (delta == 0) {
        return [-b / (2 * a)];
    } else {
        sqrt = sqrt2(delta);
        return [(-b - sqrt) / (2 * a), (-b + sqrt) / (2 * a)];
    }
}

var sqrt2 = (function() {
    var cache = {0:0, 1:1, 4:2, 9:3};
    return function(x) {
        if (cache.hasOwnProperty(x)) {
            return cache[x];
        } else {
            var result = Math.sqrt(x);
            cache[x] = result;
            return result;
        }
    }
})();

Upvotes: 2

Ruud Helderman
Ruud Helderman

Reputation: 11018

You should add a shortcut for cases where the discriminant is zero.

...
else if (b*b == 4*a*c) return [-b / (2*a)];
...

Upvotes: 1

Joanvo
Joanvo

Reputation: 5817

Add a case for when c is zero:

....
var sqrt = c==0?Math.abs(b):Math.sqrt(b*b - 4*a*c);
....

[Edit]

Also, to pass all the tests, your solution needs parenthesis when dividing here:

xVals.push((-b - sqrt)/(2*a));
xVals.push((-b + sqrt)/(2*a));

Upvotes: 3

Ruan Mendes
Ruan Mendes

Reputation: 92274

An easy way is to use memoization . Use a closure to keep a static list of values used so you don't call Math.sqrt for values you've already calculated

var cachingSqrt = (function() {
    var inputs = {};
    return function(val) {
        if (inputs.hasOwnProperty(val)) {
            return inputs[val];
        } else {
            return inputs[val] = Math.sqrt(val);
        }
    }
})();

A generalization of this process would be 

function createCachedResults(fn, scope) {
    var inputs = {};
    return function(val) {
        if (inputs.hasOwnProperty(val)) {
            return inputs[val];
        } else {
            return inputs[val] = fn.call(scope, val);
        }
    }
}

cachingSqrt  = createCachedResults(Math.sqrt, Math);

And you could use it like

var cachingSquareRoot = createCachedResults(Math.sqrt, Math);
function solveQuadratic(a, b, c) {
    if ((4*a*c > b*b) || ((a === 0) && (b === 0))) { 
        return undefined;
    }
    else if (a === 0) {
         return [-c/b];
    } else {
        var xVals = [];
        var sqrt = cachingSquareRoot(b*b - 4*a*c);
        xVals.push((-b - sqrt)/2*a);
        xVals.push((-b + sqrt)/2*a);
        if (xVals[0] === xVals[1]) { 
            xVals.pop();
        }
        return xVals;
    }
}

Upvotes: 2

Related Questions