Re:Optimizing Big Number Arithmetic Without SSE
by zvrba on Monday February 10, 2014 @06:51AM
(#7210470)
> What if the architecture doesn't have a carry? Then the compiler has to generate one when needed.
Adding two N-bit numbers produces N+1-bit result, and C gives you no direct means of accessing the full result. IMO, this is a language defect and has little to do with HW support. [This pertains also to multiplication: NxN bits -> 2N-bit result.]
If the hardware actually returns the full result, excellent; if no, the compiler has to synthesize code to compute it, if needed. Whether it's needed is inferrable by the code that follows, e.g., the type of the variable the result is assigned to.
IMO, inferring that only a partial result is used (e.g., carry is discarded) is much easier for the optimizer than inferring what some instruction sequence is supposed to do. (E.g., 4+ multiplications and few additions => single 32x32=>64 multiply.)
Adding two N-bit numbers produces N+1-bit result, and C gives you no direct means of accessing the full result. IMO, this is a language defect and has little to do with HW support. [This pertains also to multiplication: NxN bits -> 2N-bit result.]
If the hardware actually returns the full result, excellent; if no, the compiler has to synthesize code to compute it, if needed. Whether it's needed is inferrable by the code that follows, e.g., the type of the variable the result is assigned to.
IMO, inferring that only a partial result is used (e.g., carry is discarded) is much easier for the optimizer than inferring what some instruction sequence is supposed to do. (E.g., 4+ multiplications and few additions => single 32x32=>64 multiply.)