CODEWITHSUNDEEP
algorithm
winhowes
winhowes

Reputation: 8065

My algorithm is too slow

I have an algorithm that for an integer x and a starting integer i such that 1 < i < x the next value of i is computed by i = floor(x / i) + (x mod i). This continues until we reach an i that we've already seen.

In JavaScript (though this question is language agnostic):

function f(x, i) {
    var map = {};
    while(!map[i]) {
        map[i] = true;
        i = Math.floor(x / i) + (x % i); // ~~(x / i) is a faster way of flooring
    }
    return i;
}

I can prove that we will eventually reach an i we've already seen, but I'm wondering:

  1. Is there is a more efficient way of computing the next i?
  2. (More importantly) Is there is a way to compute the nth i without running through the loop n times?

Just to clarify - I know there are faster ways than using JS hash maps for that check, and that flooring can be replaced by integer division in other languages. I have made both of those optimizations, but I left them out to try to make the code easier to understand. Sorry for any confusion.

Thanks in advance!

Upvotes: 2

Views: 416

Answers (1)

MBo
MBo

Reputation: 80197

I think the main time eater - map. It uses some hashing function (probably not simple). If i range is limited by reasonable value, it would better to use bit/boolean array (or Javascript analog)

The second - two divisions. Are floats and integers distinct in Javascript? It is possible to make one integer division, finding modulo with multiplication and subtraction (due to fundamental properties of integer division/modulo definition):

p = x \\ i
i = p + (x - p * i)
or
i = x - (x \\ i) * (i - 1)

Note: integer division in most processors calculates both quotient and residue in the same time

mov eax, 17          //dividend
mov ecx, 3           //divisor
xor edx, edx         //zero
div ecx              //edx:eax pair divide by ecx
//now eax contains quotient 5, edx contains residue (modulus) 2

If you can use asm in C, or have some functions like delphi DivMod, you can make calculations some faster.

Upvotes: 3

Related Questions