uutils / uutils/coreutils

factor: only supports numbers up to 2^128 - 1 reliably with num_prime crate

Open
#9,177 4 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

U - factor
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

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.