Return to Revisions

The Lenstra-Lenstra-Lovasz lattice basis reduction algorithm is what you need. Suppose that your real number is a and you want a quadratic equation with as small coefficients as possible, of which a is nearly a root. Then calculate 1,a,a^2 (to some precision), find a nontrivial integer relation between them, and use the LLL algorithm to find a much better one from the first one. Exactly this example is discussed in the Wikipedia entry on the LLL algorithm, applied to the Golden Section number. And there is a big literature on the algorithm and its many applications. (For higher degree, calculate 1,a,a^2,...,a^n).