Real life

Expand Messages
• In the real life of computation, my B set is flexible. I should generate k*m numbers is B until the [0,nm] range is covered. So actully the real problem is to
Message 1 of 3 , Nov 14, 2006
• 0 Attachment
In the real life of computation, my B set is flexible. I should
generate k*m numbers is B until the [0,nm] range is covered. So
actully the real problem is to find optimal k such that the range of
question is covered. But checking the coverage in O(nm) is way too
slow. So I need to resolve this before I can worry about k.

If primality of the elements of A and B helps with the task, let's
assume they're all prime.

David and Phil, cool catch of the pigeonhole. I had overlooked that in
my formulation. As Phil said about FFT, I just need to check the
coverage, without generating the unnecessary intermediates.

So the output size is not really nm, it's a mere 1 digit or, say, if
you want to break the [0,nm-1] range into m sub-intervals of size n,
an output of size m would suffice. (Each digit telling if the
corresponding sub-interval is covered or not).

Ronny, I guess your test will take O(nm) again to guarantee that the
entire range is covered, right?

Thanks all for all the great feedbacks. Looking forward to your
further thoughts and guidelines.

Best wishes,

Kaveh
• ... To clarify on this: You have a _fixed_ set A and want to construct a set B, such that the differences span the interval [0,mn-1], with all members of A and
Message 2 of 3 , Nov 14, 2006
• 0 Attachment
> In the real life of computation, my B set is flexible. I should
> generate k*m numbers is B until the [0,nm] range is covered. So
> actully the real problem is to find optimal k such that the range of
> question is covered. But checking the coverage in O(nm) is way too
> slow. So I need to resolve this before I can worry about k.

To clarify on this: You have a _fixed_ set A and want to construct a set B,
such that the differences span the
interval [0,mn-1], with all members of A and B are in [0,mn-1]?

"Here is a set B that satifies the constraints" or "I have proven that no
such B exists".

Well, i think that unless you construct B, testing abitrarily generated sets
will take you a _long_ time.

Example: Take |A| = 3, |B| = 2. There are (6 choose 3) times (6 choose 2) =
20*15 = 300 possible set combinations.

The only working ones are: A = {1,3,5}, B = {0,1} and A = {3,4,5} and
B={0,3}.

That is 2 out of 300. (m,n are tiny! here)

> Ronny, I guess your test will take O(nm) again to guarantee that the
> entire range is covered, right?

Yes, if you keep track of the numbers you already tested.

Ronny
• No Ronny. A and B are both fixed sets of n and km positive integers, and their elements are not arbitrary. The problem is not to construct A and B, but to
Message 3 of 3 , Nov 14, 2006
• 0 Attachment
No Ronny. A and B are both "fixed" sets of n and km positive integers,
and their elements are not arbitrary. The problem is not to construct
A and B, but to check if their differences cover the range [0,nm].

Best wishes.

Kaveh

--- In primenumbers@yahoogroups.com, "Ronny Edler" <ronny.e@...> wrote:
>
> > In the real life of computation, my B set is flexible. I should
> > generate k*m numbers is B until the [0,nm] range is covered. So
> > actully the real problem is to find optimal k such that the range of
> > question is covered. But checking the coverage in O(nm) is way too
> > slow. So I need to resolve this before I can worry about k.
>
> To clarify on this: You have a _fixed_ set A and want to construct a
set B,
> such that the differences span the
> interval [0,mn-1], with all members of A and B are in [0,mn-1]?
>
> Furthermore, as an answer of your algorithm you need something like:
> "Here is a set B that satifies the constraints" or "I have proven
that no
> such B exists".
>
> Well, i think that unless you construct B, testing abitrarily
generated sets
> will take you a _long_ time.
>
> Example: Take |A| = 3, |B| = 2. There are (6 choose 3) times (6
choose 2) =
> 20*15 = 300 possible set combinations.
>
> The only working ones are: A = {1,3,5}, B = {0,1} and A = {3,4,5} and
> B={0,3}.
>
> That is 2 out of 300. (m,n are tiny! here)
>
> > Ronny, I guess your test will take O(nm) again to guarantee that the
> > entire range is covered, right?
>
> Yes, if you keep track of the numbers you already tested.
>
> Ronny
>
Your message has been successfully submitted and would be delivered to recipients shortly.