GPGPU Programming for Games and Science

CPU Computing 25

where the high-order 1-bit occurs at index 

d

≥ 0. The coefficients d

i

are the

remaining bits of the number, if any.

We may write r as

r =

n

d

=

2



n

+





n

−1

i=0

n

i

2

i

2



d

+





d

−1

i=0

d

i

2

i

=

1+





n

−1

i=0

n

i

2

i−

n

1+





d

−1

i=0

d

i

2

i−

d

2



n

−

d

=

1+α

1+β

2



n

−

d

(2.13)

where α and β are defined by the last equality and both numbers are neces-

sarily in the interval [0, 1).

When α ≥ β,(1+α)/(1 + β) ∈ [1, 2) and

1+α

1+β

=1+

∞



i=0

c

i

2

−(i+1)

=1.c (2.14)

When α<β,(1+α)/(1 + β) ∈ (0, 1), which implies 2(1 + α)/(1 + β) ∈ (1, 2)

and

2(1 + α)

1+β

=1+

∞



i=0

c

i

2

−(i+1)

=1.c (2.15)

Equations (2.14) and (2.15) may be combined to produce the representation

r =1.c ∗ 2



n

−

d

−ω

=1.c ∗ 2

p

(2.16)

where ω is defined ...