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

Notes on my "Fourier transform" question

Expand Messages
  • Kaveh
    The elements of my sets are random positive integers, and I need all n^2 values of (an element of A) - (an element of B). In fast multiplication using fast
    Message 1 of 1 , Nov 9, 2006
    View Source
    • 0 Attachment
      The elements of my sets are random positive integers, and I need all
      n^2 values of (an element of A) - (an element of B).

      In fast multiplication using fast fourier transform, the
      conventional O(n^2) complexity reduces to O(n Ln(n)). So I wonder if
      a similar trick might help speed up my task.

      Awaiting your feedbacks.

      Kaveh

      - Response to David: No, they're not necessarily primes. And because
      I need all n^2 values, it is (if done one by one) O(n^2).

      - Response to Peter: Fast multiplication runs in O(n Ln(n)).
      So "any" algorithm that handles two sets is not necessarily
      quadratic.

      - Response to Joshua: You got it right. I need all the elements and
      it's O(nm), unless we come up with a trick like FFT, which I am
      looking for.
    Your message has been successfully submitted and would be delivered to recipients shortly.