## Re-formulating my question

Expand Messages
• 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
Message 1 of 12 , Nov 11, 2006
• 0 Attachment
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.

Kaveh
• ... The FFT does not do nm work it only does max(n,m) work, as it s a convolution, which throws away large quantities of information compared with what s
Message 2 of 12 , Nov 12, 2006
• 0 Attachment
--- Kaveh <kaveh_vejdani@...> 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.

The FFT does not do nm work it only does max(n,m) work, as it's a convolution,
which throws away large quantities of information compared with what's
available from the nm intermediates from naive term-by-term multiplication.
(which are unnecessary for finding a product, as you only care about the sums
of the intermediates, not their individual values.)

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)). See C&P's PNaCP for such
applications of the FFT.

Note that to fail cover the range, all you need is two terms in each set with
the same difference, i.e. a1-a2=b1-b2. So perhaps looking at possible
differences within each set individually is easier than looking at terms
derived from elements of both sets.

Phil

() ASCII ribbon campaign () Hopeless ribbon campaign
/\ against HTML mail /\ against gratuitous bloodshed

[stolen with permission from Daniel B. Cristofani]

____________________________________________________________________________________
Yahoo! Music Unlimited
Access over 1 million songs.
http://music.yahoo.com/unlimited
• 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
Message 3 of 12 , Nov 12, 2006
• 0 Attachment
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.
>
>
> Kaveh
• Phil, ... I tried this in Matlab, with A=[8 6 0 0] and B=[6 2 0 0], expecting [0 2 4 6], but it didn t work. I got [2 4 0 0] instead. How can I get all the
Message 4 of 12 , Nov 16, 2006
• 0 Attachment
Phil,

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

I tried this in Matlab, with A=[8 6 0 0] and B=[6 2 0 0], expecting [0
2 4 6], but it didn't work. I got [2 4 0 0] instead.

How can I get all the possible differences?

Kaveh
• ... I don t see any bitmaps in the above. Phil () ASCII ribbon campaign () Hopeless ribbon campaign / against HTML mail / against
Message 5 of 12 , Nov 16, 2006
• 0 Attachment
--- Kaveh <kaveh_vejdani@...> wrote:
> Phil,
>
> > If you create a bitmap representing each set, FFT those, and
>
> I tried this in Matlab, with A=[8 6 0 0] and B=[6 2 0 0], expecting [0
> 2 4 6], but it didn't work. I got [2 4 0 0] instead.
>
> How can I get all the possible differences?

I don't see any bitmaps in the above.

Phil

() ASCII ribbon campaign () Hopeless ribbon campaign
/\ against HTML mail /\ against gratuitous bloodshed

[stolen with permission from Daniel B. Cristofani]

____________________________________________________________________________________

Mortgage rates near 39yr lows.
\$420k for \$1,399/mo. Calculate new payment!
www.LowerMyBills.com/lre
• ... Sorry. Does bitmap mean 0/1 representation of the sets? This time I tried: a=[1:64]*0 a(8)=1 a(6)=1 b=[1:64]*0 b(6)=1 b(2)=1 x=fft(a) y=fft(b) But again,
Message 6 of 12 , Nov 17, 2006
• 0 Attachment
>> with A=[8 6 0 0] and B=[6 2 0 0], ...

> I don't see any bitmaps in the above.

Sorry. Does bitmap mean 0/1 representation of the sets?

This time I tried:

a=[1:64]*0
a(8)=1
a(6)=1

b=[1:64]*0
b(6)=1
b(2)=1

x=fft(a)
y=fft(b)

But again, ifft(x-y) gives the same result as a-b. I must be missing
a point again.

Kaveh
• ... Yup. ... Once FFT d you multiply rather than add or subtract. And B s backwards. Multiplying the transformed vectors would tell you which values can be
Message 7 of 12 , Nov 17, 2006
• 0 Attachment
--- Kaveh <kaveh_vejdani@...> wrote:
> >> with A=[8 6 0 0] and B=[6 2 0 0], ...
>
> > I don't see any bitmaps in the above.
>
> Sorry. Does bitmap mean 0/1 representation of the sets?

Yup.

> This time I tried:
>
> a=[1:64]*0
> a(8)=1
> a(6)=1
>
> b=[1:64]*0
> b(6)=1
> b(2)=1
>
> x=fft(a)
> y=fft(b)
>
> But again, ifft(x-y) gives the same result as a-b. I must be missing
> a point again.

Once FFT'd you multiply rather than add or subtract.
And B's backwards. Multiplying the transformed vectors would tell you which
values can be created by summing. For differences do this:

? (x^8+x^6) * (x^(64-6)+x^(64-2)) / x^64
x^6 + x^4 + x^2 + 1

Therefore 6, 4, 2, and 0 can be created as differences {8,6} - {6,2}

Phil

() ASCII ribbon campaign () Hopeless ribbon campaign
/\ against HTML mail /\ against gratuitous bloodshed

[stolen with permission from Daniel B. Cristofani]

____________________________________________________________________________________
The all-new Yahoo! Mail beta
Fire up a more powerful email and get things done faster.
http://new.mail.yahoo.com
• ... Phil, I keep failing. Would you please provide me with a Matlab code that does this task using fft and ifft? Thanks. Kaveh
Message 8 of 12 , Nov 18, 2006
• 0 Attachment
> Therefore 6, 4, 2, and 0 can be created as differences {8,6} - {6,2}

Phil, I keep failing. Would you please provide me with a Matlab code
that does this task using fft and ifft?

Thanks.

Kaveh
• ... FFTs, a pointwise multiply and an IFFT perform a convolution. I have provided the result of the convolution in question, obtained directly. I can t give
Message 9 of 12 , Nov 18, 2006
• 0 Attachment
--- Kaveh <kaveh_vejdani@...> wrote:
> > Therefore 6, 4, 2, and 0 can be created as differences {8,6} - {6,2}
>
> Phil, I keep failing. Would you please provide me with a Matlab code
> that does this task using fft and ifft?

FFTs, a pointwise multiply and an IFFT perform a convolution.

I have provided the result of the convolution in question, obtained directly.

I can't give technical support for a product I do not have.

Try:
v1=FFT([0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0])
v2=FFT([0,0,1,0,0,0,1,0,0,0,0,0,0,0,0,0,0])
v3=v1*v2
v4=IFFT(v3)

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.

Phil

() ASCII ribbon campaign () Hopeless ribbon campaign
/\ against HTML mail /\ against gratuitous bloodshed

[stolen with permission from Daniel B. Cristofani]

____________________________________________________________________________________

Mortgage rates near 39yr lows.
\$510k for \$1,698/mo. Calculate new payment!
www.LowerMyBills.com/lre
• Good news: YES! Fast multiplication finally worked. Bad news: Subtraction still doesn t work. ... None of the techniques so far have answered my question. They
Message 10 of 12 , Nov 19, 2006
• 0 Attachment
Good news: YES! Fast multiplication finally worked.

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:)
> If you create a bitmap representing each set, FFT those, and
> 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)),

Kaveh
• ... () ASCII ribbon campaign () Hopeless ribbon campaign / against HTML mail / against gratuitous bloodshed [stolen with permission from
Message 11 of 12 , Nov 19, 2006
• 0 Attachment
--- Kaveh <kaveh_vejdani@...> wrote:

> Good news: YES! Fast multiplication finally worked.
>
> 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:)
> > If you create a bitmap representing each set, FFT those, and
> > 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)),
>
> Kaveh
>
>
>
>
>
> Unsubscribe by an email to: primenumbers-unsubscribe@yahoogroups.com
> The Prime Pages : http://www.primepages.org/
>
>
>
>
>
>
>

() ASCII ribbon campaign () Hopeless ribbon campaign
/\ against HTML mail /\ against gratuitous bloodshed

[stolen with permission from Daniel B. Cristofani]

____________________________________________________________________________________

Mortgage rates near 39yr lows.
\$510k for \$1,698/mo. Calculate new payment!
www.LowerMyBills.com/lre
• Ooops - I forgot that enter doesn t take me to the next field in this browser... ... Nope, as the FFT needs to be of length nm, and thus cost O((nm)^(1+eps))
Message 12 of 12 , Nov 19, 2006
• 0 Attachment
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.
>
> 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?

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

> (from your message of Nov 12:)
> > If you create a bitmap representing each set, FFT those, and
> > The problem is that the FFTs would be of length nm, and thus of
> > cost O(nm^(1+eps)).

But I'm repeating myself, it seems.

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

The polynomial arithmetic example I provided was such an example.

Phil

() ASCII ribbon campaign () Hopeless ribbon campaign
/\ against HTML mail /\ against gratuitous bloodshed

[stolen with permission from Daniel B. Cristofani]

____________________________________________________________________________________