3 ms·

Two quick remarks: > Looking at the code it’s quite obvious 3 and 5 are replaceable with any set of other numbers. What's not obvious to me (I'm not a mathema

by FabHK 7y ago

Two quick remarks: > Looking at the code it’s quite obvious 3 and 5 are replaceable with any set of other numbers. What's not obvious to me (I'm not a mathematician) is that both solutions answer the question correctly when the set of numbers is not pairwise coprime. For example, "Find the sum of all the multiples of 3 or 6 below 1000" is clearly just the same as "Find the sum of all the multiples of 3 below 1000", while the inclusion-exclusion algorithm will probably deliver a different answer. So, the set will need some pre-processing to remove common factors, which will then require adjusting the answers. Next, for the problem "Find the sum of all the multiples of <M numbers> below <N>", the naive algorithm seems to have runtime of about O(NM), while the "sophisticated" algorithm seems to have runtime O(2^M) at least - so, as we increase M (the size of the test set), the "naive" algorithm will soon be faster, or not?

Someone 7y ago
What's not obvious to me (I'm not a mathematician) is that both solutions answer the question correctly when the set of numbers is not pairwise coprime. For example, "Find the sum of all the multiples of 3 or 6 below 1000" is clearly just the same as "Find the sum of all the multiples of 3 below 1000", while the inclusion-exclusion algorithm will probably deliver a different answer. You’re right. The solution for this is to replace “product of n and m” bij “least common multiple of n and m”. So, you would get (using 4 and 6 as an example that’s slightly better than 3 and 6): Number of multiples of either 4 or 6 = Number of multiples of 4 + Number of multiples of 6 - Number of multiples of lcm(4,6) = 12 and yes, if M gets larger enough, the “naive” algorithm can get faster. It will help if you bail out once you have found _a_ divisor, and, if your numbers are ‘large enough’ (1), to do division testing in some specific order (2). (1) what is ‘large’ will be system dependent. In general, once you need bigint’s, but if your CPU doesn’t have a division instruction, it can come earlier. (2) in general, smallest to largest, but if one of your test divisors is a power of 2, move those up front. Also, if you’re forced to use bigint’s, divisors of “2^register size +/- 1 and their factors may be easier (just as testing divisibility by 9 or 11 or 9’s factor 3 is easier in decimal written integers)
- FabHK 7y ago
  > The solution for this is to replace “product of n and m” bij “least common multiple of n and m” Nice, and it works for my example, too: Number of multiples of either 3 or 6 = Number of multiples of 3 + Number of multiples of 6 - Number of multiples of lcm(3,6) = 6 = Number of multiples of 3 Cool. How to extend to more than 2 numbers?
  - deleted 7y ago
    [deleted]
  - jarekkruk 7y ago
    You could do it like in article, so for every nonempty element in powerset (combinations for each length) of those numbers calculate their lcm and add or subtract amount of multiplies of lcm according to length of element. So for A, B, C you have (M-number of multipliers) M(lcm(A)) + M(lcm(B)) + M(lcm(C)) - M(lcm(B,C)) - M(lcm(A,C)) - M(lcm(A,B)) + M(lcm(A,B,C))
kevinventullo 7y ago
The inclusion-exclusion algorithm can be made more efficient by observing that you can stop as soon as the lcm's of your subsets exceed N. That should happen fairly early on assuming e.g. N << 2^M.
- chupasaurus 7y ago
  > you can stop as soon as the lcm's of your subsets exceed N Actually if N < 2 * lcm, because you can't use the fact that the distribution of multiples is the same on (1, lcm) and (k * lcm+1, lcm(k+1)) while you still have to count on (N - N mod lcm + 1, N).

by FabHK 7y ago

Someone 7y ago

What's not obvious to me (I'm not a mathematician) is that both solutions answer the question correctly when the set of numbers is not pairwise coprime. For example, "Find the sum of all the multiples of 3 or 6 below 1000" is clearly just the same as "Find the sum of all the multiples of 3 below 1000", while the inclusion-exclusion algorithm will probably deliver a different answer. You’re right. The solution for this is to replace “product of n and m” bij “least common multiple of n and m”. So, you would get (using 4 and 6 as an example that’s slightly better than 3 and 6): Number of multiples of either 4 or 6 = Number of multiples of 4 + Number of multiples of 6 - Number of multiples of lcm(4,6) = 12 and yes, if M gets larger enough, the “naive” algorithm can get faster. It will help if you bail out once you have found _a_ divisor, and, if your numbers are ‘large enough’ (1), to do division testing in some specific order (2). (1) what is ‘large’ will be system dependent. In general, once you need bigint’s, but if your CPU doesn’t have a division instruction, it can come earlier. (2) in general, smallest to largest, but if one of your test divisors is a power of 2, move those up front. Also, if you’re forced to use bigint’s, divisors of “2^register size +/- 1 and their factors may be easier (just as testing divisibility by 9 or 11 or 9’s factor 3 is easier in decimal written integers)

FabHK 7y ago
> The solution for this is to replace “product of n and m” bij “least common multiple of n and m” Nice, and it works for my example, too: Number of multiples of either 3 or 6 = Number of multiples of 3 + Number of multiples of 6 - Number of multiples of lcm(3,6) = 6 = Number of multiples of 3 Cool. How to extend to more than 2 numbers?
- deleted 7y ago
  [deleted]
- jarekkruk 7y ago
  You could do it like in article, so for every nonempty element in powerset (combinations for each length) of those numbers calculate their lcm and add or subtract amount of multiplies of lcm according to length of element. So for A, B, C you have (M-number of multipliers) M(lcm(A)) + M(lcm(B)) + M(lcm(C)) - M(lcm(B,C)) - M(lcm(A,C)) - M(lcm(A,B)) + M(lcm(A,B,C))

kevinventullo 7y ago

The inclusion-exclusion algorithm can be made more efficient by observing that you can stop as soon as the lcm's of your subsets exceed N. That should happen fairly early on assuming e.g. N << 2^M.

chupasaurus 7y ago
> you can stop as soon as the lcm's of your subsets exceed N Actually if N < 2 * lcm, because you can't use the fact that the distribution of multiples is the same on (1, lcm) and (k * lcm+1, lcm(k+1)) while you still have to count on (N - N mod lcm + 1, N).