Someone working entirely on x86_64 very nicely demonstrates that RISC-V is not wrong to omit the carry flag.
ha, I'm not the only one to think "so what's all the risc5 gmp fuss was about, if carry flag is slow anyway?"
The radix 2^51 trick (2017)
21–30 of 86 posts
Re: The radix 2^51 trick (2017)
#22Someone working entirely on x86_64 very nicely demonstrates that RISC-V is not wrong to omit the carry flag.
This is all downstream of C omitting the carry flag, which means in practice it's very rarely used for the purpose of a carry.
Re: The radix 2^51 trick (2017)
#23The 'radix trick' also works for data structures.
Okasaki's book 'Purely Functional Data Structures' has some nice examples.
Re: The radix 2^51 trick (2017)
#24The 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.
This rule scales up all the way to multi-node supercomputers / cloud. The overhead is negligible when you can employ 10.000 cores.
Re: The radix 2^51 trick (2017)
#25The 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.
This rule scales up all the way to multi-node supercomputers / cloud. The overhead is negligible when you can employ 10.000 cores.
Amdahl says no.
Re: The radix 2^51 trick (2017)
#26how to do this for large multiplications instead?
Re: The radix 2^51 trick (2017)
#27Would it be legal for a C(++?) compiler to implement this optimization?
An 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.
Re: The radix 2^51 trick (2017)
#28> 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 th…
Because 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.
Re: The radix 2^51 trick (2017)
#29how to do this for large multiplications instead?
You 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.
Re: The radix 2^51 trick (2017)
#30[deleted]