6 ms·
The radix 2^51 trick (2017)
- addaon 1y ago> Aside: Why 13 bits instead of 12? For our purposes, we’re going to ignore the carries in the most significant limb, allowing numbers to wrap when they overflow past 2256 - 1 (just like how unsigned addition works in C with normal size integer types). As a result, we can assign 52 bits to the most significant limb and ignore the fact that it will run out of room for carries before the other limbs do. Why not give the top limb 64 bits and the other four limbs 48 bits each, then? You can accumulate more additions before normalization, you can take advantage of word alignment during splitting and normalization if your instruction set has anything useful there, and your overflow properties are identical, no?
- deleted 1y ago[deleted]
- bboreham 1y agoThen you would need 6 words to hold a 256-bit value instead of 5 in the OP, and consequently more instructions to add them.
- Sukera 1y agoBecause adding the top limbs of two encoded numbers would overflow too soon. If you set both to 2^63 for example, they overflow immediately. Might be fine for wraparound arithmetic, but not in general.
- volemo 1y agoSetting both to 2^63 means your original 256-bit numbers were 2^255, thus the addition would overflow no matter what intermediate encoding you’re using.
- vitus 1y agoSure, then set one to 2^62 and the other to -2^62 (namely: 0b1100..00). It's overflow as far as unsigned arithmetic is concerned, but not in the case of signed arithmetic. That said, when you're dealing with 256-bit integers, you're almost assuredly not working with signed arithmetic.
- immibis 1y ago...so? They don't care about top limb overflow, at all. That's the point.
- phkahler 1y ago>> Why not give the top limb 64 bits and the other four limbs 48 bits each, then? I think one goal is to use 5 64 bit registers to do 256 bit math. That means using 256/5 = 51.2 bits of each word. That's probably some kind of ideal if you want 256bit math, but not optimal if you're writing a generic big-int library. In the old days you'd want to use exactly one byte for the carry(s) because we didn't have barrel shifters to do arbitrary bit shifts efficiently. In that case I'd use 56 bits of the 64 to get nice byte alignment. This is all quite relevant for RISC-V since the ISA does not have flags.
- Thorrez 1y ago>That means using 256/5 = 51.2 bits of each word. Why must each word have the same amount? Why not 64 bits on the top word, and 48 bits on the other 4 words?
- LegionMammal978 1y agoEvenly distributing the number of bits per word lets you chain more additions/subtractions before having to normalize.
- xigoi 1y agoSure, but the point is that for the most significant limb, there is no point in having redundant bits because whatever you put in them will be discarded after normalization.
- LegionMammal978 1y agoAh, in that case, you're right, it would make sense to use all 64 bits for the top limb. Still, making them all equal-sized can have benefits if you use SIMD or similar techniques to operate on them uniformly. One project of mine has been trying to work with large integers in CUDA by distributing their limbs across a warp.
- dgoldstein0 1y ago
- russdill 1y agoI'm seriously doubtful that adc is inherently slower than add on a modern CPU other then the data hazard introduced by the carry bit. I realize the point of the article is the data hazard so this is a really minor nit.
- john-h-k 1y agouops.info has latency for both (Alder Lake) at 1 cycle but throughput (lower is better) * for add is 0.20 (ie 5 per cycle) * for adc is 0.50 (ie 2 per cycle) so it does seem correct. This seems to be a consequence of `add` being available on ports 0, 1, 5, 6, & B, whereas `adc` is only available on ports 0 & 6 So yes as an individual instruction it’s no worse, but even non-dependent instructions will be worse for OoO execution (which is more realistic than viewing it as a single instruction)
- phkahler 1y agoIntel is also supposed to introduce the new APX instructions which include a bunch of instructions that duplicate existing ones but don't set any flags. The only plausible reason to add these is for performance reasons.
- john-h-k 1y agoThis isn't just due to the actual dependencies of flag instructions at hardware level (although likely be a factor), it also majorly affects code layout. On Arm64 for example, you can make a comparison, do other operations, and then consume the result of that comparison afterwards, which is excellent for the pipeline and OoO engine. However, because most instructions on x86_64 write flags, you can't do this, and so you are forced to cram `jcc`/`setcc` instructions right after the comparison, which is less friendly to compilers and the OoO engine
- dzaima 1y agoOoO should actually be the care where that doesn't matter I'd think - the CPU can, well, execute the instructions not in the order they're in the binary; it's in-order implementations are where that matters more. And with compare & jump being adjacent they can be fused together into one uop, which Intel, AMD, and Apple Silicon all do.
- foota 1y agoWould it be legal for a C(++?) compiler to implement this optimization?
- nine_k 1y agoDoes C++ have native support for uint256?
- Arnavion 1y agoWith C, it is _BitInt(256) if the compiler supports it. The upper limit of _BitInt is implementation-defined though, so 256 is not guaranteed to be supported. Eg clang on RV64 only supports upto 128, but does support 256 on x64_64. gcc seems to not support _BitInt on RV64 at all, but does support 256 on x86_64. With C++ the existence of such "extended integer" types is implementation defined. clang at least supports the same _BitInt construct for C++ too. gcc seems to not support it. So, for the 256 case on x86_64, both clang and gcc seem to only generate the simple adc ripple version: https://gcc.godbolt.org/z/nxoEda3q5 https://gcc.godbolt.org/z/nxoEda3q5 https://gcc.godbolt.org/z/bYf4bor3f https://gcc.godbolt.org/z/bYf4bor3f
- addaon 1y agoYes, it complies with the as-if rule; there's no observable difference in behavior. This would apply as well for supporting 64 bit additions within a loop on 32- or 16-bit architectures, for example.
- rollcat 1y agoAn unexpected optimisation can introduce a side channel (most commonly timing). This one would be safe, but "how do you tell a compiler which ones [not] to use" is a whole topic by itself.
- Denvercoder9 1y agoThe C++ standard doesn't forbid introducing side channels, so the answer to the question is yes.
- brucehoult 1y agoSomeone working entirely on x86_64 very nicely demonstrates that RISC-V is not wrong to omit the carry flag.
- brucehoult 1y agoAlso, there is another way to do this while keeping 64 bit limbs. All variables uint64_t. s0 += a0; s1 += a1; s2 += a2; s3 += a3; c0 = s0 < a0; // RISC-V `sltu` c1 = s1 < a1; c2 = s2 < a2; if (s1 == -1) goto propagate0; // executes 1 time in 18,446,744,073,709,551,616 check_s2: if (s2 == -1) goto propagate1; // ditto add_carries: s1 += c0; s2 += c1; s3 += c2; goto done; propagate0: c1 = c0; goto check_s2; propagate1: c2 = c1; goto add_carries; done: The key insight here is that unless the sum at a particular limb position is all 1s the carry out from that position DOES NOT DEPEND on the carry in to that limb position, but only on whether the original add in that position produces a carry. If the sum is all 1s the the carry out is the same as the carry in. If you express this with a conditional branch which is overwhelmingly predicted as not taken then the code should execute each block of instructions entirely in parallel, provided that multiple conditional branches can be predicted as not-taken in the same clock cycle. One time in 2^64 it will execute very slowly. With 4 limb numbers on a 4-wide machine this doesn't offer an advantage over `adc` as there are also 4 code blocks. But on, say, an 8-wide machine with 8 limb numbers you're really starting to gain. It's probably not going to help on current x86_64, but might well do on Apple's M* series, where even the M1 is 8-wide, though it might be tricky to work around the Arm ISA. When the 8-wide RISC-V Ascalon processor from Tenstorrent hits hopefully late this year or early 2026 we will really see. And others such as Ventana, Rivos, XiangShan. This will work even better in a wide SIMD, if you have a fast 1-lane shift (Called slideup on RISC-V).
- phkahler 1y agoI think you want to write: if (s1 == -1) c1 = c0; if (s2 == -1) c2 = c1; These can become conditional moves on x86. I've often thought RISC-V should have implemented an IF instruction instead of compare and branch. IF would cause the next instruction to be executed conditionally while not needing a flag register at the ISA level. They could have required only branch and jump to be conditional, but it turns out conditional mov, load, and store are all very useful in real code.
- deleted 1y ago[deleted]
- nine_k 1y agoThe main takeaway: doing more operations may be faster if they are largely independent, and thus can execute in parallel. Doing fewer operations may be slower if they are forced to execute serially due to data dependency. This idea has wider applicability than operations on long integers.
- repelsteeltje 1y agoYes. Another approach would be to use regular 64 bit chunks and speculatively execute each add with and without carry in parallel. Then select the correct variant based on carry result of less significant addition. With double the amount of additions this allows for log(bits) propagation time (versus linear)
- dgoldstein0 1y agoThere's not just "result with carry" and "result without carry" but rather one variant of that per word of the input ... Which likely isn't that bad to code up.
- brucehoult 1y agoOr see https://news.ycombinator.com/item?id=44133169 https://news.ycombinator.com/item?id=44133169
- volemo 1y agoWouldn’t that produce 2^n possible results to choose from, where n is the number of chunks? That seems like a lot of additional (he-he) instructions executed.
- repelsteeltje 1y agoNope. Just 2n: each chunk pair is added once without carry, and once won't carry=1. For as long as radix=2, you either have a carry or you don't.
- mananaysiempre 1y ago
- dang 1y agoRelated. Others? The radix 2^51 trick - https://news.ycombinator.com/item?id=33706153 https://news.ycombinator.com/item?id=33706153 - Nov 2022 (6 comments) The radix 2^51 trick (2017) - https://news.ycombinator.com/item?id=23351007 https://news.ycombinator.com/item?id=23351007 - May 2020 (83 comments)
- eru 1y agoThe 'radix trick' also works for data structures. Okasaki's book 'Purely Functional Data Structures' has some nice examples.
- alwahi 1y agohow to do this for large multiplications instead?
- nickcw 1y agoYou can do large multiplications with a convolution and do the carry afterwards. A convolution can be done with FFT, pointwise multiply, inverse FFT which is O(n log n) rather that O(n^2) for traditional multiplication. The bits in each limb can be quite small though as there are lots of carries and it depends on how many digits you have and how accurate your floating point is. Some kind of FFT is how all large multiplications are done. I had a lot of fun learning about this in relation to GIMPS (the Great Internet Mersenne Prime Search) where you use a variant FFT called a DWT over an irrational base which gives you a free mod 2^n-1 which is what you want for primality testing Mersenne prime candidates using the Lucas test.
- phkahler 1y agoGIMPS is also interesting since it doesn't need to do 2 operand multiplication. It only needs squaring.
- deleted 1y ago[deleted]
- e4m2 1y agoOn modern enough x86 CPUs (Intel Broadwell, AMD Ryzen) you could also use ADX [1] which may be faster nowadays in situations where radix 2^51 representation traditionally had an edge (e.g. Curve25519). [1] https://en.wikipedia.org/wiki/Intel_ADX https://en.wikipedia.org/wiki/Intel_ADX
- ashdnazg 1y agoWith AVX512 (and to a lesser extent with AVX2) one can implement 256 bit addition pretty efficiently with the additional benefit of fitting more numbers in registers. It looks more or less like this: __m256i s = _mm256_add_epi64(a, b); const __m256i all_ones = _mm256_set1_epi64x(~0); int g = _mm256_cmpgt_epu64_mask(a, s); int p = _mm256_cmpeq_epu64_mask(s, all_ones); int carries = ((g << 1) + p) ^ p; __m256i ret = _mm256_mask_sub_epi64(s, carries, s, all_ones); The throughput even seems to be better: https://godbolt.org/z/e7zETe8xY https://godbolt.org/z/e7zETe8xY It's trivial to change this to do 512 bit addition where the improvement will be even more significant.
- amitprasad 1y agoNote that, especially on certain Intel architectures, using AVX512 instructions _at all_ can result in the whole processor downclocking, and thus ending up resulting in inconsistent / slower overall performance. https://stackoverflow.com/questions/56852812/simd-instructions-lowering-cpu-frequency/56861355#56861355 https://stackoverflow.com/questions/56852812/simd-instructio...
- adgjlsfhk1 1y ago> using AVX512 instructions _at all_ This isn't correct. AVX512 provides both a bunch of extra instructions, zmm (512 bit) registers, and an extra 16 (for a total of 32) vector registers. The donwnclocking only happens if you use 512 bit registers (not just avx512 instructions). The difference here matters a bunch since there are a bunch of really useful instructions (e.g. 64 bit integer multiply) that are added by avx512 that are pure upside. Also none of this is an issue on Zen4 or Zen5 since they use much more sensible downlclocking where it will only downclock if you've used enough instructions in a row for it to start spiking power/temp.
- amitprasad 1y agoAh yes, you’re completely correct :) General idea was just to highlight some of the dangers of vector registers. I believe the same is true of ymm (256) to a lesser extent.
- t0010q 1y agoIt's funny that carries don't just make addition difficult to parallelize. Binary addition without carry is XOR. XOR subset sum - find a subset whose XOR gives the desired target - is in P, but proper subset sum with carry is NP-complete.
- hdjrudni 1y agoI wish I came across this article a couple months ago. I was trying to encode and decode some buffers into an arbitrary base, and I eventually came to the conclusion (after far too long) that a carry could ripple all the way down the buffer, which dramatically slows down the algorithm. Actually, the eventual solution I came up might have some stuff in common with this trick too. I did eventually chunk up the buffer leaving some unused headroom to 'handle carries'. Not exactly though, I just have some wasted bits which uses a tiny bit more storage or network bandwidth but saves on compute. I wonder if I could instead pool up the carries like this and 'resolve' it in a later step. Have my cake and eat it too? Wishful thinking.
- smcin 1y agoNotwithstanding HN guidelines about not editorializing titles, I don't like these clickbaity titles amplifying a smaller claim to something overly broad: this one should have been titled: "The radix 2^51 trick to adding 64-bit integers on *some* x86 architectures in parallel without slowing the pipeline due to dependencies on carry"
- Dwedit 1y agoSaw 2^51 and thought it was about storing integers into doubles. But nope, the number for that particular use is 2^53-1, not 2^51.