551 lines
15 KiB
MQL5
551 lines
15 KiB
MQL5
//+------------------------------------------------------------------+
|
||
//| Int.mqh |
|
||
//| Copyright 2026, Niquel Mendoza. |
|
||
//| https://www.mql5.com |
|
||
//+------------------------------------------------------------------+
|
||
#property copyright "Copyright 2026, Niquel Mendoza."
|
||
#property link "https://www.mql5.com"
|
||
#property strict
|
||
|
||
#ifndef BIGNUMBERSBYLEO_SRC_INT_MQH
|
||
#define BIGNUMBERSBYLEO_SRC_INT_MQH
|
||
|
||
//+------------------------------------------------------------------+
|
||
//| |
|
||
//+------------------------------------------------------------------+
|
||
#include "Uint.mqh"
|
||
|
||
//+------------------------------------------------------------------+
|
||
//| |
|
||
//+------------------------------------------------------------------+
|
||
namespace TSN
|
||
{
|
||
//+------------------------------------------------------------------+
|
||
//| Clase big integer |
|
||
//+------------------------------------------------------------------+
|
||
struct BigInteger : public BigIBase
|
||
{
|
||
private:
|
||
void SubInPlaceMayorQue(const ulong& v[], const int bsize_abs);
|
||
void SumInPlace(const ulong &v[], const int bsize_abs);
|
||
|
||
public:
|
||
//---
|
||
BigInteger(ulong& v[], const int vs_8);
|
||
BigInteger(int initial_reserve);
|
||
BigInteger();
|
||
|
||
|
||
//---
|
||
__forceinline int Cmp(const BigIBase& b) const { return CmpInt<BigInteger>(b); }
|
||
int CmpAbs(const BigInteger& b) const;
|
||
|
||
//---
|
||
__forceinline void Neg() { m_v_s = -m_v_s; }
|
||
void operator+=(const BigInteger& b);
|
||
void operator-=(const BigInteger& b);
|
||
void operator>>=(const ulong b);
|
||
|
||
//--- floor
|
||
// Esta funcion aplica un florr (div y this es el reto osea)
|
||
// this = this % b
|
||
void ModFloor(BigUInteger& b);
|
||
|
||
//---
|
||
// GDC extenndio para retonar x:
|
||
// si tenemos:
|
||
// ax+by=gdc(a,b)
|
||
// osea:
|
||
// this*x+b*y=gdc(this,b)
|
||
// Esta funcion retorna el (x)
|
||
// Tambien se peude ver como si se tratase de obtener el inveosr modular de this, donde b es el mod
|
||
// this * x = 1 (mod b)
|
||
static BigInteger GdcExtendedRetX(const BigUInteger& a, const BigUInteger& b);
|
||
|
||
//---
|
||
static __forceinline int AbsS(int v) { return v >= 0 ? v : -v;}
|
||
};
|
||
|
||
//+------------------------------------------------------------------+
|
||
//| |
|
||
//+------------------------------------------------------------------+
|
||
BigInteger::BigInteger(ulong& v[], const int vs_8)
|
||
: BigIBase(v, vs_8)
|
||
{
|
||
}
|
||
|
||
|
||
//+------------------------------------------------------------------+
|
||
BigInteger::BigInteger(int initial_reserve)
|
||
: BigIBase(initial_reserve)
|
||
{
|
||
}
|
||
|
||
//+------------------------------------------------------------------+
|
||
BigInteger::BigInteger(void)
|
||
: BigIBase()
|
||
{
|
||
}
|
||
|
||
|
||
//+------------------------------------------------------------------+
|
||
//| |
|
||
//+------------------------------------------------------------------+
|
||
int BigInteger::CmpAbs(const BigInteger &b) const
|
||
{
|
||
// iniciales
|
||
const int abs_this_s = BIGNUMERBYLEO_ABS(m_v_s);
|
||
const int abs_other_s = BIGNUMERBYLEO_ABS(b.m_v_s);
|
||
if(abs_this_s > abs_other_s)
|
||
return BIGINTEGER_CMP_MAYOR;
|
||
if(abs_this_s < abs_other_s)
|
||
return BIGINTEGER_CMP_MENOR;
|
||
// equal en size
|
||
for(int i = abs_this_s - 1; i >= 0; i--)
|
||
{
|
||
if(m_v[i] != b.m_v[i]) // no coindice
|
||
return m_v[i] > b.m_v[i] ? BIGINTEGER_CMP_MAYOR : BIGINTEGER_CMP_MENOR;
|
||
}
|
||
return BIGINTEGER_CMP_EQ; // iguales
|
||
}
|
||
|
||
//+------------------------------------------------------------------+
|
||
//| |
|
||
//+------------------------------------------------------------------+
|
||
void BigInteger::SumInPlace(const ulong &v[], const int bsize_abs)
|
||
{
|
||
// mismo signo
|
||
// añadir normal
|
||
//---
|
||
BIGNUMERBYLEO_INT_NORMALIZE(m_v_s)
|
||
const int lkc = m_v_s;
|
||
|
||
//---
|
||
ulong carry = 0;
|
||
int i = 0;
|
||
|
||
//---
|
||
if(m_v_s > bsize_abs) // this mayor
|
||
{
|
||
m_v_s++; // por si el carry
|
||
if(m_v_s > ArraySize(m_v))
|
||
ArrayResize(m_v, m_v_s, m_v_s);
|
||
|
||
//-- empezamos por b que es el menor
|
||
for(; i < bsize_abs; i++)
|
||
{
|
||
const ulong s1 = (m_v[i] += v[i]); // suma 1
|
||
const ulong r = (m_v[i] += carry); // suma 2
|
||
carry = (s1 < v[i]) | (r < s1); // carry base, luego carray de al suma previa
|
||
}
|
||
// propagamos el carry
|
||
for(; i < lkc; i++)
|
||
{
|
||
const ulong r = (m_v[i] += carry);
|
||
carry = (r < carry);
|
||
}
|
||
}
|
||
else // el otro mayor
|
||
{
|
||
m_v_s = bsize_abs + 1; // mayor
|
||
if(m_v_s > ArraySize(m_v))
|
||
ArrayResize(m_v, m_v_s, m_v_s);
|
||
|
||
//--- comun
|
||
for(; i < lkc; i++)
|
||
{
|
||
const ulong s1 = (m_v[i] += v[i]); // suma 1
|
||
const ulong r = (m_v[i] += carry); // suma 2
|
||
carry = (s1 < v[i]) | (r < s1); // carry base, luego carray de al suma previa
|
||
}
|
||
// carry
|
||
for(; i < bsize_abs; i++)
|
||
{
|
||
const ulong r = v[i] + carry;
|
||
m_v[i] = r;
|
||
carry = (r < v[i]);
|
||
}
|
||
}
|
||
|
||
//---
|
||
if(carry)
|
||
m_v[i] = 1;
|
||
else
|
||
m_v_s--; // no hay carry exacto
|
||
|
||
//---
|
||
BIGNUMERBYLEO_INT_SNEG(m_v_s)
|
||
}
|
||
|
||
//+------------------------------------------------------------------+
|
||
//| |
|
||
//+------------------------------------------------------------------+
|
||
void BigInteger::SubInPlaceMayorQue(const ulong &v[], const int vs)
|
||
{
|
||
//----
|
||
BIGNUMERBYLEO_INT_NORMALIZE(m_v_s)
|
||
ulong borrow = 0;
|
||
int i = 0;
|
||
|
||
//---
|
||
// Chekea ambos daod qeu b en caso pueda tener mas bytes esos ya no se procesan
|
||
for(; i < vs; i++)
|
||
{
|
||
const ulong res_bor = m_v[i] - borrow; // paso 0 (a-resto)
|
||
const ulong res_f = res_bor - v[i]; // paso 1 (r-b)
|
||
borrow = (m_v[i] < borrow) | // en caso sea menor (tipo m_v es 0 y borro viene cno 1
|
||
// en ese caso tendremismo qeu prestarmos 1..
|
||
// Igual aqui si el left menor al right tendra uqe prestartse
|
||
(res_bor < v[i]);
|
||
//Print(res_f);
|
||
m_v[i] = res_f;
|
||
}
|
||
// sobra
|
||
for(; i < m_v_s; i++)
|
||
{
|
||
const ulong r = m_v[i] - borrow;
|
||
borrow = (m_v[i] < borrow); // si es menor enonces hubo uover
|
||
m_v[i] = r;
|
||
}
|
||
|
||
//---
|
||
BIGNUMBERSBYLEO_CLEAN_HIGH_ZEROS(m_v, m_v_s)
|
||
BIGNUMERBYLEO_INT_SNEG(m_v_s)
|
||
}
|
||
|
||
|
||
//+------------------------------------------------------------------+
|
||
//| |
|
||
//+------------------------------------------------------------------+
|
||
void BigInteger::operator+=(const BigInteger& b)
|
||
{
|
||
//---
|
||
// En caos sea 0 entonces podira ir a la rama de sumimplace solo si b tambien es positivo
|
||
// ahora en caso sea difenite va a la rama de cmp menor .. en ese caos se resitarai this = x-this
|
||
// y como x puede digmoa ser 0 no daria ningun error...
|
||
const int bsize = b.m_v_s;
|
||
//--- chekeamos signo
|
||
if((m_v_s ^ bsize) < 0) // diferente
|
||
{
|
||
switch(CmpAbs(b))
|
||
{
|
||
case BIGINTEGER_CMP_EQ:
|
||
{
|
||
BIGNUMBERBYLEO_ZERO
|
||
break;
|
||
}
|
||
case BIGINTEGER_CMP_MAYOR:
|
||
{
|
||
SubInPlaceMayorQue(b.m_v, BIGNUMERBYLEO_ABS(bsize));
|
||
break;
|
||
}
|
||
case BIGINTEGER_CMP_MENOR:
|
||
{
|
||
m_v_s = BIGNUMERBYLEO_ABS(m_v_s);
|
||
b.RestarConYResEn(m_v, m_v_s);
|
||
if(b.m_v_s < 0)
|
||
m_v_s = -m_v_s;
|
||
break;
|
||
}
|
||
default:
|
||
break;
|
||
}
|
||
}
|
||
else // signos iguales
|
||
{
|
||
//--- si es negativo lo cambiamos
|
||
SumInPlace(b.m_v, BIGNUMERBYLEO_ABS(bsize));
|
||
}
|
||
}
|
||
|
||
//+------------------------------------------------------------------+
|
||
//| |
|
||
//+------------------------------------------------------------------+
|
||
/* Usamos mismo alg que sum pero con - esto es posuible
|
||
dado qeu tenemos que:
|
||
1) a - b = a + (-b)
|
||
2) -a - b = (-a) + (-b)
|
||
3) a - (-b) = a + b ; nota que (-(-b) = b)
|
||
4) -a - -b = (-a) + (b) (justo lo mismo)
|
||
|
||
Osea negando el signo del b podemos replicar con una "suma" lo que haiamos con la resta
|
||
*/
|
||
void BigInteger::operator-=(const BigInteger& b)
|
||
{
|
||
//---
|
||
const int bsize = -b.m_v_s;
|
||
//--- chekeamos signo
|
||
if((m_v_s ^ bsize) < 0) // diferente
|
||
{
|
||
switch(CmpAbs(b))
|
||
{
|
||
case BIGINTEGER_CMP_EQ:
|
||
{
|
||
BIGNUMBERBYLEO_ZERO
|
||
break;
|
||
}
|
||
case BIGINTEGER_CMP_MAYOR:
|
||
{
|
||
SubInPlaceMayorQue(b.m_v, BIGNUMERBYLEO_ABS(bsize));
|
||
break;
|
||
}
|
||
case BIGINTEGER_CMP_MENOR:
|
||
{
|
||
m_v_s = BIGNUMERBYLEO_ABS(m_v_s);
|
||
b.RestarConYResEn(m_v, m_v_s);
|
||
if(b.m_v_s < 0)
|
||
m_v_s = -m_v_s;
|
||
break;
|
||
}
|
||
default:
|
||
break;
|
||
}
|
||
}
|
||
else // signos iguales
|
||
{
|
||
//--- si es negativo lo cambiamos
|
||
SumInPlace(b.m_v, BIGNUMERBYLEO_ABS(bsize));
|
||
}
|
||
}
|
||
|
||
|
||
//+------------------------------------------------------------------+
|
||
//| |
|
||
//+------------------------------------------------------------------+
|
||
void BigInteger::operator>>=(const ulong b)
|
||
{
|
||
|
||
|
||
}
|
||
|
||
|
||
//+------------------------------------------------------------------+
|
||
//| |
|
||
//+------------------------------------------------------------------+
|
||
// =
|
||
// q = floor(this/b)
|
||
// retorna R
|
||
void BigInteger::ModFloor(BigUInteger& b)
|
||
{
|
||
//---
|
||
const int bs = b.m_v_s;
|
||
const int sing = m_v_s ^ bs;
|
||
const int s = BIGNUMERBYLEO_ABS(m_v_s);
|
||
|
||
//---
|
||
if(s < bs) // menor
|
||
{
|
||
if(sing < 0) // diiferen (- y +)
|
||
{
|
||
// r = n (this) + d (B)
|
||
// aparte como b es mayor dicho signo manda..
|
||
// this = (b) - |(this)| da positivo siempre asi que
|
||
m_v_s = s;
|
||
b.RestarConYResEn(m_v, m_v_s);
|
||
}
|
||
// es + entonces tal cual x % y el resto es x.. si es menor (Como en este caso)
|
||
}
|
||
else // this mayor o igual
|
||
{
|
||
BigUInteger temp(m_v, s);
|
||
temp %= b; // reduce aqui mismo
|
||
|
||
//--- intercambiamos
|
||
ArraySwap(m_v, temp.m_v);
|
||
m_v_s = temp.m_v_s; // (ojo ya es positiuvio..)
|
||
|
||
//---
|
||
if(sing < 0) // this es - lo que quiere decir que es menor a b (Aunque siempre lo sera ahora mismo por el %)
|
||
{
|
||
// ahota mismo this es menor que b (divisor)
|
||
// la idea es que como el resto ahora es negativo
|
||
// le sumasmos el diivosr -this += b
|
||
// en ese caso seria como hace b - this
|
||
// con signo del mayor (+) como final (signo final)
|
||
|
||
//m_v_s = -m_v_s; NO dado qeu usamos el positivo
|
||
// this = b - this (magnitudes)
|
||
b.RestarConYResEn(m_v, m_v_s);
|
||
// ahor amismo this ya es positivo
|
||
}
|
||
}
|
||
}
|
||
|
||
//+------------------------------------------------------------------+
|
||
//| |
|
||
//+------------------------------------------------------------------+
|
||
// Obtiene el GDC EXT (el coeficiente x de benzout % mod positivo en un div floor)
|
||
BigUInteger BNBL_GdcExtendedRetXWMod(const BigUInteger& a, const BigUInteger& b, const BigUInteger& mod)
|
||
{
|
||
//--
|
||
const ulong gz = BigUInteger::CTZ_Commons(a, b); // 2 commons
|
||
//--- quitamos 2 commons (ahora son impares)
|
||
// u = a * 2^p
|
||
// v = b * 2^p
|
||
// quita los 2^p
|
||
BigUInteger u = a >> gz;
|
||
BigUInteger v = b >> gz;
|
||
|
||
// lo que queda (0) en caso de que ya sea impar >= 1
|
||
// en caso de que no sea impar
|
||
ulong uz = u.Ctz(); // restante
|
||
ulong vz = v.Ctz(); // restante
|
||
|
||
//----
|
||
/*
|
||
Invariante base la idea es u\v originales aparteis de los "curr"
|
||
u= t0*tu + t1tv
|
||
v= s0*tu + s1tv
|
||
|
||
Algo difernte del gdc ext bin tradicional es como la inversa
|
||
la idea luego con esto es que "invertimos" por lo que en el looop caliente en vez de dividir
|
||
podemos mul lo que no perjudica paridad, pro loq eu no hace falta un while de ajuiste..
|
||
eso solo al final..
|
||
*/
|
||
|
||
//---
|
||
const bool swap = u.m_v_s < v.m_v_s;
|
||
if(swap)
|
||
{
|
||
u.Swap(v);
|
||
BIGNUMERBYLEO_SWAP(uz, vz, ulong)
|
||
}
|
||
|
||
|
||
//--- ahora iniciamos los valores de los coeficintes
|
||
// como ay hemos modificado varios valores entonces tendremos que reflejar esos cambios
|
||
//--- s1
|
||
// v con todos los cambios es ahora mismo
|
||
// v = 2^vz * tv
|
||
// v=s0⋅tu+s1⋅tv
|
||
// s0=0
|
||
// v = s1tv
|
||
// s1 = 2^vz
|
||
const int limbs_s = int((vz >> 6) + 1);
|
||
BigInteger s1(limbs_s); // reservamos con
|
||
ArrayInitialize(s1.m_v, 0ULL); // iniciamos a 0 todo el arr
|
||
s1.SetBit(vz, true);
|
||
// s0 como detemrinamos sera 0
|
||
BigInteger s0(limbs_s);
|
||
|
||
|
||
//--- ahora t
|
||
// u=
|
||
// u = 2^uz * tu_prev
|
||
// tu_prev = q * tv + tu_actual
|
||
// u = 2^uz * (q * tv + tu_actual)
|
||
// u = (2^uz * q * tv) + (2^uz * tu_actual)
|
||
// reordenando
|
||
// u = (2^uz * tu_actual) + (2^uz * q * tv)
|
||
// t0 = 2^uz
|
||
// t1 = 2^uz * q
|
||
u %= v; // u = u % v (resto de divisor u\v)
|
||
|
||
// ahora si actulziamso t0\t1
|
||
//const int limbs_t = int((uz >> 6) + 1);
|
||
//BigInteger t0(TSN::BigIBase::EMPTY_INITIAL_RESERVE, limbs_t);
|
||
//t0.SetBit(uz, true);
|
||
|
||
ulong p = uz + vz; // sob
|
||
|
||
//---
|
||
if(u.IsNotZero())
|
||
{
|
||
const ulong shift = u.Ctz();
|
||
// aplicamos a u
|
||
u <<= shift;
|
||
// s0 le aplicamos
|
||
s0.UShiftLeft(shift);
|
||
// t0 le aplicamos
|
||
p += shift;
|
||
|
||
//---
|
||
// Aqui en hot path es basimnte el mismo algoritmo del bin normal
|
||
// solo que ahora tenemos que sumar para compesar los coeficientes
|
||
int cmp = u.Cmp(v);
|
||
while(cmp != 0) // si no es igual
|
||
{
|
||
switch(cmp)
|
||
{
|
||
case BIGINTEGER_CMP_MAYOR:
|
||
{
|
||
// ahora como restamos tu_nuevo = tu_viejo - tv
|
||
// tu_nuevo = tu_viejo - tv (+tv)
|
||
// tu_nuevo + tv = tu_viejo == tu_viejo = tu_nuevo + tv
|
||
// tu_viejo = tu_nuevo + tv
|
||
// u = t0*tu + t1tv
|
||
// u = t0*(tu_nuevo + tv) + t1tv
|
||
// u = t0*tu_nuevo+t0*tv + t1*tv
|
||
// u = t0*tu_nuevo+tv(t0 + t1)
|
||
// u = t0*tu+tv(t0 + t1)
|
||
// osea
|
||
// t1 = t0 + t1
|
||
// tambien
|
||
// s1 = s0 + s1
|
||
// la idea es que como cambiamos tu tamiben se debe de matenern la invariante
|
||
|
||
u -= v;
|
||
s1 += s0; // s1 = s0 + s1
|
||
// t no
|
||
// ahora los hacemos impar denuvo a u (puede que sea par con la resta)
|
||
const ulong s = u.Ctz();
|
||
u <<= s;
|
||
s0.UShiftLeft(s);
|
||
|
||
//--- añadimos
|
||
p += s;
|
||
break;
|
||
}
|
||
case BIGINTEGER_CMP_MENOR:
|
||
{
|
||
// rotacion ahora u reduce a v
|
||
v -= u;
|
||
s0 += s1;
|
||
// ahora los hacemos impar denuvo a u (puede que sea par con la resta)
|
||
const ulong s = v.Ctz();
|
||
v <<= s;
|
||
s1.UShiftLeft(s);
|
||
|
||
//--- añadimos
|
||
p += s;
|
||
break;
|
||
}
|
||
default:
|
||
break;
|
||
}
|
||
|
||
//---
|
||
cmp = u.Cmp(v);
|
||
}
|
||
}
|
||
|
||
//---
|
||
v <<= gz;
|
||
s0.Neg();
|
||
|
||
s1 = b \ v;
|
||
|
||
//---
|
||
while(p-- > 0)
|
||
{
|
||
if(s0.IsPar())
|
||
{
|
||
s0 -= s1;
|
||
}
|
||
s0 >>= 1;
|
||
}
|
||
|
||
//---
|
||
s1 += s0;
|
||
if(s0.CmpAbs(s1) == BIGINTEGER_CMP_MAYOR)
|
||
{
|
||
s0.Swap(s1);
|
||
}
|
||
|
||
//---
|
||
s0.ModFloor(mod);
|
||
return BigUInteger(s0.m_v, s0.m_v_s);
|
||
}
|
||
}
|
||
//+------------------------------------------------------------------+
|
||
#endif // BIGNUMBERSBYLEO_SRC_INT_MQH
|