Number of set bits in multiple

[preda]

I have a new strange problem:

Given a number "m", let's say random, thus has equal probability for its bits (in binary representation) of being 0 or 1. So in average it has log2(m)/2 1-bits.

How can I produce a multiple of m that has significantly less 1-bits in its binary representation?

The slow way would be to iterate over multiples m*k (for k in [1..N]), and select the one with the lowest number of set bits. But it seems to me that this produces a reduction of about
log2(N) 1-bits, thus this method is inefficient.

Do you know a trick for getting a multiple with a low count of set-bits?

Thanks!

[axn]

You only need to consider odd multipliers.

You can also consider multipliers of the form Mod(m, 2^n)^-1 (for this to work, m should be odd -- but that shouldn't be a problem).

[science_man_88]

Originally Posted by preda

Do you know a trick for getting a multiple with a low count of set-bits?

Thanks!

Avoid power of two multiples, is one trick, they all have the same as the original number.

[preda]

Originally Posted by axn

You only need to consider odd multipliers.

You can also consider multipliers of the form Mod(m, 2^n)^-1 (for this to work, m should be odd -- but that shouldn't be a problem).

Yes, "m" is odd, and yes, only odd multipliers considered.

By

Mod(m, 2^n)^-1

, you mean: find x such that (m * x) % 2^n == 1 ?
But if such x has about n bits, then this technique just shifts the 1-bits up, but does not necessarily remove them; so how does this help?

[axn]

Originally Posted by preda

Yes, "m" is odd, and yes, only odd multipliers considered.

By , you mean: find x such that (m * x) % 2^n == 1 ?
But if such x has about n bits, then this technique just shifts the 1-bits up, but does not necessarily remove them; so how does this help?

You can vary n from 1 .. bitcount(m). The multiplier has the property that LSB of the product is a pattern 0000...001 (n-1 zeroes and a 1). You still have to search and see if something gives a good result; there are no guarantees.

You can combine the two approaches and only search multipliers whose lowest n bits are the result of m^-1 (mod 2^n). n=1 is just all the odd multipliers, so you'll have to pick a higher one -- not sure how to go about selecting an n.

[preda]

Originally Posted by axn

You can vary n from 1 .. bitcount(m). The multiplier has the property that LSB of the product is a pattern 0000...001 (n-1 zeroes and a 1). You still have to search and see if something gives a good result; there are no guarantees.

You can combine the two approaches and only search multipliers whose lowest n bits are the result of m^-1 (mod 2^n). n=1 is just all the odd multipliers, so you'll have to pick a higher one -- not sure how to go about selecting an n.

Yes. It's just that I don't want to search "systematically" because it's too slow, let me explain.
Let's say "m" has 1M bits, with 50% 1-bits in average. Let's say I want to reduces the number of 1-bits from 50% to 25%, that would mean I need a reduction of about 250K bits.

Now, choosing the better between 2 multipliers reduces 1bit. For each additional bit, I need to double the search space. So to cut about 250K bits I'd need to check 2^250K multipliers, not practical.

I was thinking if anything more direct can be used.

[R. Gerbicz]

Originally Posted by preda

I have a new strange problem:

Given a number "m", let's say random, thus has equal probability for its bits (in binary representation) of being 0 or 1. So in average it has log2(m)/2 1-bits.

How can I produce a multiple of m that has significantly less 1-bits in its binary representation?

The slow way would be to iterate over multiples m*k (for k in [1..N]), and select the one with the lowest number of set bits. But it seems to me that this produces a reduction of about
log2(N) 1-bits, thus this method is inefficient.

Basically the real reduction for a "random" m value is much larger, fix say N=1024, then by large probability you could reduce the number of bits by sqrt(log2(m)) in k*m.

I see that this is compression problem and it is a hopeless effort to reach even a tiny compression for (general) large numbers, see https://en.wikipedia.org/wiki/Kolmogorov_complexity (compression section). Ofcourse for special numbers we can reach a great compression, for example for n=2^p-1.

[preda]

Originally Posted by R. Gerbicz

Basically the real reduction for a "random" m value is much larger, fix say N=1024, then by large probability you could reduce the number of bits by sqrt(log2(m)) in k*m.

I don't understand. Could you explain in more detail please?

I see that this is compression problem and it is a hopeless effort to reach even a tiny compression for (general) large numbers, see https://en.wikipedia.org/wiki/Kolmogorov_complexity (compression section). Ofcourse for special numbers we can reach a great compression, for example for n=2^p-1.

Yes, the compression view is useful, and shows the limits of what can be achieved.

I think I can show that, for any "m", there exists a multiple that has at most 2 bits set, and this without contradicting the compression facts. The drawback is that the number of bits in such a number would be of the order of "m".

[preda]

Originally Posted by preda

I think I can show that, for any "m", there exists a multiple that has at most 2 bits set, and this without contradicting the compression facts. The drawback is that the number of bits in such a number would be of the order of "m".

It goes like this:
Given m, let's assume odd for simplicity.
Let k = log2(m) +1, the number of bits in "m",
Let d = 2^k % m,
Let c = m - d,
then 2^k + c is a multiple of m, and has nb. of 1-bits equal to 1 + nb-1-bits(c).
Iterate:
c(i) = (2^i * c) % m,
this series eventually reaches 1. So there is a value p, where
(2^p * c) % m == 1,
and 2^(k+p) + 1 is a multiple of m.

[R. Gerbicz]

Originally Posted by preda

I don't understand. Could you explain in more detail please?

In the range [0,2^L) the number of bits of integers follow a normal distribution with L/2 mean and with c*sqrt(L) variance. So most of the numbers has number of bits in [L/2-c1*sqrt(L),L/2+c1*sqrt(L)] interval, if we suppose that the same is true for k*m then with large probability we can gain a reduction by sqrt(L) bits. (reaching with small say k<1024 in most of the cases).

Originally Posted by preda

I think I can show that, for any "m", there exists a multiple that has at most 2 bits set.

m=7 is the first counter-example, because there is no x for that 2^x+1==0 mod 7.

[CRGreathouse]

Originally Posted by preda

I think I can show that, for any "m", there exists a multiple that has at most 2 bits set

All multiples of 1048575 have at least 20 bits set. See
http://matwbn.icm.edu.pl/ksiazki/aa/aa38/aa3825.pdf
http://list.seqfan.eu/pipermail/seqf...er/003267.html
A005360, A125121, A086342.