Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>You can use the <a href="http://en.wikipedia.org/wiki/Chinese_remainder_theorem" rel="nofollow">Chinese Remainder Theorem</a> to do this. I'm going to change your notation a bit. </p> <p>Suppose you have <code>N</code> numbers of which at most <code>E</code> are even. Choose a sequence of distinct prime powers <code>q1,q2,...,qk</code> such that their product is at least <code>N^E</code>, i.e.</p> <pre><code> qi = pi^ei </code></pre> <p>where <code>pi</code> is prime and <code>ei &gt; 0</code> is an integer and </p> <pre><code> q1 * q2 * ... * qk &gt;= N^E </code></pre> <p>Now make a bunch of <code>0-1</code> matrices. Let <code>Mi</code> be the <code>qi x N</code> matrix where the entry in row <code>r</code> and column <code>c</code> has a <code>1</code> if <code>c = r mod qi</code> and a <code>0</code> otherwise. For example, if <code>qi = 3^2</code>, then row <code>2</code> has ones in columns <code>2, 11, 20, ... 2 + 9j</code> and <code>0</code> elsewhere.</p> <p>Now stack these matrices vertically to get a <code>Q x N</code> matrix <code>M</code>, where <code>Q = q1 + q2 + ... + qk</code>. The rows of <code>M</code> tell you which numbers to multiply together (the nonzero positions). This gives a total of <code>Q</code> products that you need to test for evenness. Call each row a "trial", and say that a "trial involves <code>j</code>" if the <code>j</code>th column of that row is nonempty. The theorem you need is the following:</p> <p>THEOREM: The number in position <code>j</code> is even if and only if all trials involving <code>j</code> are even.</p> <p>So you do a total of <code>Q</code> trials and then look at the results. If you choose the prime powers intelligently, then <code>Q</code> should be significantly smaller than <code>N</code>. There are asymptotic results that show you can always get <code>Q</code> on the order of</p> <pre><code>(2E log N)^2 / 2log(2E log N) </code></pre> <p>This theorem is actually a corollary of the Chinese Remainder Theorem. The only place that I've seen this used is in <a href="http://en.wikipedia.org/wiki/Group_testing" rel="nofollow">Combinatorial Group Testing</a>. Apparently the problem originally arose when testing soldiers coming back from WWII for syphilis. </p>
    singulars
    1. This table or related slice is empty.
    1. POFinding even numbers in an array without using feedback
      singulars
      1. PTQuestion
    1. PTAnswer
    1. This table or related slice is empty.
    1. USPengOne
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POFinding even numbers in an array without using feedback
      singulars
      1. PTQuestion
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COThank you. This made sense after I thought about it and did an example, but I still don't know why the theorem is true.
      singulars
      1. PO
      1. USDaniel
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload