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:

/Core/Loyc.Essentials/Math/Math128.cs

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

aH	High 64 bits of 128-bit number
aL	Low 64 bits of 128-bit number
amount	Amount 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.

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

roundDown If 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

aH	High 64 bits of the dividend.
aL	Low 64 bits of the dividend.
b	The divisor.
resultHi	High 64 bits of result.
remainder	Remainder of the division.

Returns: The low 64 bits of the result (known as the "quotient").

Exceptions

DivideByZeroException b was zero.

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

inlinestatic

Shifts a 128-bit value left.

Parameters

aH	High 64 bits
aL	Low 64 bits
amount	Number 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

aH	High 64 bits
aL	Low 64 bits
amount	Number 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

aH	High 64 bits
aL	Low 64 bits
amount	Number 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

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

aH	High 64 bits of 128-bit number
aL	Low 64 bits of 128-bit number
amount	Amount to subtract

Returns: The high 64 bits of the result.

Documentation moved to ecsharp.net

Remarks

Static Public Member Functions

Member Function Documentation