C# Algorithms for * Operator

Question

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#?

Answer 1

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.

Answer 2

MSIL aka CIL, into which C# source code is digested, has opcodes for three variations on "multiply"; "mul", "mul.ovf", and "mul.ovf.un". These are used for most built-in value types, from byte to double. They translate pretty directly down to similar native commands.

The first code is general-purpose; value1 and value2 are pushed onto the evaluation stack, then "mul" is called; value1 and value2 are popped, multiplied, and the result is pushed to the evaluation stack. The two variations are for integer multiplication only, and define "checked" overflow behavior; "mul.ovf" asserts that the signed result value will fit into the determined result type without overflow, while "mul.ovf.un" asserts that the unsigned value will fit into the result type.

The "mul" command, like most opcodes, produces a result of a type based on the specifications; the basic rules are that the operation is defined for two inputs, both of which must be the same type and one of the following: int32, uint32, int64, uint64, float, or double. For multiplication of differing types, or types not in the list such as byte, sbyte and short, a widening conversion is performed on the value of the smaller size or precision to that of the larger (or to the minimum). This happens pretty much by default for smaller integer types; the CPU won't deal with anything smaller than a word (16-bit), and some won't even deal with less than a dword at once anymore, so the CLR implementation will simply feed smaller values to the CPU as dwords.

Down at the native level, there are two basic commands in 80x86 assembler to perform multiplication on the same basic types: "MUL" will multiply any two integers (using word, dword or word64 lengths), putting the result in some length-dependent variant of the AX register, while FMUL and FMULP perform the equivalent operation on floating-point types using the chip's FPU, optionally popping the result off of the FPU's eval stack into the AX register.

As far as exactly which binary algorithm is used to arrive at the answer produced by the commands, you really shouldn't care; whatever's used, you can be sure it's much more performant than anything you could do in managed source code.

Now, for larger structural types, like Decimal and BigInteger, built-in native multiplication operations don't exist, and those types do rely on multiplication algorithms. Here's the code for BigInteger, implemented in a hidden helper BigIntegerBuilder: http://typedescriptor.net/name/types/8FF4E74C7553501B0863FF102EC0C5B1-System.Numerics.BigIntegerBuilder. Decimal uses a call to FCallMultiply; unfortunately that's an extern method tying into the MFCs so I can't find source code.

Answer 3

This is a rather mundane addendum to the other answers.

Since this question was asked, Microsoft has released the source code for .net framework. You can find the source for decimal multiply here. You will notice that the multiplication is offloaded into an internal method (FCallMultiply) buried within the CLR, so there isn't actually any source to see.

With the release/redesign of dotnet core (I'm not sure of the timeline specifics), the source code for decimal multiply method is now available online in the coreCLR "runtime" repository here.

Background:

C# decimal is composed of four 32-bit integers, one for "flags" which includes the sign and exponent, and three ints for the "value" (referred to as "high", "mid", and "low"). The exponent is from base 10 (compared to IEEE float which is base 2).

A couple notes on the multiplication source:

• Name change to VarDecMul internal method.
• UInt32x32To64 multiplies two 32 bit integers and returns a 64 bit int.

And on the algorithm:

• There is short circuit logic, if the "high" bits aren't set, they won't be multiplied. Same for "mid".
• Then multiplication is carried out in the standard "grade school" algorithm, and scaled accordingly.