aureooms/js-integer-big-endian

View on GitHub
src/core/arithmetic/div/_idivmod_schoolbook_large_divisor.js

Summary

Maintainability
A
2 hrs
Test Coverage
import assert from 'assert';

import lt from '../../../api/compare/lt.js';
import _validate from '../../array/_validate.js';
import _cmp_half from '../../compare/_cmp_half.js';
import _trim_positive from '../../convert/_trim_positive.js';
import _isub from '../sub/_isub.js';

import _idivmod_schoolbook_subroutine from './_idivmod_schoolbook_subroutine.js';

/**
 * Input
 * -----
 *  - Two integers A and B such that r^(m-1) <= A < r^m and (r^n)/2 <= B < r^(n).
 *  - No leading zeros (ONLY IN B?)
 *  - Q is initialized with some limbs.
 *
 * 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 default function _idivmod_schoolbook_large_divisor(
    r,
    a,
    ai,
    aj,
    b,
    bi,
    bj,
    q,
    qi,
) {
    assert(r >= 2);
    assert(ai >= 0 && aj <= a.length);
    assert(bi >= 0 && bj <= b.length);
    assert(qi >= 0);
    assert(q.length - qi >= aj - ai);
    // Assert(aj - ai <= 0 || a[ai] !== 0); // no leading zero NOT TRUE ?
    assert(_cmp_half(r, b, bi, bj) >= 0); // (r^n)/2 <= B < r^n (+ no leading zero)
    assert(_validate(r, q, qi, qi + aj - ai));

    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
    }
}