BigInteger.h

// Copyright (C)2023 Smiling Cat Entertainment, LTD. All Rights Reserved.
 
#pragma once
#define _USE_MATH_DEFINES
 
#include "Inline.h"
#include <corecrt_math_defines.h>
#include "CoreMinimal.h"
#include "UObject/NoExportTypes.h"
#include "MoreMath.h"
#include "BigInteger.generated.h"
 
USTRUCT(BlueprintType)
struct FBigInteger
{
    GENERATED_BODY()
 
private:
    UPROPERTY()
    TArray<uint32> Bits;
    UPROPERTY()
    int32 Sign;
 
public:
    FBigInteger();
 
    explicit FBigInteger(bool value);
 
    FBigInteger(int8 value);
 
    FBigInteger(uint8 value);
 
    FBigInteger(int16 value);
 
    FBigInteger(uint16 value);
 
    FBigInteger(int32 value);
 
    FBigInteger(uint32 value);
 
    FBigInteger(int64 value);
 
    explicit FBigInteger(uint64 value);
 
    FBigInteger(float value);
 
    FBigInteger(double value);
 
    explicit FBigInteger(const TArray<uint8>& value);
 
    FBigInteger(const TArray<uint8>& magnitude, bool isNegative);
 
    explicit FBigInteger(const TArray<uint32>& value);
 
    FBigInteger(const TArray<uint32>& magnitude, bool isNegative);
 
    static const FBigInteger Zero;
 
    static const FBigInteger One;
    
    static const FBigInteger MinusOne;
 
    static FBigInteger Add(const FBigInteger& lhs, const FBigInteger& rhs);
 
    static FBigInteger Subtract(const FBigInteger& lhs, const FBigInteger& rhs);
 
    static FBigInteger Multiply(const FBigInteger& lhs, const FBigInteger& rhs);
 
    static FBigInteger Divide(const FBigInteger& lhs, uint32 rhs);
 
    static FBigInteger Divide(const FBigInteger& lhs, uint64 rhs);
 
    static FBigInteger Divide(const FBigInteger& lhs, const FBigInteger& rhs);
    
    static uint32 Remainder(const FBigInteger& lhs, const uint32 rhs);
 
    static uint64 Remainder(const FBigInteger& lhs, const uint64 rhs);
 
    static FBigInteger Remainder(const FBigInteger& lhs, const FBigInteger& rhs);
    
    static uint32 DivRem(const FBigInteger& lhs, uint32 rhs, FBigInteger& quotient);
 
    static uint64 DivRem(const FBigInteger& lhs, uint64 rhs, FBigInteger& quotient);
 
    static FBigInteger DivRem(const FBigInteger& lhs, const FBigInteger& rhs, FBigInteger& quotient);
 
    static FBigInteger And(const FBigInteger& lhs, const FBigInteger& rhs);
 
    static FBigInteger Or(const FBigInteger& lhs, const FBigInteger& rhs);
 
    static FBigInteger Xor(const FBigInteger& lhs, const FBigInteger& rhs);
 
    static FBigInteger Invert(const FBigInteger& value);
 
    static FBigInteger Increment(const FBigInteger& value);
 
    static FBigInteger Decrement(const FBigInteger& value);
 
    static FBigInteger ClearBit(const FBigInteger& value, int32 bitIndex);
 
    static FBigInteger SetBit(const FBigInteger& value, int32 bitIndex);
 
    static FBigInteger ToggleBit(const FBigInteger& value, int32 bitIndex);
 
    static FBigInteger SetWord(const FBigInteger& value, int32 index, uint32 word);
 
    static FBigInteger ShiftLeft(const FBigInteger& value, int32 shift);
 
    static FBigInteger ShiftRight(const FBigInteger& value, int32 shift);
 
    static FBigInteger Negate(const FBigInteger& value);
 
    static FBigInteger SetSign(const FBigInteger& value, bool isNegative);
 
    static FBigInteger Abs(const FBigInteger& value);
 
    static FBigInteger Nabs(const FBigInteger& value);
 
    static FBigInteger CopySign(const FBigInteger& lhs, const FBigInteger& rhs);
 
    static const FBigInteger& Max(const FBigInteger& lhs, const FBigInteger& rhs);
 
    static const FBigInteger& MaxMagnitude(const FBigInteger& lhs, const FBigInteger& rhs);
 
    static const FBigInteger& Min(const FBigInteger& lhs, const FBigInteger& rhs);
 
    static const FBigInteger& MinMagnitude(const FBigInteger& lhs, const FBigInteger& rhs);
 
    static const FBigInteger& Select(const FBigInteger& whenTrue, const FBigInteger& whenFalse, bool condition);
 
    static const FBigInteger& Clamp(const FBigInteger& value, const FBigInteger& min, const FBigInteger& max);
 
    static int32 CountPrecisionBits(const FBigInteger& value);
 
    static int32 Nlz(const FBigInteger& value);
 
    static int32 Ntz(const FBigInteger& value);
 
    static int32 Pop(const FBigInteger& value);
 
    static int32 Compare(int32 lhs, const FBigInteger& rhs);
    
    static int32 Compare(uint32 lhs, const FBigInteger& rhs);
 
    static int32 Compare(int64 lhs, const FBigInteger& rhs);
 
    static int32 Compare(uint64 lhs, const FBigInteger& rhs);
 
    static int32 Compare(const FBigInteger& lhs, int32 rhs);
 
    static int32 Compare(const FBigInteger& lhs, uint32 rhs);
 
    static int32 Compare(const FBigInteger& lhs, int64 rhs);
 
    static int32 Compare(const FBigInteger& lhs, uint64 rhs);
 
    static int32 Compare(const FBigInteger& lhs, const FBigInteger& rhs);
 
    static int32 CompareMagnitude(const FBigInteger& lhs, const FBigInteger& rhs);
 
    static uint32 FloorLog10(const FBigInteger& value);
 
    static uint32 FloorLog2(const FBigInteger& value);
 
    static float Log10(const FBigInteger& value);
 
    static double Log10D(const FBigInteger& value);
 
    static float Log2(const FBigInteger& value);
 
    static double Log2D(const FBigInteger& value);
 
    static float Loge(const FBigInteger& value);
 
    static double LogeD(const FBigInteger& value);
 
    static float LogX(float base, const FBigInteger& value);
 
    static double LogX(double base, const FBigInteger& value);
 
    static FBigInteger Pow(int32 base, int32 exponent);
 
    static FBigInteger Pow(const FBigInteger& base, int32 exponent);
 
    static FBigInteger Pow(const FBigInteger& base, float exponent);
 
    static FBigInteger Sqrt(const FBigInteger& value);
 
    static uint32 Gcd(const FBigInteger& lhs, uint32 rhs);
    
    static uint64 Gcd(const FBigInteger& lhs, uint64 rhs);
 
    static FBigInteger Gcd(const FBigInteger& lhs, const FBigInteger& rhs);
 
    FBigInteger Add(const FBigInteger& rhs) const;
 
    FBigInteger Subtract(const FBigInteger& rhs) const;
 
    FBigInteger Multiply(const FBigInteger& rhs) const;
 
    FBigInteger Divide(uint32 rhs) const;
 
    FBigInteger Divide(uint64 rhs) const;
 
    FBigInteger Divide(const FBigInteger& rhs) const;
 
    uint32 Remainder(uint32 rhs) const;
 
    uint64 Remainder(uint64 rhs) const;
 
    FBigInteger Remainder(const FBigInteger& rhs) const;
 
    uint32 DivRem(const uint32 divisor, FBigInteger& quotient) const;
 
    uint64 DivRem(const uint64 divisor, FBigInteger& quotient) const;
 
    FBigInteger DivRem(const FBigInteger& divisor, FBigInteger& quotient) const;
 
    FBigInteger And(const FBigInteger& rhs) const;
 
    FBigInteger Or(const FBigInteger& rhs) const;
 
    FBigInteger Xor(const FBigInteger& rhs) const;
 
    FBigInteger Invert() const;
 
    FBigInteger Increment() const;
 
    FBigInteger Decrement() const;
 
    FBigInteger ClearBit(int32 bitIndex) const;
 
    FBigInteger SetBit(int32 bitIndex) const;
 
    FBigInteger ToggleBit(int32 bitIndex) const;
 
    FBigInteger SetWord(int32 index, uint32 word) const;
 
    FBigInteger ShiftLeft(int32 shift) const;
 
    FBigInteger ShiftRight(int32 shift) const;
 
    FBigInteger Negate() const;
 
    FBigInteger SetSign(bool isNegative) const;
 
    FBigInteger Abs() const;
 
    FBigInteger Nabs() const;
 
    FBigInteger CopySign(const FBigInteger& rhs) const;
 
    const FBigInteger& Clamp(const FBigInteger& min, const FBigInteger& max) const;
 
    int32 CountPrecisionBits() const;
 
    int32 Nlz() const;
 
    int32 Ntz() const;
 
    int32 Pop() const;
 
    void GetBaseTwoComponents(uint32& mantissa, int32& exponent) const;
 
    void GetBaseTwoComponents(uint64& mantissa, int32& exponent) const;
 
    int32 GetSign() const;
 
    int32 GetSignedBitLength() const;
 
    int32 GetSignedByteLength() const;
 
    int32 GetSignedWordLength() const;
 
    int32 GetLength() const;
 
    int32 GetBit(int32 position) const;
 
    uint32 GetUpperWord() const;
 
    uint32 GetWord(int32 index) const;
 
    uint32 FloorLog10() const;
 
    uint32 FloorLog2() const;
 
    float Log10() const;
    
    double Log10D() const;
 
    float Log2() const;
 
    double Log2D() const;
 
    float Loge() const;
 
    double LogeD() const;
 
    float LogX(float base) const;
 
    double LogX(double base) const;
 
    FBigInteger Pow(int32 exponent) const;
 
    FBigInteger Pow(float exponent) const;
 
    FBigInteger Sqrt() const;
 
    bool CanFitIntoInt() const;
 
    bool CanFitIntoUInt() const;
 
    bool CanFitIntoInt64() const;
 
    bool CanFitIntoUInt64() const;
 
    bool CanFitIntoFloat() const;
 
    bool CanFitIntoFloatLossy() const;
 
    bool CanFitIntoDouble() const;
 
    bool CanFitIntoDoubleLossy() const;
 
    bool IsEven() const;
 
    bool IsMinusOne() const;
 
    bool IsNegative() const;
 
    bool IsOdd() const;
 
    bool IsOne() const;
 
    bool IsPositive() const;
 
    bool IsPowerOfTwo() const;
 
    bool IsZero() const;
 
    int32 CompareTo(int32 rhs) const;
 
    int32 CompareTo(uint32 rhs) const;
 
    int32 CompareTo(int64 rhs) const;
 
    int32 CompareTo(uint64 rhs) const;
 
    int32 CompareTo(const FBigInteger& rhs) const;
 
    int32 CompareMagnitudeTo(const FBigInteger& rhs) const;
 
    FString ToString() const;
 
    FString ToHexString() const;
 
    friend FBigInteger operator+(FBigInteger lhs, const FBigInteger& rhs);
 
    friend FBigInteger operator-(FBigInteger lhs, const FBigInteger& rhs);
 
    friend FBigInteger operator*(FBigInteger lhs, const FBigInteger& rhs);
 
    friend FBigInteger operator/(FBigInteger lhs, const uint32 rhs);
 
    friend FBigInteger operator/(FBigInteger lhs, const uint64 rhs);
 
    friend FBigInteger operator/(FBigInteger lhs, const FBigInteger& rhs);
 
    friend uint32 operator%(FBigInteger lhs, const uint32 rhs);
 
    friend uint64 operator%(FBigInteger lhs, const uint64 rhs);
 
    friend FBigInteger operator%(FBigInteger lhs, const FBigInteger& rhs);
 
    friend FBigInteger operator&(FBigInteger lhs, const FBigInteger& rhs);
 
    friend FBigInteger operator|(FBigInteger lhs, const FBigInteger& rhs);
 
    friend FBigInteger operator^(FBigInteger lhs, const FBigInteger& rhs);
 
    friend FBigInteger operator<<(FBigInteger lhs, int32 shift);
 
    friend FBigInteger operator>>(FBigInteger lhs, int32 shift);
 
    FBigInteger operator+() const;
 
    FBigInteger operator-() const;
 
    bool operator!() const;
 
    FBigInteger operator~() const;
 
    FBigInteger& operator++();
 
    FBigInteger operator++(int);
 
    FBigInteger& operator--();
 
    FBigInteger operator--(int);
 
    FBigInteger& operator+=(const FBigInteger& rhs);
 
    FBigInteger& operator-=(const FBigInteger& rhs);
 
    FBigInteger& operator*=(const FBigInteger& rhs);
 
    FBigInteger& operator/=(const uint32 rhs);
 
    FBigInteger& operator/=(const uint64 rhs);
 
    FBigInteger& operator/=(const FBigInteger& rhs);
 
    FBigInteger& operator%=(const FBigInteger& rhs);
 
    FBigInteger& operator&=(const FBigInteger& rhs);
 
    FBigInteger& operator|=(const FBigInteger& rhs);
 
    FBigInteger& operator^=(const FBigInteger& rhs);
 
    FBigInteger& operator>>=(int32 shift);
 
    FBigInteger& operator<<=(int32 shift);
 
    void operator=(bool from);
 
    void operator=(int8 from);
 
    void operator=(uint8 from);
 
    void operator=(int16 from);
 
    void operator=(uint16 from);
 
    void operator=(int32 from);
 
    void operator=(uint32 from);
 
    void operator=(int64 from);
 
    void operator=(uint64 from);
 
    void operator=(float from);
 
    void operator=(double from);
 
    explicit operator bool() const;
 
    explicit operator int8() const;
 
    explicit operator uint8() const;
 
    explicit operator int16() const;
 
    explicit operator uint16() const;
 
    explicit operator int32() const;
 
    explicit operator uint32() const;
 
    explicit operator int64() const;
 
    explicit operator uint64() const;
 
    explicit operator float() const;
 
    explicit operator double() const;
 
    explicit operator TArray<uint8>() const;
 
    explicit operator TArray<uint32>() const;
 
#pragma region OperatorEq
 
    friend bool operator==(int32 lhs, const FBigInteger& rhs);
 
    friend bool operator==(uint32 lhs, const FBigInteger& rhs);
 
    friend bool operator==(int64 lhs, const FBigInteger& rhs);
 
    friend bool operator==(uint64 lhs, const FBigInteger& rhs);
 
    friend bool operator==(const FBigInteger& lhs, int32 rhs);
 
    friend bool operator==(const FBigInteger& lhs, uint32 rhs);
 
    friend bool operator==(const FBigInteger& lhs, int64 rhs);
 
    friend bool operator==(const FBigInteger& lhs, uint64 rhs);
 
    friend bool operator==(const FBigInteger& lhs, const FBigInteger& rhs);
 
#pragma endregion
#pragma region OperatorNeq
 
    friend bool operator!=(int32 lhs, const FBigInteger& rhs);
 
    friend bool operator!=(uint32 lhs, const FBigInteger& rhs);
 
    friend bool operator!=(int64 lhs, const FBigInteger& rhs);
 
    friend bool operator!=(uint64 lhs, const FBigInteger& rhs);
 
    friend bool operator!=(const FBigInteger& lhs, int32 rhs);
 
    friend bool operator!=(const FBigInteger& lhs, uint32 rhs);
 
    friend bool operator!=(const FBigInteger& lhs, int64 rhs);
 
    friend bool operator!=(const FBigInteger& lhs, uint64 rhs);
 
    friend bool operator!=(const FBigInteger& lhs, const FBigInteger& rhs);
 
#pragma endregion
#pragma region OperatorLt
 
    friend bool operator<(int32 lhs, const FBigInteger& rhs);
 
    friend bool operator<(uint32 lhs, const FBigInteger& rhs);
 
    friend bool operator<(int64 lhs, const FBigInteger& rhs);
 
    friend bool operator<(uint64 lhs, const FBigInteger& rhs);
 
    friend bool operator<(const FBigInteger& lhs, const int32 rhs);
 
    friend bool operator<(const FBigInteger& lhs, const uint32 rhs);
 
    friend bool operator<(const FBigInteger& lhs, const int64 rhs);
 
    friend bool operator<(const FBigInteger& lhs, const uint64 rhs);
 
    friend bool operator<(const FBigInteger& lhs, const FBigInteger& rhs);
 
#pragma endregion
#pragma region OperatorGt
 
    friend bool operator>(int32 lhs, const FBigInteger& rhs);
 
    friend bool operator>(uint32 lhs, const FBigInteger& rhs);
 
    friend bool operator>(int64 lhs, const FBigInteger& rhs);
 
    friend bool operator>(uint64 lhs, const FBigInteger& rhs);
 
    friend bool operator>(const FBigInteger& lhs, int32 rhs);
 
    friend bool operator>(const FBigInteger& lhs, uint32 rhs);
 
    friend bool operator>(const FBigInteger& lhs, int64 rhs);
 
    friend bool operator>(const FBigInteger& lhs, uint64 rhs);
 
    friend bool operator>(const FBigInteger& lhs, const FBigInteger& rhs);
 
#pragma endregion
#pragma region OperatorLteq
 
    friend bool operator<=(int32 lhs, const FBigInteger& rhs);
 
    friend bool operator<=(uint32 lhs, const FBigInteger& rhs);
 
    friend bool operator<=(int64 lhs, const FBigInteger& rhs);
 
    friend bool operator<=(uint64 lhs, const FBigInteger& rhs);
 
    friend bool operator<=(const FBigInteger& lhs, int32 rhs);
 
    friend bool operator<=(const FBigInteger& lhs, uint32 rhs);
 
    friend bool operator<=(const FBigInteger& lhs, int64 rhs);
 
    friend bool operator<=(const FBigInteger& lhs, uint64 rhs);
 
    friend bool operator<=(const FBigInteger& lhs, const FBigInteger& rhs);
 
#pragma endregion
#pragma region OperatorGteq
 
    friend bool operator>=(int32 lhs, const FBigInteger& rhs);
 
    friend bool operator>=(uint32 lhs, const FBigInteger& rhs);
 
    friend bool operator>=(int64 lhs, const FBigInteger& rhs);
 
    friend bool operator>=(uint64 lhs, const FBigInteger& rhs);
 
    friend bool operator>=(const FBigInteger& lhs, int32 rhs);
 
    friend bool operator>=(const FBigInteger& lhs, uint32 rhs);
 
    friend bool operator>=(const FBigInteger& lhs, int64 rhs);
 
    friend bool operator>=(const FBigInteger& lhs, uint64 rhs);
 
    friend bool operator>=(const FBigInteger& lhs, const FBigInteger& rhs);
 
#pragma endregion
 
    void SetValueIn(bool value);
 
    void SetValueIn(int8 value);
 
    void SetValueIn(uint8 value);
 
    void SetValueIn(int16 value);
 
    void SetValueIn(uint16 value);
 
    void SetValueIn(int32 value);
 
    void SetValueIn(uint32 value);
 
    void SetValueIn(int64 value);
 
    void SetValueIn(uint64 value);
 
    void SetValueIn(float value);
    
    void SetValueIn(double value);
 
    void SetValueIn(const FBigInteger& value);
 
    void SetValueIn(const TArray<uint8>& value);
 
    void SetValueIn(const TArray<uint8>& magnitude, bool isNegative);
 
    void SetValueIn(const TArray<uint32>& value);
 
    void SetValueIn(const TArray<uint32>& magnitude, bool isNegative);
 
    void AddIn(const FBigInteger& rhs);
 
    void SubtractIn(const FBigInteger& rhs);
 
    FBigInteger DivRemIn(const FBigInteger& divisor);
 
    void AndIn(const FBigInteger& rhs);
    
    void OrIn(const FBigInteger& rhs);
 
    void XorIn(const FBigInteger& rhs);
 
    void InvertIn();
 
    void IncrementIn();
 
    void DecrementIn();
 
    void ClearBitIn(int32 bitIndex);
 
    void SetBitIn(int32 bitIndex);
 
    void ToggleBitIn(int32 bitIndex);
 
    void SetWordIn(int32 index, uint32 word);
    
    void ShiftLeftIn(int32 shift);
 
    void ShiftRightIn(int32 shift);
 
    void NegateIn();
 
    void SetSignIn(bool isNegative);
 
    void AbsIn();
 
    void NabsIn();
 
    void CopySignIn(const FBigInteger& rhs);
 
    void MaxIn(const FBigInteger& rhs);
 
    void MinIn(const FBigInteger& rhs);
 
    void MaxMagnitudeIn(const FBigInteger& rhs);
 
    void MinMagnitudeIn(const FBigInteger& rhs);
 
    void SelectIn(const FBigInteger& rhs, bool condition);
 
    void ClampIn(const FBigInteger& min, const FBigInteger& max);
 
private:
    void SetValueIn(const TArray<uint32>& magnitude, int32 sign);
 
    void AddCore(const FBigInteger& V, int32 length);
    static uint32 AddCarry(uint32* u1, uint32 u2, uint32 uCarry);
    static uint32 AddCarry(uint32* u1, uint32 uCarry);
 
    void SubtractCore(const FBigInteger& V, int32 length);
    static uint32 SubBorrow(uint32* u1, uint32 u2, uint32 uBorrow);
    static uint32 SubBorrow(uint32* u1, uint32 uBorrow);
 
    static bool DivideGuessTooBig(uint64 q, uint64 valHi, uint32 valLo, uint32 divHi, uint32 divLo);
    static uint32 AddDivisor(uint32* left, int32 leftLength, const uint32* right, int32 rightLength);
    static uint32 SubtractDivisor(uint32* left, int leftLength, const uint32* right, int rightLength, uint64 q);
    static FBigInteger GcdLehmer(const FBigInteger& lhs, const FBigInteger& rhs);
    static void GcdExtractDigits(const FBigInteger& lhs, const FBigInteger& rhs, uint64& x, uint64& y);
    static bool GcdLehmerIteration(uint64& x, uint64& y, uint32& a, uint32& b, uint32& c, uint32& d, int32& iteration);
    static int32 GcdGuessLehmer(const FBigInteger& lhs, const FBigInteger& rhs, uint32& a, uint32& b, uint32& c, uint32& d);
    static void GcdLehmerCore(FBigInteger& lhs, FBigInteger& rhs, uint32& a, uint32& b, uint32& c, uint32& d, int32 iteration);
 
    void DecrementCore();
    void IncrementCore();
 
    void SetSignInCore(int32 value);
 
    uint32 GetBitsOrZero(int32 index) const;
    void EnsureLength(int32 length);
    void Trim();
 
    static const int32 bitsPerUnit = 32;
};
 
// If conditional inlining is ON, include inlinable functions here.
#if DBN_INLINE_ENABLED
#include "BigInteger.inl"
#endif