News for hackers. Stuff that matters.
Re:Adding BigInts to V8 by saagarjha on Wednesday May 02, 2018 @03:50PM (#16980558)
> That’s exactly how V8 multiplies BigInts: one digit at a time, adding up the intermediate results. The algorithm works just as well for 0 to 9 as it does for a BigInt’s much bigger digits.

Why not use a faster algorithm, like the Karatsuba algorithm[1] or the Toom-Cook[2] algorithm?

[1] https://en.wikipedia.org/wiki/Karatsuba_algorithm

[2] https://en.wikipedia.org/wiki/Toom–Cook_multiplication

Re:Adding BigInts to V8 by tzs on Wednesday May 02, 2018 @09:11PM (#16982569)
Speaking of Karatsuba, in 1993 I wrote a C++ big integer package and used Karatsuba. I had some questions about how to use it when the two numbers being multiplied are not the same length. I did some experiments, and noticed hints at some patterns in the data I was seeing. I asked about this on sci.math, but as far as I know no one ever gave an explanation.

If anyone is curious and wants to figure this out, here's my old sci.math post [1].

[1] https://groups.google.com/d/msg/sci.math/MX3MLCQ0zzA/XTqUoZk...

Re:Adding BigInts to V8 by coldsauce on Thursday May 03, 2018 @12:12AM (#16983309)
Wow! I find it remarkable that you have had this question open for 25 years without a single answer.
Re:Adding BigInts to V8 by delinka on Thursday May 03, 2018 @09:10AM (#16985629)
"...the two numbers being multiplied are not the same length."

Do you mean as counted in bits? If so, prepend zeroes until they are the same length. Does this negatively affect the algorithm's results?

EDIT: When I say 'prepend' I mean on the MSB end. In typical arithmetic on paper, that'd be adding leading zeroes (prepending) onto the numbers.

Re:Adding BigInts to V8 by taejo on Friday May 04, 2018 @08:11AM (#16993907)
You can do that - it's the "textbook" solution - but you can probably do better by not making your inputs larger: in the worst case you're going from multiplying N digits by 1 digit to N digits by N digits.
Re:Adding BigInts to V8 by saagarjha on Friday May 04, 2018 @03:44AM (#16992874)
Might be something to do with caching or fitting operands in registers?
Re:Adding BigInts to V8 by gnulinux on Thursday May 03, 2018 @08:23AM (#16985296)
Did you eventually find an answer?
Re:Adding BigInts to V8 by arnarbi on Wednesday May 02, 2018 @04:20PM (#16980804)
They may not be faster, depending on what size integers you are dealing with.

From your [1]: "As a rule of thumb, Karatsuba is usually faster when the multiplicands are longer than 320–640 bits."

Toom-3 doesn't get faster than Karatsuba (couldn't find numbers quickly). See e.g. https://fossies.org/linux/gmp/tune/README for a discussion.

Re:Adding BigInts to V8 by mrguyorama on Thursday May 03, 2018 @05:14PM (#16990042)
Sometimes we forget the lower order values when considering algorithmic complexity. Not every use case is likely to see the asymptotic behaviors.

Reminds me of a demo by my algorithms professor. A certain sorting method (I think binary) requires picking a good pivot to keep complexity down. Picking a random pivot point generally gives good results, but results in an O(n^2) algorithm when asymptotically examined. An algorithm for "perfect" point picking (mean of means I believe) was demonstrated. It resulted in a complexity of O(n) (linear). However, the scale to the linear term was 22. Therefore, in nearly every case, picking randomly would outperform it.

I did not realize Karatsuba required such large numbers to outperform. When I first learned about it, I was under the impression that it would be more effective even for barely "large" numbers

Re:Adding BigInts to V8 by dtech on Wednesday May 02, 2018 @04:05PM (#16980678)
> For now, we are shipping a baseline implementation of BigInts. [...] it is not particularly optimized. [...] we first want to see how you will use BigInts
Re:Adding BigInts to V8 by monocasa on Wednesday May 02, 2018 @04:28PM (#16980869)
To be fair, how it's used probably depends in part on how well optimized it is.
Re:Adding BigInts to V8 by ItsMe000001 on Wednesday May 02, 2018 @05:53PM (#16981481)
It's almost as if evolution of software is an iterative process where all parties move a bit at each step, not one from 0 to "fully planned ahead in advance (by expert committee)".
Re:Adding BigInts to V8 by Retra on Wednesday May 02, 2018 @11:24PM (#16983123)
There's little reason to use a poor algorithm when good ones already exist. If the problem is already solved, you don't need any expert committee, just a few days of reading and writing.
Re:Adding BigInts to V8 by ItsMe000001 on Thursday May 03, 2018 @03:04AM (#16983907)
So you already know how people are going to use BigInt, so you can tell them what optimizations are useful? Send them a message, JS runtime implementers are eager to hear from you! Keep in mind each optimization comes at a cost, so you don't want to willy-nilly implement any optimization that comes to mind (time and (code) space and (runtime memory) space complexity).
Re:Adding BigInts to V8 by bigiain on Wednesday May 02, 2018 @09:54PM (#16982763)
"It's Wagile!"
Re:Adding BigInts to V8 by jjaredsimpson on Wednesday May 02, 2018 @04:05PM (#16980682)
Those have better asymptotics but worse constants.
Re:Adding BigInts to V8 by gamegoblin on Wednesday May 02, 2018 @04:17PM (#16980790)
Specifically:

    It follows that, for sufficiently large n, Karatsuba's
    algorithm will perform fewer shifts and single-digit 
    additions than longhand multiplication, even though its 
    basic step uses more additions and shifts than the 
    straightforward formula. For small values of n, however, 
    the extra shift and add operations may make it run 
    slower than the longhand method. The point of positive 
    return depends on the computer platform and context. 
    As a rule of thumb, Karatsuba is usually faster when 
    the multiplicands are longer than 320–640 bits.
https://en.wikipedia.org/wiki/Karatsuba_algorithm#Efficiency...
Re:Adding BigInts to V8 by dsp1234 on Wednesday May 02, 2018 @04:10PM (#16980735)
Isn't their solution Toom-Cook where the base is 2^32?