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

Real life

Expand Messages
  • Kaveh
    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
    • Ronny Edler
      ... 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]?

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