
89Superefcient Monte Carlo Simulations
The procedure of doubling the number λx is summarized in Algorithm 3.4. Note that the numeri-
cal error of (3.68) is given by
≤− ++++ ≤
+
n
λ
λ
−L
(3.69)
For a given λ, the error can be made arbitrarily small by increasing the number of bits L, and there
is no error propagation.
Algorithm 3.4 Randomized Doubling
λ: = e
0
+ e
1
2 + … + e
n
2
n
Input: the multiplier.
1.
b ← (b
0
,b
1
, …,b
n
)
Initialize buffer.
Repeat
2.
b
n
←
=
∑
Calculate the LSB.
3.
x ← (x≪1) + 2
−L
s
Left shift x and restore the loss bit by adding the LSB.
4.
b ← (b≪1) + (0,0, …,X)
Left shift t ...