Sorry, an error occurred while loading the content.
Browse Groups

• ## Re: [PrimeNumbers] Does Fourier transform help with exhaustive subtractions?

(5)
• NextPrevious
• ... Hi Kaveh, I think you misunderstood Peter s point (quoted above). With fast multiplication, n digits times m digits, the result will only have n+m digits,
Message 1 of 5 , Nov 9, 2006
View Source
On 11/9/06, Peter Kosinar <goober@...> wrote:
> Consider the sets A = { N, 2N, 3N, ... N^2 }, B = { 0, 1, 2, ... N-1 }.
> The set obtained by subtracting each element of B from each element of A
> is { 1, 2, 3, ... N^2 }. In other words, the size of the resulting set can
> be quadratic and thus the worst-case runtime of any algorithm producing
> it is at least quadratic [*].

Hi Kaveh,
I think you misunderstood Peter's point (quoted above).

With fast multiplication, n digits times m digits, the result will
only have n+m digits, so Peter's argument says it takes at least
O(n+m) time just to store the resulting bignum! And indeed FFT mult
takes O(n ln n) which in general is way more than 2n.

With your subtraction problem, n numbers minus each of m numbers, the
result can have nm numbers, so he argues that since storing each
number takes O(1) time, the whole computation must take at least O(nm)
time. I think that argument sounds very convincing to me!

My solution, which takes O(1) time, depends on not storing all the
numbers, but rather on doing an O(n+m) lookup each time you want to
check if a number is in the set "A-B" that you want. Peter already
anticipated that, though, in his footnote which reminds us that the
O(nm) minimum is only true if you want to store all the nm
differences.

So, if you really need all the numbers in a list, Peter is right and
the minimum time is O(nm). If you can use some other way of
remembering the numbers, or if you know some other properties of the
numbers (like, say, the maximum is a lot less than nm, so you know
there can't be nm different differences among them) then there might
be an algorithm that exploits those other possibiities.

--Joshua Zucker
Your message has been successfully submitted and would be delivered to recipients shortly.
• Changes have not been saved
Press OK to abandon changes or Cancel to continue editing
• Your browser is not supported
Kindly note that Groups does not support 7.0 or earlier versions of Internet Explorer. We recommend upgrading to the latest Internet Explorer, Google Chrome, or Firefox. If you are using IE 9 or later, make sure you turn off Compatibility View.