# Algorithms for non-random but equidistributed ways to fill up a Cartesian plane

In pages 90-91 of this book the authors talk about uniform, but not necessarily normally distributed random ways to fill up a Cartesian grid. For example, in the attached images. These are the authors' exact instructions for generating these plots:

There are numerous schemes for generating equidistributed [but not randomly generated] sequences, including the Neiderreiter, Weyl, and Haber sequences. Let $x_{ij}$ denote the $j^{th}$ coordinate of the $i^{th}$ vector in a sequence of equidistributed vectors on the d-dimensional unit hypercube. Then these three equidistributed sequences involve iterates of the form $x_{ij}=frac(2^{q_{ij}})$ where for the Neiderreiter: $$q_{ij}=ij/(d+1)$$ for the Weyl: $$q_{ij}=ip_j$$ and for the Haber: $$q_{ij}=i(i+1)p_j/2$$ Here, $p_j$ represents the $j^{th}$ positive prime number and $frac(x)$ represents the fractional part of $x$, that is, $x$ minus the greatest integer less than $x$.

(I am only interested in the $d=2$ case)

First of all, by "Let $x_{ij}$ denote the $j^{th}$ coordinate of the $i^{th}$ vector" I understand that each $x_{ij}$ is just an $(x,y)$ pair. That is, a point on the Cartesian grid. If I've misunderstood that stop me now.

Secondly, I don't get how $frac(2^{q_{ij}})$ can produce anything but $0$ for the Weyl since the formula for $q_{ij}$ defined by the authors always generates integers, and then $2^{q_{ij}}$ is just another integer; and the fractional part of an integer is of course $0$. Edit: The Haber algorithm also always produces integers.

Looking forward to your help. Feel free to include snippets of matlab code in your answer, if you have been successful in figuring out how to code this up.

EDIT: After posting this question I discovered this errata page which clears up part of the confusion.

• For your first point, about notation. I was reading it to mean $x_i$ is a sequence of vectors $x_i = (x_{i1}, x_{i2})$. For your second point, about the Weyl sequence, I agree with you something seems off, and in fact I would say that about all of the sequences listed, but not having the book you link to makes it hard to say for sure. You might try to modify the definitions by replacing $2^{q_{ij}}$ with, say, $b^{q_{ij}}$ for irrational bases $b$ and see what you get. – froggie Mar 1 '14 at 6:22
• Also, if you're interested, another way of producing equidistributing sequences in the unit square is discussed in this problem. – froggie Mar 1 '14 at 6:23

• Weyl: $x_n=(\{n\sqrt{p_1}\},...,\{n\sqrt{p_d}\})$
• Haber: $x_n=\left(\left\{\tfrac{n(n+1)}2\sqrt{p_1}\right\},...,\left\{\tfrac{n(n+1)}2\sqrt{p_d}\right\}\right)$
• Niederreiter: $x_n=\left(\left\{n2^{1/(d+1)}\right\},\left\{n2^{2/(d+1)}\right\},...,\left\{n2^{d/(d+1)}\right\}\right)$
with $\{x\}=x-[x]$ denoting the fractional part of $x$ and $p_1,...,p_d$ distinct primes.