1
$\begingroup$

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'.)

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\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
    Commented Dec 30, 2009 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
    Commented Dec 30, 2009 at 2:11

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .