1

My attempt is to increase the performance of my JavaScript application by finding the bitwise equivalence of x mod 289

My code looks like this: lookupArray[x % 289] and x will always be in the range from 0 to 288, so I don't have to worry about negative numbers.

So basically I have a lookup array of the size 288, so if x goes above 288 it will start again from 0. I could increase the array size and repeat some of the lookup numbers if there's no bitwise equivalence for the number 289, but for some larger number instead. But what number would that be?

If the size of my lookup table was smaller, for example 240, then I would be able to use 255, but that's too low for my case.

Thanks!

Jón Trausti Arason
  • 4,548
  • 1
  • 39
  • 46
  • If the size of the array is 288, your modulo must also be 288. Remember, the indices of an array of size _n_ are from 0 to _n-1_ (in your case: 0–287). – DarkDust Jan 31 '16 at 13:05
  • Also, what makes you think that the modulo operation is your bottleneck? Have you measured? – DarkDust Jan 31 '16 at 13:06
  • I guess I meant length instead of size. There is a big difference for my application, and I have measured it. https://jsperf.com/modulo-vs-bitwise/8 – Jón Trausti Arason Jan 31 '16 at 13:07

2 Answers2

1

As far as I know Bitwise aren't alwasy accurate with the mod operation.

With regards to bitwise optimization, only modulo powers of two can "easily" be done in bitwise arithmetics. Generally speaking, only modulo powers of base b can "easily" be done with base b representation of numbers.

Here is an answer for a similar problem

Community
  • 1
  • 1
Baso
  • 1,354
  • 4
  • 19
  • 41
  • Can you describe what is meant by "only modulo powers of two can "easily" be done in bitwise arithmetics". Because I'm open for a larger number than 289. – Jón Trausti Arason Jan 31 '16 at 13:19
  • Also as far as I understand from the answer that provided above: it means if the number that you want to use in the mod operation is equal to a power of two. Means if your number is x then x = 2^(1,2,3,....etc). if your number is in this form this means it can easily be used with Bitwise for the mod operation. – Baso Jan 31 '16 at 13:38
0

I have one answer to my own question that I'm going to use, if there's no better answer.

Basically I can use any number of power of two minus one, or in other terms 2^n - 1 to replace modulus.

x & (2^n - 1)

I can then use the number 511 for my bitwise operation, but of course then I'd have to increase the size of my array. However with the increased performance it's definitely worth it.

Jón Trausti Arason
  • 4,548
  • 1
  • 39
  • 46