- Ah, this seems a little different from your last problem statement. It

seemed last time you wanted to make sure all numbers in the interval

[0,c] were covered, where c was the largest difference between elements

from A and B. Here, c can be less than n*m so you have to do O(n*m)

work to find it.

However, with the new statement, you are looking to cover the entire

range [0, n*m], which contains (n*m + 1) elements, and there are only

n*m total differences (in absolute value) between the two sets. So, we

will need another clarification to proceed on this one. Do you want to

get rid of 0, or n*m, or some other value in the range?

-David C.

Kaveh wrote:>

>

> Let A and B be two sets of n and m positive integers, respectively. We

> want to know if {(an element of A) - (an element of B)} covers the

> entire interval of [0,nm] or not, through an algorithm running faster

> than O(nm). (Something like fast fourier transform for fast

> multiplication).

>

> Any function that gives a yes/no output is good enough.

>

> Appreciating your feedbacks.

>

> Kaveh - Ooops - I forgot that 'enter' doesn't take me to the next field in this

browser...

--- Kaveh <kaveh_vejdani@...> wrote:> Good news: YES! Fast multiplication finally worked.

Nope, as the FFT needs to be of length nm, and thus cost O((nm)^(1+eps))

>

> Bad news: Subtraction still doesn't work.

>

> > However, the real question is why you're trying to use this

> > technique at all? It's got the least favourable Big-Oh of any of

> > the techniques mentioned.

>

> None of the techniques so far have answered my question. They either

> run in O(nm) or don't show how the interval [0,nm-1] will be

> covered. FFT at least gives a chance to bypass the redundant

> intermediates, if it works at all. Makes sense?

> (from your message of Nov 12:)

But I'm repeating myself, it seems.

> > If you create a bitmap representing each set, FFT those, and

> > convolve, and IFFT, then you would have your answer.

> > The problem is that the FFTs would be of length nm, and thus of

> > cost O(nm^(1+eps)).

> Assuming that you were talking of the subtraction problem (O(nm)),

The polynomial arithmetic example I provided was such an example.

> please provide an example of your suggested process in work.

Phil

() ASCII ribbon campaign () Hopeless ribbon campaign

/\ against HTML mail /\ against gratuitous bloodshed

[stolen with permission from Daniel B. Cristofani]

____________________________________________________________________________________

Sponsored Link

Mortgage rates near 39yr lows.

$510k for $1,698/mo. Calculate new payment!

www.LowerMyBills.com/lre