<commit_before>/*=============================================================================

    This file is part of FLINT.

    FLINT is free software; you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation; either version 2 of the License, or
    (at your option) any later version.

    FLINT is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with FLINT; if not, write to the Free Software
    Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301 USA

=============================================================================*/
/******************************************************************************

    Copyright (C) 2008, 2009 <NAME>
    Copyright (C) 2010 <NAME>

******************************************************************************/

#include <stdlib.h>
#include <mpir.h>
#include "flint.h"
#include "fmpz.h"
#include "fmpz_vec.h"
#include "fmpz_poly.h"

/*
    No aliasing.
    lenA >= lenB > 0.

    Sets {Q, lenA - lenB + 1} and {R, lenB - 1} to the quotient and remainder.
    Expects R to be of length lenA on input.
 */
void 
_fmpz_poly_pseudo_divrem_divconquer(fmpz * Q, fmpz * R, ulong * d, 
                          const fmpz * A, long lenA, const fmpz * B, long lenB)
{
    const long crossover1 = (lenB <= 12) ? 8 : 16;
    const long crossover2 = 128;

    const long n2 = lenB / 2;
    const long n1 = lenB - n2;

    const fmpz * d1 = B + n2;
    const fmpz * d2 = B;
    const fmpz * d3 = B + n1;
    const fmpz * d4 = B;

    if (lenB <= crossover1 || (lenA > 2 * lenB - 1 && lenA < crossover2))
    {
        _fmpz_poly_pseudo_divrem_basecase(Q, R, d, A, lenA, B, lenB);
    }
    else if (lenA <= n2 + lenB - 1)
    {
        fmpz *p1, *r1, *d2q1;
        fmpz_t f;

        /*
           Here, n1 + n2 - 1 < lenA <= n1 + 2 n2 - 1

           Shift A right by n1 and zero the bottom n2 - 1 coeffs, call this p1
         */

        p1 = (fmpz *) malloc((lenA - n1) * sizeof(fmpz));
        {
            long i;
            mpn_zero((mp_ptr) p1, n2 - 1);
            for (i = n2 - 1; i < lenA - n1; i++)
                p1[i] = (A + n1)[i];
        }

        /*
           Compute p1 div d3, at most a 2 n2 - 1 by n2 division, leaving 
           lenA - lenB + 1 <= n2 terms in the quotient
         */

        r1 = R + n1;
        _fmpz_poly_pseudo_divrem_divconquer(Q, r1, d, p1, lenA - n1, d3, n2);

        _fmpz_vec_zero(r1 + (n2 - 1), lenA - n1 - n2 + 1);

        free(p1);

        /*
           Compute d2q1 = Q d4 of length lenA - lenB + n1, which is 
           at most n1 + n2 - 1 terms
         */

        d2q1 = _fmpz_vec_init(lenA - lenB + n1);
        
        _fmpz_poly_mul(d2q1, d4, n1, Q, lenA - lenB + 1);

        /*
           Compute R = L^d R', where R' is the terms of A we have not dealt, 
           of which there are at most n1 + n2 - 1
         */

        fmpz_init(f);
        fmpz_pow_ui(f, B + (lenB - 1), *d);

        /*
           Set R to {A, n1 + n2 - 1} * f + r1 x^n1 - d2q1
         */

        _fmpz_vec_scalar_mul_fmpz(R, A, n1, f);
        _fmpz_vec_scalar_addmul_fmpz(R + n1, A + n1, n2 - 1, f);
        _fmpz_vec_sub(R, R, d2q1, lenA - lenB + n1);

        _fmpz_vec_clear(d2q1, lenA - lenB + n1);

        fmpz_clear(f);
    }
    else if (lenA > 2 * lenB - 1)
    {
        ulong s1, s2;
        const long shift = lenA - 2 * lenB + 1;

        fmpz * q1 = Q + shift;
        fmpz * q2 = Q;
        fmpz * r1 = R;
<commit_msg>Small update to pseudo_divrem_divconquer<commit_after>/*=============================================================================

    This file is part of FLINT.

    FLINT is free software; you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation; either version 2 of the License, or
    (at your option) any later version.

    FLINT is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with FLINT; if not, write to the Free Software
    Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301 USA

=============================================================================*/
/******************************************************************************

    Copyright (C) 2008, 2009 <NAME>
    Copyright (C) 2010 <NAME>

******************************************************************************/

#include <stdlib.h>
#include <mpir.h>
#include "flint.h"
#include "fmpz.h"
#include "fmpz_vec.h"
#include "fmpz_poly.h"

void 
_fmpz_poly_pseudo_divrem_divconquer(fmpz * Q, fmpz * R, ulong * d, 
                          const fmpz * A, long lenA, const fmpz * B, long lenB)
{
    const long crossover1 = (lenB <= 12) ? 8 : 16;
    const long crossover2 = 128;

    const long n2 = lenB / 2;
    const long n1 = lenB - n2;

    const fmpz * d1 = B + n2;
    const fmpz * d2 = B;
    const fmpz * d3 = B + n1;
    const fmpz * d4 = B;

    if (lenB <= crossover1 || (lenA > 2 * lenB - 1 && lenA < crossover2))
    {
        _fmpz_poly_pseudo_divrem_basecase(Q, R, d, A, lenA, B, lenB);
    }
    else if (lenA <= n2 + lenB - 1)
    {
        fmpz *p1, *r1, *d2q1;
        fmpz *f;

        /*
           Here, n1 + n2 - 1 < lenA <= n1 + 2 n2 - 1

           Shift A right by n1 and zero the bottom n2 - 1 coeffs, call this p1
         */

        p1 = (fmpz *) malloc((lenA - n1) * sizeof(fmpz));
        {
            long i;
            mpn_zero((mp_ptr) p1, n2 - 1);
            for (i = n2 - 1; i < lenA - n1; i++)
                p1[i] = (A + n1)[i];
        }

        /*
           Compute p1 div d3, at most a 2 n2 - 1 by n2 division, leaving 
           lenA - lenB + 1 <= n2 terms in the quotient
         */

        r1 = R + n1;
        _fmpz_poly_pseudo_divrem_divconquer(Q, r1, d, p1, lenA - n1, d3, n2);

        free(p1);

        /*
           Push the relevant {n2 - 1} terms of the remainder to the 
           top of {R, lenA}
         */

        {
            long i;
            for (i = n2 - 2; i >= 0; i--)
                fmpz_swap(R + lenA - (n2 - 1) + i, r1 + i);
            r1 = R + lenA - (n2 - 1);
        }

        /*
           Compute d2q1 = Q d4 of length lenA - n2, which is 
           at most n1 + n2 - 1 terms
         */

        d2q1 = R;
        _fmpz_poly_mul(d2q1, d4, n1, Q, lenA - lenB + 1);

        /*
           Compute R = L^d R', where R' is the terms of A we have not dealt, 
           of which there are at most n1 + n2 - 1; that is, 

           Set R to {A, n1 + n2 - 1} * f + r1 x^n1 - d2q1
         */

        _fmpz_vec_neg(R, R, lenA - n2);
        {
            long i;
            for (i = 0; i < lenA - lenB; i++)
                fmpz_add(R + n1 + i, R + n1 + i, R + lenA - (n2 - 1) + i);
            for ( ; i < n2 - 1; i++)
                fmpz_swap(R + n1 + i, R + lenA - (n2 - 1) + i);
        }
        f = R + lenB - 1;
        fmpz_pow_ui(f, B + (lenB - 1), *d);
        _fmpz_vec_scalar_addmul_fmpz(R, A, n1 + n2 - 1, f);
    }
    else if (lenA > 2 * lenB - 1)
    {
        ulong s1, s2;
        const long shift = lenA - 2 * lenB + 1;

        fmpz * q1 = Q + shift;
        fmpz * q2 = Q;
        fmpz * r1 = R;

{'fraction_non_alphanumeric': 0.18179477275653405, 'fraction_numerical': 0.038238702201622246, 'mean_word_length': 1.8319358366751732, 'pattern_counts': {'":': 0, '<': 29, '<?xml version=': 0, '>': 18, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '1867550', 'n_tokens_mistral': 2933, 'n_tokens_neox': 2696, 'n_words': 935}