search

Bodigrim / arithmoi

Number theory: primes, arithmetic functions, modular computations, special sequences
http://hackage.haskell.org/package/arithmoi
MIT License
147 stars 40 forks source link

Lazy factorisation of huge numbers #72

Closed Bodigrim closed 6 years ago

Bodigrim commented 7 years ago

Function factorise is a lazy producer of small factors, but not of bigger ones. If trial division is not enough, factorisation over elliptic curve is invoked, which does not return any factor, until it finds them all. This is inconvenient and redundant in many scenarios, when computations can short-circuit as soon as several first factors were found (for instance, Mobius function).

The proposed patch eliminate this defect. E. g., now it is possible to compute first factor of huge composite without factoring it completely:

> head $ factorise' $ 14145130711 * 10000000000000000000000000000000000000121 * 100000000000000000000000000000000000000000000000447
(14145130711,1)

The only (and expected) shortcoming is that the list of factors is no longer sorted. But we never claimed it is, it has always been just an implementation detail.

Bodigrim commented 7 years ago

Thanks for review! I have implemented some of suggestions.

cfredric commented 7 years ago

In the spirit of laziness, the factorise in Math.NumberTheory.GaussianIntegers could also be improved. The current implementation outputs factors in order of ascending magnitude, but that also isn't guaranteed by the doc comment - it's just an implementation detail.

I'd have to test it out to be sure (since it's been a while since I wrote that code), but I think this would be as simple as removing the reverse . in the definition of factorise (once Factorisation.factorise is modified to be lazy).

cfredric commented 7 years ago

Ahh I lied, it's not that simple. It would also require modifying factorise's helper to just add factors to the list as it goes, rather than building the list as an accumulator. But I have no doubt that's a trivial change compared to the rest of this PR :)

Bodigrim commented 7 years ago

@cfredric it would be nice if you get time to prepare a patch for Math.NumberTheory.GaussianIntegers.factorise.

Bodigrim commented 6 years ago

Patch for lazy factorise for GaussianIntegers is in #76.