Working With BigIntegers

Operations Supported

A full reference of operations supported by FBigInteger is located at Operations

How FBigInteger Handles Allocations

Next, let's address the elephant in the room: Allocations. Allocations are the bane of every game engineer's existence, but they are an unfortunate fact of that existance.

FBigInteger is a variable-length type. As such it allocates memory to hold its numerical values. This has a couple of important implications:

• Allocating too many temporary FBigIntegers will incur the wrath of the garbage collector.
• FBigIntegers values have heap locality.

Fortunately, as the buffer contained by FBigInteger is housed in an Unreal TArray<> and managed as a UPROPERTY(), there is little else for us to worry about in terms of memory management. The default destructor semantics properly deallocate the underlying arrays for us.

To avoid allocations from copying temporary values, mutating operations (methods ending in "In" or compound assignment operators) can be used on FBigIntegers, circumventing the immutable value semantics that FBigInteger operates under by default.

Exponents and roots can be particularly allocation-heavy, as is parsing and formatting.

String formatters will make a fast best guess effort to pre-allocate space in the destination string, rather than allocating space ad-hoc as characters are appended.

Overloads

Another way to avoid temporary FBigInteger allocations and gain speed is to use the narrower overloads of operations, when provided. In addition to avoiding an allocation of a temporary FBigInteger to hold the value upcast from a native type, these overloads are generally able to take some shortcuts by being able to assume that one or more of the values being operated on will fit in a less expensive native type.

For example, if you are dividing an FBigInteger by a divisor, and you know that divisor will never overflow an UnsignedInteger, then you can gain quite a bit of efficiency by using the overload that directly takes an UnsignedInteger type as the divisor operand.

Keeping it Inside the Lines

On modern systems with 64 byte cache lines, approximately every 154 or so powers of 10 (2^(2^9) or 512 bits) overflows a number to an additional cache line, eventually resulting in cache thrash when numbers are large enough to oversaturate all available cache lines. This is an unavoidable cost of modern multiple-precision integer math.

This means that overall application performance can suddenly drop off when numbers get large enough - the exact magnitude of number causing this to happen will depend on many factors including the rest of your application's workload.

Pick your largest expected value, test using numbers of that magnitude, and refine your application's performance accordingly.

Warning

Make sure you test with your largest expected values. Do not just assume you can keep scaling up FBigIntegers with performance impunity.

Operation Flavors

Operations on FBigIntegers can come in several flavors - Static, Instance, Instance-modifying, Operator, Operator-modifying, and Blueprintable.

• Static - Can be called independently of any instance of FBigInteger. These are static methods, and leave the instances that they are called on unchanged.
• Instance - Can be called on an instance of FBigInteger. These are const instance methods, and leave the instance that they are called on unchanged.
• Mutating - Can be called on an instance of FBigInteger. These are non-const instance methods, and modify the instance's state.
• Operator - A const operator overload. Leaves the instances that they are called on unchanged.
• Operator-Modifying - A non-const operator overload. Modifys the state of the instance.
• Blueprintable - This version of an operation has metadata and peculiarities specific to Blueprint-callable methods.
• Constructor - Builds a new instance.

For ease of API use, DBN strives to expose all applicable operation flavors that make sense. In many cases, the implementations of different flavors are simply inline forwards or curries to a canonical implementation.

Opcode Notation

Throughout this documentation you may see references to an opcode notation for operations, like this:

Flavor:Static BI ← add BI BI

This is my way of imposing order on the chaos, creating a manageable assembly-like shorthand for operations and their parameters. It has helped me to organize this library and ensure consistency and completeness. You don't need to understand or use this opcode notation for DBN to be useful to you.

If you want to interpret and understand this notation, it should be somewhat intuitive on several fronts.

If you have any grounding in assembly, you will note that these bear a resemblance to assembler opcodes and operands. That is a correct analogy. Even though an operation may take several forms (have several flavors), it still basically has the same inputs and outputs. Some of the inputs and outputs might redirect from different sources (such as a reference to a left-hand side parameter passed to a static method vs. an implied this value on an instance method). The opcode format seeks to help match up the different flavors of the same operation.

The basic format of an opcode is:

RT ← opcode O1 O2 ... ON

Where:

• RT is the return type of the operation
• opcode is the mnemonic (1-6 characters) describing the nature of the operation
• O1 thru ON are the operand types.

The base operand types are one or two characters and are also color-coded in the HTML version of the documentation. These colors follow the colors used for the types in blueprints where possible. DBN has a limited vocabulary of types that it works with. The types can be modified with one or more modifiers.

Generally const references are inferred. For the first parameter, whether the reference is const depends on the flavor of the operation, with the mutating flavors being non-const.

In/out and output parameters are specifically denoted as references in the opcode using the familiar ampersand (&) modifier.

Some operands are arrays, specifically TArray<>s. These are denoted using the subscript ([]) modifier.

In rare cases, some opcodes may work with a TCHAR pointer or a reference to a TCHAR pointer. Pointers are denoted with the pointer (*) modifier.

The opcode notation does not specify separate types for enums, and instead just uses the base type of the enum (usually U1).

Opcodes follow C++ rules for overloading of return types - two opcodes that differ only by return type will have different mnemomics.

Opcode Type	English Type	C++ Type	Notes
0	Void	void	Special value denoting void type or zero parameters
B	Boolean	bool
I1	Signed Byte	int8
U1	Byte	uint8
I2	Integer16	int16
U2	Unsigned Integer16	uint16
I4	Integer	int32	32 bit
U4	Unsigned Integer	uint32	32 bit
I8	Integer64	int64	64 bit
U8	Unsigned Integer64	uint64	64 bit
F4	Float	float	32 bit
F8	Double	double	64 bit
CH	Character	TCHAR
S	String	FString	UE Type
BI	Big Integer	FBigInteger	The star of the show
BF	Big Integer Formatter	UBigIntegerFormatter	Base class for formatter types
DF	Decimal Invariant Formatter	UDecimalInvariantFormatter
FF	Decimal Full Formatter	UDecimalFullFormatter
SF	Decimal Scaling Formatter	UDecimalScalingFormatter
HF	Hexadecimal Invariant Formatter	UHexadecimalInvariantFormatter
BG	Group Labeler	UGroupLabeler	Base class for group labeler types
NG	Named Group Labeler	UNamedGroupLabeler
SG	Scientific Group Labeler	UScientificGroupLabeler
MG	SI Units Group Labeler	USIUnitsGroupLabeler
CG	Custom Group Labeler	UCustomGroupLabeler
KY	Key	FKey	UE Type
CU	Culture	FCulture	UE Type
RU	Decimal Number Formatting Rules	FDecimalNumberFormattingRules	UE Type
OP	Decimal Number Formatting Options	FDecimalNumberFormattingOptions	UE Type
I4&	Integer Ref	int32&
U4&	UnsignedInteger Ref	uint32&
I8&	Integer64 Ref	int64&
U8&	UnsignedInteger64 Ref	uint64&
CH&	Character Ref	TCHAR&
S&	String Ref	FString&
BI&	BigInteger Ref	FBigInteger&
U1[]	Byte Array	TArray<uint8>
U4[]	UnsignedInteger Array	TArray<uint32>
BI[]	BigInteger Array	TArray<FBigInteger>
CH*	Character Buffer	TCHAR*
CH*&	Character Buffer Ref	TCHAR*&