以最少的加法和移位乘以常数
Multiplication by constant in fewest adds and shifts
只需使用 Robert Bernstein 的 addition, subtraction and shift. The important part of the procedure is to find the minimal (optimal) sequence of such operations. Using brute force to find the sequence leads to exponential growth of difficulty so various heuristics are used, perhaps the most commonly known is the paper Multiplication by integer constant 就可以将两个数相乘。
Vincent Lefevre 在 Multiplication by an Integer Constant 中给出的乘以 113 的示例：
3x <- x << 1 + x
7x <- 3x << 1 + x
113x <- 7x << 4 + x
我偶然发现了一个非常有趣的 answer，这让我想知道：是否可以使用 Z3（或类似的）来找到将数字乘以给定常数的最小运算符序列？我对所有这些 SAT 和 SMT 都很陌生，所以我不确定它在布尔可满足性问题的背景下是否有意义？
确实可以。但是请注意，问题是 NP-hard。
前段时间我们用一个更一般的问题（多常数乘法）做了一个实验：http://web.ist.utl.pt/nuno.lopes/pubs/mcm-pb10.pdf
基本上结果很令人失望。专用算法要快得多。
只需使用 Robert Bernstein 的 addition, subtraction and shift. The important part of the procedure is to find the minimal (optimal) sequence of such operations. Using brute force to find the sequence leads to exponential growth of difficulty so various heuristics are used, perhaps the most commonly known is the paper Multiplication by integer constant 就可以将两个数相乘。
Vincent Lefevre 在 Multiplication by an Integer Constant 中给出的乘以 113 的示例：
3x <- x << 1 + x
7x <- 3x << 1 + x
113x <- 7x << 4 + x
我偶然发现了一个非常有趣的 answer，这让我想知道：是否可以使用 Z3（或类似的）来找到将数字乘以给定常数的最小运算符序列？我对所有这些 SAT 和 SMT 都很陌生，所以我不确定它在布尔可满足性问题的背景下是否有意义？
确实可以。但是请注意，问题是 NP-hard。
前段时间我们用一个更一般的问题（多常数乘法）做了一个实验：http://web.ist.utl.pt/nuno.lopes/pubs/mcm-pb10.pdf
基本上结果很令人失望。专用算法要快得多。