Karatsuba algorithm for bigint multiplication

[anematode]

Hi,

I was wondering if a faster algorithm for bigint multiplication could be used for large bigints. The Karatsuba algorithm is relatively simple, so it wouldn't increase the code size by much while being significantly faster. I would love to contribute code for this. (Though I'm not sure what algorithm the project already uses!)

[jakobkummerow]

Using faster algorithms (Karatsuba and others) is certainly possible. Currently, JSBI uses naive/"schoolbook" algorithms for all operations.

I'm not very enthusiastic about it because JSBI is intended to be compiled away (to native BigInts) eventually, and therefore:

• it would make sense to add faster algorithms to the native implementations first, as it would be weird if switching from JSBI to native caused a performance loss.
• as more browsers add native BigInt support, there is less need for JSBI to exist at all, and even less need to invest effort into making JSBI better.

Also, keep in mind that Karatsuba multiplication is faster than the naive algorithm only for BigInts above a certain size. The exact threshold of course depends on the specifics of the respective implementation (so you have to measure it, can't predict it); it's typically somewhere in the range of hundreds or even thousands of bits. Do you have a use case where such BigInts occur?

Generally, if you care about JSBI's performance, you'd probably get more benefit from fixing #40, so it might make sense to do that first.

All that said, I wouldn't mind reviewing a PR.

[anematode]

Alright, well I shall try contribute the relevant code to V8 first before working here.

[Yaffle]

btw, https://github.com/peterolson/BigInteger.js uses this algorithm, but not for BigInt, although, it could be implemented on the top, although, for me it becomes faster when multiplying numbers with 2000 bits...

[Yaffle]

looks like @jakobkummerow is adding Karatsuba multiplication to v8's implementation - v8/v8@df7f886#diff-76c04c73eab3df20b8b3bf73408fd6126492eff6ae660014ab81def8eb1da27d

[jakobkummerow]

Indeed, V8's built-in BigInts now(*) use Karatsuba multiplication (when they're large enough). And there's more to come, stay tuned :-)

(*) As of today: on Chrome Canary; will be in the M93 release.

FWIW, I currently don't have any plans to work on JSBI performance. I assume that most devs compile it away anyway.

[Yaffle]

@jakobkummerow ,
Thanks for working on BigInt!
Are you planning to implement another algorithm for division too? I tried to implement Newton's method once, but my implementation was very slow, and only for some very large numbers better than schoolbook. Although, it seems, Java BigInteger switch to fast algorithm for the same threshold as for Karatsuba multiplication, which is promising.

[jakobkummerow]

As I said: "more to come" :-)

If you want to stay up to date, you can follow/star crbug.com/v8/11515.