//+------------------------------------------------------------------+ //| 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 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 __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 // 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 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(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(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>= 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