C# Algorithms for * Operator

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

6

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.

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 80×86 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.

2

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.

Trang chủ Giới thiệu Sinh nhật bé trai Sinh nhật bé gái Tổ chức sự kiện Biểu diễn giải trí Dịch vụ khác Trang trí tiệc cưới Tổ chức khai trương Tư vấn dịch vụ Thư viện ảnh Tin tức - sự kiện Liên hệ Chú hề sinh nhật Trang trí YEAR END PARTY công ty Trang trí tất niên cuối năm Trang trí tất niên xu hướng mới nhất Trang trí sinh nhật bé trai Hải Đăng Trang trí sinh nhật bé Khánh Vân Trang trí sinh nhật Bích Ngân Trang trí sinh nhật bé Thanh Trang Thuê ông già Noel phát quà Biểu diễn xiếc khỉ Xiếc quay đĩa Dịch vụ tổ chức sự kiện 5 sao Thông tin về chúng tôi Dịch vụ sinh nhật bé trai Dịch vụ sinh nhật bé gái Sự kiện trọn gói Các tiết mục giải trí Dịch vụ bổ trợ Tiệc cưới sang trọng Dịch vụ khai trương Tư vấn tổ chức sự kiện Hình ảnh sự kiện Cập nhật tin tức Liên hệ ngay Thuê chú hề chuyên nghiệp Tiệc tất niên cho công ty Trang trí tiệc cuối năm Tiệc tất niên độc đáo Sinh nhật bé Hải Đăng Sinh nhật đáng yêu bé Khánh Vân Sinh nhật sang trọng Bích Ngân Tiệc sinh nhật bé Thanh Trang Dịch vụ ông già Noel Xiếc thú vui nhộn Biểu diễn xiếc quay đĩa Dịch vụ tổ chức tiệc uy tín Khám phá dịch vụ của chúng tôi Tiệc sinh nhật cho bé trai Trang trí tiệc cho bé gái Gói sự kiện chuyên nghiệp Chương trình giải trí hấp dẫn Dịch vụ hỗ trợ sự kiện Trang trí tiệc cưới đẹp Khởi đầu thành công với khai trương Chuyên gia tư vấn sự kiện Xem ảnh các sự kiện đẹp Tin mới về sự kiện Kết nối với đội ngũ chuyên gia Chú hề vui nhộn cho tiệc sinh nhật Ý tưởng tiệc cuối năm Tất niên độc đáo Trang trí tiệc hiện đại Tổ chức sinh nhật cho Hải Đăng Sinh nhật độc quyền Khánh Vân Phong cách tiệc Bích Ngân Trang trí tiệc bé Thanh Trang Thuê dịch vụ ông già Noel chuyên nghiệp Xem xiếc khỉ đặc sắc Xiếc quay đĩa thú vị
Trang chủ Giới thiệu Sinh nhật bé trai Sinh nhật bé gái Tổ chức sự kiện Biểu diễn giải trí Dịch vụ khác Trang trí tiệc cưới Tổ chức khai trương Tư vấn dịch vụ Thư viện ảnh Tin tức - sự kiện Liên hệ Chú hề sinh nhật Trang trí YEAR END PARTY công ty Trang trí tất niên cuối năm Trang trí tất niên xu hướng mới nhất Trang trí sinh nhật bé trai Hải Đăng Trang trí sinh nhật bé Khánh Vân Trang trí sinh nhật Bích Ngân Trang trí sinh nhật bé Thanh Trang Thuê ông già Noel phát quà Biểu diễn xiếc khỉ Xiếc quay đĩa
Thiết kế website Thiết kế website Thiết kế website Cách kháng tài khoản quảng cáo Mua bán Fanpage Facebook Dịch vụ SEO Tổ chức sinh nhật