I'm trying to build a language compiler, but have come across a math-specific problem when implementing addition between integral types.

I have n integers int_1 to int_n where each number has an inclusive minimum, inclusive maximum and guaranteed values that it is unequal to (the exclusions). These exclusions are guaranteed to be in between minimum and maximum, and not equal to either of those.

For example, if int_1 had a minimum of 5, maximum of 10 and exclusions of {7, 8}. that would mean it is guaranteed to be equal to one of: {5, 6, 9, 10}.

Let's say int_2 had a minimum of 1, maximum of 3 and exclusions of {}. It is guaranteed to be equal to any one of {1, 2, 3}.

Finally, let's call int_sum the number equal to int_1 + int_2. int_sum has a minimum of 6 (5 + 1), maximum of 13 (10 + 3) and a set of exclusions.

My question is how to determine this set of exclusions. To generalize past the case of adding two integers: the minimum of the sum of those n integers is all their minimums added together. The maximum of that sum is all their maximums together. How do I calculate the set of exclusions for the sum of those integers, considering that each of summed integers has its own minimum, maximum and set of exclusions (either empty or non-empty)?

  • $\begingroup$ You are not talking about Integers for they have set values. $\endgroup$ – William Elliot May 29 at 5:58
  • $\begingroup$ @WilliamElliot What type of problem does this correspond to when considered as manipulating a bunch of sets? $\endgroup$ – Mario Ishac May 29 at 6:53

The values the sum can take can efficiently be represented using generating functions. A variable that can take values in a set $S$ can be represented by the generating function $\sum_{k\in S}x^k$, and then the sum of variables that can take values in sets $S_i$ can be represented by the product

$$ \prod_i\sum_{k\in S_i}x^k $$

and can take exactly the values $n$ for which the coefficient of $x^n$ in this product is non-zero.

To make this computationally efficient, you can form the product one factor at a time and retain only the information whether the coefficients are zero or not. This corresponds to forming the sum of the variables one variable at a time and retaining the information which values the partial sum can take; the multiplication corresponds to trying out all combinations of summands in the factors.

In your example for the sum of two variables, the result is

$$ (x^5+x^6+x^9+x^{10})(x^1+x^2+x^3)=x^6+2x^7+2x^8+x^9+x^{10}+2x^{11}+2x^{12}+x^{13}\;, $$

so in this case the sum can take any value from $6$ to $13$ without any exclusions.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.