Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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

share|improve this question
    
As in 2 * 3 or Math.Pi * 2.0? –  delnan Dec 11 '12 at 17:47
4  
actually that is implementation defined (at the level of the hardware most of the time) and they can use any implementation as long as it conforms with the defined standard (IEEE 754 IIRC) –  ratchet freak Dec 11 '12 at 17:48
1  
So the compiler simply tells the hardware to multiply two numbers? :O –  Harsha Dec 11 '12 at 17:50
3  
exactly, most processors these days have a floating point ALU built in, if there is no matching operation in the target platform (when there is only support for single precision and you want to use double precision) the compiler is free to use whatever algorithm it wants –  ratchet freak Dec 11 '12 at 17:55
2  
@Harsha: In the case of primitives, yes. In the case of other numerics, no. Most non-primitive multiplication is not implemented in C# (e.g., Decimal.cs has an extern call to FCallMultiply). However, if you want to see some framework multiplication, check out RefSrc\Source\.Net\4.0\DEVDIV_TFS\Dev10\Releases\RTMRel\ndp\fx\src\security\sys‌​tem\security\cryptography\BigInt.cs within .Net 4+ on referencesource.microsoft.com/netframework.aspx . The code is exactly what you would expect. –  Brian Dec 11 '12 at 17:57
show 2 more comments

2 Answers

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.

share|improve this answer
add comment

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.

share|improve this answer
    
I don't think those CIL instructions are used for decimal, especially since it's not a primitive .Net type. –  svick Dec 12 '12 at 1:28
    
After a second look, agreed. It does have an alias, and it is a ValueType, but it isn't in the same class as the smaller floating-point and integral types. Edited. –  KeithS Dec 12 '12 at 15:38
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.