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: BinaryInteger/factorial() #83

Closed
oscbyspro opened this issue Sep 5, 2024 · 2 comments
Closed

Add: BinaryInteger/factorial() #83

oscbyspro opened this issue Sep 5, 2024 · 2 comments
Labels
addition oh, so shiny!

Comments

@oscbyspro
Copy link
Owner

oscbyspro commented Sep 5, 2024

Combinations and permutations use factorials; it could be fun. I know little about the state-of-the-art factorial algorithms, but a quick search gives some recursive divide-and-conquer stuff and a bunch of prime swings. I'd rather not prime sieve until I have a scalable sieve approach I'm content with, so maybe I'll try the recursive divide-and-conquer stuff.

@oscbyspro oscbyspro added the addition oh, so shiny! label Sep 5, 2024
@oscbyspro
Copy link
Owner Author

The factorial of an infinite binary integer is (value: 0, error: true) because infinite even factors over-shift the result.

@oscbyspro oscbyspro added this to the Ultimathnum 0.9.0 milestone Sep 5, 2024
@oscbyspro
Copy link
Owner Author

oscbyspro commented Sep 6, 2024

I added an over-shift fast path so that silly systems integer factorials don't take too long to compute.

oscbyspro added a commit that referenced this issue Sep 9, 2024
The first iteration of the loop is pointless so we skip it with a downshift by one. Note that the index is at least 2 at this point, so the shifted index is still nonzero. This patch only matters for small factorials, or not at all.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
addition oh, so shiny!
Projects
None yet
Development

No branches or pull requests

1 participant