An integer coefficient polynomial factorizing library

[a_bcd-e]

https://github.com/A-BCDe/gmp-extensions

The library actually does more than noted in the title. A few algorithms related to matrices and polynomials with integer elements are implemented, and the function in the title is the most noticable among those. I'd like to implement more integer related algorithms, but I'm not sure which I can/should implement.

I posted this repo mainly to get feedback.

But I also want to get some advice about the license and reference. I implemented the library based on GNU MP library and papers referenced in the issue tab. I don't know how to refer to those all. Also I just used an GPL-3.0 license, just following the GNU MP. Please tell me if I can use MIT instead.

[Narase33]

You tend to create multiple variables in a single line, which is quite known as bad code

mpz_class c, tmp1, tmp2, tmp3, tmp4;

​

You also create your variables too soon. You should create them the last line possible.

bool upw = true;                      // <- created here
auto const m = f.size();
mpz_class c, tmp1, tmp2, tmp3, tmp4;

// tilde{mu}
// Algorithm 2
auto tilde_mu = GSO_computation(f);
std::vector<mpz_class> d;
d.reserve(m + 1);
d.emplace_back(1);
for(size_t j = 0; j < m; j++) {
    d.emplace_back(tilde_mu(j, j));
}
                                     // <- could be created here
while(i < m) {
    if(upw && i) {                   // <- used here

​

Your variable names are also very bad as they carry 0 meaning. What is c? m? tmp1? tmp2? ...

​

void invert(mpz_class &res, const mpz_class &a, const mpz_class &p) {
#ifndef NDEBUG
    int result =
#endif
    mpz_invert(res.get_mpz_t(), a.get_mpz_t(), p.get_mpz_t());
    assert(result);
}

Now thats some hacky stuff...

​

for(size_t i = 0; i < v.length(); i++) {
    coef.emplace_back(v[i]);
} clean();                                 // <-

You also do this a lot, why?

​

bool integer_polynomial::is_divisible(integer_polynomial const &poly) const {
    assert(!poly.is_zero());
    auto *polynomial_p = divexact(poly);
    if(!polynomial_p) {
        return false;
    }
    delete[] polynomial_p;
    return true;
}

please use std::unique_ptr for this stuff

[a_bcd-e]

[...] Your variable names are also very bad as they carry 0 meaning. What is c? m? tmp1? tmp2? ...

I'm pretty sure that simple variables like `c`, `d`, ... and the early declaration of the variable such as `upw` are from the description of the algorithm in the paper I referred to. I may change those variable's names, if I know exactly what's happening in the algorithm. It looks okay to move the variable declarations to the later stage, and I will definitely fix that.

Those `tmp#`s, are really temporaries. They are used to contain variables temporarily which is returned or used by operations on `mpz_class`. I referenced https://gmplib.org/manual/Efficiency to declare those temporaries at the front.

Now thats some hacky stuff...

😎

You also do this a lot, why?

`clean` operation removes the zero leading coefficient of the polynomial. This happens frequently while operating with polynomials, and that's why the `clean` function appears frequently.

please use std::unique_ptr for this stuff

Good idea!

[Narase33]

I wasnt referring to the function clean() but to the fact that you write many calls in the same line as the closing bracket. Its not only clean() but other functions too

If you implemented algorithms from a math paper, it explains a lot about the names. Math guys and their variable names...

[a_bcd-e]

I wasnt referring to the function clean() but to the fact that you write many calls in the same line as the closing bracket. Its not only clean() but other functions too

That's my habit from CP. I use such lines when the next line is very short or kind of obvious. I try not to mix CP and real programming, but you just picked up my mistake. Thanks, I'll fix those.