Quote from: RetiredCoder on November 07, 2024, 08:49:07 PM

If I need to increase average distance I generate larger jumps, but I don't change the number of jumps in the jump table.
But it seems you do, you added 8 more points to get x256 average distance somehow. So next my question is how do you generate the jump table?

Powers of two, and adjust the last element to the value needed to have the desired average.

This jump set was proven optimal here (e.g. minimizes total number of operations):

Kangaroos, Monopoly and Discrete Logarithms, J. M. Pollard, 2000

You can experiment (like I did) with lots of types of jump sets (powers of 3, 4, fibonacci, squarings, cubing) and compare them. Some will have more or less jump points than others, the important thing here is the average value, not the size of the jump set.

There is a relationship between the average jump size, the jump set, the interval size, and the number of kangaroos (processors). My intuition is that you (and JLP) are observing that a smaller than optimal jump average (sqrt(b)), combined with a larger number of kangaroos (millions or more), results in some bounded runtime, which make you think the jump sizes were optimal, when actually the non-optimal jumps were practically compensated by having lots of kangaroos.

Question for you: do you prefer fewer kangaroos that jump faster, or lots of kangaroos that jump slower?

How can you explain case #3 (the awful case with runtime 172 sqrt)? When the Tame and Wild are separated by a distance of b/2, and the average jump size is much too small, it will take a lot of jumps for them to ever meet. In the random case, it's a little better than that, but still too far from the optimal case (e.g. a correct larger average jump size).