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

Offer conversion with Natural. #678

Open
kindaro opened this issue May 11, 2024 · 1 comment
Open

Offer conversion with Natural. #678

kindaro opened this issue May 11, 2024 · 1 comment

Comments

@kindaro
Copy link
Contributor

kindaro commented May 11, 2024

A task one sometimes has to deal with is to take a number and look at the bytes it is made of. In other words, a number can be seen as an array of bytes. Specifically, there is a one to one inlay of numbers into byte strings and its inverse from byte strings back to numbers. It would be convenient if such a pair of functions could be found in this package.

There are two ways to encode a number into an array: least or most significant bit first. We can pick whichever is faster. There is also some confusion as to whether the encoding of 0 should be an empty byte string or a lonely zero byte. Neither is more mathematically principled than the other — we can pick whichever is more handy for our algorithm.

I think there is a linear time algorithm for either most significant or least significant digit first. But we can talk about implementation details once the design is agreed upon.

@clyring
Copy link
Member

clyring commented May 16, 2024

ghc-bignum provides some primitives along these lines. See naturalToAddr and naturalFromAddr (and their ByteArray# analogues) in GHC.Num.Natural.

integer-simple is not so kind, though its representation does allow repeated shifts and integerToWord calls to extract the bytes in linear time. But it's probably not worth fiddling with the older bignum libraries at all.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants