Branch: refs/heads/main
Home: https://github.com/WebKit/WebKit
Commit: b071cfab287ac1ec66a98171f1bad1d6845f3c77
https://github.com/WebKit/WebKit/commit/b071cfab287ac1ec66a98171f1bad1d6845f3c77
Author: Sosuke Suzuki <[email protected]>
Date: 2026-10-01 (Thu, 01 Oct 2026)
Changed paths:
A JSTests/microbenchmarks/bigint-div-large.js
A JSTests/microbenchmarks/bigint-mod-large.js
A JSTests/stress/bigint-divide-burnikel-ziegler.js
A JSTests/stress/bigint-sqrt-cbrt-large.js
M Source/JavaScriptCore/runtime/JSBigInt.cpp
M Source/JavaScriptCore/runtime/JSBigInt.h
Log Message:
-----------
[JSC] Add Burnikel-Ziegler division to `JSBigInt`
https://bugs.webkit.org/show_bug.cgi?id=325444
Reviewed by Yusuke Suzuki.
JSBigInt divides with Knuth's Algorithm D, whose cost is the product of the
lengths of the quotient and the divisor. Dividing 15999 digits by 8000 digits
takes 64.6 ms, while multiplying 8000 x 8000 digits takes 1.25 ms since
321444@main.
Add Burnikel-Ziegler division, which brings that to 4.8 ms. It divides 2n
digits by n digits with two divisions of half the size and two multiplications
of n/2 x n/2 digits, so it gets faster with the multiplication. This is a port
of V8's implementation [1] of the algorithm by Burnikel and Ziegler [2].
divideSchoolbook now accepts a quotient buffer that is one digit shorter when
the top digit of the quotient is zero, which the recursion relies on.
It is used when the divisor has at least 24 digits and the quotient at least
48, and the recursion stops below 16 digits. Splitting once replaces half of
the steps of Algorithm D with two multiplications, and adds comparisons,
copies, additions and subtractions that are linear in n. Measured, that pays
off from a divisor of 24 digits. The linear work is done at every level of the
recursion whatever the length of the quotient, so a longer divisor needs a
longer quotient: a divisor of 100 digits is split 3 times and pays off from a
quotient of about 14 digits, one of 8000 digits is split 10 times and pays off
from about 40.
x / y in microseconds. x % y takes about the same.
digits Before After
71 / 24 1.486 1.293
163 / 100 6.637 3.858
599 / 300 92.376 34.027
1047 / 1000 47.799 34.450
1999 / 1000 1013.279 228.569
7999 / 4000 16052.961 1806.259
15999 / 8000 64621.925 4813.910
70 / 24 1.417 1.409
8031 / 8000 261.009 260.949
Baseline Patched
bigint-mod-cached 14.1296+-0.1289 ? 14.2176+-0.1076
?
bigint-mod-cached-large 2.7126+-0.0391 2.6849+-0.0512
might be 1.0103x faster
bigint-mul-very-large 173.7965+-3.5102 ? 173.8182+-1.8761
?
bigint-div-large 200.3873+-2.4353 ^ 86.3507+-1.1622
^ definitely 2.3206x faster
bigint-mod-large 199.7541+-2.7749 ^ 85.8994+-1.0926
^ definitely 2.3254x faster
bigint-mul-large 128.9683+-1.0524 128.7207+-1.2326
bigint-mul-huge 134.7472+-0.7741 ? 136.5796+-1.3127
? might be 1.0136x slower
bigint-mul-large-unequal 277.8469+-4.9122 277.6766+-2.4297
[1]:
https://source.chromium.org/chromium/chromium/src/+/main:v8/src/bigint/div-burnikel.cc
[2]: Christoph Burnikel and Joachim Ziegler, "Fast Recursive Division", Research
Report MPI-I-98-1-022, Max-Planck-Institut fuer Informatik, 1998.
Tests: JSTests/microbenchmarks/bigint-div-large.js
JSTests/microbenchmarks/bigint-mod-large.js
JSTests/stress/bigint-divide-burnikel-ziegler.js
JSTests/stress/bigint-sqrt-cbrt-large.js
* JSTests/microbenchmarks/bigint-div-large.js: Added.
(test):
(next):
* JSTests/microbenchmarks/bigint-mod-large.js: Added.
(test):
(next):
* JSTests/stress/bigint-divide-burnikel-ziegler.js: Added.
(shouldBe):
(check):
(64.width.1000.1.x.BigInt):
(64.width.1000.1.x):
* JSTests/stress/bigint-sqrt-cbrt-large.js: Added.
(shouldBe):
* Source/JavaScriptCore/runtime/JSBigInt.cpp:
(JSC::addDigitAndPropagate):
(JSC::subtractDigitAndPropagate):
(JSC::copyAndZeroExtend):
(JSC::JSBigInt::FFTContainer::startDefault):
(JSC::JSBigInt::FFTContainer::start):
(JSC::JSBigInt::divideSchoolbook):
(JSC::JSBigInt::burnikelZieglerBasecase):
(JSC::JSBigInt::burnikelZieglerD3n2n):
(JSC::JSBigInt::burnikelZieglerD2n1n):
(JSC::JSBigInt::divideBurnikelZiegler):
(JSC::shouldUseBurnikelZiegler):
(JSC::JSBigInt::divideDigitsInto):
(JSC::JSBigInt::divideImpl):
(JSC::JSBigInt::divideDigits):
(JSC::JSBigInt::remainderImpl):
(JSC::FFT::addDigitAndPropagate): Deleted.
(JSC::FFT::subtractDigitAndPropagate): Deleted.
(JSC::FFT::copyAndZeroExtend): Deleted.
* Source/JavaScriptCore/runtime/JSBigInt.h:
Canonical link: https://commits.webkit.org/322437@main
To unsubscribe from these emails, change your notification settings at
https://github.com/WebKit/WebKit/settings/notifications
