[Solved]: Checking whether a number divides any of a set of other numbers

Problem Detail: 

Consider a static set $S$ of positive numbers from range $[1..10^9]$. Is there an efficient algorithm to answer queries of the form: "Given a number $d$ is there an element $x \in S$ such that $d | x$".

1. Simple straightforward check takes $O(|S|)$ time per query and uses $O(|S|)$ memory.
2. Storing all the divisors for every element of $S$ makes query time $O(1)$ but uses too much memory and precomputation time $O(|S| \times \sqrt{|\max(S)|})$.

I'm interested in an algorithm that uses less memory than second solution (because $|S| \sim 10^6$) and still somewhat faster queries than first solution (number of queries is also $\sim 10^6$).

Asked By : SkyterX

Answered By : jbapple

With the following techniques, I have been able to achieve a speedup of 100,000x over the brute force method of storing the dividend in an array and checking each dividend each time a divisor needs to be checked.

To do this, I use 10-20x as much working space as the brute force method when I am pre-processing the set of dividends. In the end, I use roughly 2-3x as much storage as the brute force method. I believe the working space requirement can be reduced substantially (see below) by the use of more complex algorithms.

To be specific about timing, with $\sim10^6$ dividends and divisors, the brute force method takes $0.02 \mu s$ for each dividend (that's the build) and $16{,}000{,}000 \mu s$ per divisor (that's the query) while my method takes $55 \mu s$ per dividend and the same time per divisor.

To create the structure, first make a trie of the dividends. Treat them as strings of prime factors, biggest factor first. Thus, 650 would be inserted into the trie as the string $\langle 13,5,5,2 \rangle$. Insert not only that string, but also all subsequences. In this case, that means to also insert:

• $\langle \rangle$
• $\langle 13 \rangle$
• $\langle 13,5 \rangle$
• $\langle 13,5,5 \rangle$
• $\langle 13,5,5,2 \rangle$ (the first sequence)
• $\langle 13,5,2 \rangle$
• $\langle 13,2 \rangle$
• $\langle 5 \rangle$
• $\langle 5,5 \rangle$
• $\langle 5,5,2 \rangle$
• $\langle 5,2 \rangle$
• $\langle 2 \rangle$

This represents all divisors of the dividend 650. Since all divisors are in the trie, queries can now proceed by just factoring the divisor in the same way (as a list of prime factors, largest first) and then traversing the trie. If the traversal hits a dead end before the divisor's prime sequence is exhausted, it divides no dividend in the trie.

Space-wise, for $\sim10^6$ random 31-bit dividends, this takes up 7-10x as much space as just storing the dividends themselves.

Sidebar: This is roughly the same amount of space as storing every divisor of every dividend in a hash table. I find this interesting on its own, as this is much less than the $n \sqrt{n}$ or $n \sqrt[3]{n}$ space upper bounds posted in the question and comments, I suspect because of overlap - 2 divides many numbers, but it only needs to be stored once. This method uses $60\mu s$ per dividend and $0.3\mu s$ per divisor on my computer, making about twice as fast as this trie/DAG method, while using the same amount of working space but larger storage space during queries.

To decrease the space usage of the tree, make a compressed acyclic graph of it, using the algorithm from "Comparison of Construction Algorithms for Minimal, Acyclic, Deterministic, Finite-State Automata from Sets of Strings", by Jan Daciuk. The big ideas, as I see them, are to:

1. Make an equivalence relation on DAG/Trie nodes in which two nodes are equivalent if they have the same set of children pointing to the same literal nodes. This makes deciding trie equality take time proportional to the number of children of a node, not the number of descendants. This is very important.

2. Use a postorder traversal to dedupe the nodes, so that the children of a node are already deduped before the parent, ensuring the equivalence relation doesn't miss anything.

This reduces the number of notes in the Trie/DAG by a factor of 6ish in my testing. Note that this does not do nearly as well if the prime factor strings are inserted smallest-prime first. I think that's due to the nature of the minimum automaton, in which nodes with the same label nearer to the root have many outgoing edges. Putting larger primes nearer the root reduces the amount of duplication near the root. I suspect this is related to the problem of picking a variable ordering in Binary Decision Diagrams.

In my testing, 80-90% of the work of the algorithm is actually the problem of factoring the numbers. I used trial division; if you use a better algorithm, I think your algorithm will be faster.

The working space required can be reduced using "Incremental construction of minimal acyclic finite state automata", by Daciuk et al.

In the below table, the space bounds are the amount of memory used divided by the number of items, and time bounds are the number of microseconds divided by the number of items.

$$ \begin{array}{|c|c|c|c|c|} \hline \textbf{Method} & \textbf{Construction time ($\mu s$)} & \textbf{Query time ($\mu s$)} & \textbf{Working space} & \textbf{Storage space}\\ \hline \text{Query every dividend} & 0.02 & 16{,}000{,}000 & 1 & 1\\ \hline \text{Store every divisor} & 60 & 0.3 & 7-10 & 7-10\\ \hline \text{This method} & 55 & 55 & 7-10 & 2-3\\ \hline \text{Incremental minimization} & ? & 55 & 2-3 & 2-3\\ \hline \end{array} $$

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/48305

3.2K people like this

 Download Related Notes/Documents