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

Re: [PrimeNumbers] Re: Re-formulating my question

Expand Messages
  • Phil Carmody
    ... () ASCII ribbon campaign () Hopeless ribbon campaign / against HTML mail / against gratuitous bloodshed [stolen with permission from
    Message 1 of 12 , Nov 19, 2006
      --- 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
    Your message has been successfully submitted and would be delivered to recipients shortly.