Square Root
This example demonstrates how to compute the square root of $c=2$ using large integers represented by qbpp::cpp_int. Let $s = 10 ^{20}$ be a fixed integer. Since QUBO++ cannot handle real numbers directly, we compute $\sqrt{cs^2}$ instead of $\sqrt{c}$. From the following relation,
we can obtain an approximation of $\sqrt{c}$ with 20 decimal-digit precision.
Formulation of the square root computation
We define a native integer variable $x$ that takes values in the range $[s, 2s]$. We then formulate the problem using the following equation:
\[\begin{aligned} x ^ 2 &= cs ^ 2 \end{aligned}\]Declaring this equality as a constraint with qbpp::cons() makes the energy the square of the violation, that is:
By finding the value of $x$ that minimizes this expression, we obtain an approximation of the square root of $c$ with 20 decimal-digit precision. Since $x$ is not expanded into binary variables, the constraint stays a quadratic expression in $x$.
QUBO++ program
The following QUBO++ program constructs an expression based on the above idea and solves it using the Easy Solver:
#define INTEGER_TYPE_CPP_INT
#include <qbpp/qbpp.hpp>
#include <qbpp/easy_solver.hpp>
int main() {
const int c = 2;
auto s = qbpp::integer("100000000000000000000");
auto x = s <= qbpp::int_var("x") <= c * s;
auto f = qbpp::cons(x * x == c * s * s);
f.simplify();
auto solver = qbpp::EasySolver(f);
auto sol = solver.search({{"time_limit", 10.0}});
auto xv = sol(x);
std::cout << "sqrt(" << c << ") ≈ " << xv << " / " << s << std::endl;
std::cout << " = " << (xv / s) << "." << (xv % s) << std::endl;
std::cout << "Energy = " << sol.energy() << std::endl;
}
Since the values of the expression reach about $10^{40}$ and do not fit in 64-bit integers, we define INTEGER_TYPE_CPP_INT before including the header, which sets both coeff_t and energy_t to cpp_int (arbitrarily large integers). The constant s, the native integer variable x, and the expression f are defined according to the formulation described above. The Easy Solver is executed with a time limit of 10 seconds.
The integer solution xv is split into its quotient xv / s and remainder xv % s, which are joined by a decimal point to obtain the decimal representation. Only cpp_int integer arithmetic is used, so no precision is lost by converting to double. Note, however, that leading zeros of the remainder are lost when it has fewer than 20 digits (for example, for $c=26$, $\sqrt{26}=5.0990\ldots$ would be printed as 5.990...). In general, the remainder must be zero-padded to 20 digits with std::setw(20) << std::setfill('0') (from <iomanip>). In this example with $c=2$, the remainder has exactly 20 digits, so this is not a problem.
This program produces the following output:
sqrt(2) ≈ 141421356237309504880 / 100000000000000000000
= 1.41421356237309504880
Energy = 2281431565136320033809509291861647360000
We can confirm that the Easy Solver outputs the correct approximation:
\[\sqrt{2}\approx 1.41421356237309504880\]Note that the reported energy value is not zero, and the equality constraint is not satisfied exactly. This is simply because there is no exact integer solution to the equality. Instead, the solver finds a solution that minimizes the error of the equality constraint. The energy value shown in the output corresponds to the square of this error. Since the error is minimized, the resulting value of $x$ represents an approximation of the square root.