Another idea:
do you use the symetrie?
If you shift the range from [a,b] to [-(b-a)/2, (b-a)/2] and you generate tame in this range, for each point you create actually a couple of opposite points in the same interval (same x), in this way you probably should have more collisions.
The tame points starting from the negative part of the interval create a couple of points that move towards the center of the interval, while the tame points starting from the positive part create a couple of points that move towards the extreme of the interval. In this way, each tame walks across the double of the points in the interval (with the same computational cost). Same for the wild ones.
Yes i have to investigate, I already tested several things without improving things.
Translating tame is like translating wild in the opposite direction.No. I meant: translate tame
and wild. Not only tame. In a interval with 2^n points but only 2^(n-1) coordinates 'x' (instead of 2^n) to increase the probability to have a collision. If you do the same number of steps in a half space (from coordinates x point of view), the chance should be higher. Half number of x coordinates, half DP, same number of steps, more chance.
Like I said before,
a tame kangaroo and a wild kangaroo in this scenario collide not only if they fall in the same position but if they fall in 2 different positions (but symetric respect of the center of the interval) as well.
If you instead translate this interval in any other position of the curve, when a tame kangaroo and a wild kangaroo fall in 2 positions symetric respect of the center of the interval, your current algorithm doesn't detect a collision, simply because it can't know (without more computation) the x coordinate of the symetric point (respect of (a+b)/2 * G) of any DP that lies in the hashtable (
and a symetric point of a DP generally is not a DP)
May be a brownian motion can be interesting (having positive and negative jump).
My idea goes a little in that direction too, cause the jumps are always positive but the points generated go in both direction, exploiting the symetrie of the curve.
Example:
when a sequence starts from -k*G (negative part):
-k*G, (-k + 2^17)*G, (-k +2^17 + 2^3)*G, .... forth -->but in this way you have too (for free) the x coordinates of :
+k*G, (+k - 2^17)*G, (+k- 2^17 - 2^3)*G, .... <-- back
the movement is like this:
zero point
(--> <--) extreme:
-k*G, k*G
(--> <--) extreme:
(-k+2^17)*G, -(-k+2^17)*G
(--> <--) extreme:
(-k+2^17+2^3)*G, -(-k+2^17+2^3)*G
when a sequence starts/arrives in the positive part:
k*G, (k + 2^8)*G, (k +2^8 + 2^31)*G, .... forth -->-k*G, (-k - 2^8)*G, (-k -2^8 - 2^31)*G, .... <-- back
zero point
<-- (
)--> extreme: -k*G,
k*G <--(
)--> extreme: -(k+2^8)*G,
(k+2^8)*G <--(
)--> extreme: -(k+2^8+2^31)*G,
(k+2^8+2^31)*G
