Quote from: kTimesG on August 28, 2024, 03:11:38 PM

Quote from: nomachine on August 28, 2024, 12:32:04 PM

Puzzle 130: ~ [Expected Hops: 2^65.64 (57392798431464251392)]

How much storage is needed to precompute Puzzle 130 ?

1. That number is kind of a reference point, can vary ± 20% Besides, the best known complexity is rather 1.66 * sqrt(b) but requires special attention when jumping through the point at infinity. Speed is better when we're certain we'll never need to double a point or go through O, since that special branch goes away..

2. It's non-sense to precompute stuff when you know all the variables. It's just faster to solve the problem. Pre-computation makes sense to search and save traps inside the same space where the wild kangaroos will jump around.

You don't need any storage to solve 130 or 160 or 66 or 250+ bits. Storage is only needed if DP > 0 or if you have more than a single Tame and Wild kangaroo. But since we don't have forever to do all those gazillion ops, the catch is to compute a lot of kangaroos in parallel - as we definitely can't compute just two kangaroos in parallel, the next jump depends on their current value.

So storage depends on whatever you wish to accomplish. Might as well just save an ID of the kangaroo that reached a DP, and re-create the walk when a match occurs, to get the distance. But it's slow if the walk was a long one.

posible prevompute part for ex from 1 to 10

then you stast 100 use precomputed.