Easy numbers

Some numbers are easier to work with than others, especially for computer arithmetic—and even more so with weak processors. So let’s have a look at easy numbers that we can sometimes exploit to get faster code.

Let’s first define what is an easy number:

Definition. A number is k-easy if it has exactly k one bits in its binary representation.

Let’s say that 1 is trivially easy. More so that in many circumstances we can just ignore it (multiplying or dividing by one doesn’t change the expression), and adding or subtracting one is supposed to be inexpensive. In general, we will consider a number to be easier than another if it has fewer 1 bits than the other; and the fewer the bits, the better (for a reason we’ll explain in a moment).

The first few 1-easy numbers are 1, 2, 4, 8, 16, 32, 64, … the powers of two.

The first few 2-easy numbers are 3, 5, 6, 9, 10, 12, 17, 18, 20, 24,…

3-easy numbers are 7, 11, 13, 14, 19, 21, 22,…

4-easy numbers are 15, 23, 27, 29, 30, 39,…

etc.

*
* *

The basic supposition (and motivation) behind easy numbers is that addition, subtraction, and shifts are fast, while multiplications and divisions are expensive. That’s not always exactly true, because even ATMEL chips sports 2-cycle multiplies—yet don’t have a division instruction.

Multiplying can always be reduced to a sum of shifts. Let a and b be to integers, of which only b is easy. We can rewrite the product as:

a\times{b}=a(2^{k_2}+2^{k_1}+2^{k_0})

=a2^{k_2}+a2^{k_1}+a2^{k_0}

which can be written as

int result=(a<<k2)+(a<<k1)+(a<<k0);

If shifts are expensive and your compiler doesn’t already do this, you can re-write it as

int t=a<<k0;
int result=t;
t<<=(k1-k0);
result+=t;
t<<=(k2-k1-k0);
result+=t;

However, the compiler will have the last word. On G++ 5.x, the above with b=19=2^4+2^1+2^0 just generates:

minim1(int a):
  % edi is first param
  % eax return value
  imul eax, edi, 19
  ret

*
* *

Division is a bit trickier, but can be done in much the same way. A division, like \frac{a}{b} can be rewritten as a product, a\frac{1}{b}. The fraction \frac{1}{b} may, or may not be an easy number. While b=19=2^4+2^1+2^0 is an easy number, \frac{1}{19}=0.0000110101111\ldots clearly isn’t. Still, we can rewrite it as:

\displaystyle \frac{1}{19}=2^{-5}+2^{-6}+2^{-8}+2^{-10}+\cdots

and rewrite

\displaystyle \frac{a}{19}=a(2^{-5}+2^{-6}+2^{-8}+2^{-10}+\cdots)

=a2^{-5}+a2^{-6}+a2^{-8}+a2^{-10}+\cdots

That is,

int div19naif(int a)
 {
  return (a>>5)+(a>>6)+(a>>8);
 }

Of course, \frac{1}{19} is especially evil for that purpose. The first power is 2^{-5}, and this will cause large rounding error for small dividends. You could prescale everything to get better accuracy:

int div19(int a)
 {
  a<<=16;
  return
   ( (a>>5)
     +(a>>6)
     +(a>>8)
     +(a>>10)
     +(a>>11)
     +(a>>12)
     +(a>>13)
     +(a>>16)
     )>>16;
 }

But that kind of kills its usefulness.

*
* *

Counting the number of bits could be done at compile-time, and unbeknownst to the user. If you still need to know the numbers of 1-bits in a number:

// solution a bit more complicated than wished as
// the nested type std::make_unsigned<T> cannot
// be automagically deduced
//
// http://eel.is/c++draft/temp.deduct.type#5.1
//
template <typename T>
constexpr int __one_bits(typename std::make_unsigned<T>::type u)
 {
  return u ? (u&1)+__one_bits<T>(u>>1) : 0;
 }

template <typename T>
constexpr int one_bits(T u) { return __one_bits<T>(u); }

int main()
 {
  for (int k=1;k<7;k++)
   {
    std::cout << k << ": ";
    for (int i=0;i<128;i++)
     if (one_bits(i)==k)
      std::cout << i << " ";
    std::cout << std::endl;
   }
  return 0;
 }

It outputs:

1: 1 2 4 8 16 32 64 
2: 3 5 6 9 10 12 17 18 20 24 33 34 36 40 48 65 66 68 72 80 96 
3: 7 11 13 14 19 21 22 25 26 28 35 37 38 41 42 44 49 50 52 56 67 69 70 73 74 76 81 82 84 88 97 98 100 104 112 
4: 15 23 27 29 30 39 43 45 46 51 53 54 57 58 60 71 75 77 78 83 85 86 89 90 92 99 101 102 105 106 108 113 114 116 120 
5: 31 47 55 59 61 62 79 87 91 93 94 103 107 109 110 115 117 118 121 122 124 
6: 63 95 111 119 123 125 126 

2 Responses to Easy numbers

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: