search

PRL-PRG / UFOs

User Fault Objects: making vectors lazy and forgetful.
12 stars 3 forks source link

I don't believe the binary search implementation is correct #26

Closed jimhester closed 3 years ago

jimhester commented 3 years ago

At https://github.com/PRL-PRG/UFOs/blob/84c8ac6476afdb5ee7993ab54dc6727e1e22377b/ufos/src/mappedMemory/sparseList.c#L92-L93

The key insight in the linked post seems to be that the sum needs to be done with unsigned arithmetic, otherwise the sum overflows. Your implementation uses signed 64 bit integers in the sum, so I believe it would still have the same issue.

In languages with >>>, the sign is discarded, so the overflow doesn't matter, but C and C++ don't have this operator so you need to cast the operands to uint64_t before summing I believe.

See http://codepad.org/HnaW00QX for an example

electroCutie commented 3 years ago

@jimhester i think that setting the middle, low, and high markers to always be unsigned would also be correct, yes?

jimhester commented 3 years ago

yeah that should work as well

electroCutie commented 3 years ago

Put the fix into the latest patch on the feature branch for subsetting along with another fix

Thanks for the catch