
///////////////////////////////////////////////////////////////////////////////
//                                                                           //
//                               Big number                                  //
//                                                                           //
///////////////////////////////////////////////////////////////////////////////
// Big number consist of a decimal part in lower bytes of buffer, and integer part
// in higher bytes of buffer. Buffer size remains unchanged, but parts can be
// shorted or expanded basely on its content - integer part can expand on start
// of chain with 0 or 0xffff (based on IsNeg flag), decimal part can expand
// on end of chain with 0.
//
// Integer part cannot have zero size, it must be at least 1 entry long.
//
// Some functions use global temporary numbers - be aware of multithread.

#define BIGDEFINT	512		// default size of integer part (in bytes, 1233 digits)
#define BIGDEFDEC	512		// default size of decimal part (in bytes, 1233 digits)
#define BIGDEFPREC	1200	// default decimal precision (in digits)

#ifdef _MT
#define BIGTEMPNUM	20		// number of temporary numbers
#else // _MT
#define BIGTEMPNUM	5		// number of temporary numbers
#endif // _MT

// compare result
enum {
	COMP_LE = -1,		// num1 < num2
	COMP_EQ = 0,		// num1 == num2
	COMP_GR = 1,		// num1 > num2
};

// big number entry
#ifdef WIN64
#define BIGBITS 64	// number of bits per entry
typedef s64 bint;	// signed
typedef u64 buint;	// unsigned
typedef u32 buintH; // unsigned half sized
#else // WIN64
#define BIGBITS 32	// number of bits per entry
typedef s32 bint;	// signed
typedef u32 buint;	// unsigned
typedef u16 buintH; // unsigned half sized
#endif // WIN64

#define BIGSIZE sizeof(buint) // size of one entry (in bytes)
#define BIGMAX (~(buint)0) // maximal number (all 1's)
#define BIGLASTBIT ((buint)1 << (BIGBITS-1)) // mask of last bit

#define BIGSIZE64 sizeof(u64) // commont size of entry (for rounding buffer size)

// 63 bits = 18.96488973 digits (= log of max. number)
#define DIGPERBIT 0.3010299957	// number of digits per bit
#define BITPERDIG 3.321928095	// number of bits per digit

#define DIGPERBYTE 2.408239965	// number of digits per byte
#define BYTEPERDIG 0.4152410119	// number of bytes per digit

#define DIGPERWRD (BIGBITS*DIGPERBIT) // number of digits per entry
#define WRDPERDIG (BITPERDIG/BIGBITS) // number of entries per digit

#define BIGBITS14 (BIGBITS/4) // 1/4 sized bits
#define BIGMASK14 (((buint)1 << BIGBITS14)-1) // 1/4 sized mask
#define BIGBITS12 (BIGBITS/2) // 1/2 sized bits
#define BIGMASK12 (((buint)1 << BIGBITS12)-1) // 1/2 sized mask
#define BIGBITS34 (BIGBITS*3/4) // 3/4 sized bits
#define BIGMASK34 (((buint)1 << BIGBITS34)-1) // 3/4 sized mask

// macro

// prepare length with 1 number (dec1, dec2, dec, len1, len2, len)
//   dec1 = length of decimal part of num1, limited to DecMax
//   dec2 = length of decimal part of num2, limited to DecMax
//   dec = length of common decimal part (shorter dec1 or dec2)
//   len1 = length of integer part of num1, limited to IntMax
//   len2 = length of integer part of num2, limited to IntMax
//   len = length of common integer part (shorter len1 or len2)
#define BIGPREP1()							\
	bint dec1 = m_DecNum;					\
	bint dec2 = num.m_DecNum;				\
	if (dec2 > m_DecMax) dec2 = m_DecMax;	\
	bint dec = dec1;						\
	if (dec > dec2) dec = dec2;				\
	m_DecNum = dec;							\
	bint len1 = m_IntNum;					\
	bint len2 = num.m_IntNum;				\
	if (len2 > m_IntMax) len2 = m_IntMax;	\
	bint len = len1;						\
	if (len > len2) len = len2;				\
	m_IntNum = len;

// prepare length with 2 numbers (dec1, dec2, dec, len1, len2, len)
#define BIGPREP2()							\
	bint dec1 = num1.m_DecNum;				\
	if (dec1 > m_DecMax) dec1 = m_DecMax;	\
	bint dec2 = num2.m_DecNum;				\
	if (dec2 > m_DecMax) dec2 = m_DecMax;	\
	bint dec = dec1;						\
	if (dec > dec2) dec = dec2;				\
	m_DecNum = dec;							\
	bint len1 = num1.m_IntNum;				\
	if (len1 > m_IntMax) len1 = m_IntMax;	\
	bint len2 = num2.m_IntNum;				\
	if (len2 > m_IntMax) len2 = m_IntMax;	\
	bint len = len1;						\
	if (len > len2) len = len2;				\
	m_IntNum = len;

// required size in bytes to ensure required number of digits
inline bint DigToByte(bint dig)
{
	return (((bint)(dig*BITPERDIG+0.99999999)+7)/8 + BIGSIZE-1)/BIGSIZE*BIGSIZE;
}

// === low level math

// multiply 2 entries, rH:rL = a * bH:bL
void MulWW(buint* rL, buint* rH, buint a, buintH bL, buintH bH);

// multiply 2 entries, rH:rL = a * bL (bH = 0)
void MulWL(buint* rL, buint* rH, buint a, buintH bL);

// square entry, rH:rL = a * a
void SqrWW(buint* rL, buint* rH, buint a);

// add 2 dbl-entries, r = a + b
void AddWW(buint* rL, buint* rH, buint aL, buint aH, buint bL, buint bH);

// sub 2 dbl-entries, r = a - b
void SubWW(buint* rL, buint* rH, buint aL, buint aH, buint bL, buint bH);

// divide 3-entry by 2-entry, r = a / b
void DivWW(buint* rX, buint* rH, buint* rL, buint aX, buint aH, buint aL, buint bX, buint bH, buint bL);

// === Long number class

class bignum
{
protected:

	// max. length of integer part (in number of entries, minimal 1 entry)
	bint	m_IntMax;

	// max. length of decimal part (in number of entries)
	bint	m_DecMax;

	// current length of integer part (in number of entries)
	bint	m_IntNum;

	// current length of decimal part (in number of entries)
	bint	m_DecNum;

	// number is negative
	bool	m_IsNeg;

	// data
	buint*	m_Data;

	// expand parts (on start of operation)
	void ExpInt(bint intnum);
	void ExpDec(bint decnum);

	// reduce parts (on end of operation)
	void RedInt();
	void RedDec();
	inline void Reduce() { this->RedInt(); this->RedDec(); }

	// cut integer high bits to valid result
	//void CutInt(bint bits);

	// highest entry expanding integer part
	inline buint High() const { return m_IsNeg ? BIGMAX : 0; }

// --- data string operations

	// fill data string
	static void FillStr(buint* dst, buint val, bint len);

	// copy data string in UP direction (must be dst < src if overlapped)
	static void CopyStr(buint* dst, const buint* src, bint len);

	// copy data string in DOWN direction (must be dst > src if overlapped)
	static void CopyDownStr(buint* dst, const buint* src, bint len);

	// scan equal data string in UP direction (returns length of equal data)
	static bint ScanEquStr(const buint* dst, buint val, bint len);

	// scan not equal data string in UP direction (returns length of not equal data)
	static bint ScanNEquStr(const buint* dst, buint val, bint len);

	// shift data string left to higher bits (shift=0..63, inputs and outputs carry bits)
	static buint LShiftStr(buint carry, int shift, buint* dst, buint* src, bint len);

	// shift data string right to lower bits (shift=0..63, inputs and outputs carry bits)
	static buint RShiftStr(buint carry, int shift, buint* dst, buint* src, bint len);

	// compare equal data string (returns length of equal data)
	static bint CompEquStr(const buint* num1, const buint* num2, bint len);

	// compare data string (returns COMP_LE,...)
	static int CompStr(const buint* num1, const buint* num2, bint len);

	// bit inverse data string
	static void NotStr(buint* dst, bint len);
	static void NotStr(buint* dst, const buint* src, bint len);

	// bit AND data string
	static void AndStr(buint* dst, const buint* src, bint len);
	static void AndStr(buint* dst, const buint* src1, const buint* src2, bint len);

	// bit OR data string
	static void OrStr(buint* dst, const buint* src, bint len);
	static void OrStr(buint* dst, const buint* src1, const buint* src2, bint len);

	// bit XOR data string
	static void XorStr(buint* dst, const buint* src, bint len);
	static void XorStr(buint* dst, const buint* src1, const buint* src2, bint len);

	// negate data string (returns carry flag - set if number is not 0)
	static buint NegStr(buint* dst, bint len);
	static buint NegStr(buint* dst, const buint* src, bint len);

	// increment data string (returns carry flag)
	static buint IncStr(buint* dst, bint len);
	static buint IncStr(buint* dst, const buint* src, bint len);

	// decrement data string (returns carry flag)
	static buint DecStr(buint* dst, bint len);
	static buint DecStr(buint* dst, const buint* src, bint len);

	// add data string (ouputs carry)
	static buint AddStr(buint cy, buint* dst, const buint* src, bint len);
	static buint AddStr(buint cy, buint* dst, const buint* src1, const buint* src2, bint len);

	// sub data string (outputs carry)
	static buint SubStr(buint cy, buint* dst, const buint* src, bint len);
	static buint SubStr(buint cy, buint* dst, const buint* src1, const buint* src2, bint len);
	static buint InvSubStr(buint cy, buint* dst, const buint* src, bint len);

	// negate data string with decrement, dst = -1 - src - cy (outputs carry)
	static buint NegDecStr(buint cy, buint* dst, const buint* src, bint len);
	static buint NegDecStr(buint cy, buint* dst, bint len);

	// multiply data string by one word (inputs and outputs carry bits))
	static buint MulStr(buint carry, buint num, buint* dst, const buint* src, bint len);

	// multiply data string by one world and add to destination (inputs and outputs carry bits)
	static buint MulAddStr(buint carry, buint num, buint* dst, const buint* src, bint len);

	// square data string (len is size of source, destination is sized 2*len)
	static void SqrStr(buint* dst, const buint* src, bint len);

	// divide data string by an integer (returns reminder = carry)
	static buint DivStr(buint carry, buint num, buint* dst, const buint* src, bint len);

	// expand number division by an integer (returns length of expansion)
	static bint DivUExpStr(buint carry, buint num, buint* dst, bint maxlen);

	///////////////////////////////////////////////////////////////////////////////
	// divide data strings
	//   carry = highest word of dividend src1
	//   dst = destination, on result it will contain quotient with length (len1 - len2 + 1), dst can be NULL if result not required
	//   src1 = source with dividend, length len1, on result it will contain remainder with length len2
	//   len1 = length of src1 with dividend (must be len1 >= len2)
	//   src2 = source with divisor, length len2
	//   len2 = length of src2 with divisor (must be > 2, must be len1 >= len2)
	// Divisor must be normalised - must be rotated left so its highest bit is 1 !
	// Divisor must be not longer than dividend and must be long 3 or more entries.
	static void Div2Str(buint carry, buint* dst /* = NULL */, buint* src1, bint len1, const buint* src2, bint len2);

public:

	// constructor (intsize/decsize = size of integer/decimal part in bytes)
	bignum();
	bignum(bint intsize, bint decsize);
	bignum(LPCTSTR text); // number in format: "-123.456"

	// desctructor
	~bignum();

	// initialize max. size of number and set content to 0
	// intsize/decsize = size of integer/decimal part in bytes
	// decrease = decrease size if needed
	void SetMaxSize(bint intsize, bint decsize, bool decrease = true);

	// copy number from another number (does not resize buffer size and limits)
	// timings: 100 dig 25 ns, 1000 dig 70 ns, 10k dig 200 ns, 100k dig 4 us
	void Copy(const bignum& num);

	// duplicate number, returns exact copy of this number (creates new number using malloc)
	bignum* Dup() const;

	// exchange two numbers
	void Exchange(bignum& num);

	// max. length of integer part (in number of entries or in bytes, minimal 1 entry)
	inline bint IntMax() const { return m_IntMax; } // number of entries
	inline bint IntMaxSize() const { return m_IntMax*BIGSIZE; } // number of bytes
	inline bint IntMaxDig() const { return (bint)(m_IntMax*DIGPERWRD+0.99999999); } // approx. number of valid digits

	// max. length of decimal part (in number of entries or in bytes)
	inline bint DecMax() const { return m_DecMax; } // number of entries
	inline bint DecMaxSize() const { return m_DecMax*BIGSIZE; } // number of bytes
	inline bint DecMaxDig() const { return (bint)(m_DecMax*DIGPERWRD); } // approx. number of valid digits

	// max. length of number (in number of entries or in bytes)
	inline bint LenMax() const { return m_IntMax + m_DecMax; } // number of entries
	inline bint LenMaxSize() const { return (m_IntMax + m_DecMax)*BIGSIZE; } // number of bytes
	inline bint LenMaxDig() const { return this->IntMaxDig() + this->DecMaxDig(); } // approx. number of valid digits

	// current length of integer part (in number of entries or in bytes)
	inline bint IntNum() const { return m_IntNum; } // number of entries
	inline bint IntSize() const { return m_IntNum*BIGSIZE; } // number of bytes
	inline bint IntDig() const { return (bint)(this->IntBits()*DIGPERBIT+0.99999999); } // approx. number of valid digits

	// current length of decimal part (in number of entries or in bytes)
	inline bint DecNum() const { return m_DecNum; } // number of entries
	inline bint DecSize() const { return m_DecNum*BIGSIZE; } // number of bytes
	inline bint DecDig() const { return (bint)(this->DecBits()*DIGPERBIT); } // approx. number of valid digits

	// current length of number (in number of entries or in bytes)
	inline bint LenNum() const { return m_IntNum + m_DecNum; } // number of entries
	inline bint LenSize() const { return (m_IntNum + m_DecNum)*BIGSIZE; } // number of bytes
	inline bint LenDig() const { return this->IntDig() + this->DecDig(); } // approx. number of valid digits

	// check if number is negative
	inline bool IsNeg() const { return m_IsNeg; }

	// sign (-1=negative, +1=positive, 0=zero)
	inline int Sign() const { return m_IsNeg ? -1 : ((m_IntNum + m_DecNum == 0) ? 0 : 1); }

	// check if number is zero
	inline bool Equ0() const { return (m_IntNum + m_DecNum == 0) && !m_IsNeg; }

	// check if number is 1
	inline bool Equ1() const
		{ return (m_IntNum == 1) && (m_DecNum == 0) && (*this->Base() == 1); }

	// check if number is -1
	inline bool EquM1() const { return (m_IntNum + m_DecNum == 0) && m_IsNeg; }

	// data
	inline buint* Data() { return m_Data; }
	inline const buint* Data() const { return m_Data; }

	// pointer to number base (= start of integer part)
	inline buint* Base(bint off = 0) { return &m_Data[m_DecMax + off]; }
	inline const buint* Base(bint off = 0) const { return &m_Data[m_DecMax + off]; }

	// get integer value with limitation
	buint UIntVal() const;
	bint IntVal() const;
	buint UIntAbs() const;

// --- base operations

	// set number to 0
	void Set0();

	// set number to 1
	void Set1();

	// set number to -1
	void SetM1();

	// set signed number
	void Set(bint n);

	// set unsigned number
	void SetU(buint n);

	// fill with a pattern (default = overflow = maximal positive number,
	// intmax/decmax = max. length in number of entries)
	// ASM timing: 100 dig 13 ns, 1000 dig 28 ns, 10k dig 200 ns, 100k dig 2.8 us
	// C timing: 100 dig 13 ns, 1000 dig 27 ns, 10k dig 200 ns, 100k dig 2.8 us
	void Fill(buint val = BIGMAX, bool neg = false, bint intmax = -1, bint decmax = -1);

	// scan equal pattern in UP direction (off = offset from number base of first entry;
	// returns length of equal data in number of entries)
	bint ScanEqu(buint val = 0, bint off = 0);

	// scan not equal pattern in UP direction (off = offset from number base of first entry;
	// returns length of not equal data in number of entries)
	bint ScanNEqu(buint val = 0, bint off = 0);

	// compare if numbers are equals
	bool CompEqu(const bignum& num) const;

	// compare with another number (returns COMP_LE,...)
	int Comp(const bignum& num) const;

	// compare with signed number (returns COMP_LE,...)
	int Comp(bint num) const;

	// compare with unsigned number (returns COMP_LE,...)
	int CompU(buint num) const;

	// compare with 0 (returns COMP_LE,...)
	inline int Comp0() const
		{ return m_IsNeg ? COMP_LE : ((m_IntNum + m_DecNum == 0) ? COMP_EQ : COMP_GR); }

	// negate number, this = -this, this = -num
	void Neg();
	void Neg(const bignum& num);

	// absoluite value, this = ABS(this)
	inline void Abs() { if (m_IsNeg) this->Neg(); }

	// increment, this = this + 1, this = num + 1
	void Inc();
	void Inc(const bignum& num);

	// decrement, this = this - 1, this = num - 1
	void Dec();
	void Dec(const bignum& num);

	// get number of valid bits of integer part (without highest sign bit)
	bint IntBits() const;

	// get number of valid bits of decimal part
	bint DecBits() const;

	// get total number of valid bits (without highest sign bit)
	inline bint LenBits() const { return this->IntBits() + this->DecBits(); }

	// floor, nearest less or equal integer (round down, 2.2 -> 2, -2.2 -> -3)
	inline void Floor() { m_DecNum = 0; }
	void Floor(const bignum& num);

	// ceiling, nearest greater or equal integer (round up, 2.2 -> 3, -2.2 -> -2)
	void Ceil();
	void Ceil(const bignum& num);

	// fraction, without floor integer (2.2 -> 0.2, -2.2 -> 0.8)
	inline void Fract() { m_IntNum = 0; m_IsNeg = false; }
	void Fract(const bignum& num);

	// round to nearest integer (2.2 -> 2, 2.8 -> 3)
	void Round();
	void Round(const bignum& num);

	// round to nearest integer towards zero (2.2 -> 2, -2.2 -> -2)
	void Integer();
	void Integer(const bignum& num);

	// convert to ASCIIZ text into buffer of size approx. 1 + 2.4*size in bytes,
	// returns number of digits; decmax = max. number of decimal digits (-1=unlimited)
	// timings: 100 dig 3 us, 1000 dig 20 us, 10k dig 1 ms, 100k dig 80 ms
	// (int 50k dig 70 ms, dec 50k dig 11 ms)
	bint ToTextBuf(char* buf, bint bufsize, bint decmax = -1) const;
	CText ToText(bint decmax = -1) const;

	// convert number from text (len=text length, -1=unlimited or terminated by 0, returns number of processed characters)
	// timings: 100 dig 3 us, 1000 dig 24 us, 10k dig 1.5 ms, 100k dig 140 ms
	// (int 50k dig 6 ms, dec 50k dig 140 ms)
	bint FromTextBuf(const char* text, bint len = -1);

	// convert number from text (returns new position)
	int FromText(const CText& text, int pos = 0);

	// raw random number (maxint/maxdec = max. number of digits of integer/decimal part)
	// timings: 100 dig 50 ns, 1000 dig 260 ns, 10k dig 2 us, 100k dig 23 us
	void RandRaw(bint maxint, bint maxdec, bint minint = 1, bint mindec = 0);

// --- bit operations (negative number expands its highest bit to "1")

	// bit NOT (changes sign)
	// this = NOT this
	// timings: 100 dig 8 ns, 1000 dig 25 ns, 10k dig 200 ns, 100k dig 3 us
	void Not();
	void Not(const bignum& num);

	// bit AND of 2 numbers, store result here (numbers may overlap)
	// this = num1 AND num2
	void And(const bignum& num1, const bignum& num2);
	void And(const bignum& num1, bint num2); // signed
	void AndU(const bignum& num1, buint num2); // unsigned
	inline void And(bint num1, const bignum& num2) { this->And(num2, num1); } // signed
	inline void AndU(buint num1, const bignum& num2) { this->AndU(num2, num1); } // unsigned

	// bit AND this number with another number (numbers may overlap)
	// this = this AND num
	void And(const bignum& num);
	void And(bint num); // signed
	void AndU(buint num); // unsigned

	// bit OR of 2 numbers, store result here (numbers may overlap)
	// this = num1 OR num2
	void Or(const bignum& num1, const bignum& num2);
	void Or(const bignum& num1, bint num2); // signed
	void OrU(const bignum& num1, buint num2); // unsigned
	inline void Or(bint num1, const bignum& num2) { this->Or(num2, num1); } // signed
	inline void OrU(buint num1, const bignum& num2) { this->OrU(num2, num1); } // unsigned

	// bit OR this number with another number (numbers may overlap)
	// this = this OR num
	void Or(const bignum& num);
	void Or(bint num); // signed
	void OrU(buint num); // unsigned

	// bit XOR of 2 numbers, store result here (numbers may overlap)
	// this = num1 XOR num2
	void Xor(const bignum& num1, const bignum& num2);
	void Xor(const bignum& num1, bint num2); // signed
	void XorU(const bignum& num1, buint num2); // unsigned
	inline void Xor(bint num1, const bignum& num2) { this->Xor(num2, num1); } // signed
	inline void XorU(buint num1, const bignum& num2) { this->XorU(num2, num1); } // unsigned

	// bit XOR this number with another number (numbers may overlap)
	// this = this XOR num
	void Xor(const bignum& num);
	void Xor(bint num); // signed
	void XorU(buint num); // unsigned

	// shift bits left, to higher bits (negative = shift bits right)
	// timings: 100 dig 21 ns, 1000 dig 50 ns, 10k dig 400 ns, 100k dig 5 us
	void LShift(s64 shift);
	void LShift(const bignum& num, s64 shift);
	inline void LShift(const bignum& shift) { this->LShift(shift.IntVal()); }
	inline void LShift(const bignum& num, const bignum& shift) { this->LShift(num, shift.IntVal()); }

	// shift bits right, to lower bits (negative = shift bits left)
	void RShift(s64 shift);
	void RShift(const bignum& num, s64 shift);
	inline void RShift(const bignum& shift) { this->RShift(shift.IntVal()); }
	inline void RShift(const bignum& num, const bignum& shift) { this->RShift(num, shift.IntVal()); }

// --- addition

	// add 2 bignums together, store result here (numbers may overlap)
	// this = num1 + num2
	// timings add two num: 100 dig 40 ns, 1000 dig 140 ns, 10k dig 1 us, 100k dig 14 us
	void Add(const bignum& num1, const bignum& num2);
	void Add(const bignum& num1, bint num2); // signed
	void AddU(const bignum& num1, buint num2); // unsigned
	inline void Add(bint num1, const bignum& num2) { this->Add(num2, num1); } // signed
	inline void AddU(buint num1, const bignum& num2) { this->AddU(num2, num1); } // unsigned

	// add number to this number (numbers may overlap)
	// this = this + num
	void Add(const bignum& num);
	void Add(bint num); // signed
	void AddU(buint num); // unsigned

// --- subtraction

	// sub 2 numbers, store result here (numbers may overlap)
	// this = num1 - num2
	void Sub(const bignum& num1, const bignum& num2);
	void Sub(const bignum& num1, bint num2); // signed
	void SubU(const bignum& num1, buint num2); // unsigned
	void Sub(bint num1, const bignum& num2); // signed
	void SubU(buint num1, const bignum& num2); // unsigned

	// sub number from this number (numbers may overlap)
	// this = this - num
	void Sub(const bignum& num);
	void Sub(bint num); // signed
	void SubU(buint num); // unsigned

	// inv sub - subtract this number from other number (numbers may overlap)
	void InvSub(const bignum& num);
	void InvSub(bint num); // signed
	void InvSubU(buint num); // unsigned

// --- multiplication

	// mul 2 numbers, store result here
	// this = num1 * num2;
	// timings mul two num: 100 dig 380 ns, 1000 dig 9 us, 10k dig 800 us, 100k dig 80 ms, 1M dig 7 sec
	void Mul(const bignum& num1, const bignum& num2);
	inline void Mul(const bignum& num) { this->Mul(*this, num); }
	void Mul(const bignum& num1, bint num2); // signed
	void MulU(const bignum& num1, buint num2); // unsigned
	inline void Mul(bint num1, const bignum& num2) { this->Mul(num2, num1); } // signed
	inline void MulU(buint num1, const bignum& num2) { this->MulU(num2, num1); } // unsigned

	// mul by number
	// timings: 100 dig 40 ns, 1000 dig 300 ns, 10k dig 1 us, 100k dig 20 us, 1M dig 100 us
	void Mul(bint num); // signed
	void MulU(buint num); // unsigned

	// square
	inline void Sqr() { this->Mul(*this, *this); }
	inline void Sqr(const bignum& num) { this->Mul(num, num); }

	// factorial (requires size of integer part approx. 2*num bytes)
	// (values up to 10000! are cached to fast access)
	/* Required bytes of integer part:
		100!: 9*8 = 72 B = 158 dig (3 us)
		200!: 20*8 = 160 B = 375 dig (10 us)
		500!: 59*8 = 472 B = 1135 dig (40 us)
		1000!: 134*8 = 1072 B = 2568 dig (140 us)
		2000!: 298*8 = 2384 B = 5736 dig (600 us)
		5000!: 848*8 = 6784 B = 16326 dig (3.5 ms)
		10000!: 1851*8 = 14808 B = 35660 dig (15 ms)
		20000!: 4015*8 = 31210 B = 77338 dig (66 ms)
		50000!: 11069*8 = 88552 B = 213237 dig (440 ms)
		100000!: 23699*8 = 189592 B	= 456574 dig (2 sec)
		200000!: 50522*8 = 404176 B = 973351 dig (8 sec)
		500000!: 136632*8 = 1093056 B = 2632342 dig (1 min)
		1000000!: 288889*8 = 2311112 B = 5565709 dig (5 min)
	*/
	void Fact();
	void Fact(buint num);

// --- divide

// !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
// divide 2 numbers (this=num1/num2), store result here and remainder to 'rem'
// num1 = dividend, num2 = divisor, this = quotient, rem = remainder (do integer division or NULL=do decimal division)
	void Div(const bignum& num1, const bignum& num2, bignum* rem = NULL);

	// div by number, returns remainder
	// timings: 100 dig 240 ns, 1000 dig 1.8 us, 10k dig 16 us, 100k dig 160 us, 1M dig 1.6 ms
	buint DivUInt(buint num); // unsigned, only integer part
	buint DivU(buint num); // unsigned
};

extern int FactMem;			// size of factorial cache buffer

// temporary numbers (be aware of multitask - use TryLock to find free number!)
extern bignum BigTempNum[BIGTEMPNUM]; // temporary numbers
extern CLock BigTempLock[BIGTEMPNUM]; // locks of numbers

// get temporary number (return index)
int GetBigTemp();

// free temporary number (-1=invalid)
void FreeBigTemp(int inx);

// test power of two: if ((d & (d-1)) == 0) .... (0x1000 & 0x0FFF = 0)

// assembler
#ifdef X86
extern "C" u64 CheckComp_x64(u64 par1, u64 par2, u64 par3, u64 par4, u64 par5, u64 par6);
extern "C" void FillStr_x64(buint* dst, buint val, bint len);
extern "C" void CopyStr_x64(buint* dst, const buint* src, bint len);
extern "C" void CopyDownStr_x64(buint* dst, const buint* src, bint len);
extern "C" bint ScanEquStr_x64(const buint* dst, buint val, bint len);
extern "C" bint ScanNEquStr_x64(const buint* dst, buint val, bint len);
extern "C" u64 LShiftStr_x64(buint carry, int shift, buint* dst, buint* src, bint len);
extern "C" u64 RShiftStr_x64(buint carry, int shift, buint* dst, buint* src, bint len);
extern "C" bint CompEquStr_x64(const buint* num1, const buint* num2, bint len);
extern "C" int CompStr_x64(const buint* num1, const buint* num2, bint len);
extern "C" void NotStr_x64(buint* dst, bint len);
extern "C" void NotStr2_x64(buint* dst, const buint* src, bint len);
extern "C" void AndStr_x64(buint* dst, const buint* src, bint len);
extern "C" void AndStr2_x64(buint* dst, const buint* src1, const buint* src2, bint len);
extern "C" void OrStr_x64(buint* dst, const buint* src, bint len);
extern "C" void OrStr2_x64(buint* dst, const buint* src1, const buint* src2, bint len);
extern "C" void XorStr_x64(buint* dst, const buint* src, bint len);
extern "C" void XorStr2_x64(buint* dst, const buint* src1, const buint* src2, bint len);
extern "C" buint IncStr_x64(buint* dst, bint len);
extern "C" buint IncStr2_x64(buint* dst, const buint* src, bint len);
extern "C" buint DecStr_x64(buint* dst, bint len);
extern "C" buint DecStr2_x64(buint* dst, const buint* src, bint len);
extern "C" buint AddStr_x64(buint cy, buint* dst, const buint* src, bint len);
extern "C" buint AddStr2_x64(buint cy, buint* dst, const buint* src1, const buint* src2, bint len);
extern "C" buint SubStr_x64(buint cy, buint* dst, const buint* src, bint len);
extern "C" buint SubStr2_x64(buint cy, buint* dst, const buint* src1, const buint* src2, bint len);
extern "C" buint InvSubStr_x64(buint cy, buint* dst, const buint* src, bint len);
extern "C" buint MulStr_x64(buint carry, buint num, buint* dst, const buint* src, bint len);
extern "C" buint MulAddStr_x64(buint carry, buint num, buint* dst, const buint* src, bint len);
extern "C" void AddSqrStr_x64(buint* dst, const buint* src, bint len);
extern "C" buint DivStr_x64(buint carry, buint num, buint* dst, const buint* src, bint len);
extern "C" bint DivUExpStr_x64(buint carry, buint num, buint* dst, bint maxlen);
#endif // X86

extern "C" void Test_x64(buint* dst, buint* src);

