still have lots of collision in same herd (using -d 0, it disable the distinguished point, so all collision and cycle are detected). The size of this table seems to no impact the bad collision number. I will read the ref[8] asap.
https://www.math.auckland.ac.nz/~sgal018/RamCiren.pdf
Hi, for your tuning's problems you can apply the following considerations to the classic version. This paper doesn't deal with equivalence classes.
Quote
“type 1” bad points: it could happen that some processor never finds a distinguished point
--> To guard against bad steps of type 1 van Oorschot and Wiener [22] set a maximum number of steps in
a walk. They choose this maximum to be 20/θ steps and show that the proportion of bad
points of type 1 is at most 5 × 10^−8. If a processor takes this many steps without hitting a distinguished point then it restarts on a new random starting point.
--> To guard against bad steps of type 1 van Oorschot and Wiener [22] set a maximum number of steps in
a walk. They choose this maximum to be 20/θ steps and show that the proportion of bad
points of type 1 is at most 5 × 10^−8. If a processor takes this many steps without hitting a distinguished point then it restarts on a new random starting point.
Quote
“type 2” bad points: it seems to be impossible to design pseudorandom walks which cover T or W uniformly but which do not sometimes overstep the boundaries. Steps outside the regions of interest cannot be included in our probabilistic analysis and so such steps are “wasted”. We call these “type 2” bad points.
We now give the main result of the paper, which is a version of the Gaudry-Schost algorithm which has a
faster running time. The key observation is that the running time of the Gaudry-Schost algorithm depends
on the size of the overlap between the tame and wild sets. If it is possible to make the size of this overlap
constant for all possible Q then the expected running time will be constant for all problem instances. We
achieve this by choosing walks which only cover certain subsets of T and W.
Precisely, instead of using the sets T and W of the previous section
T = [-N,N]
W = [k-N,k+N]
we use
T0 = [−2N/3, 2N/3] ⊆ T
W0 = [k − N, k − N/3] ∪ [k + N/3, k + N] ⊆ W (see Figure 1).
Running time: 2.05*sqrt(N)
We now give the main result of the paper, which is a version of the Gaudry-Schost algorithm which has a
faster running time. The key observation is that the running time of the Gaudry-Schost algorithm depends
on the size of the overlap between the tame and wild sets. If it is possible to make the size of this overlap
constant for all possible Q then the expected running time will be constant for all problem instances. We
achieve this by choosing walks which only cover certain subsets of T and W.
Precisely, instead of using the sets T and W of the previous section
T = [-N,N]
W = [k-N,k+N]
we use
T0 = [−2N/3, 2N/3] ⊆ T
W0 = [k − N, k − N/3] ∪ [k + N/3, k + N] ⊆ W (see Figure 1).
Running time: 2.05*sqrt(N)
Considering the DP too:
Quote
In the 1-dimensional case we use a standard pseudorandom walk as used by Pollard [15] and van Oorschot
and Wiener [22] i.e., small positive jumps in the exponent. The average distance in the exponent traveled
by a walk is m/θ, where m is the mean step size and θ is the probability that a point is distinguished. For
example, one may have m = c1√N and θ = c2/√N for some constants 0 < c1 < 1 and 1 < c2. Therefore, to
reduce the number of bad steps of type 2 we do not start walks within this distance of the right hand end
of the interval. In other words,
we do not start walks in the following subset of T0
[2N/3 - (m/theta), 2N/3]
we do not start walks in the following subset of W0
[k − N/3 - m/theta, k − N/3] ⊆ W and [k + N -m/theta, k + N] ⊆ W
Let m be the mean step size and max the maximum step size.
The probability that a walk has bad points of type 2 is at most
p =(20 max −m) / (2N*θ/3 − m)
For the values m = c1√N1, max = 2m and θ = c2/√N1 the value of p in equation is 39c1/(2c2/3 −
c1) which can be made arbitrarily small by taking c2 sufficiently large (i.e., by storing sufficiently many
distinguished points). Hence, even making the over-cautious assumption that all points are wasted if a walk
contains some bad points of type 2, the expected number of walks in the improved Gaudry-Schost algorithm
can be made arbitrarily close to the desired value when N is large. In practice it is reasonable to store at
least 2^30 distinguished points, which is quite sufficient to minimise the number of bad points of type 2.
We stress that the choices of m, max and θ are not completely arbitrary. Indeed, if one wants to bound
the number of bad points of type 2 as a certain proportion of the total number of steps (e.g., 1%) then for
a specific N there may be limits to how large θ and max can be. For smaller N we cannot have too small a
probability of an element being distinguished or too large a mean step size.
and Wiener [22] i.e., small positive jumps in the exponent. The average distance in the exponent traveled
by a walk is m/θ, where m is the mean step size and θ is the probability that a point is distinguished. For
example, one may have m = c1√N and θ = c2/√N for some constants 0 < c1 < 1 and 1 < c2. Therefore, to
reduce the number of bad steps of type 2 we do not start walks within this distance of the right hand end
of the interval. In other words,
we do not start walks in the following subset of T0
[2N/3 - (m/theta), 2N/3]
we do not start walks in the following subset of W0
[k − N/3 - m/theta, k − N/3] ⊆ W and [k + N -m/theta, k + N] ⊆ W
Let m be the mean step size and max the maximum step size.
The probability that a walk has bad points of type 2 is at most
p =(20 max −m) / (2N*θ/3 − m)
For the values m = c1√N1, max = 2m and θ = c2/√N1 the value of p in equation is 39c1/(2c2/3 −
c1) which can be made arbitrarily small by taking c2 sufficiently large (i.e., by storing sufficiently many
distinguished points). Hence, even making the over-cautious assumption that all points are wasted if a walk
contains some bad points of type 2, the expected number of walks in the improved Gaudry-Schost algorithm
can be made arbitrarily close to the desired value when N is large. In practice it is reasonable to store at
least 2^30 distinguished points, which is quite sufficient to minimise the number of bad points of type 2.
We stress that the choices of m, max and θ are not completely arbitrary. Indeed, if one wants to bound
the number of bad points of type 2 as a certain proportion of the total number of steps (e.g., 1%) then for
a specific N there may be limits to how large θ and max can be. For smaller N we cannot have too small a
probability of an element being distinguished or too large a mean step size.
Let us spin this wheel and set the center of the range to the Zero point 
