Documentation errors

[asaf92]

I've read the algorithm documentation thoroughly and it seems to have many mistakes regarding the dp array.

dp meaning

The explanation for dp is:

Let's use a 3-d array dp[l][n][k] of size 4148, where n is the number of bits, k is the remaining number of k, and l is the most significant bit of the excluding endpoint.

It says "excluding", but later on it says that dp[1][i][1] = i because:

...3-bit quinary with k=1, it has three instances 001, 010, 100

Isn't 100 supposed to be excluded here?

Unclear l and n values

What does it mean when l = 1 and n = 1? The range [0, 1) doesn't make much sense and for any k that's not 0, dp[1][1][k] should return 0.
Also, in the docs it says:

  for each i in [2, 13] and j in [2, 7]:
    dp[1][i][j] = SUM{k:[0,4]}dp[0][i-1][j-k];

The meaning of dp[0][3][1] for example means "the range between [000,000)" which makes no sense.

I looked at another PR/Issue (#2) where the code was included and it seems like l should be 1 there, but even in that case it makes no sense because dp[1][2][2] should equal 1 (only 02 is valid between [00, 10)), but here it's going to return a different answer because dp[1][1][2] + dp[1][1][1] + dp[1][1][0] = 1 + 1 + 1 = 3.

Can you please clarify these issues?
Thanks!

[HenryRLee]

Hi @asaf92, thanks for creating an issue and pointing out the mistakes. This helps us improving the project.

I realized what's the root mistake in the documentation. In dp[l][n][k], n should be indicating the number of bits minus 1, or we can view it as the number of zeros. For example range [000, 1000) should be stored in dp[1][3][k].

Correcting this concept, let's try to validate each of your issues:

1. dp[1][3][1] = 3. This is correct, as it's actually indicating the range [000, 1000) with k = 3, so the instances are 001, 010, 100.

2. dp[1][1][k] makes sense now, as it's indicating the range [0, 10), which is actually any one bit quinary number. So any k <= 4 should be valid.

3. dp[1][i][j] = SUM{k:[0,4]}dp[0][i-1][j-k]; You're right, that should be dp[1][i][j] = SUM{k:[0,4]}dp[1][i-1][j-k];

4. dp[1][2][2] = 3. This is also correct, as the actual range is [00, 100), and the instances are 02, 11, 20.

Since you are the one that found the issue, you're very welcome to create a pull request to update the documentation as well. Or I can do it in a couple of weeks.

Appreciate your contribution.

[asaf92]

Thanks for the response.

You're right. I added a pull request with suggested fixes.

In my code I actually managed to solve it in a different way by keeping the original definition of n, but changing the dp[1][1][k] base cases to dp[1][2][k]. In regards to this project, it makes more sense to change the docs so that n would mean "the number of zeros", as it would be compatible with the existing LUTs that are stored in this repository.