mul-karatsuba.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.

// Karatsuba multiplication. This is loosely based on Go's implementation
// found at https://golang.org/src/math/big/nat.go, licensed as follows:
//
// Copyright 2009 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file [1].
//
// [1] https://golang.org/LICENSE

#include <algorithm>
#include <utility>

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

namespace v8 {
namespace bigint {

// If Karatsuba is the best supported algorithm, then it must check for
// termination requests. If there are more advanced algorithms available
// for larger inputs, then Karatsuba will only be used for sufficiently
// small chunks that checking for termination requests is not necessary.
#if V8_ADVANCED_BIGINT_ALGORITHMS
#define MAYBE_TERMINATE
#else
#define MAYBE_TERMINATE …
#endif

namespace {

// The Karatsuba algorithm sometimes finishes more quickly when the
// input length is rounded up a bit. This method encodes some heuristics
// to accomplish this. The details have been determined experimentally.
int RoundUpLen(int len) { … }

// This method makes the final decision how much to bump up the input size.
int KaratsubaLength(int n) { … }

// Performs the specific subtraction required by {KaratsubaMain} below.
void KaratsubaSubtractionHelper(RWDigits result, Digits X, Digits Y,
                                int* sign) { … }

}  // namespace

void ProcessorImpl::MultiplyKaratsuba(RWDigits Z, Digits X, Digits Y) { … }

// Entry point for Karatsuba-based multiplication, takes care of inputs
// with unequal lengths by chopping the larger into chunks.
void ProcessorImpl::KaratsubaStart(RWDigits Z, Digits X, Digits Y,
                                   RWDigits scratch, int k) { … }

// Entry point for chunk-wise multiplications, selects an appropriate
// algorithm for the inputs based on their sizes.
void ProcessorImpl::KaratsubaChunk(RWDigits Z, Digits X, Digits Y,
                                   RWDigits scratch) { … }

// The main recursive Karatsuba method.
void ProcessorImpl::KaratsubaMain(RWDigits Z, Digits X, Digits Y,
                                  RWDigits scratch, int n) { … }

#undef MAYBE_TERMINATE

}  // namespace bigint
}  // namespace v8
chromium/v8/src/bigint/mul-karatsuba.cc
