vote up 1 vote down
star

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

flag

1 Answer

vote up 2 vote down
check

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

link|flag
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? – Richard Dec 30 at 2:04
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. – Michael Lugo Dec 30 at 2:11

Your Answer

Get an OpenID
or

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