In addition to inputs consisting entirely of random bits, the
bigint test shell now also generates inputs that are powers of
two (i.e. have many 0-bits) and inputs with many 1-bits.
Empirically, these kinds of inputs are more likely to flush out
corner case bugs.

Bug: v8:11515
Change-Id: Ib69f12bf215055991b028196dc54ebbc00780bae
Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/3055292
Commit-Queue: Jakob Kummerow <jkummerow@chromium.org>
Reviewed-by: Maya Lekova <mslekova@chromium.org>
Cr-Commit-Position: refs/heads/main@{#76729}

No multiplications needed, just putting bits directly into
the right places.

Bug: v8:11515
Change-Id: I65e5658bb5ed12caec9325f414563526f8edbbf3
Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/3055291
Commit-Queue: Jakob Kummerow <jkummerow@chromium.org>
Reviewed-by: Maya Lekova <mslekova@chromium.org>
Cr-Commit-Position: refs/heads/main@{#76727}

Combining parts in a balanced-binary-tree like order allows us to
use fast multiplication algorithms.

Bug: v8:11515
Change-Id: I6829929671770f009f10f6f3b383501fede476ab
Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/3049079Reviewed-by: Maya Lekova <mslekova@chromium.org>
Commit-Queue: Jakob Kummerow <jkummerow@chromium.org>
Cr-Commit-Position: refs/heads/main@{#76404}

It was previously only passed to compilation units in src/bigint/,
but inconsistencies arise when it's not passed to other compilation
units that #include src/bigint/bigint.h.

Fixed: chromium:1233397
Change-Id: Idb310d8c13bad12766699086574aa2c3869eb56c
Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/3056452Reviewed-by: Leszek Swirski <leszeks@chromium.org>
Commit-Queue: Jakob Kummerow <jkummerow@chromium.org>
Cr-Commit-Position: refs/heads/master@{#75941}

Now that we have advanced division algorithms, we can implement
a divide-and-conquer strategy for toString-conversions, to make
their complexity sub-quadratic.
For example, this speeds up `(2n ** (2n ** 21n)).toString().length`
from 9400 ms to 200 ms on my laptop.

Bug: v8:11515
Change-Id: Id20f7f2928dc7308609f4c1688f32b252e04f433
Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/3017805Reviewed-by: Maya Lekova <mslekova@chromium.org>
Commit-Queue: Jakob Kummerow <jkummerow@chromium.org>
Cr-Commit-Position: refs/heads/master@{#75880}

Dividing by first computing a multiplicative inverse is faster than
Burnikel-Ziegler division for very large inputs.

Bug: v8:11515
Change-Id: Ice45690c3fa4eef7102d418cdd3d82a942a076c5
Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/3015573
Commit-Queue: Jakob Kummerow <jkummerow@chromium.org>
Reviewed-by: Maya Lekova <mslekova@chromium.org>
Cr-Commit-Position: refs/heads/master@{#75743}

The Schönhage-Strassen method for *very* large inputs.

This is a reland of 347ba357,
with added zero-initialization to pacify MSan (spurious report).

Originally:
> Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/3000742
> Commit-Queue: Jakob Kummerow <jkummerow@chromium.org>
> Reviewed-by: Maya Lekova <mslekova@chromium.org>
> Cr-Commit-Position: refs/heads/master@{#75659}

Bug: v8:11515
Change-Id: Ieac6e174bde6eb09af0a9a9a49969feabca79e81
Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/3018081Reviewed-by: Maya Lekova <mslekova@chromium.org>
Commit-Queue: Jakob Kummerow <jkummerow@chromium.org>
Cr-Commit-Position: refs/heads/master@{#75663}

This reverts commit 347ba357.

Reason for revert: MSAN https://ci.chromium.org/ui/p/v8/builders/ci/V8%20Linux%20-%20arm64%20-%20sim%20-%20MSAN/39275/overview

Original change's description:
> [bigint] FFT-based multiplication
>
> The Schönhage-Strassen method for *very* large inputs.
>
> Bug: v8:11515
> Change-Id: Ie8613f54928c9d3f6ff24e3102bc809de9f4496e
> Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/3000742
> Commit-Queue: Jakob Kummerow <jkummerow@chromium.org>
> Reviewed-by: Maya Lekova <mslekova@chromium.org>
> Cr-Commit-Position: refs/heads/master@{#75659}

Bug: v8:11515
Change-Id: Ib0601e91bbd8ac5732b57730e3507eb0fa7e3947
No-Presubmit: true
No-Tree-Checks: true
No-Try: true
Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/3015574
Auto-Submit: Leszek Swirski <leszeks@chromium.org>
Commit-Queue: Rubber Stamper <rubber-stamper@appspot.gserviceaccount.com>
Bot-Commit: Rubber Stamper <rubber-stamper@appspot.gserviceaccount.com>
Cr-Commit-Position: refs/heads/master@{#75660}

The Schönhage-Strassen method for *very* large inputs.

Bug: v8:11515
Change-Id: Ie8613f54928c9d3f6ff24e3102bc809de9f4496e
Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/3000742
Commit-Queue: Jakob Kummerow <jkummerow@chromium.org>
Reviewed-by: Maya Lekova <mslekova@chromium.org>
Cr-Commit-Position: refs/heads/master@{#75659}

A generalization of Karatsuba's idea for even larger inputs.

Bug: v8:11515
Change-Id: I50eac2d313bf4217bf2f55ca2e64b5f120f40206
Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/2999870
Auto-Submit: Jakob Kummerow <jkummerow@chromium.org>
Commit-Queue: Michael Achenbach <machenbach@chromium.org>
Reviewed-by: Michael Achenbach <machenbach@chromium.org>
Reviewed-by: Maya Lekova <mslekova@chromium.org>
Cr-Commit-Position: refs/heads/master@{#75598}

The Burnikel-Ziegler division algorithm is used for divisors
with 57 or more internal digits. It has better asymptotic
complexity than "schoolbook" division because it can make use
of fast multiplication under the hood.

Bug: v8:11515
Change-Id: Ib5d573a0afa560d42972c4ae06aff810a8b9cadb
Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/2960221
Commit-Queue: Jakob Kummerow <jkummerow@chromium.org>
Reviewed-by: Maya Lekova <mslekova@chromium.org>
Cr-Commit-Position: refs/heads/master@{#75310}

This is a reland of 81dd3f42,
which was a reland of 59eff3bf

Original change's description:
> [bigint] Karatsuba multiplication
>
> The Karatsuba algorithm is used for BigInts with 34 or more internal
> digits, and thanks to better asymptotic complexity provides greater
> speedups the bigger the inputs.
>
> Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/2782283
> Reviewed-by: Michael Achenbach <machenbach@chromium.org>
> Reviewed-by: Thibaud Michaud <thibaudm@chromium.org>
> Cr-Commit-Position: refs/heads/master@{#74916}

Bug: v8:11515
Change-Id: I08f7d59dfa39fb3b532684685afd9fa750e0e84e
Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/2933666Reviewed-by: Clemens Backes <clemensb@chromium.org>
Reviewed-by: Michael Achenbach <machenbach@chromium.org>
Commit-Queue: Jakob Kummerow <jkummerow@chromium.org>
Cr-Commit-Position: refs/heads/master@{#74969}

This reverts commit 81dd3f42.

Reason for revert: Does not compile on MSVC: https://ci.chromium.org/ui/p/v8/builders/ci/V8%20Win64%20-%20msvc/18017/overview

Original change's description:
> Reland "[bigint] Karatsuba multiplication"
>
> This is a reland of 59eff3bf
>
> Original change's description:
> > [bigint] Karatsuba multiplication
> >
> > The Karatsuba algorithm is used for BigInts with 34 or more internal
> > digits, and thanks to better asymptotic complexity provides greater
> > speedups the bigger the inputs.
> >
> > Bug: v8:11515
> > Change-Id: I5ab0e318173ea4a02ced3f156d3c17e0259c5036
> > Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/2782283
> > Commit-Queue: Jakob Kummerow <jkummerow@chromium.org>
> > Reviewed-by: Michael Achenbach <machenbach@chromium.org>
> > Reviewed-by: Thibaud Michaud <thibaudm@chromium.org>
> > Cr-Commit-Position: refs/heads/master@{#74916}
>
> Bug: v8:11515
> Change-Id: I5ece2ff29ef11ea304980c053887d9746cfc80bc
> Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/2933497
> Reviewed-by: Thibaud Michaud <thibaudm@chromium.org>
> Commit-Queue: Jakob Kummerow <jkummerow@chromium.org>
> Cr-Commit-Position: refs/heads/master@{#74922}

Bug: v8:11515
Change-Id: Ie4a80256174fc8d9f714c01f012ac2dc6247a220
No-Presubmit: true
No-Tree-Checks: true
No-Try: true
Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/2933665
Auto-Submit: Clemens Backes <clemensb@chromium.org>
Commit-Queue: Rubber Stamper <rubber-stamper@appspot.gserviceaccount.com>
Bot-Commit: Rubber Stamper <rubber-stamper@appspot.gserviceaccount.com>
Cr-Commit-Position: refs/heads/master@{#74926}

This is a reland of 59eff3bf

Original change's description:
> [bigint] Karatsuba multiplication
>
> The Karatsuba algorithm is used for BigInts with 34 or more internal
> digits, and thanks to better asymptotic complexity provides greater
> speedups the bigger the inputs.
>
> Bug: v8:11515
> Change-Id: I5ab0e318173ea4a02ced3f156d3c17e0259c5036
> Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/2782283
> Commit-Queue: Jakob Kummerow <jkummerow@chromium.org>
> Reviewed-by: Michael Achenbach <machenbach@chromium.org>
> Reviewed-by: Thibaud Michaud <thibaudm@chromium.org>
> Cr-Commit-Position: refs/heads/master@{#74916}

Bug: v8:11515
Change-Id: I5ece2ff29ef11ea304980c053887d9746cfc80bc
Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/2933497Reviewed-by: Thibaud Michaud <thibaudm@chromium.org>
Commit-Queue: Jakob Kummerow <jkummerow@chromium.org>
Cr-Commit-Position: refs/heads/master@{#74922}

This reverts commit 59eff3bf.

Reason for revert: Breaks UBSan - https://ci.chromium.org/ui/p/v8/builders/ci/V8%20Linux64%20UBSan/16697/overview

Original change's description:
> [bigint] Karatsuba multiplication
>
> The Karatsuba algorithm is used for BigInts with 34 or more internal
> digits, and thanks to better asymptotic complexity provides greater
> speedups the bigger the inputs.
>
> Bug: v8:11515
> Change-Id: I5ab0e318173ea4a02ced3f156d3c17e0259c5036
> Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/2782283
> Commit-Queue: Jakob Kummerow <jkummerow@chromium.org>
> Reviewed-by: Michael Achenbach <machenbach@chromium.org>
> Reviewed-by: Thibaud Michaud <thibaudm@chromium.org>
> Cr-Commit-Position: refs/heads/master@{#74916}

Bug: v8:11515
Change-Id: Ifd3d651a26441ba36a23724c6eb1a9915f6e41a8
No-Presubmit: true
No-Tree-Checks: true
No-Try: true
Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/2933496
Auto-Submit: Maya Lekova <mslekova@chromium.org>
Commit-Queue: Rubber Stamper <rubber-stamper@appspot.gserviceaccount.com>
Bot-Commit: Rubber Stamper <rubber-stamper@appspot.gserviceaccount.com>
Cr-Commit-Position: refs/heads/master@{#74918}

The Karatsuba algorithm is used for BigInts with 34 or more internal
digits, and thanks to better asymptotic complexity provides greater
speedups the bigger the inputs.

Bug: v8:11515
Change-Id: I5ab0e318173ea4a02ced3f156d3c17e0259c5036
Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/2782283
Commit-Queue: Jakob Kummerow <jkummerow@chromium.org>
Reviewed-by: Michael Achenbach <machenbach@chromium.org>
Reviewed-by: Thibaud Michaud <thibaudm@chromium.org>
Cr-Commit-Position: refs/heads/master@{#74916}