Quote from: NotATether on Today at 05:22:50 AM

Quote from: kTimesG on June 29, 2024, 01:06:16 PM

...
So a total of 6 multiplications for each jump of each kangaroo.

So since there's an error ratio of only using 2-steps folding: r(r - 1) / 2N
and you have 6 multiplications / jump
and you do a lot of jumps deterministically

at some point, that error will exhibit itself and all future computations get screwed up.

That error rate would be approximately 2**32 squared, i.e. 2**64, divided by 2**256 * 2 so 2**-193 per kangaroo.

If we want to be pragmatic, then approximately 2**-191 something per kangaroo or a 1/2**191 chance it messes up, when we account the 6 multiplications per kangaroo.

But it's still a really small number.

We can make a lot of pairs for which they are equal to the un-reduced product. But it is much harder to satisfy the second condition, and I don't know if anyone has generated any counter-examples.

That's not really correct.

Each kangaroo contributes to a running product for a single inversion.

So when a multiply is incorrect then the root product to invert is wrong, and this results in a wrong root inverse. The inversion is then propagated back to each kangaroo.

So then the whole batch gets corrupted from that point on.

Let's say 512 kangs/batch. The error goes up from 2**-193 to 2**-185.

Imagine then that the discrete points that get saved are then redistributed to other work items, in a batch with other correct kangaroos. Then that batch gets corrupted right after the first batch jump as well, since one of the points was computed wrong.

And you have 512 wrong points already. Maybe each of them ends up in its own batch.

Regarding the counterexample test vector to proof the incorrectness... well, unless there's some part of the code that actually checks if a discrete point is indeed correct, then it's a silent bug. I don't think it's possible to calculate what values you need to trigger the bug, due to the huge numbers involved. In this case, who can ever know if their results are in a valid state or not?