[papa2fire]

I still have trouble understanding your code. I don’t get why you’re still using ‘probas’ and the inverse probability (line 186:187). I suggest creating an array of 3^14 random numbers and simply using it as input to the function to sum Hamming distances. Since you prefer C++, I made a naive version. I create a space of 3^14 elements, but instead of random numbers, I use sequential ones (the value at position i is equal to i). This makes it easier to compare results. For example, the sum of the Hamming neighbors up to 4 from the first element should give you 18847285404. Let me know how long it takes on your machine (maybe better via GitHub, as it notifies replies to comments). I’m sure you’ll figure out how to optimize it. https://github.com/petopello/PSA/blob/main/naive.cpp

[GistNoesis]

My code is just iterating over the relevant points.

Line 186:187 is the trick to group negative probabilities. You can't apply this if you want to take into account a payout structure which depends on the result.

The more flexible version is Line 421, where you don't use this inverse probability trick, and instead of recomputing proba from scratch could use a precomputed array of 3^14 random element.

Both version should return the same result. You have two boolean useNaive and neighborInBetSpace (4 possibilities) which allows to choose the summation strategy to use, it should give the same results.

I tried understanding your code, but I have trouble understanding the recurrence relation, and where it comes from. In particular how do you make sure you avoid double counting (The neighborhood of a neighborhood contain the original point).

My experiments are about understanding your algorithm in terms of things I understand, namely loop optimizations, partitioning, reordering and memoization. I am trying to make the structure emerge from simple code transformations (to guarantee exactitude). This process usually consist into writing nested loops with everything being recomputed inside the innermost loop, and then find a way to reuse the computations.

Fast code is about memory usage and recomputing from a small cache is often faster than materializing a big array.

[papa2fire]

To understand recursion, and given that we know the initial value of r (r=4), I suggest replacing the recursive calls with a simple copy-paste of the function body. You’ll see that it’s just four nested loops each one iterating over the 14 dimensions and making changes to them. Each loop starts at the next dimension after the previous one, ensuring that changes are only made in increasing order. This is the key to avoiding duplicates—each pair of modified dimensions is generated only once (e.g., 1&2 is generated, but 2&1 is not). This is controlled by the last parameter (min), which defaults to 0 and sets the starting value of the loops. Another way to see it is that the function returns the sum of neighbors up to distance r, but only by making changes in dimensions equal to or greater than 'min'.

[GistNoesis]

Is the recursion relation you use https://en.wikipedia.org/wiki/Hockey-stick_identity ? Are you sure you can't use https://en.wikipedia.org/wiki/Pascal%27s_rule instead for a simpler recursion. Have you also tried using https://en.wikipedia.org/wiki/Vandermonde%27s_identity ?

[papa2fire]

Ohh, very interesting, thanks! I’m not entirely sure, but yes, I’d say my naive implementation uses the hockey stick principle. That said, I think many implementations are possible. We could also eliminate recursion by using an index array to store the values of 'min' variable, but I think that would make the behavior harder to understand.

In any case, the key point in my view is that there are 19,321 neighbors at distance ≤4. If we assume as an input condition that their values can be arbitrary—that is, the value of one neighbor has no relation to the others—then regardless of the implementation or mathematical identity used, we’ll end up performing 19,320 summations.

It’s a different story if we want to repeat this process for multiple points. In that case, we can optimize, since some neighbors might be shared and summed only once. This is exactly what my algorithm does: by handling everything in a matrix-based way, it reduces the number of summations per point to just 101 instead of 19,321. I’m not sure if there’s a specific mathematical identity behind this. In fact, I asked on StackExchange but haven’t had much success: https://math.stackexchange.com/questions/5040947/efficient-a...