factor: only supports numbers up to 2^128 - 1 reliably with num_prime crate
Nobody has claimed this yet.
- Dominant language
- Rust
- Stars
- 24.1k
- Forks
- 2k
- Avg merge
- 1d 5h
- Merged PRs (30d)
- 365
Description
This issue is similar to https://github.com/uutils/coreutils/issues/1559, except that at the time of factor's implementation currently, u128 digit should be supported without issues using num_prime crate. The numbers that aren't supported reliably is anything above u128. For example, the factor implementation we have fails for 340282366920938463463374607431768211456768211458:
$ ~/coding-project/coreutils/target/release/factor 340282366920938463463374607431768211456768211458
factor: Factorization incomplete. Remainders exists.
On GNU, we see the following results:
$ factor 340282366920938463463374607431768211456768211458
340282366920938463463374607431768211456768211458: 2 11 11 2875070119 2895113854549549 168931247951478372779
It's true that GNU being compiled with GMP allows this factorization to be performed (otherwise, you get factor: ‘340282366920938463463374607431768211456768211458’ is too large ), but if we want to support this within uutils' factor, we might want to figure out how to get the num_prime crate to work reliably and correctly with >u128 digits or use something else entirely.
Contributor guide
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Research direction
Start with the existing factor implementation and its use of the num_prime crate. Reproduce the reported input and compare its output with GNU factor, then investigate whether num_prime can reliably handle values above u128 or whether another approach is needed. Done means factorization no longer reports an incomplete remainder for supported values above u128.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- rust
- Domain
- cli
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 35/100