<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 "fmpz_poly.h"

/*
    A brief analysis...

    Case 1:  lenA <= lenB + n2 - 1

    Recursive call is to (lenA - n1, n2), which falls into Cases (1) or (3).
    Allocates lenA - n1.

    This reduces lenA to about 2/3 lenA, so recursively allocation is not 
    a problem for the time being.

    Case 2: lenA > 2 * lenB - 1

    Recursive calls to (2 lenB - 1, lenB) and (lenA - lenB, lenB), which 
    fall into Cases (3) and (2), respectively.
    Allocates 2*lenB-1.

    The first recursive call is no problem.  The second call is the 
    main problem, but this is just the problem with unbalanced division. 
    At least I got rid of the allocation in this case, by passing in a 
    modifiable copy of A.

    Case 3:

    Recursive calls to (lenA - 2 n2, n1) and (lenB + n2 - 1, lenB), 
    which fall into Case (1).
    Allocates lenA - 2 n2 and n1 + 2 n2 - 1.

    The first call reduces lenA to about 1/2 lenA, so here recursive 
    allocation is not a problem.  The second call might still be of 
    size about lenA, ouch.  But we are saved as this lands in Case (1) 
    so in the worst case every other call drops the length from lenA 
    to 2/3 lenA.  Not great, but good enough for now?
 */

static void 
__fmpz_poly_pseudo_divrem_divconquer(fmpz * Q, fmpz * R, ulong * d, 
                                     const fmpz * A, long lenA, 
                                     const fmpz * B, long lenB)
{
    if (lenB <= 16 || (lenA > 2 * lenB - 1 && lenA < 128))
    {
        _fmpz_poly_pseudo_divrem_basecase(Q, R, d, A, lenA, B, lenB);
    }
    else
    {<commit_msg>Remove an explanation from the top of 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 "fmpz_poly.h"

static void 
__fmpz_poly_pseudo_divrem_divconquer(fmpz * Q, fmpz * R, ulong * d, 
                                     const fmpz * A, long lenA, 
                                     const fmpz * B, long lenB)
{
    if (lenB <= 16 || (lenA > 2 * lenB - 1 && lenA < 128))
    {
        _fmpz_poly_pseudo_divrem_basecase(Q, R, d, A, lenA, B, lenB);
    }
    else
    {
{'fraction_non_alphanumeric': 0.20073243305104144, 'fraction_numerical': 0.022659647516594186, 'mean_word_length': 2.9157706093189963, 'pattern_counts': {'":': 0, '<': 14, '<?xml version=': 0, '>': 12, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '6595941', 'n_tokens_mistral': 1295, 'n_tokens_neox': 1152, 'n_words': 539}