tag:blogger.com,1999:blog-6555947.post2397682432726768576..comments2014-01-12T10:46:48.153-07:00Comments on The Geomblog: Faure sequences and quasi-Monte Carlo methodsSuresh Venkatasubramaniannoreply@blogger.comBlogger5125tag:blogger.com,1999:blog-6555947.post-86039725615466323882007-05-23T13:22:00.000-06:002007-05-23T13:22:00.000-06:00you're right, and the recurrence I think will work...you're right, and the recurrence I think will work out to n + log n overall. <BR/><BR/>However, this is why I ruled out such methods: I know that such a procedure can be used, but for the specific application in mind, we can't rely on computing the entire sequence in advance: the storage requirements are too onerous.Sureshhttp://www.blogger.com/profile/15898357513326041822noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-34927489244566136212007-05-23T12:56:00.000-06:002007-05-23T12:56:00.000-06:00Whoops. I think I meant van Corput sequence, not H...Whoops. I think I meant van Corput sequence, not Halton sequence.mhumnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-49134942737783435192007-05-23T12:30:00.000-06:002007-05-23T12:30:00.000-06:00Two further observations:To simplify notation, let...Two further observations:<BR/><BR/>To simplify notation, let $\sigma(n,j)$ denote the jth entry of $\sigma(n)$.<BR/><BR/>If you have access to all of $\sigma(n)$ and the binary Halton<BR/>sequence H(i) (H(1) = 0.5, H(2) = 0.25, H(3) = 0.75, etc...), you can compute $\sigma(2^k n, j)$ as $2^k \sigma(n, j) + 2^k H(\lfloor j/n\rfloor)$. With this observation -- and constant-time access to the Halton sequence -- you can compute $\sigma(n, j)$ in time proportional to the Hamming weight of n. Not great, but maybe slightly better.<BR/><BR/>Secondly, if instead of requiring that we compute each $\sigma(n,j)$ in less than log(n) operations we require that we compute all $\sigma(n,j)$ for j=1,...,n in less than nlog(n) operations I think we can do better. Note that $\sigma(n,1) = 0$, $\sigma(n,n) = n-1$ and $\sigma(2n+1,n) = n$ for all n. Then, if we compute $\sigma(n,j)$ recursively in the obvious way (e.g.: $\sigma(2n, j) = 2\sigma(n,j) if j < n, 2\sigma(n,j-n)+1 else$ and $\sigma(2n+1,j) = n if j=n, 2*\sigma(n) if j<n and 2*\sigma(n)<n, etc...$) but stopping whenever we reach some calculation of the form $\sigma(m,1)$ or $\sigma(m,m)$. Now, we can compute at least 2 entries of $\sigma(n)$ with zero recursive levels (I say "at least" because we get 3 entries if n is odd), at least 2 entries with one recursion, at least 4 entries with two recursions, at least 8 entries with three, etc... Following this line of reasoning and working out all the sums, we find that to calculate all n entries of $\sigma(n)$, we only need to explore a linear number of recursions.mhumnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-33539200006264492262007-05-11T12:07:00.000-06:002007-05-11T12:07:00.000-06:00I'm willing to count this as a single operation. B...I'm willing to count this as a single operation. Basically, I'm using a RAM model: the reverse operation is somewhat unorthodox for a RAM model, but I'm allowing it, because it yields a closed form.Sureshhttp://www.blogger.com/profile/15898357513326041822noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-57175679578801179662007-05-11T01:57:00.000-06:002007-05-11T01:57:00.000-06:00You can compute the jth entry of $\sigma(2^k)$ by ...You can compute the jth entry of $\sigma(2^k)$ by taking the reverse of the k-bit binary representation of j. E.g., in binary, $\sigma(8)$ = (000, 100, 010, 110, 001, 101, 011, 111). Do you count this as fewer than log(n) operations or exactly equal to log(n) operations?mhumnoreply@blogger.com