BigNumberByLeo/Src/Base/Int.mqh

//+------------------------------------------------------------------+
//|                                                          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