4 ms·

The article here: https://news.ycombinator.com/item?id=23351007 https://news.ycombinator.com/item?id=23351007 specifically recommends against the carry varian

The article here: https://news.ycombinator.com/item?id=23351007 https://news.ycombinator.com/item?id=23351007 specifically recommends against the carry variants of addition, because the instructions are still dependent on each other and don't pipeline well. In other words, it's using the same algorithm, just buried in a single instruction, and that doesn't necessarily make it faster. Have you considered using a strategy similar to what the article suggests? I think the HN comments also had some additional suggestions.

devit 6y ago
The dependency is unavoidable due to the way addition works. The approach in the article only works if you are adding a lot of numbers together, and then indeed doing carry propagation once at the end is obviously faster. But of course there is no way that doing the carry propagation yourself on one addition can possibly be faster on a decent CPU that implements add-with-carry efficienly.
- jeffdavis 6y ago
  Maybe it's worth considering an interface to a big int library that can defer carry work across many operations, and then normalizing at the end? That certainly sounds useful for, e.g., totaling an array of big integers.
adwn 6y ago
> that doesn't necessarily make it faster Did you miss the "And got a 3x speedup" part of the post you were replying to? Actual benchmarks of real code always trump theoretical deliberations.
- jeffdavis 6y ago
  Yikes. I was just trying to link to a relevant technique that the author might find helpful. A big integer library may have many use cases; a benchmark only shows one data point. It's possible that by deferring carry work across more operations he'd see an even bigger improvement.
palmtree3000 6y ago
I was briefly very excited when I read that article, actually. But as devit points out in a sibling comment, that technique is only relevant to cases where you're adding more than 2 numbers. Multiplication initially seemed like a very promising use case, since it's basically repeated addition. But I'm not super optimistic about that, because I think it's dominated by the alternate optimization of noticing that the product of two 64 bit numbers cannot saturate the high 64 bits of the resulting 128 bit number, which causes carries to be bounded [1]. [1] https://github.com/rocurley/bignum/blob/b45448a156fb9100ab06e58d65d4d4ee14474a09/src/schoolbook_mul.rs#L11 https://github.com/rocurley/bignum/blob/b45448a156fb9100ab06...

devit 6y ago

The dependency is unavoidable due to the way addition works. The approach in the article only works if you are adding a lot of numbers together, and then indeed doing carry propagation once at the end is obviously faster. But of course there is no way that doing the carry propagation yourself on one addition can possibly be faster on a decent CPU that implements add-with-carry efficienly.

jeffdavis 6y ago
Maybe it's worth considering an interface to a big int library that can defer carry work across many operations, and then normalizing at the end? That certainly sounds useful for, e.g., totaling an array of big integers.

adwn 6y ago

> that doesn't necessarily make it faster Did you miss the "And got a 3x speedup" part of the post you were replying to? Actual benchmarks of real code always trump theoretical deliberations.

jeffdavis 6y ago
Yikes. I was just trying to link to a relevant technique that the author might find helpful. A big integer library may have many use cases; a benchmark only shows one data point. It's possible that by deferring carry work across more operations he'd see an even bigger improvement.

palmtree3000 6y ago

I was briefly very excited when I read that article, actually. But as devit points out in a sibling comment, that technique is only relevant to cases where you're adding more than 2 numbers. Multiplication initially seemed like a very promising use case, since it's basically repeated addition. But I'm not super optimistic about that, because I think it's dominated by the alternate optimization of noticing that the product of two 64 bit numbers cannot saturate the high 64 bits of the resulting 128 bit number, which causes carries to be bounded [1]. [1] https://github.com/rocurley/bignum/blob/b45448a156fb9100ab06e58d65d4d4ee14474a09/src/schoolbook_mul.rs#L11 https://github.com/rocurley/bignum/blob/b45448a156fb9100ab06...