Ideally, the distribution over the acceptable pairs would be close to uniform.
x and the pair are all positive integers
(This is for code, so I need a constructive solution)
Thanks!
Ideally, the distribution over the acceptable pairs would be close to uniform.
x and the pair are all positive integers
(This is for code, so I need a constructive solution)
Thanks!
Dirichlet showed that the number of pairs of positive integers $(a,b)$ with $ab \le x$ is $x \log x + (2 \gamma - 1)x + O(\sqrt{x})$ where $\gamma$ is Euler's constant (see e.g. http://www.math.uiuc.edu/~hildebr/ant/main.pdf Theorem 2.20). Of those, $x + O(\sqrt{x})$ have $a,b \le \sqrt{x}$, while there are $\lfloor x/a \rfloor$ with a given value of $a$. So we can do the following.
You said close to uniform, so I proffer the following. Given $x$, the acceptable pairs $(a,b)$ are the lattice points in the first quadrant subject to the constraint $ab
This suggests the following heuristic approach. The cdf of the random variable $a$ is approximately $ F(A)=Pr(a\le A)=\frac{\ln A-\gamma}{\ln x-\gamma}. $
The usual trick would be then to
At this time this is a very crude description. We need to do a lot of critical thinking and testing to verify that the approximation errors inherent in this approach won't disturb the algorithm too much. When $x$ is relatively small, the Euler-Mascheroni approximation has an error that may disturb things. Also I'm not sure how to best do the `rounding' of the value of $a$ in step 2. Simple rounding or truncation may not be best.
Let's assume for simplicity that the size of $x$ is "feasible", i.e. we can afford to store an array of size $\approx \sqrt x$. For $i=1,\ldots \lfloor\sqrt x\rfloor$ let $a_i=\lfloor \frac xi\rfloor$, $b_i=2a_i-2i+1$, $s_i=\sum_{j\le i} b_j$. Then $s_{\lfloor\sqrt x\rfloor}$ is the number of valid points.
If the above is not feasible (e.g. $x$ is too big), the following rejection-method should be fine:
This essentially generates a point in the area bounded by $0\le r_1\le x$, $0\le r_2\le x$ and $r_1r_2\le x$ and rejects points not in the corresponding unit squares. This could be improved (less rejecting) by treating the cases $r_1=2$ and $r_2=2$ specially (not just $r_1=1$, $r_2=1$ as the above does).