Division by linear polynomial is not linear with degree of dividend

[codeblooded1729]

I have found that when dividing by a polynomial divisible by a large power of x, by a linear polynomial, it takes too much time. The algorithm is thus, no longer linear in the degree of polynomial

fn main() {
    use ark_std::{Zero, UniformRand};
    use std::time::Instant;
    use ark_bls12_381::Fq as F;
    let mut rng = rand::thread_rng();
    let deg = 100000;
    let mut coeffs = vec![];
    for  _ in 0..deg/2 {
        coeffs.push(F::zero());
    }

    for _ in deg/2..deg {
        coeffs.push(F::rand(&mut rng));
    }

    let f = DensePolynomial::from_coefficients_vec(coeffs);
    let linear_poly = DensePolynomial::from_coefficients_vec(vec![F::rand(&mut rng), F::rand(&mut rng)]);

    let now = Instant::now();
    let (_quotient, _remainder) = DenseOrSparsePolynomial::from(f).divide_with_q_and_r(
        &DenseOrSparsePolynomial::from(linear_poly)
    ).unwrap();
    let elapsed = now.elapsed();
    println!("Took time {:?}", elapsed);
}

cargo run --release
Took time 29.807877232s

The issue needs to be fixed, or maybe we can have a special method for division by linear poly

[Pratyush]

Thanks for catching this @codeblooded1729 ! For division by linear polynomials, I think the recommended way is to declare the divisor as a SparsePolynomial. However, I agree that the naive behaviour should not be so slow. Do you want to submit a PR that checks if the divisor is sparse (for some heuristic criteria of sparsity) and calls the sparse division routine?

[codeblooded1729]

There is an O(l * (k - l + 1)) algorithm in Shoup's book, where l is the degree of divisor and k is the degree of dividend. Should I implement that instead?

[Pratyush]

Sorry for the delay on this, but if you're still interested, please go ahead and implement that

[mmagician]

Ping @codeblooded1729, are you still interested in implementing this?