Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

GeneROMst: Incorect generational index normalization formula for wrap-around #3

Open
eddyp opened this issue Jul 20, 2020 · 0 comments
Assignees
Labels
bug Something isn't working

Comments

@eddyp
Copy link
Contributor

eddyp commented Jul 20, 2020

Current description says "in case of wrap around, to ease up chronological ordering, we need to calculate normalized generation indexes of entry i (gi): gi = (Gi + N) % N",

But looking at the example values for wrap-around case 2 3 5 18 , and the example gi values for these (18 19 21 2), the applied formula was actually gi = (Gi + N) % 2N.

Note that if the '% N' formula is applied, we'd get collisions on the example between Gi=2 and Gi=18, as they'd map to gi=2.

Hence the right formula should be %2N.

The correctness of the normalization could be checked based on the property "starting with some arbitrary Gi in [0, 2N), write an arbitrary number of entries <= N, and gi (the normalized Gi) should be oldest/smallest"

@eddyp eddyp added the bug Something isn't working label Jul 20, 2020
@eddyp eddyp self-assigned this Jul 20, 2020
@eddyp eddyp added this to the Validated schematic milestone Jun 8, 2021
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
bug Something isn't working
Projects
None yet
Development

No branches or pull requests

1 participant