# Tag Info

85

Consider the set of keys $K=\{0,1,...,100\}$ and a hash table where the number of buckets is $m=12$. Since $3$ is a factor of $12$, the keys that are multiples of $3$ will be hashed to buckets that are multiples of $3$: Keys $\{0,12,24,36,...\}$ will be hashed to bucket $0$. Keys $\{3,15,27,39,...\}$ will be hashed to bucket $3$. Keys $\{6,18,30,42,...\}$ ...

34

always compress random data sets by more than 50% That's impossible. You can't compress random data, you need some structure to take advantage of. Compression must be reversible, so you can't possibly compress everything by 50% because there are far less strings of length $n/2$ than there are of length $n$. There are some major issues with the paper: They ...

26

You are confusing the number $n$ with the number of bits needed to represent $n$. Here $b =$ the number of bits needed to represent $n$ (so $b \approx \lg n$). This makes a huge difference. A $O(n)$-time algorithm is a $O(2^b)$-time algorithm -- exponential in the number of bits. In comparison, the "efficient" algorithm you found has a running time that ...

24

Quick answer: Never, for practical purposes. It is not currently of any practical use. First, let's separate out "practical" compositeness testing from primality proofs. The former is good enough for almost all purposes, though there are different levels of testing people feel is adequate. For numbers under 2^64, no more than 7 Miller-Rabin tests, or ...

19

So your problem is as follows: Input: integers $\ell,u$ Question: does there exist a prime in $[\ell,u]$? As far as I know, it is not known whether that problem is in P or not. Here's what I do know: Primality testing (given a single number, test whether it is prime) is in P, so if the range is small enough, you can exhaustively test each number in the ...

18

The (asymptotically) most efficient deterministic primality testing algorithm is due to Lenstra and Pomerance, running in time $\tilde{O}(\log^6 n)$. If you believe the Extended Riemann Hypothesis, then Miller's algorithm runs in time $\tilde{O}(\log^4 n)$. There are many other deterministic primality testing algorithms, for example Miller's paper has an $\... 17 Whether a collision is less likely using primes depends on the distribution of your keys. If many of your keys have the form$a+k\cdot b$and your hash function is$H(n)=n \bmod m$, then these keys go to a small subset of the buckets iff$b$divides$n$. So you should minimize the number of such$b$, which can be achieved by choosing a prime. If on the ... 16 I'm going to defer to Tom van der Zanden who seems to have read the paper and discovered a weakness in the method. While I didn't read the paper in detail, going from the abstract and the results table, it seems like a broadly believable claim. What they claim is a consistent 50% compression ratio on text files (not "all files"), which they note is around ... 14 What do you mean by "directly"? This is not well-defined. Arguing that an algorithm doesn't do something during its computation is not a nice well-defined concept (when that something is a semantic condition). It is probably one of the most common mistakes that people make when thinking about algorithms because they look at obvious cases and think it is ... 12 You ask: Is this really feasible as the authors suggest it? According to the paper, their results are very efficient and always compress data to a smaller size. Won't the dictionary size be enormous? Yes, of course. Even for their hand-picked example ("THE QUICK SILVER FOX JUMPS OVER THE LAZY DOG"), they don't achieve compression, because the ... 11 This is very much an open problem. I'll sketch some classes that the problem could "naturally" fit in. Your definition is somewhat awkward to work with, the problem is hard to fit in to any existing complexity class. The language you've defined is the intersection of the languages$\{(x,n)|\pi(x)\leq n\}$and$\{(x,n)|\pi(x)\geq n\}$. So if for instance$\{(...

10

When $n$ is the input, we test $\sqrt{n}$ divisors. However, we also have to take into account the complexity of division itself. For a number with $b$ bits, this takes $O(b \log b \log\log b)$ operations, when we are using the Schönhage–Strassen algorithm. Since half of the numbers below $\sqrt{n}$ have $\log(\sqrt{n})$ digits, we may assume the all have ...

9

Whether this has an impact (also) depends on how you treat collisions. When using some variants of open hashing, using primes guarantees empty slots are found as long as the table is sufficiently empty. Try to show the following, for instance: Assume we want to insert an element that hashes to address $a$ and resolve collisions by trying positions $a + i^2$ ...

9

O'Neil  call this the "unfaithful sieve". It's much slower than the sieve of Eratosthenes. For each prime $p$ you do work $\sim p/\log p$ and so the total number of divisions up to $x$ is roughly $x^2/(2\log^2 x)$ if you assume composites are free. (That's essentially true: they take at most $2\sqrt x/\log x$ divisions each for a total of at most $2x^{3/... 9 The advantage in using base 2 is that we know all of the psp's base 2 up to$2^{64}$. It has been verified that none of these psp(2)'s passes a Lucas test when the parameters$P, Q$are chosen in accord with any of the methods in the Baillie/Wagstaff paper. If you choose a random base, there might be some composite$n$that passes both the Fermat and Lucas ... 9 The complexity is measured as a function of the size of the input. You don't have here an array of$n$numbers but a number$n$. The size of the input is$O(\log n)$(to store a number$n$you need$\lfloor log_2(n) + 1 )\rfloor$bits). Hence,$O(\sqrt n)$is not polynomial in the size of the input. The answer to the second question is a direct ... 8 First, two facts about coprime integers: Iff$a$and$b$are coprime, then$ab = \mathrm{lcm}(a,b)$Iff$a$is coprime to both$b$and$c$, then$a$is coprime to$bc$It follows from this that a set of distinct integers$\{a, b, \cdots z\}$is pairwise coprime if its product is equal to its least common multiple. You can compute the least common multiple ... 7 The Rabin-Miller algorithm also tests, given a number$n$, whether$Z_n$has a nontrivial root of Unity. Carmichael numbers pass the Fermat test (for every basis$a$), but for every Carmichael number$n$, there exist many numbers$a$such that the test for unity roots fails on$a$(that is, the sequence$a,2a,...,2^ra$eventually displays a nontrivial root ... 7 By the prime number theorem, about a$1/\log(n)$fraction of numbers in the range$[n/2,n]$are prime. We know that the algorithm will take$\Theta(\sqrt{n})$time for each of them (since for all$x \in [n/2,n]$, we have$x = \Theta(\sqrt{n})$). Therefore, $$\mathbb{E}[T(X_n)] = \Omega\left({\sqrt{n} \over \log n}\right).$$ This is enough to establish ... 6 So you have two numbers that: both have two prime factors, and you strongly suspect that they share a factor. So one is$n_{1}=pq_{1}$the other$n_{2}=pq_{2}$. What is their GCD? 6 Entropy effectively bounds the performance of the strongest lossless compression possible. Thus there exist no algorithm that can compress random data sets by always more than 50%. 6 newbie's answer already explains it all. But if I had to add something to this, I'd put it in simpler words. When you talk about a polynomial time algorithm, what you actually mean is that the running time of the algorithm is a polynomial in the input length. The input length is, roughly speaking, the number of keystrokes required to express the input. To ... 5 Although this question is old, the considerations are still relevant and there is still some lack of proper analysis on which prime sieve to choose for various purposes. In this evaluation, it is important to note that these intense considerations are only necessary for ranges of primes in the order of a hundreds of millions or more: A simple trial ... 5 The exact running time depends on your computation model. When analyzing arithmetic with large numbers, we usually count either bit operations, or arithmetic operations on words of size$O(\log n)$(where$n$is the input size, which in your case is the logarithm of the number you want to factor). This means that in a constant amount of time the first model ... 5 References for the test: Pomerance, Selfridge, Wagstaff, "The Pseudoprimes to 25 x 10^9", July 1980. Page 1024-1025, Check if n is a strong probable prime base 2. Check whether n is a Lucas probable prime using method A (Selfridge) or B. The authors offer$30 to the first finder of a counterexample or proof of non-existence. It references the next paper ...

5

Yes, here is a simple approach (there are likely more efficient ones). Let $n$ be the number given. Observe that $2 \leq p \leq n$ and $1 \leq i \leq \log_2(n)$. For each possible value of $i$ in the range $\{1, \ldots, \log_2(n)\}$, you can do a binary search for a $p$ in the range $\{2, \ldots, n\}$ such that $p^{i} = n$.

5

You can use a sieve to enumerate all prime numbers up to $n$. There are multiple algorithms; see the Wikipedia article I link for some examples. The sieve of Atkin and wheel sieves apparently run in $O(n)$ time.

4

Let me rephrase your algorithm (starting at a different base case): Initialize P to be the empty list. for n from 2 to MAX: if no integer in P divides n: add n to P return P Let $p_1,p_2,\ldots$ be an enumeration of the primes. The probability that $p_1,\ldots,p_i$ do not divide a number $n$ is roughly  \prod_{j=1}^i \left(1 - \frac{1}{p_j}\right) ...

Only top voted, non community-wiki answers of a minimum length are eligible