Enhanced C#
Language of your choice: library documentation
Static Public Member Functions | List of all members
Loyc.Math.Math128 Class Reference

Contains methods for manipulating 128-bit numbers, multiplying 64-bit numbers to produce 128-bit results, and dividing 128-bit numbers by 64-bit numbers. More...


Source file:

Remarks

Contains methods for manipulating 128-bit numbers, multiplying 64-bit numbers to produce 128-bit results, and dividing 128-bit numbers by 64-bit numbers.

MathEx.MulDiv and MathEx.MulShift rely on this class for 64x64 MulDiv() and MulShift().

Some functionality is incomplete at this time, e.g. there are no comparison methods or 128+128 addition/subtraction.

This class works on raw Int64 values, so a 128-bit number is represented by a pair of Int64s, one with high bits and one with low bits. By convention, the low 64 bits are always unsigned (because they contain no sign bit), and the high 64 bits may be signed or unsigned, which represents the sign of the 128-bit number as a whole.

Many methods pass the low 64 bits by reference and the high 64 bits by value, returning the "new" high 64 bits as the return value. This is done to help implement signed math in terms of unsigned math. If the parameter type is "ref ulong", C# does not allow you to pass "ref long", even with a cast. Passing the high bits by value is therefore less cumbersome.

Static Public Member Functions

static ulong Multiply (ulong a, ulong b, out ulong resultHi)
 
static ulong Multiply (long a, long b, out long resultHi)
 
static long Divide (long aH, ulong aL, long b, out long remainder, bool roundDown)
 Divides an signed 128-bit number by a signed 64-bit number to produce a 64-bit result. More...
 
static ulong Divide (long aH, ulong aL, long b, out long resultHi, out long remainder, bool roundDown)
 Divides an signed 128-bit number by a signed 64-bit number to produce a 128-bit result. More...
 
static ulong Divide (ulong aH, ulong aL, ulong b, out ulong remainder)
 Divides an signed 128-bit number by a signed 64-bit number to produce a 64-bit result. More...
 
static ulong Divide (ulong aH, ulong aL, ulong b, out ulong resultHi, out ulong remainder)
 Divides an unsigned 128-bit number by an unsigned 64-bit number to produce a 128-bit result. More...
 
static ulong ShiftLeft (ulong aH, ref ulong aL, int amount)
 Shifts a 128-bit value left. More...
 
static ulong ShiftLeftFast (ulong aH, ref ulong aL, int amount)
 Variation of ShiftLeft() for cases when you know 64 > amount >= 0. More...
 
static ulong ShiftLeftEx (ref ulong aH, ref ulong aL, int amount)
 Shifts a 128-bit value left and saves the overflowed bits. More...
 
static ulong RotateLeft (ulong aH, ref ulong aL, int amount)
 
static ulong ShiftRight (ulong aH, ref ulong aL, int amount)
 Shifts a 128-bit value right. More...
 
static long ShiftRight (long aH, ref ulong aL, int amount)
 
static ulong Add (ulong aH, ref ulong aL, ulong amount)
 Adds a 64-bit number to a 128-bit number. More...
 
static ulong Subtract (ulong aH, ref ulong aL, ulong amount)
 Subtracts a 64-bit number from a 128-bit number. More...
 
static long Add (long aH, ref ulong aL, long amount)
 
static long Subtract (long aH, ref ulong aL, long amount)
 
static void Negate (ref long aH, ref ulong aL)
 
static long SignExtend (long a)
 

Member Function Documentation

static ulong Loyc.Math.Math128.Add ( ulong  aH,
ref ulong  aL,
ulong  amount 
)
inlinestatic

Adds a 64-bit number to a 128-bit number.

Parameters
aHHigh 64 bits of 128-bit number
aLLow 64 bits of 128-bit number
amountAmount to add
Returns
The high 64 bits of the result.
static long Loyc.Math.Math128.Divide ( long  aH,
ulong  aL,
long  b,
out long  remainder,
bool  roundDown 
)
inlinestatic

Divides an signed 128-bit number by a signed 64-bit number to produce a 64-bit result.

Returns
Returns the division result (known as the "quotient"). If the result is too large to represent, long.MinValue or long.MaxValue is returned instead.

Referenced by Loyc.Math.MathEx.MulDiv().

static ulong Loyc.Math.Math128.Divide ( long  aH,
ulong  aL,
long  b,
out long  resultHi,
out long  remainder,
bool  roundDown 
)
inlinestatic

Divides an signed 128-bit number by a signed 64-bit number to produce a 128-bit result.

Parameters
roundDownIf true, the result is rounded down, instead of being rounded toward zero, which changes the remainder and quotient if a is negative but b is positive.

When dividing a negative number by a positive number, it is conventionally rounded toward zero. Consequently, the remainder is zero or negative to satisfy the standard integer division equation a = b*q + r, where q is the quotient (result) and r is the remainder.

This is not always what you want. So, if roundDown is true, the result is rounded down instead of toward zero. This ensures that if 'a' is negative and 'b' is positive, the remainder is positive too, a fact which is useful for modulus arithmetic. The table below illustrates the difference:

inputs   | standard  | roundDown
         |  output   |  output  
 a   b   |   q   r   |   q   r
--- ---  |  --- ---  |  --- ---
 7   3   |   2   1   |   2   1
-7   3   |  -2  -1   |  -3   2
 7  -3   |  -2   1   |  -3  -2
-7  -3   |   2  -1   |   2  -1
static ulong Loyc.Math.Math128.Divide ( ulong  aH,
ulong  aL,
ulong  b,
out ulong  remainder 
)
inlinestatic

Divides an signed 128-bit number by a signed 64-bit number to produce a 64-bit result.

If the result did not fit in 64 bits, this method returns ulong.MaxValue.

static ulong Loyc.Math.Math128.Divide ( ulong  aH,
ulong  aL,
ulong  b,
out ulong  resultHi,
out ulong  remainder 
)
inlinestatic

Divides an unsigned 128-bit number by an unsigned 64-bit number to produce a 128-bit result.

Parameters
aHHigh 64 bits of the dividend.
aLLow 64 bits of the dividend.
bThe divisor.
resultHiHigh 64 bits of result.
remainderRemainder of the division.
Returns
The low 64 bits of the result (known as the "quotient").
Exceptions
DivideByZeroExceptionb was zero.

References Loyc.Math.MathEx.Log2Floor().

static ulong Loyc.Math.Math128.ShiftLeft ( ulong  aH,
ref ulong  aL,
int  amount 
)
inlinestatic

Shifts a 128-bit value left.

Parameters
aHHigh 64 bits
aLLow 64 bits
amountNumber of bits to shift.
Returns
The new value of aH

The convention is that signed numbers use Int64 for aH and unsigned numbers used UInt64 for aH. The fact that aH is not passed by reference makes it easier to shift a signed number left by casting aH to UInt64. The cast would not be allowed if passing by reference. Of course, right shift, on the other hand, requires two separate methods since it behaves differently for signed and unsigned inputs.

This method does not allow shifting by a negative amount. The reason is that there is only one ShiftLeft, so if the amount is negative, it's not known whether a signed or unsigned ShiftRight is intended.

static ulong Loyc.Math.Math128.ShiftLeftEx ( ref ulong  aH,
ref ulong  aL,
int  amount 
)
inlinestatic

Shifts a 128-bit value left and saves the overflowed bits.

Parameters
aHHigh 64 bits
aLLow 64 bits
amountNumber of bits to shift. Negative amounts are not permitted.
Returns
The bits that were shifted off the left side.

Asserts that amount > 0 (no exception)

static ulong Loyc.Math.Math128.ShiftLeftFast ( ulong  aH,
ref ulong  aL,
int  amount 
)
inlinestatic

Variation of ShiftLeft() for cases when you know 64 > amount >= 0.

static ulong Loyc.Math.Math128.ShiftRight ( ulong  aH,
ref ulong  aL,
int  amount 
)
inlinestatic

Shifts a 128-bit value right.

Parameters
aHHigh 64 bits
aLLow 64 bits
amountNumber of bits to shift.
Returns
The new value of aH

This method, unlike ShiftLeft(), allows shifting by a negative amount, which is translated to a left shift.

TODO: ShiftRightEx

Referenced by Loyc.Math.MathEx.MulShift().

static ulong Loyc.Math.Math128.Subtract ( ulong  aH,
ref ulong  aL,
ulong  amount 
)
inlinestatic

Subtracts a 64-bit number from a 128-bit number.

Parameters
aHHigh 64 bits of 128-bit number
aLLow 64 bits of 128-bit number
amountAmount to subtract
Returns
The high 64 bits of the result.