C# Algorithms for * Operator

algorithmsc

I was reading up on Algorithms and came across the Karatsuba multiplication algorithm and a little wiki-ing led to the Schonhage-Strassen and Furer algorithms for multiplication.

I was wondering what algorithms are used on the * operator in C#? While multiplying a pair of integers or doubles, does it use a combination of algorithms with some kind of strategy based on the size of the numbers? How could I find out the implementation details for C#?

Best Answer

As with all implementation details, it's specific to the implementation (duh), but this is something that's practically universal: If the CPU supports the number type and operation (reasonably recent processors do, for floats, doubles, and the fixed-width integers), you just use that. There may be many layers in between, such as an interpreter, a JIT compiler for the IL, or something entirely else, but that's just wrappers and the actual operation is delegated to the hardware.

You'll have a very hard time beating a good hardware implementation in software, regardless of the choice of algorithm -- with one "common" exception: A slow FPU can sometimes be beaten by sacrificing some features, but that's a very low-level optimization. But that's not something language implementations usually do.

For arbitrary precision integers/numbers (such as BigInt and BigDecimal), you can't (entirely) rely on the hardware operations, as they are too constrained in word size. In such cases, algorithms start to matter, but again it's implementation specific and I can't give any generalizations. Note that the base is usually much greater than 10, to get the most out of the fixed-precision operations. I know that more than one highly used arbitrary precision arithmetic package (specifically, CPython's and PyPy's long type, and the relevant piece of Mathematica) use, or at least consider, Karatsuba's algorithm.

Related Topic