Problem Statement

When counting integers in binary, if you put a (binary) point to the right of the count then the column immediately to the left denotes a digit with a multiplier of

2

0

{\displaystyle 2^{0}}

; the digit in the next column to the left has a multiplier of

2

1

{\displaystyle 2^{1}}

; and so on. So in the following table: the binary number "10" is

1 ×

2

1

0 ×

2

0

{\displaystyle 1\times 2^{1}+0\times 2^{0}}

. You can also have binary digits to the right of the “point”, just as in the decimal number system. In that case, the digit in the place immediately to the right of the point has a weight of

2

− 1

{\displaystyle 2^{-1}}

, or

1

/

2

{\displaystyle 1/2}

. The weight for the second column to the right of the point is

2

− 2

{\displaystyle 2^{-2}}

or

1

/

4

{\displaystyle 1/4}

. And so on. If you take the integer binary count of the first table, and reflect the digits about the binary point, you end up with the van der Corput sequence of numbers in base 2. The third member of the sequence, binary 0.01, is therefore

0 ×

2

− 1

1 ×

2

− 2

{\displaystyle 0\times 2^{-1}+1\times 2^{-2}}

or

1

/

4

{\displaystyle 1/4}

. This sequence is also a superset of the numbers representable by the "fraction" field of an old IEEE floating point standard. In that standard, the "fraction" field represented the fractional part of a binary number beginning with "1." e.g. 1.101001101. Hint A hint at a way to generate members of the sequence is to modify a routine used to change the base of an integer: the above showing that 11 in decimal is

1 ×

2

3

0 ×

2

2

1 ×

2

1

1 ×

2

0

{\displaystyle 1\times 2^{3}+0\times 2^{2}+1\times 2^{1}+1\times 2^{0}}

. Reflected this would become .1101 or

1 ×

2

− 1

1 ×

2

− 2

0 ×

2

− 3

1 ×

2

− 4

{\displaystyle 1\times 2^{-1}+1\times 2^{-2}+0\times 2^{-3}+1\times 2^{-4}}

Let's start with the solution:

Program VanDerCorput;
{$IFDEF FPC}
  {$MODE DELPHI}
{$ELSE}
  {$APPTYPE CONSOLE}
{$ENDIF}

type
  tvdrCallback = procedure (nom,denom: NativeInt);

{ Base=2
function rev2(n,Pot:NativeUint):NativeUint;
var
  r : Nativeint;
begin
  r := 0;
  while Pot > 0 do
  Begin
    r := r shl 1 OR (n AND 1);
    n := n shr 1;
    dec(Pot);
  end;
  rev2 := r;
end;
}

function reverse(n,base,Pot:NativeUint):NativeUint;
var
  r,c : Nativeint;
begin
  r := 0;
//No need to test n> 0 in this special case, n starting in upper half
  while Pot > 0 do
  Begin
    c := n div base;
    r := n+(r-c)*base;
    n := c;
    dec(Pot);
  end;
  reverse := r;
end;

procedure VanDerCorput(base,count:NativeUint;f:tvdrCallback);
//calculates count nominater and denominater of Van der Corput sequence
// to base 
var
 Pot,
 denom,nom,
 i : NativeUint;
Begin
  denom := 1;
  Pot := 0;
  while count > 0 do
  Begin
    IF Pot = 0 then
      f(0,1);
    //start in upper half
    i := denom;
    inc(Pot);
    denom := denom *base;

    repeat
      nom := reverse(i,base,Pot);
      IF count > 0 then
        f(nom,denom)
      else
        break;
      inc(i);
      dec(count);
    until i >= denom;
  end;
end;

procedure vdrOutPut(nom,denom: NativeInt);
Begin
  write(nom,'/',denom,'  ');
end;

var
 i : NativeUint;
Begin
  For i := 2 to 5 do
  Begin
    write(' Base ',i:2,' :');
    VanDerCorput(i,9,@vdrOutPut);
    writeln;
  end;
end.