Optimising Javascript

Question

I was given a quiz and I had gotten the answer wrong and It's been bugging me ever since so I thought I'd ask for your thoughts

I needed to optimise the following function

function sumOfEvenNumbers(n) {
    var sum = 0;
    for(let i = 2; i < n;i++){
      if(i % 2 == 0) sum += i;
    }
    return sum;
 }

 console.log(sumOfEvenNumbers(5));

I came up with

function sumOfEvenNumbers(n) {
    var sum = 0;
    while(--n >= 2) sum += n % 2 == 0? n : 0
    return sum;
}

console.log(sumOfEvenNumbers(5));

What other ways were there?

Would help if you explained the point of the function rather than expecting us to know. — j08691, Apr 27 '17 at 18:27
Note that currently the two functions don't even give identical answers. — Etheryte, Apr 27 '17 at 18:31
I thought the *name* of the function pretty clearly identified what it did: Return the sum of all the even numbers less than some limit. — Martin Bonner supports Monica, Apr 27 '17 at 18:34
This question is classic too broad. "Give me every possible other way to do this function". It *might* be okay on [codereview.se], but even there you'd need to define what you're trying to improve. — Heretic Monkey, Apr 27 '17 at 18:39
@MikeMcCaughan would it be possible to move this over or should I delete this question and go over to this section? — Kendall, Apr 27 '17 at 18:42
I don't have enough knowledge about that site to say whether this should go over there or not. I'd read their help center and see if it's on topic before doing anything. — Heretic Monkey, Apr 27 '17 at 18:53
I'm voting to close this question as off-topic because it is not a programming question, but a math question. — , Apr 29 '17 at 12:29

score 3 · Answer 1 · answered Apr 27 '17 at 18:33

3

Sum of n numbers:

var sum = (n * (n+1)) / 2;

Sum of n even numbers:

var m = Math.floor(n/2);
var sum = 2 * (m * (m+1) /2);

answered Apr 27 '17 at 18:33

NS0

6,016
1
15
14

Isn't `2 * (m * (m+1) / 2)` exactly the same as `m * (m+1)`? – Apr 29 '17 at 12:31

ibrahim mahrir · Accepted Answer · 2017-04-27T18:45:43.043

3

It's a bit of a math question. The sum appears to be the sum of an arithmitic sequence with a common difference of 2. The sum is:

sum = N * (last + first) / 2;

where N is the number of the numbers in the sequence, last is the last number of those numbers, and first is the first.

Translated to javascript as:

function sumOfEvenNumbers(n) {
    return Math.floor(n / 2) * (n - n % 2 + 2) / 2;
}

Because the number of even numbers between 2 and n is Math.floor(n / 2) and the last even number is n - n % 2 (7 would be 7 - 7 % 2 === 6 and 8 would be 8 - 8 % 2 === 8). and the first is 2.

edited Apr 27 '17 at 18:45

answered Apr 27 '17 at 18:37

ibrahim mahrir

31,174
5
48
73

1

Why Math.floor in one half, and n-n%2 in the other? – Martin Bonner supports Monica Apr 27 '17 at 18:42
@MartinBonner Because if `n` is `15` then `Math.floor(n / 2)` will be `7` and `n - n % 2` will be `14`. – ibrahim mahrir Apr 27 '17 at 18:44
@ibrahim mahir I myself did not get this solution for Martin Bonner's exact same reason – Kendall Apr 27 '17 at 18:44

score 2 · Answer 3 · edited May 23 '17 at 12:26

You can compute these sums using an arithmetic sum formula in constant time:

// Return sum of positive even numbers < n:
function sumOfEvenNumbers(n) {
  n = (n - 1) >> 1;
  return n * (n + 1);
}

// Example:
console.log(sumOfEvenNumbers(5));

Above computation avoids modulo and division operators which consume more CPU cycles than multiplication, addition and bit-shifting. Pay attention to the limited range of the bit-shifting operator >> though.

See e.g. http://oeis.org/A002378 for this and other formulas leading to the same result.

Martin Bonner supports Monica · Answer 4 · 2017-04-27T18:46:08.950

1

First thing is to eliminate the test in the loop:

function sumOfEvenNumbers(n) {
   var sum = 0;
   var halfN= Math.floor(n/2);
   for(let i = 1; i < n/2;i++) {
      sum += i;
   }
   return sum * 2;
}

Then we can observe that is just calculating the sum of all the integers less than a limit - and there is a formula for that (but actually formula is for less-equal a limit).

function sumOfEvenNumbers(n) {
   var halfNm1= Math.floor(n/2)-1;
   var sum = halfNm1 * (halfNm1+1) / 2;
   return sum * 2;
}

And then eliminate the division and multiplication and the unnecessary addition and subtraction:

function sumOfEvenNumbers(n) {
   var halfN= Math.floor(n/2);
   return (halfN-1) * halfN;
}

edited Apr 27 '17 at 18:46

answered Apr 27 '17 at 18:31

Martin Bonner supports Monica

28,528
3
51
88

Sum of even numbers is the OP problem I think ;) – Tushar Gupta Apr 27 '17 at 18:33
@Tushar I changed the function name while he was editing – Kendall Apr 27 '17 at 18:34
2

OK, so were both downvotes for the name not matching the new name? – Martin Bonner supports Monica Apr 27 '17 at 18:38

bcherny · Answer 5 · 2017-04-27T20:04:00.140

1

Your solution computes in linear (O(N)) time.

If you use a mathematical solution, you can compute it in O(1) time:

function sum(n) {
  let half = Math.ceil(n/2)
  return half * (half + 1)
}

edited Apr 27 '17 at 20:04

answered Apr 27 '17 at 18:34

bcherny

3,072
2
27
35

2

where is variable `w` from? – Nina Scholz Apr 27 '17 at 18:35
2

Typo - should be 2. – bcherny Apr 27 '17 at 18:37
1

Given an argument of 2, the original would return 0. You return 2. I *hate* off-by-one errors. – Martin Bonner supports Monica Apr 27 '17 at 18:43
Updated to use `Math.ceil` instead. – bcherny Apr 27 '17 at 20:04
@bcherny : Using `Math.ceil` doesn't fix it. An input of 2 *still* returns 2 (rather than 0). – Martin Bonner supports Monica May 02 '17 at 07:00

Egor Stambakio · Answer 6 · 2017-04-27T22:38:22.370

0

Because the question is tagged ecmascript-6 :)

const sumEven = x => [...Array(x + 1).keys()].reduce((a, b) => b % 2 === 0 ? a + b : a, 0);

// set max number

console.log(sumEven(10));

edited Apr 27 '17 at 22:38

answered Apr 27 '17 at 18:46

Egor Stambakio

17,836
5
33
35

Optimising Javascript

6 Answers6