1
$\begingroup$

I am looking for a function that will take take n inputs and have 1 output, and knowing the 1 output and function you can get back the n inputs, without error and computationally easy in both directions.

For example, the smallest natural number solution to a linear diophantine equation.

ax + by = c

Where x and y are some numbers, likes just say 3 and 5.

304923049049*3 + 2049823483230*5 = 11163886563297

Now given 11163886563297, we can solve

a*3 + b*5 = 11163886563297

This has infinite many solutions to it, but only 1 of them is "smallest". My limited understanding is that finding the smallest solution to a linear diophantine equation is not computationally easy, and has to be done by bruteforce. ( I also think the smallest solution is not even the numbers I picked, bad example but I think you get the point)

My hope is that the function is super fast to calculate both way computationally, and allow for many inputs. Like 100 inputs and get 1 output and from the 1 output get back the 100 inputs.

I understand it probably doesn't exist, but I am looking for good candidates, even some which seem to be the case but havent been proven they are accurate or inaccurate.

$\endgroup$
3
  • 2
    $\begingroup$ Maybe the Cantor pairing function (please see Wikipedia) can serve as a basis. If we combine pairs in parallel it might be acceptably fast. But simple interleaving, though cruder, will likely be far more efficient. $\endgroup$ – André Nicolas Jun 11 '15 at 5:42
  • $\begingroup$ Something reasonably close, but not onto, is to send your $n$ arguments $(a_1,a_2,...,a_n)$ to $2^{a_1}3^{a_2}...p_n^{a_n}$, where $p_n$ is the $n$th prime. Factorization in general is slow, of course, but here we know which factors we want, so the inverse operation just becomes an integer division a linear number of times in the sum of the arguments on the left hand side, or at most $\log_2$ times on the right hand side. $\endgroup$ – Kevin Arlin Jun 11 '15 at 6:14
  • $\begingroup$ Andre please post cantor/interleaving as an answer so I may mark it. $\endgroup$ – ParoX Jul 14 '15 at 4:21
0
$\begingroup$

This question is very related to: https://stackoverflow.com/questions/919612/mapping-two-integers-to-one-in-a-unique-and-deterministic-way

In which @nawfal posts this link: http://szudzik.com/ElegantPairing.pdf which the pairing function is as space-efficient as possible .

$\endgroup$

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.