Loading ...
Sorry, an error occurred while loading the content.

Re-formulating my question

Expand Messages
  • Kaveh
    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.

      Appreciating your feedbacks.

      Kaveh
    • Phil Carmody
      ... 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
      • David Cleaver
        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.
          >
          > Appreciating your feedbacks.
          >
          > Kaveh
        • 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
            > convolve, and IFFT, then you would have your answer.

            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
          • Phil Carmody
            ... 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
              > > convolve, and IFFT, then you would have your answer.
              >
              > 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]



              ____________________________________________________________________________________
              Sponsored Link

              Mortgage rates near 39yr lows.
              $420k for $1,399/mo. Calculate new payment!
              www.LowerMyBills.com/lre
            • Kaveh
              ... 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
              • Phil Carmody
                ... 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
                • Kaveh
                  ... 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
                  • Phil Carmody
                    ... 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]



                      ____________________________________________________________________________________
                      Sponsored Link

                      Mortgage rates near 39yr lows.
                      $510k for $1,698/mo. Calculate new payment!
                      www.LowerMyBills.com/lre
                    • Kaveh
                      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
                        > 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)),
                        please provide an example of your suggested process in work.

                        Kaveh
                      • Phil Carmody
                        ... () 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
                          > > 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)),
                          > please provide an example of your suggested process in work.
                          >
                          > Kaveh
                          >
                          >
                          >
                          >
                          >
                          > Unsubscribe by an email to: primenumbers-unsubscribe@yahoogroups.com
                          > The Prime Pages : http://www.primepages.org/
                          >
                          >
                          > Yahoo! Groups Links
                          >
                          >
                          >
                          >
                          >


                          () 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
                        • Phil Carmody
                          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
                            > > 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)).

                            But I'm repeating myself, it seems.

                            > Assuming that you were talking of the subtraction problem (O(nm)),
                            > please provide an example of your suggested process in work.

                            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]



                            ____________________________________________________________________________________
                            Sponsored Link

                            Mortgage rates near 39yr lows.
                            $510k for $1,698/mo. Calculate new payment!
                            www.LowerMyBills.com/lre
                          Your message has been successfully submitted and would be delivered to recipients shortly.