koros0111/BigNumberByLeo
Watch
1
0
Fork
You've already forked BigNumberByLeo
 0
forked from nique_372/BigNumberByLeo
Code Pull requests Activity
BigNumberByLeo/Src/Base/Main.mqh

2120 lines
56 KiB
MQL5
Raw Permalink Blame History

//+------------------------------------------------------------------+
//| Main.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_BASE_MAIN_MQH
#define BIGNUMBERSBYLEO_SRC_BASE_MAIN_MQH
//+------------------------------------------------------------------+
//| |
//+------------------------------------------------------------------+
#include "..\\Utils\\Main.mqh"
#include "Def.mqh"
//+------------------------------------------------------------------+
//| |
//+------------------------------------------------------------------+
//#define BIGINTGERBYLEO_MACRO_AS_FUNCION
//+------------------------------------------------------------------+
//| |
//+------------------------------------------------------------------+
namespace TSN
{
//+------------------------------------------------------------------+
//| |
//+------------------------------------------------------------------+
/* xor\or
a ^ 0 = a
{
1 ^ 0 = 1 (en caso sea 1 entonces 1 dado que son difente)
0 ^ 0 = 0 (en caso sea 0 ambos iguales 0 igual)
ambos casos se conerva
}
a | 0 = a
Lo mismo daod que añades 0 nada
aparte
1 | 0 = 1
0 | 0 = 0
*/
//+------------------------------------------------------------------+
//| |
//+------------------------------------------------------------------+
// maximo numero a represetar = 2^31-1 (INT MAX) elementos * 64bits = 137438953408 este es el maximo numero de bits
// que peude tener un numero dado que un array como maximo tamaño dtiene INT_MAX elementos no peude tener mas
// y como cada elemtnos es un uint64_t entonces se peude repenstart ese numero * 64 bits
#define BIGNUMERBYLEO_UINTEGER_IZ_ZERO (m_v_s == 1 && m_v[0] == 0ULL)
#define BIGNUMERBYLEO_BITS_TO_LIMBS(v) (v>>6)
#define BIGNUMERBYLEO_LIMBS_TO_BITS(v) (v<<6)
//+------------------------------------------------------------------+
//| |
//+------------------------------------------------------------------+
struct BigUInteger
{
public:
//---
ulong m_v[];
int m_v_s;
//--- Constructores
// raw se transfiere (swaping)
BigUInteger(ulong& v[], const int vs_8);
//-- high
BigUInteger(const string& str, int base); // desde string (Base 10)
BigUInteger(const long number); // si se quiere iniciar desde un numero
BigUInteger(const int& e[], int initial_reserve);
BigUInteger(const double& e[], const long number);
BigUInteger();
//-- Vacio inica desde bytes
BigUInteger(const uchar& bytes[], int byteorder);
//--- unitarios
//-- Negacion
BigUInteger operator~() const;
//--- bit simples
//-- and
void operator&=(const BigUInteger& b);
BigUInteger operator&(const BigUInteger& b) const;
__forceinline ulong operator&(const long _b) const;
//-- or
void operator|=(const BigUInteger& b);
BigUInteger operator|(const BigUInteger& b) const;
BigUInteger operator|(const long _b) const;
//-- xor
void operator^=(const BigUInteger& b);
BigUInteger operator^(const BigUInteger& b) const;
BigUInteger operator^(const long _b) const;
//-- dezplazamientos
// left
void operator<<=(const long _b);
BigUInteger operator<<(const long _b) const;
// right
void operator>>=(const long _b);
BigUInteger operator>>(const long _b) const;
//---- aritmeticos
//- suma
void operator+=(const BigUInteger& b);
BigUInteger operator+(const BigUInteger& b) const;
void operator+=(const long _b);
BigUInteger operator+(const long _b) const;
//- resta
void operator-=(const BigUInteger& b);
BigUInteger operator-(const BigUInteger& b) const;
void operator-=(const long _b);
BigUInteger operator-(const long _b) const;
//- mul
void operator*=(const BigUInteger& b);
BigUInteger operator*(const BigUInteger& b) const;
void operator*=(const long _b);
BigUInteger operator*(const long _b) const;
//- div or mod
// vs otro b completo
template <typename TOp>
void DivModInPlace(BigUInteger& b);
//- div
// nota no es const BigUInteger& b dado que como tal NO modificamso b
// solo que nos tomoamos prestado su array para lectura noma...
__forceinline void operator/=(BigUInteger& b);
BigUInteger operator/(BigUInteger& b) const;
void operator/=(const long _b);
BigUInteger operator/(const long _b) const;
//- mod
__forceinline void operator%=(BigUInteger& b);
BigUInteger operator%(BigUInteger& b) const;
void operator%=(const long _b);
ulong operator%(const long _b) const;
//--- compracion
// basicas
bool operator>(const BigUInteger& b) const;
bool operator>=(const BigUInteger& b) const;
bool operator==(const BigUInteger& b) const;
// derivadas
__forceinline bool operator!=(const BigUInteger& b) const { return !(this == b); }
__forceinline bool operator<(const BigUInteger& b) const { return !(this >= b); }
__forceinline bool operator<=(const BigUInteger& b) const { return !(this > b); }
// zero
__forceinline bool IsZero() const { return BIGNUMERBYLEO_UINTEGER_IZ_ZERO; }
__forceinline bool IsNotZero() const { return !BIGNUMERBYLEO_UINTEGER_IZ_ZERO; }
//--- acceso a limbs (sin chekeo raw maxima velociad)
__forceinline ulong operator[](const int limb_idx) const { return m_v[limb_idx]; }
//--- complejos
// this = base
// e = exp (long)
// n = (mod n)
BigUInteger PowMod(const long e, const BigUInteger& n);
// Es probasblemnete un primo?¿
bool IsProbablePrime(int rounds);
// GCD Maximo comun divisor normal
// = gdc(this, v) (retrona ulong)
ulong Gdc(const ulong v) const;
//---
// 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)
BigUInteger GdcExtendedRetX(const BigUInteger& b);
//--- From
void FromBytesLE(const uchar& buf[]);
void FromBytesBE(const uchar& buf[]);
//--- Utilidades
// TRandom debe generar n limbs
template <typename TRandom>
__forceinline void FillRandom();
//--- To
//- bytes
// NOTA: retornan el tamaño final (no cuanto escribieron.. exactamente)
int ToBytesLE(uchar& buf[], int w = 0, int k = BIGUINTEGER_TOBYTES_DEFAULTK) const;
int ToBytesBE(uchar& buf[], int w = 0, int k = BIGUINTEGER_TOBYTES_DEFAULTK) const;
//- string
int ToString(uchar& buf[]) const;
//---
static const int EMPTY_INITIAL_RESERVE[1];
static const double EMPTY_NUMBER_EXACT[1];
};
//+------------------------------------------------------------------+
//| |
//+------------------------------------------------------------------+
const int BigUInteger::EMPTY_INITIAL_RESERVE[1] = {0};
const double BigUInteger::EMPTY_NUMBER_EXACT[1] = {0.0};
//+------------------------------------------------------------------+
//| Constructores |
//+------------------------------------------------------------------+
// Nota v ya muere ahi noramlte esto lo usarimos en operator
// pro que ahora v tiene size=0 nada
BigUInteger::BigUInteger(ulong &v[], const int vs_8)
: m_v_s(vs_8)
{
// ahora m_v tiene el desipcrity de v y asi rotan
ArraySwap(m_v, v);
}
//+------------------------------------------------------------------+
// exacto
// casos de uso (pro ejemplo get extendner retx con un numero normal
// perimo hay qeu converit a big integer si usas el contrucot normal te reserva mucho espcio
// asi que usamos lo nceisa solo 1 dado qeu no lo usaremos mas.. este es ele caso de uso)
BigUInteger::BigUInteger(const double &e[], const long number)
: m_v_s(1)
{
ArrayResize(m_v, 1);
m_v[0] = ulong(number);
}
//+------------------------------------------------------------------+
BigUInteger::BigUInteger(const long number)
: m_v_s(1)
{
ArrayResize(m_v, 32, 32); // tamaño inicial de reserva
m_v[0] = ulong(number);
}
//+------------------------------------------------------------------+
BigUInteger::BigUInteger()
: m_v_s(1)
{
ArrayResize(m_v, 32, 32); // tamaño inicial de reserva
m_v[0] = 0ULL;
}
//+------------------------------------------------------------------+
BigUInteger::BigUInteger(const int &e[], int initial_reserve)
: m_v_s(1)
{
ArrayResize(m_v, initial_reserve, initial_reserve);
m_v[0] = 0ULL;
}
//+------------------------------------------------------------------+
BigUInteger::BigUInteger(const string& str, int base)
: m_v_s(1)
{
//---
const int digtis = g_tsn_biguinteger_base_max[base];
if(digtis < 0)
{
// En caso de error lo inciamos como 0
ArrayResize(m_v, 32, 32);
m_v[0] = 0ULL;
return;
}
//---
const int l = StringLen(str);
const int req = l << 1;
if(ArraySize(m_v) < req) // no hay tamaño suficiente
ArrayResize(m_v, req, req);
m_v[0] = 0ULL;
//---
int i = 0;
while(i < l)
{
const int take = (l - i < digtis) ? (l - i) : digtis;
ulong chunk_val = 0;
ulong chunk_pow = 1;
//---
for(int k = 0; k < take; k++)
{
chunk_val = chunk_val * base + (str[i++] ^ '0');
chunk_pow *= base;
}
//---
this *= chunk_pow; // desplaza lo acumulado por la potencia correcta
this += chunk_val; // suma el chunk nuevo
}
}
//+------------------------------------------------------------------+
BigUInteger::BigUInteger(const uchar &bytes[], int byteorder)
{
if(byteorder == BIGUINTEGER_LOADBYTES_BE)
FromBytesBE(bytes);
else
FromBytesLE(bytes);
}
//+------------------------------------------------------------------+
//| |
//+------------------------------------------------------------------+
#define BIGUINTGER_LOADFROMBYTES_CHECK \
if(k < 1) \
{\
if(ArraySize(m_v) < 1)\
ArrayResize(m_v, 32, 32);\
m_v_s = 1;\
m_v[0] = 0ULL;\
return; \
}
//+------------------------------------------------------------------+
//| |
//+------------------------------------------------------------------+
template <typename TRandom>
// firma esperada (const ulong& in, const int ins)
__forceinline void BigUInteger::FillRandom()
{
TRandom::Random(m_v, m_v_s);
}
//+------------------------------------------------------------------+
//| |
//+------------------------------------------------------------------+
void BigUInteger::FromBytesLE(const uchar& buf[])
{
//---
const int k = ArraySize(buf);
BIGUINTGER_LOADFROMBYTES_CHECK
//---
if(k > ArraySize(m_v))
ArrayResize(m_v, k, k);
//---
const int sob = k & 7; // % 8 cuantos sobraan
const int blocks = k - sob; // Cuantos bloques enteros procesaremos
//--- Ahora si
m_v_s = 0;
int r = 0;
// bloques completos
for(; r < blocks;)
{
//--- write
m_v[m_v_s++] = ulong(buf[r++]) |
ulong(buf[r++]) << 8 |
ulong(buf[r++]) << 16 |
ulong(buf[r++]) << 24 |
ulong(buf[r++]) << 32 |
ulong(buf[r++]) << 40 |
ulong(buf[r++]) << 48 |
ulong(buf[r++]) << 56;
}
// en caso haya sobrante
if(sob)
{
m_v[m_v_s] = 0ULL;
for(int j = 0; j < (sob << 3); j += 8)
m_v[m_v_s] |= ulong(buf[r++] << j);
m_v_s++;
}
//--- Limpiamos zeros altos..
BIGNUMBERSBYLEO_CLEAN_HIGH_ZEROS
}
//+------------------------------------------------------------------+
// La idea es leer desde el byte[0] (mas significativo) a menos significativo
// lo demas el armado es igual
void BigUInteger::FromBytesBE(const uchar& buf[])
{
//---
const int k = ArraySize(buf);
BIGUINTGER_LOADFROMBYTES_CHECK
//---
if(k > ArraySize(m_v))
ArrayResize(m_v, k, k);
//---
const int sob = k & 7; // % 8 cuantos sobraan
const int blocks = k - sob; // Cuantos bloques enteros procesaremos
//--- Ahora si
int r = blocks - 1;
// bloques completos
for(; r >= 0;)
{
//--- write
m_v[m_v_s++] = ulong(buf[r--]) |
ulong(buf[r--]) << 8 |
ulong(buf[r--]) << 16 |
ulong(buf[r--]) << 24 |
ulong(buf[r--]) << 32 |
ulong(buf[r--]) << 40 |
ulong(buf[r--]) << 48 |
ulong(buf[r--]) << 56;
}
// en caso haya sobrante
if(sob)
{
r = sob - 1; // reinicamos dado qeu peude ser (-1)
m_v[m_v_s] = 0ULL;
for(int j = 0; j < (sob << 3); j += 8)
m_v[m_v_s] |= ulong(buf[r--] << j);
m_v_s++;
}
//--- Limpiamos zeros altos..
BIGNUMBERSBYLEO_CLEAN_HIGH_ZEROS
}
//+------------------------------------------------------------------+
//| |
//+------------------------------------------------------------------+
int BigUInteger::ToBytesLE(uchar &buf[], int w = 0, int k = BIGUINTEGER_TOBYTES_DEFAULTK) const
{
//---
const int vs_bytes = (m_v_s << 3);
if(k == BIGUINTEGER_TOBYTES_DEFAULTK)
k = vs_bytes;
//---
if(k + w > ArraySize(buf))
ArrayResize(buf, k + w);
//---
int ksob = k - vs_bytes; // cuantos bytes sobrrana (padding)
//---
int blocks, sob;
if(ksob <= 0) // menor o igual a lo que tenemos
{
blocks = k >> 3; // Cuantos bloques enteros procesaremos
sob = k & 7; // % 8 cuantos sobraan
}
else // en este caso hay que agregar padding calculs con el max (usamos sin sob)
{
blocks = m_v_s;
sob = 0;
}
//--- Ahora si
int r = 0;
// bloques completos
for(; r < blocks; r++)
{
const ulong v = m_v[r];
//--- write
buf[w++] = uchar(v);
buf[w++] = uchar(v >> 8);
buf[w++] = uchar(v >> 16);
buf[w++] = uchar(v >> 24);
buf[w++] = uchar(v >> 32);
buf[w++] = uchar(v >> 40);
buf[w++] = uchar(v >> 48);
buf[w++] = uchar(v >> 56);
}
// en caso haya sobrante
if(sob)
{
const ulong v = m_v[r];
for(int j = 0; j < (sob << 3); j += 8)
buf[w++] = uchar(v >> j);
}
//--- Padding de zeros al final
if(ksob > 0) // hay sobrante
{
ksob += w; // fin
for(; w < ksob; w++)
buf[w] = 0;
}
//---
return w;
}
//+------------------------------------------------------------------+
int BigUInteger::ToBytesBE(uchar &buf[], int w = 0, int k = -1) const
{
//---
const int vs_bytes = (m_v_s << 3);
if(k == BIGUINTEGER_TOBYTES_DEFAULTK)
k = vs_bytes;
//---
if(k + w > ArraySize(buf))
ArrayResize(buf, k + w);
//---
int ksob = k - vs_bytes; // cuantos bytes sobrrana (padding)
//---
int blocks, sob;
if(ksob <= 0) // menor o igual a lo que tenemos
{
blocks = k >> 3; // Cuantos bloques enteros procesaremos
sob = k & 7; // % 8 cuantos sobraan
}
else // en este caso hay que agregar padding calculs con el max (usamos sin sob)
{
blocks = m_v_s;
sob = 0;
}
//---
int r = blocks - 1;
//--- Padding de zeros al inicio
if(ksob > 0) // hay sobrante
{
ksob += w;
for(; w < ksob; w++)
buf[w] = 0;
}
//--- Ahora si
// bloques completos
for(; r >= 0; r--)
{
const ulong v = m_v[r];
//--- write
buf[w++] = uchar(v >> 56);
buf[w++] = uchar(v >> 48);
buf[w++] = uchar(v >> 40);
buf[w++] = uchar(v >> 32);
buf[w++] = uchar(v >> 24);
buf[w++] = uchar(v >> 16);
buf[w++] = uchar(v >> 8);
buf[w++] = uchar(v);
}
// en caso haya sobrante
if(sob)
{
r++;
const ulong v = m_v[r];
for(int j = ((sob << 3) - 8); j >= 0; j -= 8)
buf[w++] = uchar(v >> j);
}
//---
return w;
}
//+------------------------------------------------------------------+
//| |
//+------------------------------------------------------------------+
int BigUInteger::ToString(uchar& buf[]) const
{
//--- Contamos digitos de todos
// cada bit es un digito
int n = 0;
for(int i = m_v_s - 1; i >= 0; i--)
{
ulong v = m_v[i];
while(v)
{
v /= 10ULL;
n++;
}
}
//---
const int fn = ArrayResize(buf, n);
Print(n);
n--; // ahora baja
//--- To integer
for(int i = m_v_s - 1; i >= 0; i--)
{
ulong uvalue = m_v[i];
//---
while(uvalue >= 100)
{
const ulong idx = (uvalue % 100ULL) << 1ULL;
buf[n--] = g_tsn_digit_pairs[idx + 1];
buf[n--] = g_tsn_digit_pairs[idx];
uvalue /= 100ULL;
}
//---
if(uvalue >= 10)
{
const ulong idx = (uvalue << 1ULL);
buf[n--] = g_tsn_digit_pairs[idx + 1];
buf[n--] = g_tsn_digit_pairs[idx];
}
else
{
buf[n--] = uchar('0' + uvalue);
}
}
return fn;
}
//+------------------------------------------------------------------+
//| |
//+------------------------------------------------------------------+
bool BigUInteger::operator>(const BigUInteger& b) const
{
if(m_v_s != b.m_v_s)
return m_v_s > b.m_v_s; // quien es mayor
// en caso de que sean iguales
for(int i = m_v_s - 1; i >= 0; i--)
{
if(m_v[i] != b.m_v[i]) // no coindice
return m_v[i] > b.m_v[i];
}
return false;
}
//+------------------------------------------------------------------+
//| |
//+------------------------------------------------------------------+
bool BigUInteger::operator>=(const BigUInteger& b) const
{
if(m_v_s != b.m_v_s)
return m_v_s >= b.m_v_s; // quien es mayor o igual
// en caso de que sean iguales
for(int i = m_v_s - 1; i >= 0; i--)
{
if(m_v[i] != b.m_v[i]) // en caso no sean iguales
return m_v[i] > b.m_v[i];
}
// son iguales
return true;
}
//+------------------------------------------------------------------+
//| |
//+------------------------------------------------------------------+
bool BigUInteger::operator==(const BigUInteger& b) const
{
if(m_v_s != b.m_v_s)
return false;
for(int i = m_v_s - 1; i >= 0; i--)
{
if(m_v[i] != b.m_v[i])
return false;
}
return true;
}
//+------------------------------------------------------------------+
//| neg bit |
//+------------------------------------------------------------------+
BigUInteger BigUInteger::operator~() const
{
ulong v[];
ArrayResize(v, m_v_s);
for(int i = 0; i < m_v_s; i++)
v[i] = ~m_v[i];
return BigUInteger(v, m_v_s);
}
//+------------------------------------------------------------------+
//| and |
//+------------------------------------------------------------------+
void BigUInteger::operator&=(const BigUInteger& b)
{
if(b.m_v_s < m_v_s)
{
// b es menor lo qeu se nos aplica es menor [1][0] &= [2]
m_v_s = b.m_v_s; // lo bajamos
}
//---
for(int i = 0; i < m_v_s; i++)
m_v[i] &= b.m_v[i];
}
//+------------------------------------------------------------------+
BigUInteger BigUInteger::operator&(const BigUInteger& b) const
{
//---
ulong v[];
int vs = m_v_s;
//---
if(b.m_v_s < vs)
{
// b es menor lo qeu se nos aplica es menor [1][0] &= [2]
vs = b.m_v_s; // lo bajamos
}
//---
ArrayResize(v, vs);
//---
for(int i = 0; i < vs; i++)
v[i] = m_v[i] & b.m_v[i];
//---
return BigUInteger(v, vs);
}
//+------------------------------------------------------------------+
__forceinline ulong BigUInteger::operator&(const long _b) const
{
return m_v[0] & ulong(_b);
}
//+------------------------------------------------------------------+
//| or |
//+------------------------------------------------------------------+
void BigUInteger::operator|=(const BigUInteger& b)
{
if(m_v_s > b.m_v_s) // this es mayor
{
for(int i = 0; i < b.m_v_s; i++) // hasta donde de
m_v[i] |= b.m_v[i];
}
else // b es mayor
{
// [1][0] |= [1][1][1]
int i = 0;
for(; i < m_v_s; i++)
m_v[i] |= b.m_v[i];
//---
m_v_s = b.m_v_s; // ahora del mismo tamaño
// chekeo dado que incilate peude no tener el mismo tamao (reservas impliciatas)
// que se hacen
if(ArraySize(m_v) < m_v_s)
ArrayResize(m_v, m_v_s, m_v_s);
//--- el resto copy directo (a|0=a)
for(; i < m_v_s; i++)
m_v[i] = b.m_v[i];
}
}
//+------------------------------------------------------------------+
BigUInteger BigUInteger::operator|(const BigUInteger& b) const
{
//---
ulong v[];
int vs;
//---
if(m_v_s > b.m_v_s) // this es mayor
{
vs = m_v_s;
ArrayResize(v, vs);
int i = 0;
// hasta terminar con b
for(; i < b.m_v_s; i++)
v[i] = m_v[i] | b.m_v[i];
// resto
for(; i < vs; i++)
v[i] = m_v[i];
}
else // b es mayor
{
vs = b.m_v_s;
ArrayResize(v, vs);
int i = 0;
// terminar con this
for(; i < m_v_s; i++)
v[i] = m_v[i] | b.m_v[i];
// resto
for(; i < vs; i++)
v[i] = b.m_v[i];
}
//---
return BigUInteger(v, vs);
}
//+------------------------------------------------------------------+
BigUInteger BigUInteger::operator|(const long _b) const
{
//---
ulong v[];
ArrayResize(v, m_v_s);
v[0] = m_v[0] | ulong(_b);
// copia
for(int i = 1; i < m_v_s; i++)
v[i] = m_v[i];
//---
return BigUInteger(v, m_v_s);
}
//+------------------------------------------------------------------+
//| xor |
//+------------------------------------------------------------------+
void BigUInteger::operator^=(const BigUInteger& b)
{
if(m_v_s > b.m_v_s) // this es mayor
{
for(int i = 0; i < b.m_v_s; i++) // hasta donde de
m_v[i] ^= b.m_v[i];
}
else // b es mayor
{
// [1][0] ^= [1][1][1]
int i = 0;
for(; i < m_v_s; i++)
m_v[i] ^= b.m_v[i];
//---
m_v_s = b.m_v_s; // ahora del mismo tamaño
// chekeo dado que incilate peude no tener el mismo tamao (reservas impliciatas)
// que se hacen
if(ArraySize(m_v) < m_v_s)
ArrayResize(m_v, m_v_s, m_v_s);
//--- el resto copy directo (a^0=a)
for(; i < m_v_s; i++)
m_v[i] = b.m_v[i];
}
}
//+------------------------------------------------------------------+
BigUInteger BigUInteger::operator^(const BigUInteger& b) const
{
//---
ulong v[];
int vs;
//---
if(m_v_s > b.m_v_s) // this es mayor
{
vs = m_v_s;
ArrayResize(v, vs);
int i = 0;
// hasta terminar con b
for(; i < b.m_v_s; i++)
v[i] = m_v[i] ^ b.m_v[i];
// resto
for(; i < vs; i++)
v[i] = m_v[i];
}
else // b es mayor
{
vs = b.m_v_s;
ArrayResize(v, vs);
int i = 0;
// terminar con this
for(; i < m_v_s; i++)
v[i] = m_v[i] ^ b.m_v[i];
// resto
for(; i < vs; i++)
v[i] = b.m_v[i];
}
//---
return BigUInteger(v, vs);
}
//+------------------------------------------------------------------+
BigUInteger BigUInteger::operator^(const long _b) const
{
//--- hay data alemnos 1
ulong v[];
ArrayResize(v, m_v_s);
v[0] = m_v[0] ^ ulong(_b);
// copia
for(int i = 1; i < m_v_s; i++)
v[i] = m_v[i];
//---
return BigUInteger(v, m_v_s);
}
//+------------------------------------------------------------------+
//| |
//+------------------------------------------------------------------+
void BigUInteger::operator<<=(const long _b)
{
//---
const ulong b = ulong(_b);
const int els = int(b >> 6); // b / 64
const int els_sob = int(b & 63); // % 64
//---
if(els_sob == 0) // exacto
{
//---
m_v_s += els;
if(m_v_s < ArraySize(m_v))
ArrayResize(m_v, m_v_s);
//---
int i = m_v_s - 1;
for(; i >= els; i--)
m_v[i] = m_v[i - els];
//---
for(; i >= 0; i--)
m_v[i] = 0ULL;
//---
return;
}
//---
int r = m_v_s - 1; // read pointer
const int srh = (64 - els_sob); // shr
ulong hi = m_v[r]; // valor de lectura actual hi
const ulong overflow = hi >> srh; // si los altos habia valor randeo del dhift en adelante
//---
m_v_s += els;
int w = m_v_s - 1; // escritura en els-1 (depende de que tantos salots elsb haya)
if(overflow)
{
if(++m_v_s > ArraySize(m_v)) // si la reserva actual es menor al vactual
ArrayResize(m_v, m_v_s);
m_v[m_v_s - 1] = overflow;
}
else
{
// no hay ovw enotnces nada
if(m_v_s > ArraySize(m_v)) // si la reserva actual es menor al vactual
ArrayResize(m_v, m_v_s);
}
//--- iter
while(r > 0)
{
const ulong prev = m_v[--r]; // valor previo
m_v[w--] = (hi << els_sob) | (prev >> srh); // (valor alto dezplaado) | (valor bajo overflow siguiente)
hi = prev; // ahora el alto es nuestro prev (Curr)
}
m_v[w] = hi << els_sob; // terminos con el valor 0 o ultimo
}
//+------------------------------------------------------------------+
// crea uno nuevo
BigUInteger BigUInteger::operator<<(const long _b) const
{
//---
const ulong b = ulong(_b);
const int els = int(b >> 6); // b / 64
const int els_sob = int(b & 63); // % 64
//---
ulong v[];
int vs = m_v_s;
//---
if(els_sob == 0) // exacto
{
//---
vs += els;
ArrayResize(v, vs);
//---
int i = vs - 1;
for(; i >= els; i--)
v[i] = m_v[i - els];
//---
for(; i >= 0; i--)
v[i] = 0ULL;
//---
return BigUInteger(v, vs);
}
//---
int r = vs - 1; // read pointer
const int srh = (64 - els_sob); // shr
ulong hi = m_v[r]; // valor de lectura actual hi
const ulong overflow = hi >> srh; // si los altos habia valor randeo del dhift en adelante
//---
vs += els;
int w = vs - 1; // escritura en els-1 (depende de que tantos salots elsb haya)
if(overflow)
{
vs++;
ArrayResize(v, vs);
v[vs - 1] = overflow;
}
else
{
ArrayResize(v, vs);
}
//--- iter
while(r > 0)
{
const ulong prev = m_v[--r]; // valor previo
v[w--] = (hi << els_sob) | (prev >> srh); // (valor alto dezplaado) | (valor bajo overflow siguiente)
hi = prev; // ahora el alto es nuestro prev (Curr)
}
v[w] = hi << els_sob; // terminos con el valor 0 o ultimo
//---
return BigUInteger(v, vs);
}
//+------------------------------------------------------------------+
//| |
//+------------------------------------------------------------------+
/*
[..[..]] [[..]..]
>> ..
entonces
[....] [[..][..]]
en (m_v[el_sh_b] >> el_sh); tomtamos el 0 y lo demplzamosmo
[[..]..] a [..[..]]
toca rellenar altos del +1
ahi entra y (que ahora mismo apunta al=1)
y que da [[..][..]]
pero slk = 2 asi que l aisuinte iuteacion ya no se da (2<2 = false)
*/
//+------------------------------------------------------------------+
void BigUInteger::operator>>=(const long _b)
{
//---
const ulong b = ulong(_b);
const int el_sh_b = int(b >> 6);
const int el_sh = int(b & 63); // numero de bits sobrandses en b
if(el_sh == 0)
{
// si es 0
if(el_sh_b == 0)
{
m_v_s = 1;
m_v[0] = 0ULL;
return;
}
//---
m_v_s -= el_sh_b;
//---
for(int i = 0; i < m_v_s; i++)
m_v[i] = m_v[i + el_sh_b];
//---
return;
}
//--- prev
const int slk = m_v_s; // locked size
const int shr = 64 - el_sh; // shr
m_v_s -= el_sh_b; // aqui lo reduicmos el tamaño V en numero de bloques
//--- iter
m_v[0] = (m_v[el_sh_b] >> el_sh); // primera escritura de bajos
int w = 0; // ahora empezamos apartir de aqui
for(int l = el_sh_b; l < slk; l++)
{
const ulong y = m_v[l]; // curr temp
// previa rellenamos los altos (y se trunca a los bits que caben ahi)
// por eso ya no se requeriria mascara
m_v[w++] |= y << shr; // aqui ahora al (w) le aumentos los atlos
m_v[w] = (y >> el_sh); // nueva
}
}
//+------------------------------------------------------------------+
BigUInteger BigUInteger::operator>>(const long _b) const
{
//---
const ulong b = ulong(_b);
const int el_sh_b = int(b >> 6);
const int el_sh = int(b & 63); // numero de bits sobrandses en b
if(el_sh == 0)
{
// si es 0
if(el_sh_b == 0)
{
return BigUInteger();
}
//---
const int vs = m_v_s - el_sh_b;
BIGINTEGERBYLEO_ALLOC_V
//---
for(int i = 0; i < m_v_s; i++)
v[i] = m_v[i + el_sh_b];
//---
return BigUInteger(v, vs);
}
//--- prev
const int shr = 64 - el_sh; // shr
const int vs = m_v_s - el_sh_b; // aqui lo reduicmos el tamaño V en numero de bloques
BIGINTEGERBYLEO_ALLOC_V
//--- iter
m_v[0] = (m_v[el_sh_b] >> el_sh); // primera escritura de bajos
int w = 0; // ahora empezamos apartir de aqui
for(int l = el_sh_b; l < m_v_s; l++)
{
const ulong y = m_v[l]; // curr temp
// previa rellenamos los altos (y se trunca a los bits que caben ahi)
// por eso ya no se requeriria mascara
m_v[w++] |= y << shr; // aqui ahora al (w) le aumentos los atlos
m_v[w] = (y >> el_sh); // nueva
}
return BigUInteger(v, vs);
}
//+------------------------------------------------------------------+
//| |
//+------------------------------------------------------------------+
/*
//--- Suma en dos pasos
// La razon por la cual neceistmoas doble paso es el sigueinte
// Pongamos el siguiente ejemplo qeu tenemos base=10
// 99
// 91 caso en el que llevamos 1 y tenemos que usamr 9+9+1 si sumas todo tal cual tendiramso como reusto 9
// pero a y b son 9 ambos dfarian false.. asi que necesimoats hacelro en paso primero la suma tal cual
// pura 9+9 = 8 carray 1 luego 8+1 9 seria el reusto para ese digiti y ese seira el reustlado base
// esto pasa pro qeu si tenemos a+b el reusltaod sin carray prievio siemprte sera menor a aob
// pero con el carry esto peude cambiar y hacerlo igual por eso reueeirmos obtener el carry de ambas sumas
*/
//+------------------------------------------------------------------+
void BigUInteger::operator+=(const BigUInteger& b)
{
//--- Alg
const int lkc = m_v_s;
ulong carry = 0;
int i = 0;
//---
if(m_v_s > b.m_v_s) // 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 < b.m_v_s; i++)
{
const ulong s1 = (m_v[i] += b.m_v[i]); // suma 1
const ulong r = (m_v[i] += carry); // suma 2
carry = (s1 < b.m_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 = b.m_v_s + 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] += b.m_v[i]); // suma 1
const ulong r = (m_v[i] += carry); // suma 2
carry = (s1 < b.m_v[i]) | (r < s1); // carry base, luego carray de al suma previa
}
// carry
for(; i < b.m_v_s; i++)
{
const ulong r = b.m_v[i] + carry;
m_v[i] = r;
carry = (r < b.m_v[i]);
}
}
//---
if(carry)
m_v[i] = 1;
else
m_v_s--; // no hay carry exacto
}
//+------------------------------------------------------------------+
BigUInteger BigUInteger::operator+(const BigUInteger& b) const
{
BigUInteger v = this;
v += b;
return BigUInteger(v.m_v, v.m_v_s);
}
//+------------------------------------------------------------------+
void BigUInteger::operator+=(const long _b)
{
//---
const ulong b = ulong(_b);
const ulong s1 = (m_v[0] += b);
//--- Hay carry
if(s1 < b)
{
//--- resize (por si acaso)
const int lkc = m_v_s;
if(++m_v_s > ArraySize(m_v))
ArrayResize(m_v, m_v_s, m_v_s);
//----
ulong carry = 1;
//--- iteracion
int i = 1;
for(; i < lkc; i++)
{
const ulong r = (m_v[i] += carry); // resultado
carry = (r < carry); // carry check
}
//--- carry final
if(carry) // si hay carry
{
m_v[i] = 1;
}
else // no hay
{
m_v_s--;
}
}
}
//+------------------------------------------------------------------+
BigUInteger BigUInteger::operator+(const long b) const
{
BigUInteger v = this;
v += b;
return BigUInteger(v.m_v, v.m_v_s);
}
//+------------------------------------------------------------------+
//| |
//+------------------------------------------------------------------+
void BigUInteger::operator-=(const BigUInteger& b)
{
//----
ulong borrow = 0;
int i = 0;
//---
// Chekea ambos daod qeu b en caso pueda tener mas bytes esos ya no se procesan
for(; i < b.m_v_s && i < m_v_s; i++)
{
const ulong res_bor = m_v[i] - borrow; // paso 0 (a-resto)
const ulong res_f = res_bor - b.m_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 < b.m_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;
}
// Print(borrow);
// check
BIGNUMBERSBYLEO_CLEAN_HIGH_ZEROS
// maneo de underflow
}
//+------------------------------------------------------------------+
BigUInteger BigUInteger::operator-(const BigUInteger& b) const
{
BigUInteger v = this;
v -= b;
return BigUInteger(v.m_v, v.m_v_s);
}
//+------------------------------------------------------------------+
void BigUInteger::operator-=(const long _b)
{
//---
// Chekea ambos daod qeu b en caso pueda tener mas bytes esos ya no se procesan
const ulong b = ulong(_b);
const ulong res_f = m_v[0] - b; // paso 1 (a-b)
if(m_v[0] < b) // si es menor hay borrow
{
ulong borrow = 1;
m_v[0] = res_f;
// sobra
for(int i = 1; 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;
}
// check
BIGNUMBERSBYLEO_CLEAN_HIGH_ZEROS
}
else
{
// No hay borrow
m_v[0] = res_f; // tal cual
}
// maneo de underflow
// nota que aqui el underflow tipo 5 - 10
// oasaria qeu aqui si se manjea el compilador ya lo hace auto
// dado qeu el unico caso para que peuda usceder es que m_v[0] sea menor a b
// no hay otro
}
//+------------------------------------------------------------------+
BigUInteger BigUInteger::operator-(const long _b) const
{
BigUInteger v = this;
v -= _b;
return BigUInteger(v.m_v, v.m_v_s);
}
//+------------------------------------------------------------------+
//| |
//+------------------------------------------------------------------+
void BigUInteger::operator*=(const BigUInteger& b)
{
//--- min y max
int min, max;
if(m_v_s > b.m_v_s)
{
min = b.m_v_s;
max = m_v_s;
}
else
{
min = m_v_s;
max = b.m_v_s;
}
//--- resize
const int lks = m_v_s;
m_v_s += b.m_v_s;
//--- temp
ulong v[];
ArrayResize(v, m_v_s, m_v_s);
ArrayInitialize(v, 0ULL);
//--- Algoritmo de escuela simple
if(min < BIGNUMBERBYLEO_MUL_SCHOL_TO_KARATSUBA)
{
for(int i = 0; i < lks; i++)
{
// por cada digiito de b le multiples el digit curr a
ulong carry = 0;
//--- oeprando a
const ulong a = m_v[i];
const ulong a_lo = (uint)a; // parte baja
const ulong a_hi = a >> 32; // alta
//---
// iteraicon de digitos
for(int j = 0; j < b.m_v_s; j++)
{
ulong hi, lo;
BIGNUMBERSBYLEO_MUL64(b.m_v[j], hi, lo)
//--
// la suma en si es tipo (lo+hi+previo+carry)
// devido al carry y para evitar bugs
// lo haremos en pasos
// de dicha suma peude salir carry asi que eso lo vemos luegoi
// en esots 2 pasos no sumasmo hi dado que es el alto y ahi esta como el carry
// que luego pasaremos..
//--- lo+carry
const ulong sum1 = lo + carry; // suma1
//--- (prev) + curr
const ulong sum2 = sum1 + v[i + j];
//---
v[i + j] = sum2; // tal cual
//--- ahora armamos el carry
// hi (lo qeu se nos sale) +
// carray de la sum1
// carry de la suma2
carry = hi + (sum1 < lo) + (sum2 < lo);
}
//---- carry a la posicion final
if(carry)
{
v[i + b.m_v_s] = carry;
}
//--- sumamos el carry al final
//--- Añadimos (posicion final)
/* int pos = ;
while(carry != 0)
{
const uint64_t sum = v[pos] + carry;
v[pos] = sum;
carry = sum < v[pos]; // sale entonces reuqier + 1
pos++; // siguiente posicion
}*/
}
//---
while(m_v_s > 0 && v[m_v_s - 1] == 0)
m_v_s--;
}
else
{
// en caso este balanceado ratio ~2 no mucho
// max>min siempre y para uqe que cumpla esto:
// max<=min*2 osea que como minimo min = max/2
// no puede ser mayot ni menor tampoco 0 eso ya lo grantizamos por los ifs..
if(max <= (min << 1))
{
// metodo 2 Karatsuba
/*
El metodo dos parte de interpeteat a:
a*b
como dos polinomios
a=a1*x^m+a0
b=b1*x^m+b0
donde:
a1=parte alta
a0=parte baja
x=base
m=(numero de digitos del numero en si entre 2)
Esto es posible dado que expresamos el numero como dos partes (tipo) notacion
cientiica una base elevado a la mitad de digitiso*valorbajo + valor ato ejemplo
120000 ()
x=10
m=3 (6/2)
a=120*10^3+0=120000
Ahora si mulltiplacas estos dos polinomios tal que:
a*b= (a1*x^m+a0) * (b1*x^m+b0)
=
(a1*x^m+a0) *
(b1*x^m+b0)
--------------------
= (a1*x^m)(b1*x^m)+a0(b1*x^m)+b0(a1x^m)+(a0b0)
Ahora reordenamos
a1b1x^m2+a0(b1*x^m)+b0(a1x^m)+(a0b0)
Podemos sacar a x^m como factor comun ahi
x^m(a0b1+b0a1)
Queda:
a1b1x^m2+x^m(a0b1+b0a1)+a0b0
Ahora la idea por lo qeu entendi es que ahora mismo estasmo ejecutnado una multiplacion de toda la vida
ahora la idea es simplificar
para eso (a0b1+b0a1) esto que podemos verlo como (ab+cd) tenemos aqui 4 terminos..
diferentes por lo qeu no podemos factoriuzalo lo qeu si es que podemos aprovechar
algo interesante:
(a+b)(c+d) = ac+ad+bc+bd
Esto es multiplacion de binomios..
la idea e sque si interpatmaos ese a0b1+b0a1 como eso nos da:
(a0+a1)(b0+b1) =
a0b0+a0b1+a1b0+a1b1
Nota que eligmos esa convinacion para poder aplicar el truco que usaremos ahora
Esto si te das cuenta ciertas partes ya las tenemos... a0b0 y b1a1 ya los tenemso calculados
entonces renombrando:
(a0+a1)(b0+b1) = z0 + a0b1+a1b0 + z2
donde:
z2 = b1a1
z0 = a0b0
reordenmoas la parte izq:
= (a0b1+a1b0) + z0 + z2 (no imprta el orden dado que es suma propiedad comutativa)
ahora pasamos al otro lado
z2 - z0 - (a0+a1)(b0+b1) = a0b1+a1b0
o tambien:
a0b1+a1b0 = (a0+a1)(b0+b1) - z0 - z2
bueno entonces con eso ya podemos calucalr lo que nos falta para tener z1 con 3 multiplaciones
(z0, z2 y la de ()()) en vez de 4...
entcones la funcion seira algo asi
primero calcullkos z0 y z2 primero eso y luego z1 (a0b1+a1b0)
sale claucalos = (a0+a1)(b0+b1) - z0 - z2
luego de eso aplicas el x^m
Ejemplo multipllacar
10
45
x=10
m=1
a = 1*10^1+0 , osea que a1=1, a0=0
b = 4*10^1+5 , osea que b1=4, b0=5
calculomoes z0 (b1a1 ) y z2 (a0b0)
z0=1*4=4
z2=0*5=0
ahora z1
z1=(a0+a1)(b0+b1) - z0 - z2
remplazando:
(0+1)(5+4) - 0 - 4
(1)(9) - 0 - 4
9 - 0 - 4
9 - 4
z1=5
final remplzamos en:
z0x^m2+x^mz1+z2 = 4*100+10*5+0= 400 + 50 + 0 = 450
*/
//--- ahora si codigo
// const int base_mitad = max >> 1; // mitad
//int o_a1 = base_mitad;
// int o
//--- ahora partimos: a
// this [][][][]
// BigUInteger()
// ArraySwap()
}
}
//--- Intercambiamos arrays
ArraySwap(m_v, v); // m_v=v y v=m_v
}
//+------------------------------------------------------------------+
BigUInteger BigUInteger::operator*(const BigUInteger& b) const
{
BigUInteger v = this;
v *= b;
return BigUInteger(v.m_v, v.m_v_s);
}
//+------------------------------------------------------------------+
void BigUInteger::operator*=(const long _b)
{
//---
const ulong b = ulong(_b);
//---
const int lkc = m_v_s;
if(++m_v_s > ArraySize(m_v))
ArrayResize(m_v, m_v_s, m_v_s);
//---
ulong carry = 0;
int i = 0;
for(; i < lkc; i++)
{
//--- mul (b * a) = hi\lo
const ulong a = m_v[i];
const ulong a_lo = (uint)a; // parte baja
const ulong a_hi = a >> 32; // alta
//- paso
ulong hi, lo;
BIGNUMBERSBYLEO_MUL64(b, hi, lo)
//--- parte baja
const ulong sum = carry + lo; // previo + 1
m_v[i] = sum;
//---
carry = hi + (sum < lo);
}
//---
if(carry)
m_v[i] = carry;
else
m_v_s--;
}
//+------------------------------------------------------------------+
BigUInteger BigUInteger::operator*(const long _b) const
{
BigUInteger v = this;
v *= _b;
return BigUInteger(v.m_v, v.m_v_s);
}
//+------------------------------------------------------------------+
//| |
//+------------------------------------------------------------------+
/*
// caso simple
// resto = divisor*cociente - diviendoo
// lo = dividendo
// b = divisor
// m_v[i] = cociente | q = cociente
*/
//---
#define BIG_UINTEGER_FULL_DIV_ALG(q) \
const ulong b = ulong(_b); \
ulong resto = 0; \
for(int i = m_v_s - 1; i >= 0; i--) \
{ \
if(resto) \
{ \
q=CNumberUtils::Div128to64(resto, m_v[i], b, resto); \
} \
else \
{ \
const ulong lo = m_v[i]; \
q = lo / b; \
resto = lo - b * q; \
} \
}
//+------------------------------------------------------------------+
//| |
//+------------------------------------------------------------------+
#define BIGINTGERBYLEO_DIVMOD_V_MOD (1)
#define BIGINTGERBYLEO_DIVMOD_V_DIV (2)
//---
struct BigUintegerMod
{
const uchar bytes[BIGINTGERBYLEO_DIVMOD_V_MOD];
};
struct BigUintegerDiv
{
const uchar bytes[BIGINTGERBYLEO_DIVMOD_V_DIV];
};
//+------------------------------------------------------------------+
//| |
//+------------------------------------------------------------------+
template <typename TOp>
void BigUInteger::DivModInPlace(BigUInteger& b)
{
//--- Chekeos rapidos antes de ir a por el algoritmo com tal
const int divisor_len = b.m_v_s;
if(divisor_len == 1)
{
// Aplicamos para 1 limb
if(sizeof(TOp) == BIGINTGERBYLEO_DIVMOD_V_MOD)
{
this %= b.m_v[0];
}
else
{
this /= b.m_v[0];
}
return;
}
// el dividendo this es menor que el divisor?¿ en len
if(m_v_s < divisor_len)
{
if(sizeof(TOp) == BIGINTGERBYLEO_DIVMOD_V_DIV)
{
// cociente=0
m_v_s = 1;
m_v[0] = 0ULL;
}
// Ahora si es mod como x/y donde x es menor a 0 el resto es x= (this) asi que no hace falta hacer
// nada ni cambiar tamaños.
return;
}
// Usaremos el mismo algoritmo qeu usamos en la division base
//---- Normalizamos
const int shift = CLZ(b[divisor_len - 1]);
const int lkc = m_v_s;
//--- temporal b..
// Por un momenot le robamos los daots a b
// (luego le devolemos daod qeu bn es de solo lecutra no lo modifciaresmo)
// Entonces debido a eso no tiene sentido estar crenado copias si no las necesitamos
BigUInteger bn(b.m_v, divisor_len);
ulong div[];
//---
const int shr = 64 - shift;
if(shift > 0)
{
// Nada entonces tenemos que modificar bn le devolvemos
ArraySwap(b.m_v, bn.m_v);
// Ahora dezplazamos y escalamos
//--- Normalizamos B
// Aplicamos .. para empzar a bn
ArrayResize(bn.m_v, divisor_len);
for(int i = divisor_len - 1; i > 0; i--)
bn.m_v[i] = (b[i] << shift) | (b[i - 1] >> shr);
bn.m_v[0] = b[0] << shift;
//---- Normalizamos el dividendo
const int ns = m_v_s + 1;
ArrayResize(div, ns);
// sig
// overflow aqui
div[lkc] = m_v[lkc - 1] >> shr;
for(int i = lkc - 1; i > 0; i--)
div[i] = (m_v[i] << shift) | (m_v[i - 1] >> shr);
div[0] = m_v[0] << shift; // ultimo
}
else
{
//--- Ahora el diviosr (bn)
// Se presta tal cual no hace falta crear copias inncesarias
//--- Copiamos tal cual el dividendo
const int ns = m_v_s + 1;
ArrayResize(div, ns);
ArrayCopy(div, m_v, 0, m_v_s);
div[divisor_len] = 0;
}
//---
// Ahora reducimos el tamaño real..
// (dividendo len) - (divisor len)
m_v_s = lkc - divisor_len + 1;
//---- iteracion por cada digito del cociente
const ulong divisor_hi = bn[divisor_len - 1];
const ulong divisor_hi2 = bn[divisor_len - 2];
//---
for(int j = (lkc - divisor_len); j >= 0; j--)
{
//---
const int dividendo_pos = j + divisor_len;
//--- Estimacion inicial
// Dividos lso altos de div[] por el max alto de bn
ulong qhat, rhat;
if(div[dividendo_pos]) // mayor a 1 hay hi part
{
qhat = CNumberUtils::Div128to64(
div[dividendo_pos],
div[dividendo_pos - 1], divisor_hi, rhat);
}
else // 0 entonces division de toda la vida
{
qhat = div[dividendo_pos - 1] / divisor_hi;
rhat = (div[dividendo_pos - 1] - (divisor_hi * qhat));
}
//--- Correcion
while(true) // dado que n>1 siempre
{
ulong p_hi, p_lo;
// Multiplicamos
// qhat (cociente) * n-2 digito... la ide es ver si se pasa
CNumberUtils::Mul64to128(qhat, divisor_hi2, p_hi, p_lo);
//--- En caso sea mayot o en todo caso igual pero si el bajo mayor al digiot -2 del dividendo
const bool mayor = (p_hi > rhat) || (p_hi == rhat && p_lo > div[dividendo_pos - 2]);
if(!mayor)
break;
//--
qhat--;
const ulong lrhat = rhat;
rhat += divisor_hi;
//---
if(rhat < lrhat)
break;
}
//--- Ahora una vez correigdo multiplicamos y restamos
ulong borrow = 0;
// por cada digito del divisor lo multiplicmos por el qhat y restamos al this
// La idea aqui al igual qeu el algoritmo base
// es una vez que tenmas ese cocicnete lo multples con el divisor
// y luego le resmtoa al dividendno
for(int i = 0; i < divisor_len; i++)
{
//---
ulong p_hi, p_lo;
CNumberUtils::Mul64to128(qhat, bn[i], p_hi, p_lo);
//---
// sumar el borrow anterior al producto (p_hi:p_lo) + borrow
const ulong sum_lo = p_lo + borrow;
const ulong sum_hi = p_hi + (sum_lo < p_lo);
// restamos
const ulong old = div[i + j];
div[i + j] = old - sum_lo;
//--- lo que prestamos
borrow = sum_hi + (old < sum_lo);
}
//---
const ulong old_top = div[dividendo_pos];
div[dividendo_pos] = old_top - borrow;
//--- en caso haya underflow debemso de corregir esa estimacion en -1
// por lo tanatmos debemos de sumar 1 veces el divisor al diviendo
if(old_top < borrow)
{
//---
qhat--;
//---
ulong carry = 0;
for(int i = 0; i < divisor_len; i++)
{
// le sumasmo a cada digito +1 veces el diivsor real
ulong s2 = div[i + j] + bn[i];
// overflow al sumar
ulong c_out = (s2 < div[i + j]);
// lo añadimos al carry
s2 += carry;
// puede haber overflow al sumar el carray a s2 asiq eu tambien lo agregmoa a cout
c_out += (s2 < carry); // overflow al sumar el carry
// escribismo devuelta
div[i + j] = s2;
// assing
carry = c_out;
}
// añadimos carry
div[dividendo_pos] += carry;
}
//--- Escribimos en this el resultado tal cual
if(sizeof(TOp) == BIGINTGERBYLEO_DIVMOD_V_DIV) // solo si es div modificamos m_v
{
if(qhat == 0)
{
m_v_s--; // Reducimos tamaño
//Print("redux");
continue;
}
//---
//PrintFormat("qhat[%d] = %I64u", j , qhat);
m_v[j] = qhat;
}
}
//---
if(sizeof(TOp) == BIGINTGERBYLEO_DIVMOD_V_DIV) // en caso sea div
{
// no nos interesa el rest solo deovlelr a b lo qeu le tomamos prestado
if(shift == 0)
{
ArraySwap(b.m_v, bn.m_v); // le devolvemos el valor..
}
}
else
{
//---
// AQUI NO hace falta resize pro qeu m_v_s>divisor_len anteriormente ya se chekeo
//---
m_v_s = divisor_len; // tiene el valor de divisor len inicalemtne
if(shift > 0)
{
//---
const int last = divisor_len - 1;
m_v[last] = div[last] >> shift;
if(!m_v[last])
m_v_s--;
//---
for(int i = last - 1; i >= 0; i--)
{
m_v[i] = (div[i] >> shift) | (div[i + 1] << shr);
if(!m_v[i])
m_v_s--; // restmoas es 0
}
}
else
{
//---
//Print("hola");
int i = divisor_len - 1;
for(; i >= 0; i--)
{
if(div[i] == 0)
m_v_s--;
}
//--- ahora si copiamos
ArrayCopy(m_v, div, 0, 0, m_v_s); //
// Le devolvemos lo qeu tomamos prestado a b
ArraySwap(b.m_v, bn.m_v); // le devolvemos el valor..
}
}
}
//+------------------------------------------------------------------+
//| |
//+------------------------------------------------------------------+
__forceinline void BigUInteger::operator/=(BigUInteger& b)
{
DivModInPlace<BigUintegerDiv>(b);
}
//+------------------------------------------------------------------+
BigUInteger BigUInteger::operator/(BigUInteger& b) const
{
BigUInteger v = this;
v /= b;
return BigUInteger(v.m_v, v.m_v_s);
}
//+------------------------------------------------------------------+
void BigUInteger::operator/=(const long _b)
{
//---
BIG_UINTEGER_FULL_DIV_ALG(m_v[i])
//---
// peude dehjar 0
// 256 | 3 -- aqui pro jeemplo 2/3=0
// 0
// 256 | 3
// 24 08 ---
// -16 | 3
// 085
// 15
// -1
// quedo 085
// entonces eso lo tenemos que limpiar 85 resto 1
BIGNUMBERSBYLEO_CLEAN_HIGH_ZEROS
}
//+------------------------------------------------------------------+
BigUInteger BigUInteger::operator/(const long _b) const
{
BigUInteger v = this;
v /= _b;
return BigUInteger(v.m_v, v.m_v_s);
}
//+------------------------------------------------------------------+
//| |
//+------------------------------------------------------------------+
__forceinline void BigUInteger::operator%=(BigUInteger& b)
{
DivModInPlace<BigUintegerMod>(b);
}
//+------------------------------------------------------------------+
BigUInteger BigUInteger::operator%(BigUInteger& b) const
{
BigUInteger v = this;
v /= b;
return BigUInteger(v.m_v, v.m_v_s);
}
//+------------------------------------------------------------------+
void BigUInteger::operator%=(const long _b)
{
//--- algorimo en comun
BIG_UINTEGER_FULL_DIV_ALG(m_v[i])
//--- el resto siempre queda en un rango menor a ULONG_MAX o igual asi que truncamos el tamaño
m_v_s = 1; // truncamos el size
m_v[0] = resto; // asiganamos
}
//+------------------------------------------------------------------+
ulong BigUInteger::operator%(const long _b) const
{
ulong q;
BIG_UINTEGER_FULL_DIV_ALG(q)
return resto;
}
//+------------------------------------------------------------------+
//| |
//+------------------------------------------------------------------+
ulong BigUInteger::Gdc(ulong r) const
{
//---
ulong prev_r = r;
//--
// Primera division (Big / nuimber)
r = this % r; // div / r
// Luego de aqui un gdc normal dado que r<r (osea cabe en ulong)
//--- apartir de ahora gcd entre prev_r y r
if(r == 0ULL)
return prev_r;
// usaremos algortimo binario para esto (stein)
// Lo primro que haremos sera calclar el ctz (baiinamte el min 2s uq ehay en ambos)
ulong full = r | prev_r;
full = TSNTABLES_SWAR_64_DEJAR_SOLO_MINUS_SIG_BYTE(full);
// la idea es ver cuantos "2" comunes tenemos
const int shift = TSNTABLES_SWAR_64_GET_BIT(full);
//--- ahora pelamos a (u (r))
// gcd(u, 2v) = gcd(u, v), solo si u es impar esto dado qeu 2 no es un divisor comun entre dos
// reduimos su valor
full = TSNTABLES_SWAR_64_DEJAR_SOLO_MINUS_SIG_BYTE(r);
r >>= TSNTABLES_SWAR_64_GET_BIT(full);
//---
while(r)
{
// prev_r posiblemte viene de ser par o impar neismo shjacelro impar.
//-- quyitamos los 2s (la idea tambien es hacer a prevr = v impar)
full = TSNTABLES_SWAR_64_DEJAR_SOLO_MINUS_SIG_BYTE(prev_r);
prev_r >>= TSNTABLES_SWAR_64_GET_BIT(full);
//--- ahora si restamos
// la idea es que el mod clasifiaco para obtener el resto
// lo podemos sacar restamos sucesivamnte (claramente en mas pasos pero se logra)
// aqui tamiben se usa: gdc(u,v)=gdc(u,v-u) (como ambos son impares (por disñeo el 1 siempre activo))
if(prev_r < r)
{
// punto de cambio... (igual que el temp previo. en la versino cno %)
// aqui es menor .. resta al revez y temporal para volver a asingar
const ulong t = prev_r;
prev_r = r - prev_r;
r = t;
}
else
prev_r = prev_r - r;
}
//---
return prev_r << shift;
}
//+------------------------------------------------------------------+
//| |
//+------------------------------------------------------------------+
bool BigUInteger::IsProbablePrime(int rounds)
{
return true;
}
//+------------------------------------------------------------------+
//| |
//+------------------------------------------------------------------+
//a=this
//b=b
BigUInteger BigUInteger::GdcExtendedRetX(const BigUInteger& b)
{
//--
return this;
}
//+------------------------------------------------------------------+
//| |
//+------------------------------------------------------------------+
BigUInteger BigUInteger::PowMod(const long e, const BigUInteger &n)
{
BigUInteger resultado(1);
return BigUInteger();
}
//--- end namespace
}
//+------------------------------------------------------------------+
//| |
//+------------------------------------------------------------------+
/*
a b = A *
c d = B
- -
(Carry) (a*d+Carry)(b*d)
(c*a) (c*b)
--------------------------
*/
//+------------------------------------------------------------------+
//
#endif // BIGNUMBERSBYLEO_SRC_BASE_MAIN_MQH
// a += b
View git blame Copy permalink