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

Req. normalized arbitrary integer elements #26

Open
oscbyspro opened this issue Jun 22, 2024 · 3 comments
Open

Req. normalized arbitrary integer elements #26

oscbyspro opened this issue Jun 22, 2024 · 3 comments
Labels
brrr such code, much wow documentation scribbles n' doodles! maybe to do, or not to do?

Comments

@oscbyspro
Copy link
Owner

Idea: generic algorithms would never need to perform conservative normalization checks or transformations in big integer branches if big integers are required to offer normalized elements. InfiniInt<T> already does this because it would be silly to do otherwise, but generic algorithms cannot yet assume it.

@oscbyspro oscbyspro added the brrr such code, much wow label Jun 22, 2024
@oscbyspro
Copy link
Owner Author

oscbyspro commented Jun 22, 2024

BinaryInteger/isZero was the first use case I thought of, but I suppose I could improve it be checking the appendix bit first and performing the comparison backwards. I'm sure there are other use cases, however.

Edit: I suppose BinaryInteger/isZero would still improve somewhat since it would compare zero elements instead of one or zero elements (backwards). At the same time, big integers are kind of slow by definition so I would not put much emphasis on an element comparison.

@oscbyspro oscbyspro added documentation scribbles n' doodles! maybe to do, or not to do? labels Jun 22, 2024
oscbyspro added a commit that referenced this issue Jun 23, 2024
This changes makes DataInt/isZero an O(1) operation for normalized instances because the last element of a normalized instance must not be zero when the appendix is zero.
@oscbyspro oscbyspro closed this as not planned Won't fix, can't repro, duplicate, stale Jun 23, 2024
@oscbyspro
Copy link
Owner Author

oscbyspro commented Jul 26, 2024

Another unnecessary normalization is found in BinaryInteger.random(in:using:)'s arbitrary integer path, more specifically in one of the internal Randomness algorithms.

@oscbyspro oscbyspro reopened this Jul 26, 2024
@oscbyspro oscbyspro changed the title Req. big integer elements be normalized Req. that arbitrary integer body is normalized Jul 26, 2024
@oscbyspro oscbyspro changed the title Req. that arbitrary integer body is normalized Req. normalized arbitrary integer body Jul 26, 2024
@oscbyspro oscbyspro changed the title Req. normalized arbitrary integer body Req. normalized arbitrary integer elements Jul 27, 2024
@oscbyspro
Copy link
Owner Author

oscbyspro commented Jul 27, 2024

My primary concern is that normalized elements may not be normalized after you reinterpret them, which this project does a lot. It could be surprising if elements and elements-as-type behave differently. Also, the performance improvement is small.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
brrr such code, much wow documentation scribbles n' doodles! maybe to do, or not to do?
Projects
None yet
Development

No branches or pull requests

1 participant