<commit_before>import { _trim_positive } from '../../convert/_trim_positive' ;
import { lt } from '../../../api/compare/lt' ;
import { _isub } from '../sub' ;
import { _idivmod_schoolbook_subroutine } from './_idivmod_schoolbook_subroutine' ;

/**
 * Input
 * -----
 *  - Two integers A and B such that r^(m-1) <= A < r^m and (r^n)/2 <= B < r^(n).
 *  - No leading zeros
 *
 * Output
 * -----
 *  The quotient floor( A/B ) and the remainder A mod B.
 *
 * @param {Number} r The radix.
 * @param {Array} a Dividend.
 * @param {Number} ai Left of dividend.
 * @param {Number} aj Right of dividend.
 * @param {Array} b Divisor.
 * @param {Number} bi Left of divisor.
 * @param {Number} bj Right of divisor.
 * @param {Array} q Quotient.
 * @param {Number} qi Left of quotient.
 */
export function _idivmod_schoolbook_large_divisor ( r , a , ai , aj , b , bi , bj , q , qi ) {

	const m = aj - ai ;
	const n = bj - bi ;

	// If m < n, return the quotient 0 and the remainder A.
	if ( m < n ) return ;

	if ( m === n ) {

		// If m = n, then if A < B, return the quotient 0 and the remainder A;
		if ( lt( a , ai , aj , b , bi , bj ) ) return ;

		// if A ≥ B, return the quotient 1 and the remainder A - B.
		++q[qi+m-1] ;
		_isub( r , a , ai , aj , b , bi , bj ) ;
		return ;

	}

	// If m = n + 1, compute the quotient and remainder of A/B
	// using algorithm 3.1 and return them.
	if ( m === n + 1 ) return _idivmod_schoolbook_subroutine( r , a , ai , aj , b , bi , bj , q , qi ) ;


	// 4. A' <- A/β^{m-n-1} and s <- A mod β^{m-n-1}
	const _aj = ai + n + 1 ;

	// 5. Compute the quotient q' and the remainder r' of A'/B using algorithm 3.1.
	_idivmod_schoolbook_subroutine( r , a , ai , _aj , b , bi , bj , q , qi ) ;

	// 6. Compute the quotient q and remainder r of( β^{m-n-1} r' + s ) / B recursively.
	const ak = _trim_positive( a , ai , _aj ) ;
	_idivmod_schoolbook_large_divisor( r , a , ak , aj , b , bi , bj , q , qi + ak - ai ) ;

	// 7. Return the quotient Q = β^{m-n-1} q' + q and remainder R = r

}<commit_msg>:bug: fix(_idivmod_schoolbook_large_divisor): Make it nonrecursive.<commit_after>import { _trim_positive } from '../../convert/_trim_positive' ;
import { lt } from '../../../api/compare/lt' ;
import { _isub } from '../sub' ;
import { _idivmod_schoolbook_subroutine } from './_idivmod_schoolbook_subroutine' ;

/**
 * Input
 * -----
 *  - Two integers A and B such that r^(m-1) <= A < r^m and (r^n)/2 <= B < r^(n).
 *  - No leading zeros
 *
 * Output
 * -----
 *  The quotient floor( A/B ) and the remainder A mod B.
 *
 * @param {Number} r The radix.
 * @param {Array} a Dividend.
 * @param {Number} ai Left of dividend.
 * @param {Number} aj Right of dividend.
 * @param {Array} b Divisor.
 * @param {Number} bi Left of divisor.
 * @param {Number} bj Right of divisor.
 * @param {Array} q Quotient.
 * @param {Number} qi Left of quotient.
 */
export function _idivmod_schoolbook_large_divisor ( r , a , ai , aj , b , bi , bj , q , qi ) {

	while ( true ) { // non-recursive

	const m = aj - ai ;
	const n = bj - bi ;

	// If m < n, return the quotient 0 and the remainder A.
	if ( m < n ) return ;

	if ( m === n ) {

		// If m = n, then if A < B, return the quotient 0 and the remainder A;
		if ( lt( a , ai , aj , b , bi , bj ) ) return ;

		// if A ≥ B, return the quotient 1 and the remainder A - B.
		++q[qi+m-1] ;
		_isub( r , a , ai , aj , b , bi , bj ) ;
		return ;

	}

	// If m = n + 1, compute the quotient and remainder of A/B
	// using algorithm 3.1 and return them.
	if ( m === n + 1 ) return _idivmod_schoolbook_subroutine( r , a , ai , aj , b , bi , bj , q , qi ) ;


	// 4. A' <- A/β^{m-n-1} and s <- A mod β^{m-n-1}
	const _aj = ai + n + 1 ;

	// 5. Compute the quotient q' and the remainder r' of A'/B using algorithm 3.1.
	_idivmod_schoolbook_subroutine( r , a , ai , _aj , b , bi , bj , q , qi ) ;

	// 6. Compute the quotient q and remainder r of( β^{m-n-1} r' + s ) / B recursively.
	const ak = _trim_positive( a , ai , _aj ) ;
	//_idivmod_schoolbook_large_divisor( r , a , ak , aj , b , bi , bj , q , qi + ak - ai ) ;
	qi += ak - ai; // non recursive because some implementation
	ai = ak;       // do not have tail-call optimization ?

	// 7. Return the quotient Q = β^{m-n-1} q' + q and remainder R = r
	}

}
{'fraction_non_alphanumeric': 0.16094924812030076, 'fraction_numerical': 0.009868421052631578, 'mean_word_length': 2.3440691280439907, 'pattern_counts': {'":': 0, '<': 21, '<?xml version=': 0, '>': 3, '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': '1086070', 'n_tokens_mistral': 1741, 'n_tokens_neox': 1607, 'n_words': 602}