# Integer Program for Multiplication of Large Numbers

Given two numbers in binary representation $$b_1,b_2$$ and let $$k_1, k_2$$ be the number of digits.

What would be an integer program that models the multiplication of these two numbers? The restriction is that the variables as well as the coefficients of the variables are not allowed to take huge values (that it is still solvable in floating point arithmetic for large numbers).

The integer program needs at least $$k_1+k_2$$ binary variables to model the result of the multiplication.

• Are $b_1$ and $b_2$ constant or variable? Is $2^{k_1+k_2-1}$ considered huge as a coefficient? Jul 7, 2020 at 15:24
• @RobPratt i would be interested in both version. Yes this is really large! I am looking for something that still works for $k_1=100$. Jul 7, 2020 at 16:05
• As a warmup, I recommend considering addition (with binary carryover variables) instead of multiplication. Jul 7, 2020 at 16:32

If the numbers are small enough, you can model the multiplication $$z=xy$$ in a quadratic program, and add the equality $$x = \sum2^i b_i$$ to relate each number $$x$$ to its binary representation.