C# 11.0 generic math is very powerful extension to already capable generic types system present in C# since version 2.0. Besides static interface members there are couple of changes that make it easier to express math concepts in C#. Let’s see what needed to change in order to add this neat feature.
Note
This blog post participates in C# Advent Calendar 2022. Expect around 50 awesome posts this month, with 2 being revealed every day. It’s digital/C#-oriented counterpart of old German tradition
Interfaces and operations
While generic math is C# 11 feature, there were some new additions in .NET framework itself. In order to facilitate appropriate abstraction, the following interfaces were introduced and numeric/built-in types subsequently started implementing them:
In C# 11 it is now possible to specify operators as checked. Compiler will select appropriate version depending on context (Visual Studio will navigate to appropriate operator definition upon pressing F12/“Go to definition”). Let’s see that on example:
readonlyrecordstructPoint(intX,intY){publicstaticPointoperatorchecked+(Pointleft,Pointright)=>checked(new(left.X+right.X,left.Y+right.Y));publicstaticPointoperator+(Pointleft,Pointright)=>new(left.X+right.X,left.Y+right.Y);}//usagevarpoint=newPoint(int.MaxValue-1,int.MaxValue-2);//Point { X = 2147483646, Y = 2147483645 }var@unchecked=unchecked(point+point);//Point { X = -4, Y = -6 }var@checked=checked(point+point);//⚠️ throws System.OverflowException
Identity element and constants
Every number type usually (always for C# numbers but that is not necessarily the case in math) has some identity elements for most popular operations (addition and multiplication). The following listing demonstrates them using generic guard as these constants are not publicly exposed
In order to be able to smoothly convert numbers from other number types, several methods were added:
CreateChecked - convert “exactly” or throw if number falls outside the representable range
CreateSaturating - convert values saturating any values that fall outside the representable range
CreateTruncating - convert values truncating any values that fall outside the representable range
//specifying generic type is not needed, it's just here for clarity varb1=byte.CreateSaturating<int>(300);//255varb2=byte.CreateTruncating(300);//44varb3=byte.CreateChecked(300);//⚠️ Arithmetic operation resulted in an overflow.varb4=byte.CreateChecked(3.14);//3
Dedicated functions
New function were introduced to built-in types to facilitate typical operation that we perform with given number groups.
//Check if integer is power of two. Equivalent to BitOperations.IsPow2(1024) varisPow=int.IsPow2(1024);// true//Population count (number of bits set). Same as BitOperations.PopCount(15) - vectorized if possible varpop=int.PopCount(15);// 4//Cubic root of a specified number. Equivalent to MathF.Cbrt(x)varcbrt=float.Cbrt(8.0f);// 2//Sine of the specified angle (in radians). Equivalent to MathF.Sin(x)varsin=float.Sin(float.Pi/6.0f);//0.5
We are now ready to propose a new type that will denote a generic matrix of number-like structures. Make sure to read a post about static interface members if that concept is still new to you.
Structure
Let’s start with simple definition. Just for fun we will be restricting our number generic parameter to unmanaged types. This is not strictly needed for our example but it will allow for some tricks like faster array enumeration
publicpartialclassMatrix<TNumber>//for now we are not extending any interfacewhereTNumber:unmanaged//needed for pointer "magic"{privatereadonlyTNumber[,]_data;publicintRows{get;}publicintColumns{get;}publicintSize{get;}publicTNumberthis[intiRow,intiCol]=>_data[iRow,iCol];publicMatrix(TNumber[,]data){_data=data;Rows=data.GetLength(0);Columns=data.GetLength(1);Size=Rows*Columns;}//optionally we'd like to be able to create Matrix using 1-D array with certain number of columns publicunsafeMatrix(TNumber[]data,intcolumns){vardata2d=newTNumber[data.Length/columns,columns];fixed(TNumber*pSource=data,pTarget=data2d){for(inti=0;i<data.Length;i++)pTarget[i]=pSource[i];}_data=data2d;Rows=data2d.GetLength(0);Columns=data2d.GetLength(1);}}
Matrix operations
While this class already is able to store some data, we would not be able to do anything meaningful with it. Let’s add our first math operation - addition. Since that operation uses only addition and needs to be seeded with zero (additive identity) we could modify our generic guard to:
classMatrixwhereTNumber:unmanaged,IAdditionOperators<TNumber,TNumber,TNumber>,IAdditiveIdentity<TNumber,TNumber>{/*...*/publicunsafeTNumberSum(){varresult=TNumber.AdditiveIdentity;fixed(TNumber*pData=_data)//use pointers to be able to iterate array faster {varp=pData;for(inti=0;i<Size;i++)result+=*p++;}returnresult;}}
but we would be better off when that guard would be changed to
publicpartialclassMatrix<TNumber>whereTNumber:unmanaged,//it is just necessary to mark number type appropriately to be able to use it in generic contextsINumberBase<TNumber>{/*...*/publicunsafeTNumberSum(){//"Zero" also looks more natural in that context as opposed to "AdditiveIdentity"varresult=TNumber.Zero;fixed(TNumber*pData=_data){varp=pData;for(inti=0;i<Size;i++)result+=*p++;}returnresult;}}
Summation is obviously useful but it’s also trivial in it’s form. For instance let’s consider C# whole number types. Like in math, natural and integer numbers are closed under addition. When you consider other operations on these numbers, say division, this is no longer the case. While we could calculate an average of integers in C# as follows
publicunsafeTResultSum<TResult>()whereTResult:INumber<TResult>{varresult=TResult.Zero;fixed(TNumber*pData=_data){varp=pData;for(inti=0;i<Size;i++)result+=TResult.CreateChecked(*p++);}returnresult;}// now Average can use Sum<TResult>publicTResultAverage<TResult>()whereTResult:INumber<TResult>{TResultsum=Sum<TResult>();returnsum/TResult.CreateChecked(Size);}
No matrix is complete without Determinant function. While there are dozens of algorithms to do that, I’ll use a plain decomposition approach due to it’s simplicity
publicTNumberDeterminant(){if(Rows!=Columns)thrownew("Determinant of a non-square matrix doesn't exist");vardet=TNumber.Zero;if(Rows==1)returnthis[0,0];if(Rows==2)returnthis[0,0]*this[1,1]-this[0,1]*this[1,0];for(intj=0;j<Columns;j++){TNumberreduced=this[0,j]*Minor(0,j).Determinant();if(j%2==1)reduced=-reduced;det+=reduced;}returndet;}publicMatrix<TNumber>Minor(intiRow,intiCol){varminor=newTNumber[Rows-1,Columns-1];intm=0;for(inti=0;i<Rows;i++){if(i==iRow)continue;intn=0;for(intj=0;j<Columns;j++){if(j==iCol)continue;minor[m,n]=this[i,j];n++;}m++;}returnnew(minor);}
Similarly it might be useful to obtain largest and smallest element in matrix. Since that requires some comparisons, let’s add IComparisonOperators<TNumber, TNumber, bool> interface to our generic guard for TNumber. Doing so enables us to then use comparison operators. We will however lose (as a consequence) the ability of using types that do not possess relational ordering - Complex type being most notable here
Note
Using IComparisonOperators<TNumber, TNumber, bool> is somewhat limiting. It’s probably more important to be able to use final matrix with types like Complex especially if Min/Max operation could be added using different approach. So final design of matrix might reflect that notion
publicunsafeTNumberMin(){if(Size==0)thrownew("Matrix is empty");TNumberresult;fixed(TNumber*pData=_data){varp=pData;result=*p;for(inti=1;i<Size;i++)result=Min(result,*p++);}returnresult;staticTNumberMin(TNumberx,TNumbery){if((x!=y)&&!TNumber.IsNaN(x))returnx<y?x:y;returnTNumber.IsNegative(x)?x:y;}}publicunsafeTNumberMax(){if(Size==0)thrownew("Matrix is empty");TNumberresult;fixed(TNumber*pData=_data){varp=pData;result=*p;for(inti=1;i<Size;i++)result=Max(result,*p++);}returnresult;staticTNumberMax(TNumberx,TNumbery){if(x!=y)returnTNumber.IsNaN(x)?x:y<x?x:y;returnTNumber.IsNegative(y)?x:y;}}
Matrix operators
Have a look at the following operators (code example might need expanding):
//add 2 matricespublicunsafestaticMatrix<TNumber>operator+(Matrix<TNumber>left,Matrix<TNumber>right){if(left.Rows!=right.Rows||left.Columns!=right.Columns)thrownew("Sum of 2 matrices is only possible when they are same size");vardata=newTNumber[left.Rows,left.Columns];varsize=left.Rows*left.Columns;fixed(TNumber*lSource=left._data,rSource=right._data,target=data){for(inti=0;i<size;i++)target[i]=lSource[i]+rSource[i];//checked operator version would differ only in this line}returnnewMatrix<TNumber>(data);}//right-side operator for adding single number element-wisepublicunsafestaticMatrix<TNumber>operator+(Matrix<TNumber>left,TNumberright){vardata=newTNumber[left.Rows,left.Columns];varsize=left.Rows*left.Columns;fixed(TNumber*lSource=left._data,target=data){for(inti=0;i<size;i++)target[i]=lSource[i]+right;}returnnewMatrix<TNumber>(data);}// Multiplication. More efficient function might be chosen for production code. // This is just to illustrate this operatorpublicstaticMatrix<TNumber>operator*(Matrix<TNumber>a,Matrix<TNumber>b){introwsA=a.Rows,colsA=a.Columns,rowsB=b.Rows,colsB=b.Columns;if(colsA!=rowsB)thrownew("Matrixes can't be multiplied");vardata=newTNumber[rowsA,colsB];for(inti=0;i<rowsA;i++){for(intj=0;j<colsB;j++){vartemp=TNumber.Zero;for(intk=0;k<colsA;k++)temp+=a[i,k]*b[k,j];data[i,j]=temp;}}returnnewMatrix<TNumber>(data);}
Parsing
No math structure is complete without parsing and formatting routines. We would like to support multiple matrix definition formats like:
Matlab: [1,2,3 ; 4,5,6 ; 7,8,9]
Mathematica: {{1,2,3},{4,5,6},{7,8,9}}
natural notation:
147258369
The code below might do the trick (full code is linked at the end of current article):
/// <summary>Parsing and formatting operation for matrices</summary>publicinterfaceIMatrixTextFormat{/// <summary>/// Parse matrix from text buffer /// </summary> Matrix<TNumber>Parse<TNumber>(ReadOnlySpan<char>s)whereTNumber:unmanaged,IComparisonOperators<TNumber,TNumber,bool>,INumberBase<TNumber>;/// <summary>/// Attempt to format current matrix in provided text buffer/// </summary> boolTryFormat<TNumber>(Matrix<TNumber>matrix,Span<char>destination,outintcharsWritten,ReadOnlySpan<char>format)whereTNumber:unmanaged,IComparisonOperators<TNumber,TNumber,bool>,INumberBase<TNumber>;}publicreadonlystructStandardFormat:IMatrixTextFormat{privatereadonlyIFormatProvider_underlyingProvider;privatereadonlyNumberStyles?_numberStyles;privatereadonlychar_elementSeparator;privatestaticreadonlychar[]_rowSeparators=Environment.NewLine.ToCharArray();publicStandardFormat():this(CultureInfo.InvariantCulture){}publicStandardFormat(IFormatProvider?underlyingProvider,NumberStylesnumberStyles=NumberStyles.Any){_numberStyles=numberStyles;_underlyingProvider=underlyingProvider??CultureInfo.InvariantCulture;(_underlyingProvider,_elementSeparator)=GetParameters();}private(IFormatProviderProvider,charElementSeparator)GetParameters(){varprovider=_underlyingProvider??CultureInfo.InvariantCulture;charelementSeparator=_elementSeparator!='\0'?_elementSeparator:(providerisCultureInfoci?ci.TextInfo.ListSeparator.Trim().Single():';');return(provider,elementSeparator);}publicMatrix<TNumber>Parse<TNumber>(ReadOnlySpan<char>s)whereTNumber:unmanaged,IComparisonOperators<TNumber,TNumber,bool>,INumberBase<TNumber>{var(provider,elementSeparator)=GetParameters();varnumberStyles=_numberStyles??NumberStyles.Any;varrowsEnumerator=s.Split(_rowSeparators,true).GetEnumerator();if(!rowsEnumerator.MoveNext())thrownewFormatException("Non empty text is expected");varfirstRow=rowsEnumerator.Current;intnumCols=0;usingvarbuffer=newValueSequenceBuilder<TNumber>(stackallocTNumber[32]);foreach(varcolinfirstRow.Split(elementSeparator,true)){if(col.IsEmpty)continue;buffer.Append(TNumber.Parse(col,numberStyles,provider));numCols++;}intnumRows=1;while(rowsEnumerator.MoveNext()){varrow=rowsEnumerator.Current;if(row.IsEmpty)continue;foreach(varcolinrow.Split(elementSeparator,true)){if(col.IsEmpty)continue;buffer.Append(TNumber.Parse(col,numberStyles,provider));}numRows++;}varmatrix=newTNumber[numRows,numCols];buffer.AsSpan().CopyTo2D(matrix);returnnewMatrix<TNumber>(matrix);}publicboolTryFormat<TNumber>(Matrix<TNumber>matrix,Span<char>destination,outintcharsWritten,ReadOnlySpan<char>format)whereTNumber:unmanaged,IComparisonOperators<TNumber,TNumber,bool>,INumberBase<TNumber>{var(provider,elementSeparator)=GetParameters();varnewLine=_rowSeparators.AsSpan();varnewLineLen=newLine.Length;intcharsWrittenSoFar=0;for(inti=0;i<matrix.Rows;i++){for(intj=0;j<matrix.Columns;j++){booltryFormatSucceeded=matrix[i,j].TryFormat(destination[charsWrittenSoFar..],outvartryFormatCharsWritten,format,provider);charsWrittenSoFar+=tryFormatCharsWritten;if(!tryFormatSucceeded){charsWritten=charsWrittenSoFar;returnfalse;}if(j<matrix.Columns-1){if(destination.Length<charsWrittenSoFar+2){charsWritten=charsWrittenSoFar;returnfalse;}destination[charsWrittenSoFar++]=elementSeparator;destination[charsWrittenSoFar++]=' ';}}if(i<matrix.Rows-1){if(destination.Length<charsWrittenSoFar+newLineLen){charsWritten=charsWrittenSoFar;returnfalse;}newLine.CopyTo(destination[charsWrittenSoFar..]);charsWrittenSoFar+=newLineLen;}}charsWritten=charsWrittenSoFar;returntrue;}}
Beyond standard number types
So far we’ve assumed (quite correctly) that only types that implement INumberBase<TNumber> interface are built‑in system number types. Let’s quickly implement a rational/fraction structure and see how it can be used in our matrix. For brevity I’m only providing/implementing formatting routines (stay tuned for more functionality):
publicreadonlyrecordstructRational<TNumber>(TNumberNumerator,TNumberDenominator):IEquatable<Rational<TNumber>>,IComparisonOperators<Rational<TNumber>,Rational<TNumber>,bool>,INumberBase<Rational<TNumber>>whereTNumber:IBinaryInteger<TNumber>//make sense to allow only integers for numerator and denominator{publicstaticRational<TNumber>Zero=>new(TNumber.Zero,TNumber.One);publicstaticRational<TNumber>One=>new(TNumber.One,TNumber.One);publicstaticRational<TNumber>AdditiveIdentity=>Zero;publicstaticRational<TNumber>MultiplicativeIdentity=>One;publicstaticintRadix=>TNumber.Radix;publicRational():this(TNumber.Zero,TNumber.One){}publicRational<TNumber>Simplify(){var(num,denom)=this;intsignNum=TNumber.Sign(num),signDenom=TNumber.Sign(denom);if(signDenom<0&&(signNum<0||signNum>0)){num=-num;denom=-denom;}if(num==TNumber.Zero||num==TNumber.One||num==-TNumber.One)returnthis;vargcd=GreatestCommonDivisor(num,denom);returngcd>TNumber.One?newRational<TNumber>(num/gcd,denom/gcd):this;}privatestaticTNumberGreatestCommonDivisor(TNumbera,TNumberb)=>b==TNumber.Zero?a:GreatestCommonDivisor(b,a%b);privatestaticreadonlystringTopDigits="⁰¹²³⁴⁵⁶⁷⁸⁹";privatestaticreadonlystringBottomDigits="₀₁₂₃₄₅₆₇₈₉";privatestaticreadonlycharTopMinus='⁻';privatestaticreadonlycharBottomMinus='₋';privatestaticreadonlycharDivider='⁄';publicboolTryFormat(Span<char>destination,outintcharsWritten,ReadOnlySpan<char>format,IFormatProvider?provider){var(num,denom)=this;intsignNum=TNumber.Sign(num),signDenom=TNumber.Sign(denom);if(signDenom<0&&(signNum<0||signNum>0)){num=-num;denom=-denom;}provider??=CultureInfo.InvariantCulture;charsWritten=0;if(destination.Length<3)returnfalse;booltryFormatSucceeded=num.TryFormat(destination,outvartryFormatCharsWritten,format,provider);charsWritten+=tryFormatCharsWritten;if(!tryFormatSucceeded||destination.Length<charsWritten+2)returnfalse;varnumBlock=destination[..charsWritten];for(inti=0;i<numBlock.Length;i++){varc=numBlock[i];if(!IsSimpleDigit(c)&&c!='-')returnfalse;numBlock[i]=c=='-'?TopMinus:TopDigits[c-'0'];}if(destination.Length<charsWritten+2)returnfalse;destination[charsWritten++]=Divider;tryFormatSucceeded=denom.TryFormat(destination[charsWritten..],outtryFormatCharsWritten,format,provider);varstartOfDenomBlock=charsWritten;charsWritten+=tryFormatCharsWritten;if(!tryFormatSucceeded)returnfalse;vardenomBlock=destination.Slice(startOfDenomBlock,tryFormatCharsWritten);for(inti=0;i<denomBlock.Length;i++){varc=denomBlock[i];if(!IsSimpleDigit(c)&&c!='-')returnfalse;denomBlock[i]=c=='-'?BottomMinus:BottomDigits[c-'0'];}returntrue;staticboolIsSimpleDigit(charc)=>(uint)c<128&&(uint)(c-'0')<='9'-'0';}publicstringToString(string?format,IFormatProvider?formatProvider)=>this.FormatToString(format,formatProvider);publicoverridestring?ToString()=>ToString("G",null);/*... remaining code omitted for brevity*/}
Now we can use Rational structure in our matrix:
varrationalMatrix=newMatrix<Rational<int>>(Enumerable.Range(1,9).Select(i=>newRational<int>(i*10*(i%2==0?1:-1),//--------------------------------i*123)).ToArray(),3);//formatting of matrix delegates element formatting to Rational struct vartext=rationalMatrix.ToString();
Code “performance” is ambiguous term. It may refer to both ease/speed of development of given feature or how said feature behaves during program runtime. Let me address the former one first as it may be easier to demonstrate
Speed of development
Some time ago I’ve create genericpredictor that used logistic regression. In that context “generic” meant that it was not dedicated and could be used to solve any binary classification problem (while being universal enough that same mechanism might be employed for multi-class classification).
I decided to introduce generic math to this predictor as users may then opt to use, say, different floating point number type (likeSystem.SingleorSystem.Half) when it will give them similar results (for certain problems this really might be the case) but with smaller memory footprint and faster processing times. All that conversion was done on separate branch.
One can observe that merely a few changes needed to be applied. Conversion took me not more than 5 minutes. Had this coding be done with generic math in mind from the beginning - impact would have probably been even more negligible - provided that generic math is a concept known by developer (learning curve tends to be steep here)
Runtime performance
Have a look at my proposal of a simple vector structures. Among them you will find dedicated version for LongVector (not embedded here for brevity) and dedicated version for System.Double:
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Below you will find version that uses generic math along with version that uses generic math in tandem with pointer arithmetics (Vector2.cs and others were not embedded for brevity):
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
One can clearly see that memory-wise, they all behave the same - by not allocating anything. Types in benchmark were defined as structs. While it may not be best option for such data structures, it helps here by not obstructing our view with needless allocations).
Double benchmarks are always ~2 times slower than Long ones but that has nothing to do with generic math itself - floating-point related operations are generally slower on CPUs.
What also can be observed is that difference in processing speed is negligible. Generic math is not adding much. In case we need to optimize, we can do so by employing pointer arithmetics or (better yet) - Spans.
One could argue that DoubleVectorand LongVector could also benefit from using additional optimization techniques but we need to repeat them for each and every case. We might probably be more tempted to introduce optimizations when many (generic) types can benefit from these actions.
This graph summarizes in details all benchmarks performed for System.Long type for various vector sizes. One can clearly see that differences are almost negligible
Same data, but restricted only to largest sizes:
Source code
Full benchmark and results can be found under this gist
Summary
We’ve seen how one might go about implementing generic math in their code. This matrix is not complete but quite soon I intend to finish it. It will be distributed via nuget like my other packages.
Are you still not convinced? It seems that Microsoft is already using generic math in their libraries i.e. in many places in LINQ including (but not limited to) Average or Sum, which replaced some old and seasoned dedicated types copy-and-paste method implementations. If Microsoft is having faith in generic math, there is no reason that shouldn’t you.
Bonus - physics
This should be treated as a work-in-progress but have a look at my initial proposal on how units can now be defined in C#: Generic Units