Branch: refs/heads/main
Home: https://github.com/WebKit/WebKit
Commit: a24e36116cd45409f82d7838670452fec6375e70
https://github.com/WebKit/WebKit/commit/a24e36116cd45409f82d7838670452fec6375e70
Author: Yusuke Suzuki <[email protected]>
Date: 2025-12-09 (Tue, 09 Dec 2025)
Changed paths:
M Source/JavaScriptCore/runtime/JSBigInt.cpp
M Source/JavaScriptCore/runtime/JSBigInt.h
Log Message:
-----------
[JSC] Implement Comba Multiplication in JSBigInt
https://bugs.webkit.org/show_bug.cgi?id=303801
rdar://166106744
Reviewed by Dan Hecht.
This patch implements Comba's Multiplication algorithm[1] for small
same-sized JSBigInt multiplication. The algorithm is accumulating all
I's column values and move carries via t1 and t2.
So, for each column, compute `(t2, t1, t0) += A[j] * B[k]`
And store t0 as a final result, and move t2 and t1 carries to the next
column. This method is significantly faster for small sized BigInt
multiplication due to streamlined multiplication and add. In general, up
to N=16, it is faster than the textbook approach.
[1]: https://everything2.com/title/Comba+multiplication
* Source/JavaScriptCore/runtime/JSBigInt.cpp:
(JSC::CombaAccumulator::mac):
(JSC::CombaAccumulator::storeAndShift):
(JSC::CombaAccumulator::computeColumn):
(JSC::CombaAccumulator::pass):
(JSC::JSBigInt::multiplyComba):
(JSC::JSBigInt::multiplyImpl):
* Source/JavaScriptCore/runtime/JSBigInt.h:
Canonical link: https://commits.webkit.org/304184@main
To unsubscribe from these emails, change your notification settings at
https://github.com/WebKit/WebKit/settings/notifications
