Return to Revisions

The Lenstra-Lenstra-Lovasz (LLL) 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$).