When counting integers in binary, if you put a (binary) point to the righEasyLangt 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:

  0.
  1.
 10.
 11.
 ...
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.

  .0
  .1
  .01
  .11
  ...
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}

.



 Distribution of 2500 points each: Van der Corput (top) vs pseudorandom




0
≤
x
<
1


{\displaystyle 0\leq x<1}


Monte Carlo simulations
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:

>>> def base10change(n, base):
	digits = []
	while n:
		n,remainder = divmod(n, base)
		digits.insert(0, remainder)
	return digits
 
>>> base10change(11, 2)
[1, 0, 1, 1]
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}}





Task description

 Create a function/method/routine that given n, generates the n'th term of the van der Corput sequence in base 2.
 Use the function to compute and display the first ten members of the sequence. (The first member of the sequence is for n=0).
 As a stretch goal/extra credit, compute and show members of the sequence for bases other than 2.


See also

 The Basic Low Discrepancy Sequences
 Non-decimal radices/Convert
 Van der Corput sequence


 
[Van der Corput sequence for Rosetta Code.
 EDSAC solution, Initial Orders 2.]
 
[Library subroutine M3 - prints header at load time and is then overwritten.
 Here, the last character sets the teleprinter to figures.]
            PFGKIFAFRDLFUFOFE@A6FG@E8FEZPF
            *VAN!DER!CORPUT!SEQUENCE@&#17A*BIT!!!#35A*BIT@&#
            ..PZ [blank tape then re-sync]
 
[Define load addresses]
            T55K P100F  [V parameter: van der Corput subroutines]
            T51K P64F   [G parameter: print subroutine]
            T47K P400F  [M parameter: main routine]
 
[Subroutines to return n'th element of van der Corput sequence.
 17-bit version: Call by GV, pass n in 0F (not preserved), result in 4F.
 35-bit version: Call by G1V, pass n in 0D (not preserved), result in 4D.]
            E25K TV GK
            G2@  [jump to 17-bit version]
            G25@ [jump to 35-bit version]
[17-bit version.
 On EDSAC, it's a matter of reversing the bits after the binary point
 To save time, we use a table to reverse the 16 bits in groups of 4.]
      [2]   A3F T24@    [plant return link as usual]
            H5 6@       [set mult reg to 0...01111 binary]
            A55@ T4F    [set marker bit 0...01 in result]
      [7]   A4F L4F T4F [shift result 4 left]
            CF          [acc := next 4 bits of n]
            LD          [shift into address field]
            A58@ T14@   [plant A order to load from table]
     [14]   AF          [{planted) load bits from table]
            A4F         [add to result]
            G22@        [jump out if marker bit has reached sign bit]
            T4F         [update result]
            AF R4F TF   [shift n 4 right]
            E7@         [always loop back]
     [22]   S57@        [done, remove marker bit]
            T4F         [store final result]
     [24]   ZF          [(planted) jump to return to caller]
 
[35-bit version. Very similar to the 17-bit version, except that
 after reversing 8 groups of 4, there are 2 bits left over,
 which require separate treatment.]
     [25]   A3F T54@    [plant return link as usual]
            H56@        [set mult reg to 0...01111 binary]
            YF L2F      [set marker bit 0...0100 in result]
     [30]   L4F T4D     [shift result 4 left]
            CF LD A58@ T36@ AF A4F T4F [update from table as in 17-bit version]
            ADR4FTD     [shift n 4 right]
            A4D         [load result]
            E30@        [if marker bit hasn't reached sign bit, loop back]
[Last 2 bits]
     [44]   L1FT4D      [shift result 2 right]
            CF LD A58@ T50@ [plant A order as in 17-bit version]
     [50]   AF          [Planted) load bits from table]
            R1F A4F T4F [shift table entry 2 right and add to result]
     [54]   ZF          [(planted) jump to return to caller]
[Constants]
     [55]   PD          [17-bit 1]
     [56]   P7D         [17-bit 15]
     [57]   K4096F      [17-bit 10...0 binary]
     [58]   A59@        [order to load from table{0}]
[Table to reverse group of 4 bits, e.g. table{0010b} = 0100b]
     [59]   PFP4FP2FP6FP1FP5FP3FP7FPDP4DP2DP6DP1DP5DP3DP7D
 
[Library subroutine P1 to print number in range 0 <= x < 1.
 Caller must print leading '0.' if required. 21 storage locations.]
            E25K TG
            GKA18@U17@S20@T5@H19@PFT5@VDUFOFFFSFL4FTDA5@A2FG6@EFU3FJFM1F
 
[Main routine]
            E25K TM GK
      [0]   PF PF       [n, 35 bits, must be at even address]
      [2]   PF          [negative count of terms]
      [3]   P10F        [<=== EDIT number of terms, in address field]
      [4]   PD          [17-bit integer 1]
      [5]   MF          [dot (in figures mode)]
      [6]   @F          [carriage return]
      [7]   &F          [line feed]
      [8]   !F          [space character]
      [9]   K4096F      [null character]
 
[Enter with acc = 0]
     [10]   T#@         [n := 0]
            S3@ T2@     [initialize negative count]
     [13]   A@ TF       [pass 17-bit n in 0F]
     [15]   A15@ GV     [call 17-bit van der Corput routine]
            TD          [clear 0D, including sandwich bit]
            A4F T1F     [extend 17-bit result to 35 bits in 0D]
            O4@ O5@     [print '0.']
     [22]   A22@ GG P5F [print result to 5 decimals]
            O8@ O8@     [print 2 spaces]
            A#@ TD      [pass 35-bit n in 0D]
     [29]   A29@ G1V    [call 35-bit van der Corput routine]
            A4D TD      [pass result in 0D]
            O4@ O5@     [print '0.']
     [35]   A35@ GG P10F [print result to 10 decimals]
            O6@ O7@     [print CR LF]
            A2@ A2F     [inc negative count]
            E48@        [jump out if count = 0]
            T2@         [update count]
            A@ A4@ T@   [inc n]
            E13@        [loop back]
     [48]   O9@         [print null to flush teleprinter buffer]
            ZF          [stop]
 
            E10Z        [define entry point]
            PF          [acc = 0 on entry]
[end]
 