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

Add partial implementation of arbitrary-precision integers #2

Merged
merged 15 commits into from Apr 30, 2017
Merged

Conversation

xwu
Copy link
Owner

@xwu xwu commented Apr 29, 2017

...and correct some implementations in Rational.

Although it was possible to implement many of the simpler algorithms using a two's complement representation, it proved to be difficult to implement multiplication or division without taking the absolute value. Some reading suggests that most (if not all) arbitrary-precision integer implementations use sign-and-magnitude representation. Thus, I have switched back to that representation (which was one option that I had already explored).

This PR contains working implementations of comparison, addition, subtraction, long multiplication, and negation. Additional testing is required to verify correctness.

No attempt has yet been made to implement division or bit shifting, and no updated implementation is included for other bitwise operations. It remains unclear to me whether generic use of such operations always assumes two's complement representation, or whether it is appropriate to simply perform these bitwise operations on the native sign-and-magnitude representation.

Future directions include implementation of more sophisticated multiplication algorithms such as Karatsuba.

@xwu xwu changed the title [WIP] Add arbitrary-precision integers Add partial implementation of arbitrary-precision integers Apr 30, 2017
@xwu xwu merged commit 1736e69 into master Apr 30, 2017
@xwu xwu deleted the big branch April 30, 2017 23:48
@xwu xwu added the enhancement label May 7, 2017
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

Successfully merging this pull request may close these issues.

None yet

1 participant