-3

Given a set S of n natural numbers below 9n/7, how can one establish the number of pairs summing to every number from 0 to 18n/7? (2-combinations, 3 < n)
Let m be the maximum value of elements in S.
If m was n-1, the sequence of counts of pairs summing up to ( 0, 1, … 18n/7 ) would be [ 0, 1, 1, 2, 2, … m/2, m/2, (m+2)/2, m/2, m/2, (m-2)/2, … 2, 1, 1, 0, …, 0 ] for odd n, or [ 0, 1, 1, 2, … (n-2)/2, (n-2)/2, n/2, n/2, n/2, (n-2)/2, (n-2)/2, (n-4)/2, … 2, 1, 1, 0, …, 0 ] for even n.
It isn't too difficult to establish the counts if n is an element of S (and one of the numbers below isn't), as is nesting two loops and just counting the occurrences of each sum - Ο(n²):

How can one establish a histogram of pair sums (much) faster than Ο(n²)?
(Does knowing m < 9n/7 help?
Is it notably harder for 9n/2 < m ((semi-)sparse set)?)

greybeard
  • 2,249
  • 8
  • 30
  • 66
  • I'm having difficulty understanding your question. You may want to try to explain more clearly. – Richard Jan 13 '17 at 09:46
  • @Richard I'd be glad to (be able to). It might be helpful if you pointed out something specific to be unclear. – greybeard Jan 13 '17 at 09:48
  • As I already mentioned, it doesn't seem that the bounds are very helpful to find a fast algorithm. But I really don't know is it possible to avoid fourier transform and get better than O(n log n), or just something better than n^1.5. It is interesting. – Saeed Amiri Jan 13 '17 at 11:47
  • @Spektre, what you are saying makes no sense. After all DFT takes n log n, I really and again really don't see how sorting can help? About your math skill, I think you should ask it in a new thread and more precisely. This comment is the answer to the comment on amit's answer. – Saeed Amiri Jan 14 '17 at 10:11
  • @SaeedAmiri for FFT approach youre right but all of the stuff is important for the non FFT approaches which is all this about... I did not ask for help (just stated so it is clear I could be wrong) – Spektre Jan 14 '17 at 10:39
  • @Spektre, This is what you wrote: "BTW I wanted to do the DFT/NTT approach too but cant make it work ". It means two things: 1. You are eager to use FFT, 2. You don't know how to do it. You also wrote: "I can do the convolution easily (using it for bignum multiplication) but not the modular convolution". Sorry I really don't understand you. – Saeed Amiri Jan 14 '17 at 11:30
  • @SaeedAmiri you need to read the linked QA [ Alternate way to compute product of pairwise sums mod 10^9+7 faster than O(N^2)](http://stackoverflow.com/q/41531391/2521214) for that. btw I just got it to work with NTT and the modular convolution. And also found out what was the problem with my FFT approach. – Spektre Jan 14 '17 at 13:21
  • @Spektre, I don't see how that Q&A is related to advantage of sorting! – Saeed Amiri Jan 14 '17 at 14:36

1 Answers1

1

It can be done in O(nlogn), using Fourier transformation.

First recall that a convolution is defined as:

(h*g)[n] = sum { h[n-i] + f[i] | i in Z }

And note that a convolution on the histogram of the data is exactly what you want. Convolution can be calculated in O(nlogn) using Fourier transform.

This gives the basic following algorithm:

  1. Create histogram with has/tree based map. Let it be h.
  2. using fourier transform to find (h*h).
amit
  • 175,853
  • 27
  • 231
  • 333
  • (:Dang. I thought I skilfully avoided mentioning convolution, as I'm looking for ideas for an [_Alternate_ way to compute product of pairwise sums](http://stackoverflow.com/q/41531391/3789665).:) – greybeard Jan 13 '17 at 10:44
  • @greybeard First, that was not the question... Second, by one more step you simply multiply the pairs needed, which should be efficient using smart exponent algorithm. – amit Jan 13 '17 at 10:48
  • `First, [an Alternate way to compute product of pairwise sums] was not [How can one establish a histogram of pair sums fast]` indeed. Someone even asked a separate question. `Second…` That looks a sketch of the reference approach the question linked above searches alternatives to. – greybeard Jan 13 '17 at 11:33
  • (`Create histogram with [hash]/tree based map` - or do a counting sort, considering there are not much more possible values than there are elements.) – greybeard Jan 13 '17 at 11:35
  • @greybeard, counting sort won't help much, as per fourier transform one does not need it. Also if it was helpful, in the general problem one could first sort in n log n and then do the rest. The bottleneck is not about sorting. But if you want to avoid DFT then just use O(n^1.6) method based on polynomial multiplications. – Saeed Amiri Jan 13 '17 at 11:39
  • @SaeedAmiri: "counting sort" of the elements to establish amit's `h`, not of the sums. – greybeard Jan 13 '17 at 11:45
  • @greybeard, At any moment in the general algorithm you can do a O(n log n) sorting on whatever you want. I don't see any point of counting sort. Actually I don't see how sorting can play any role at all (having n logn algorithm in hand). – Saeed Amiri Jan 13 '17 at 11:53
  • @SaeedAmiri the histogram (counting,or sorting) of `h` is just to speed up the convolution `h*g` as some elements are duplicate so they can be handled as power of a single value lowering the `n` for the `O(n^2)` process. And also working with exponents instead of values is faster for the convolution operation itself because the task this is targeted on is done on modular arithmetics `GF(1000000009)` where is significantly slower to `modmul,modpow` values then combining exponents (which can be done with simple `int` arithmetics directly). – Spektre Jan 14 '17 at 09:16
  • @SaeedAmiri The `m` limit is important so we can do bucket sort/histogram in `O(n)`. BTW I wanted to do the **DFT/NTT** approach too but cant make it work ... I can do the convolution easily (using it for bignum multiplication) but not the modular convolution ... My math skills are not very good in number theory an finite fields so I must have done something wrong somewhere or ignore some theorem ... still trying though :) – Spektre Jan 14 '17 at 09:20