Add implementations of remainder trees and smooth part

sagemath / sage

Main repository of SageMath

https://www.sagemath.org

Other

1.44k stars 480 forks source link

Add implementations of remainder trees and smooth part #29370

Open roed314 opened 4 years ago

roed314 commented 4 years ago

Dan Bernstein has a paper from 2004 with an algorithm for computing the smooth parts of a bunch of integers. I recently implemented a simple version of it (without much effort toward optimization) which can still be useful when used on long lists.

Component: factorization

Author: David Roe

Branch/Commit: public/ticket/29730 @ 9239d24

Issue created by migration from https://trac.sagemath.org/ticket/29370

roed314 commented 4 years ago

Branch: u/roed/smooth_parts

roed314 commented 4 years ago

New commits:

655f4f4 Smooth parts

roed314 commented 4 years ago

Commit: 655f4f4

roed314 commented 4 years ago

Author: David Roe

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 4 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

2b951f5 Improvement to remainders to prevent unnecessary multiplication

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 4 years ago

Changed commit from 655f4f4 to 2b951f5

mkoeppe commented 4 years ago

comment:4

Batch modifying tickets that will likely not be ready for 9.1, based on a review of the ticket title, branch/review status, and last modification date.

mezzarobba commented 4 years ago

comment:5

Some quick comments:

The branch needs to be rebased.
The patchbot has a couple of complaints about docstring formatting. Maybe also remove the spaces around = in examples like n.smooth_part(B = 10).
I think your product tree algorithm requires commutativity. If that's indeed the case, it should be documented and/or checked (or improved).

I don't understand what this block is for:

+        if not isinstance(x, Integer):
+            x = Integer(x)

I don't like that there are no tests covering 0, 1, and negative inputs.

mkoeppe commented 3 years ago

comment:8

Setting new milestone based on a cursory review of ticket status, priority, and last modification date.

mkoeppe commented 3 years ago

comment:9

Setting a new milestone for this ticket based on a cursory review.

fchapoton commented 2 years ago

Changed commit from 2b951f5 to 9239d24

fchapoton commented 2 years ago

Changed branch from u/roed/smooth_parts to public/ticket/29730

fchapoton commented 2 years ago

comment:13

branch refreshed

New commits:

9239d24 Smooth parts