Update based on Michael's answer (thanks again!) - Can the LLL or PSLQ algorithms provide a (knowably - i.e. not just incidental) unique solution for the set of integer multiplicative factors? Are there other algorithms (perhaps with worse run-time complexities) that can?

Imagine that one has a set of 'n' finite-precision real numbers - (r_1, r_2, ..., r_n), each with an associated positive integer multiplicative factor, (i_1, i_2, ..., i_n). Here, one only has access to the values in the set of real numbers, as well as the sum of the real numbers multiplied by their corresponding multiplicative factors, 'S', i.e. - Sum(i_1*n_1, i_2*n_2, ..., i_n*r_n).

What's the most efficient way to test that the sum of a particular set of real numbers will (or, obviously, will not) always allow us to extract a unique solution for the set of integer multiplicative factors? Or to find/do this with fewest restrictions on the values of the integer multiplicative factors?

In the case that this has a very simple answer, apologies.

(Edit - Changed "each with an associated "set of" positive integer multiplicative factors" --> "each with an associated positive integer multiplicative factor". One finite-precision real number 'r_k' has one integer multiplicative factor 'i_k'.)


You want integer relation algorithms, such as the LLL algorithm.

  • $\begingroup$ Michael - thank you! However, from reading the description, I am not sure that the LLL or PSLQ algorithm will provide a solution that is unique? Can we insure that there is no 'lost information' for integer multiplicative factors from the summation operation? $\endgroup$ – Richard Dec 30 '09 at 2:04
  • $\begingroup$ I don't know; I just know the names of the algorithms, I haven't actually used them. Sorry I can't be of more help. $\endgroup$ – Michael Lugo Dec 30 '09 at 2:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.