Efficient method to find a pair that sum to a given value in a list in matematica style

Question

Given an array nums and an number target, find all pairs in array whose sum is equal to target.

A simple method is to generate all possible pairs and compare the sum of every pairs with target,

obviously, this is an inefficient method

SeedRandom[1];
nums = Union@Round[RandomReal[20, 10^3], 0.001];
target = 5;

Select[Subsets[nums, {2}], Total[#] == target  &] // AbsoluteTiming

{0.846554, {{0.362, 4.638}, {0.671, 4.329}, {1.402, 3.598}, {1.561, 3.439}}}

A better way is to use a hash table

dict = Association@Table[nums[[i]] -> i, {i, Length@nums}];
Do[With[{n = nums[[i]]}, 
  If[KeyExistsQ[dict, target - n] && n < target - n, 
   Print[{n, target - n}]]], {i, Length@nums}]

I want to know if there is a more concise and efficient way to do it in Mathematica.

Additional

The above data is just for the convenience of testing, the real data has 16-bit machine accuracy,

What I really care about is not just the sum of two numbers, it can also be other binary operations,

For example, the ratio of two numbers is close to 2.

target = 1/2;
error = 10^-10.;
Select[Subsets[nums, {2}], Abs[Divide @@ # - target] < error &] // AbsoluteTiming

{0.480564,{{0.342,0.684},{0.469,0.938},{0.671,1.342},{0.914,1.828},{1.104,2.208},{1.12,2.24},{1.335,2.67},{1.993,3.986},{2.564,5.128},{2.642,5.284},{2.852,5.704},{3.372,6.744},{4.161,8.322},{4.565,9.13},{4.903,9.806},{4.921,9.842},{5.349,10.698},{6.011,12.022},{6.286,12.572},{6.446,12.892},{6.507,13.014},{7.2,14.4},{7.662,15.324},{8.828,17.656},{8.853,17.706},{8.975,17.95},{9.147,18.294}}}

So I hope there is a more general way.

Updated

For summation, I have thought of a good way

GatherBy[nums, Sort@Round[{#, target - #}, 10^-10.] &] //
  Select[Length@# > 1 &] // AbsoluteTiming

For the ratio of two numbers, I have no ideas yet.

Answer 1

This might not be perfect "Mathematica style" because it uses Compile and procedural programming. But it is the fastest that I have managed to come up with so far:

cf = Compile[{{nums, _Real, 1}, {target, _Real}, {tol0, _Real}},
   Block[{bag, counter, a, x, y, j, tol},
    tol = Ramp[tol0];
    bag = Internal`Bag[Most[{0.}]];
    a = Sort[nums];
    j = Length[a];
    y = Compile`GetElement[a, j];
    Do[
     x = Compile`GetElement[a, i];
     While[j >= i && x + y > target + 0.5 tol,
      y = Compile`GetElement[a, --j];
      ];
     While[j >= i && Abs[x + y - target] <= tol,
      Internal`StuffBag[bag, x];
      Internal`StuffBag[bag, y];
      y = Compile`GetElement[a, --j];
      ];
     , {i, 1, Length[a]}];
    Partition[Internal`BagPart[bag, All], 2]
    ],
   CompilationTarget -> "C",
   RuntimeOptions -> "Speed"
   ];

Now:

pairs = cf[nums, target, 1. 10^-8]; // RepeatedTiming

7.78*10^-6

The complexity is dominated by the Sort and depends on which sorting algorithm is employed. For example, a quicksort would use $O(n \, \log(n))$ time on average where $n$ is the length of the list num. The rest of the algorithm (the Do loop) has complexity $O(n)$

Answer 2

IntegerPartitions is very fast but only works with rational numbers, so we need to round to $1/1000$ instead of $0.001$:

SeedRandom[1];
nums = Union@Round[RandomReal[20, 10^3], 1/1000];
target = 5;

IntegerPartitions[target, {2}, nums] // AbsoluteTiming
(*    {0.004219, {{2319/500, 181/500}, {4329/1000, 671/1000},
                  {1799/500, 701/500}, {3439/1000, 1561/1000}}}    *)

As for comparing the ratio of two numbers, you can extend the above to using the rounded logarithms of the numbers.