div-barrett.cc | Explore in Territory

// Copyright 2021 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

// Barrett division, finding the inverse with Newton's method.
// Reference: "Fast Division of Large Integers" by Karl Hasselström,
// found at https://treskal.com/s/masters-thesis.pdf

// Many thanks to Karl Wiberg, [email protected], for both writing up an
// understandable theoretical description of the algorithm and privately
// providing a demo implementation, on which the implementation in this file is
// based.

#include <algorithm>

#include "src/bigint/bigint-internal.h"
#include "src/bigint/digit-arithmetic.h"
#include "src/bigint/div-helpers.h"
#include "src/bigint/vector-arithmetic.h"

namespace v8 {
namespace bigint {

namespace {

void DcheckIntegerPartRange(Digits X, digit_t min, digit_t max) { … }

}  // namespace

// Z := (the fractional part of) 1/V, via naive division.
// See comments at {Invert} and {InvertNewton} below for details.
void ProcessorImpl::InvertBasecase(RWDigits Z, Digits V, RWDigits scratch) { … }

// This is Algorithm 4.2 from the paper.
// Computes the inverse of V, shifted by kDigitBits * 2 * V.len, accurate to
// V.len+1 digits. The V.len low digits of the result digits will be written
// to Z, plus there is an implicit top digit with value 1.
// Needs InvertNewtonScratchSpace(V.len) of scratch space.
// The result is either correct or off by one (about half the time it is
// correct, half the time it is one too much, and in the corner case where V is
// minimal and the implicit top digit would have to be 2 it is one too little).
// Barrett's division algorithm can handle that, so we don't care.
void ProcessorImpl::InvertNewton(RWDigits Z, Digits V, RWDigits scratch) { … }

// Computes the inverse of V, shifted by kDigitBits * 2 * V.len, accurate to
// V.len+1 digits. The V.len low digits of the result digits will be written
// to Z, plus there is an implicit top digit with value 1.
// (Corner case: if V is minimal, the implicit digit should be 2; in that case
// we return one less than the correct answer. DivideBarrett can handle that.)
// Needs InvertScratchSpace(V.len) digits of scratch space.
void ProcessorImpl::Invert(RWDigits Z, Digits V, RWDigits scratch) { … }

// This is algorithm 3.5 from the paper.
// Computes Q(uotient) and R(emainder) for A/B using I, which is a
// precomputed approximation of 1/B (e.g. with Invert() above).
// Needs DivideBarrettScratchSpace(A.len) scratch space.
void ProcessorImpl::DivideBarrett(RWDigits Q, RWDigits R, Digits A, Digits B,
                                  Digits I, RWDigits scratch) { … }

// Computes Q(uotient) and R(emainder) for A/B, using Barrett division.
void ProcessorImpl::DivideBarrett(RWDigits Q, RWDigits R, Digits A, Digits B) { … }

}  // namespace bigint
}  // namespace v8
chromium/v8/src/bigint/div-barrett.cc
