//+------------------------------------------------------------------+ //| 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_UINT_MQH #define BIGNUMBERSBYLEO_SRC_BASE_UINT_MQH //+------------------------------------------------------------------+ //| | //+------------------------------------------------------------------+ #include "Common.mqh" //+------------------------------------------------------------------+ //| | //+------------------------------------------------------------------+ namespace TSN { //+------------------------------------------------------------------+ //| | //+------------------------------------------------------------------+ // 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 //+------------------------------------------------------------------+ //| | //+------------------------------------------------------------------+ // ahora mismo usaremos el contructor normal // dado que siempre itera al menos 1 vez #define BigUintegerConstCheck(v, vs) BigUInteger(v, vs) //+------------------------------------------------------------------+ //| Clase biguinteger | //+------------------------------------------------------------------+ struct BigUInteger : public BigIBase { public: //--- Constructores //--- tomando prestado BigUInteger(ulong& v[], const int vs_8); BigUInteger(const int vs_8, ulong& v[]); //-- valor BigUInteger(const ulong number, int reserve); BigUInteger(ENUM_BIGNUMBERBYLEO_STR_BASE base, const string& str); //-- desde bytes BigUInteger(const uchar& bytes[], int byteorder); //-- reserva \ default BigUInteger(int initial_reserve); BigUInteger(); //--- unitarios //-- Negacion BigUInteger operator~() const; //--- bit simples //-- and void operator&=(const BigUInteger& b); BigUInteger operator&(const BigUInteger& b) const; __forceinline ulong operator&(const ulong b) const; //-- or void operator|=(const BigUInteger& b); BigUInteger operator|(const BigUInteger& b) const; BigUInteger operator|(const ulong b) const; //-- xor void operator^=(const BigUInteger& b); BigUInteger operator^(const BigUInteger& b) const; BigUInteger operator^(const ulong b) const; //-- dezplazamientos // left __forceinline void operator<<=(const ulong b) { UShiftLeft(b); } BigUInteger operator<<(const ulong b) const; // right void operator>>=(const ulong b); BigUInteger operator>>(const ulong b) const; //---- aritmeticos //- suma void operator+=(const BigUInteger& b); BigUInteger operator+(const BigUInteger& b) const; void operator+=(const ulong b); BigUInteger operator+(const ulong b) const; //- resta void operator-=(const BigUInteger& b); BigUInteger operator-(const BigUInteger& b) const; void operator-=(const ulong b); BigUInteger operator-(const ulong b) const; //- mul void operator*=(const BigUInteger& b); BigUInteger operator*(const BigUInteger& b) const; void operator*=(const ulong b); BigUInteger operator*(const ulong 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 ulong b); BigUInteger operator/(const ulong b) const; //- mod __forceinline void operator%=(BigUInteger& b); BigUInteger operator%(BigUInteger& b) const; void operator%=(const ulong b); ulong operator%(const ulong b) const; //--- compracion __forceinline int Cmp(const BigIBase& b) const { return CmpInt(b); } //-- basicas // big bool operator>(const BigUInteger& b) const; bool operator>=(const BigUInteger& b) const; bool operator==(const BigUInteger& b) const; // normal __forceinline bool operator>(const ulong b) const { return m_v_s > 1 || (m_v[0] > b) ; } __forceinline bool operator>=(const ulong b) const { return m_v_s > 1 || (m_v[0] >= b); } __forceinline bool operator==(const ulong b) const { return m_v_s > 1 || (m_v[0] == b); } //-- derivadas // big __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); } // normal __forceinline bool operator!=(const ulong b) const { return !(this == b); } __forceinline bool operator<(const ulong b) const { return !(this >= b); } __forceinline bool operator<=(const ulong b) const { return !(this > b); } //--- complejos // this = base // e = exp (long) // n = (mod n) void PowMod(const ulong e, const BigUInteger& n); void PowMod(const BigUInteger& e, const BigUInteger &n); // Es probasblemnete un primo?¿ template bool IsProbablePrime(int rounds) const; // GCD Maximo comun divisor normal // = gdc(this, v) (retrona ulong) ulong Gdc(const ulong v) const; //--- From \ LLenar // dataos ranodm (llena en unr ango menor a other) template __forceinline void FillRandomRange(const BigUInteger& other); // desde bytes void FromBytesLE(const uchar& buf[]); void FromBytesBE(const uchar& buf[]); // de otro (swap robando buffer) __forceinline void RobarDe(BigUInteger& other); // formato DER (tag) (len) (Content) int FromDER(const uchar& buf[], int r); //--- Utilidades //--- To (converiones) //- 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; //- DER Format // k=numero de bytes a esceribir // wlen=byte de esvritua de len // is_high_encinado=marca si el mas alto qeu tiene dato tiene el bti 7 encenidod (para el 0x0) int DerEstimateLen(bool& is_high_encendido, int& k, uchar& lenw) const; //-- string int ToString(uchar& buf[]) const; //---- static __forceinline int AbsS(int v) { return v; } }; //+------------------------------------------------------------------+ //| | //+------------------------------------------------------------------+ /* 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 */ //+------------------------------------------------------------------+ //| Constructores | //+------------------------------------------------------------------+ BigUInteger::BigUInteger(ulong &v[], const int vs_8) : BigIBase(v, vs_8) { } //+------------------------------------------------------------------+ BigUInteger::BigUInteger(const int vs_8, ulong& v[]) : BigIBase(vs_8, v) { } //+------------------------------------------------------------------+ BigUInteger::BigUInteger(const ulong number, int reserve) : BigIBase(number, reserve) { } //+------------------------------------------------------------------+ BigUInteger::BigUInteger(int initial_reserve) : BigIBase(initial_reserve) { } //+------------------------------------------------------------------+ BigUInteger::BigUInteger() : BigIBase() { } //+------------------------------------------------------------------+ //| Propios contructors | //+------------------------------------------------------------------+ BigUInteger::BigUInteger(ENUM_BIGNUMBERBYLEO_STR_BASE base, const string& str) { //--- m_v_s = BIGNUMERBYLEO_INITIAL_SIZE_ZERO; //--- const int digtis = g_tsn_biguinteger_base_max[base]; if(digtis < 0) { // En caso de error lo inciamos como 0 ArrayResize(m_v, BIGNUMERBYLEO_INITIAL_RESERVE, BIGNUMERBYLEO_INITIAL_RESERVE); 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) : BigIBase() { if(byteorder == BIGUINTEGER_LOADBYTES_BE) FromBytesBE(bytes); else FromBytesLE(bytes); } //+------------------------------------------------------------------+ //| | //+------------------------------------------------------------------+ template __forceinline void BigUInteger::FillRandomRange(const BigUInteger& other) { m_v_s = other.m_v_s; TRandom::RandomUlongArrRange(m_v, m_v_s, other[m_v_s - 1]); } // n_menos2 //+------------------------------------------------------------------+ //| | //+------------------------------------------------------------------+ void BigUInteger::FromBytesLE(const uchar& buf[]) { //--- const int k = ArraySize(buf); if(k > ArraySize(m_v)) ArrayResize(m_v, k, k); //--- int j; CNumberUtils::ULL_LoadFromBytesLE(k, m_v, m_v_s, buf, j); //--- Limpiamos zeros altos.. BIGNUMBERSBYLEO_CLEAN_HIGH_ZEROS(m_v, m_v_s) } //+------------------------------------------------------------------+ // 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); if(k > ArraySize(m_v)) ArrayResize(m_v, k, k); //--- int j; CNumberUtils::ULL_LoadFromBytesBE(k, m_v, m_v_s, buf, j); //--- Limpiamos zeros altos.. BIGNUMBERSBYLEO_CLEAN_HIGH_ZEROS(m_v, m_v_s) } //+------------------------------------------------------------------+ //| DER Functions | //+------------------------------------------------------------------+ int BigUInteger::FromDER(const uchar &buf[], int r) { //--- tag if(buf[r++] != CBL_ASN1_TAG_INTEGER) // tag integer return -1; // invalido //--- len int t = buf[r++]; if((t & CBL_ASN1_MASK_BYTEALTO) != 0) { //--- const int lr = r; t &= CBL_ASN1_MASK_CLEAN_BYTEALTO; //--- // Ahora de aqui puieden venir 127 bytes que peuden representar unnumero enorme // Pero como tal?¿ en MQL5 una array de ulongs max size= INT_MAX // Transofmrado a bytes 17K Mill aprox... asi que seria un numero en bin tal que // 0100 0000 0000 0000 0000 0000 0000 0000 0000 // algo de 36 bits de numero que caben en un ulong osea solo podemos leer algo de 5 bytes aprox (4.5) r += t; // numero de bytes del numero //--- t = 0; // quizas meter un guard mas k<32 ahi ya se deitne pro qeu no tendira mas sentido?¿ // seguir leyendo bytes dado que pare mpar buf no peude tener mas lenght que eso... (int) for(int i = r - 1, k = 0; i >= lr && k < 32; i--, k += 8) { t |= int(buf[i]) << k; } // listo ya tenemos el numero de bytes.. ahora.. } /* con la convencion entonces si se peude represnetar el 0... else if(t == 1 && buf[r] == 0) // 2 pos es 0 entonces mvs 0 { BIGNUMBERBYLEO_ZERO return ++r; }*/ // tal cual sin nada.. // ahora r apunta al byte justo a leer const int lr = r; //------ Ahora toca leer el numero en si //--- const int sob = t & 7; // % 8 cuantos sobraan const int blocks = t - sob; // Cuantos bloques enteros procesaremos // bloque=byte (mal nomrbe quizas) //--- Ahora si (leemos como BE) const int fr = r + blocks; r = fr - 1; m_v_s = 0; // bloques completos for(; r >= lr;) { //--- 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 = lr + (sob - 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++; } //--- return fr; // hasta donde leimos (nueva posicion para leer) } //+------------------------------------------------------------------+ int BigUInteger::DerEstimateLen(bool& is_high_encendido, int& k, uchar& lenw) const { //--- if(BIGNUMERBYLEO_UINTEGER_IZ_ZERO) { k = 1; is_high_encendido = false; lenw = 1; // 1+0 return 3; } //--- const int vs_bytes = (m_v_s << 3); // en bytes const ulong high = m_v[m_v_s - 1]; // alto const int clz = CBitTricks::CLZ(high); // clz k = vs_bytes - (clz >> 3); // k is_high_encendido = (uchar(high >> (((63 - clz) >> 3) << 3)) & 0x80) != 0; // alto encendido const int number_len_size = is_high_encendido + k; // el len del numero en si //--- calculo del len (final) uchar count = 1; if(number_len_size > 127) { int l = number_len_size; // en cuantos bytes reqeurrimos (extra) do { l >>= 8; count++; } while(l > 0); lenw = CBL_ASN1_MASK_BYTEALTO | count; } else { lenw = uchar(number_len_size); } //--- final retornamso todo lo que estiamso para el der return 1 + count + number_len_size; } //+------------------------------------------------------------------+ #define BIGUINTEGERBYLEO_DER_WRITE(buf, w, num, is_high_encendido, k, lenw, total) \ { \ buf[w++] = CBL_ASN1_TAG_INTEGER; \ CBL_ASN1_U_WRITELEN(buf, w, lenw, total) \ if(is_high_encendido) \ buf[w++] = 0x00; \ const int blocks = k >> 3; \ const int sob = k & 7; \ int r = blocks - 1; \ for(; r >= 0; r--) \ { \ const ulong v = num[r]; \ 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); \ } \ if(sob) \ { \ r++; \ const ulong v = num[r]; \ for(int j = ((sob << 3) - 8); j >= 0; j -= 8) \ buf[w++] = uchar(v >> j); \ } \ } //+------------------------------------------------------------------+ //| To Bytes | //+------------------------------------------------------------------+ 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; else if(k == BIGUINTEGER_TOBYTES_EXACTK) { // en este caso -2 exacto miramos el mas alto // y en base a eso reducimos k = vs_bytes - (CBitTricks::CLZ(m_v[m_v_s - 1]) >> 3); } //--- 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; else if(k == BIGUINTEGER_TOBYTES_EXACTK) { // en este caso -2 exacto miramos el mas alto // y en base a eso reducimos k = vs_bytes - (CBitTricks::CLZ(m_v[m_v_s - 1]) >> 3); } //--- 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; } //+------------------------------------------------------------------+ //| To Str | //+------------------------------------------------------------------+ 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 BigUintegerConstCheck(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[]; const int vs = BIGNUMERBYLEO_MIN(b.m_v_s, m_v_s); //--- ArrayResize(v, vs); //--- for(int i = 0; i < vs; i++) v[i] = m_v[i] & b.m_v[i]; //--- return BigUintegerConstCheck(v, vs); } //+------------------------------------------------------------------+ __forceinline ulong BigUInteger::operator&(const ulong b) const { return m_v[0] & 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) ArrayCopy(m_v, b.m_v, i, i, m_v_s); } } //+------------------------------------------------------------------+ 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 ArrayCopy(v, b.m_v, i, i, vs); } //--- return BigUintegerConstCheck(v, vs); } //+------------------------------------------------------------------+ BigUInteger BigUInteger::operator|(const ulong b) const { //--- ulong v[]; ArrayResize(v, m_v_s); v[0] = m_v[0] | b; ArrayCopy(v, m_v, 1, 1, m_v_s); //--- return BigUintegerConstCheck(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) ArrayCopy(m_v, b.m_v, i, i, m_v_s); } } //+------------------------------------------------------------------+ 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 ArrayCopy(v, b.m_v, i, i, vs); } //--- return BigUintegerConstCheck(v, vs); } //+------------------------------------------------------------------+ BigUInteger BigUInteger::operator^(const ulong b) const { //--- hay data alemnos 1 ulong v[]; ArrayResize(v, m_v_s); v[0] = m_v[0] ^ b; ArrayCopy(v, m_v, 1, 1, m_v_s); //--- return BigUintegerConstCheck(v, m_v_s); } //+------------------------------------------------------------------+ //| | //+------------------------------------------------------------------+ // crea uno nuevo BigUInteger BigUInteger::operator<<(const ulong b) const { //--- chekeamos 0 dado que 0<> 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 ulong b) { //--- neceistamos chekear dado que si size=1 pero "jalamos" 1 entonces queda en 0 (no peude ser 0 el size) const int el_sh_b = int(b >> 6); if(el_sh_b >= m_v_s) { BIGNUMBERBYLEO_ZERO return; } //--- const int el_sh = int(b & 63); // numero de bits sobrandses en b if(el_sh == 0) { //--- 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 + 1; 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 } BIGNUMBERSBYLEO_CLEAN_HIGH_ZEROS(m_v, m_v_s) } //+------------------------------------------------------------------+ BigUInteger BigUInteger::operator>>(const ulong b) const { //--- neceistamos chekear dado que si size=1 pero "jalamos" 1 entonces queda en 0 (no peude ser 0 el size) const int el_sh_b = int(b >> 6); if(el_sh_b >= m_v_s) return BigUInteger(0ULL, 1); //--- const int el_sh = int(b & 63); // numero de bits sobrandses en b if(el_sh == 0) { //--- 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 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 + 1; 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 } BIGNUMBERSBYLEO_CLEAN_HIGH_ZEROS(v, vs) 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 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 ulong 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(m_v, m_v_s) // maneo de underflow } //+------------------------------------------------------------------+ BigUInteger BigUInteger::operator-(const BigUInteger& b) const { BigUInteger v = this; v -= b; return BigUInteger(v.m_v, v.m_v_s); } //+------------------------------------------------------------------+ // si es 0 da underflow. void BigUInteger::operator-=(const ulong b) { //--- // Chekea ambos daod qeu b en caso pueda tener mas bytes esos ya no se procesan 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(m_v, m_v_s) } else { // No hay borrow m_v[0] = res_f; // tal cual } } //+------------------------------------------------------------------+ BigUInteger BigUInteger::operator-(const ulong 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; } //--- BIGNUMBERSBYLEO_CLEAN_HIGH_ZEROS(v, 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 //--- 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 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 ulong 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) \ 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 BIGNUMBERBYLEO_ZERO } // 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 = CBitTricks::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 ulong bn[]; ArraySwap(bn, b.m_v); // 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); // Ahora dezplazamos y escalamos //--- Normalizamos B // Aplicamos .. para empzar a bn ArrayResize(bn, divisor_len); for(int i = divisor_len - 1; i > 0; i--) bn[i] = (b[i] << shift) | (b[i - 1] >> shr); bn[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 { //--- Copiamos tal cual el dividendo const int ns = m_v_s + 1; // Si es div necesitamos un intermdio para el resto // asi que no podemos eleigr m_v por que ya esta ocupado solo copiamos if(sizeof(TOp) == BIGINTGERBYLEO_DIVMOD_V_DIV) { ArrayResize(div, ns); ArrayCopy(div, m_v, 0, 0, m_v_s); } else { if(ns > ArraySize(m_v)) ArrayResize(m_v, ns); // lo agrandamos si hace falta // ahora mismo div sera=m_v ArraySwap(div, m_v); } //--- 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); // 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"); // intercambiamos ahora m_v le quita lo quie le dio a div ArraySwap(m_v, div); //--- BIGNUMBERSBYLEO_CLEAN_HIGH_ZEROS(m_v, m_v_s) //--- // Le devolvemos lo qeu tomamos prestado a b ArraySwap(b.m_v, bn); // 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 ulong 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(m_v, m_v_s) } //+------------------------------------------------------------------+ BigUInteger BigUInteger::operator/(const ulong 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 ulong 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 ulong b) const { ulong q; BIG_UINTEGER_FULL_DIV_ALG(q) return resto; } //+------------------------------------------------------------------+ //| | //+------------------------------------------------------------------+ ulong BigUInteger::Gdc(ulong r) const { //--- // a = this // b = r (prev_r) ulong prev_r = r; //-- // Primera division (Big / nuimber) r = this % r; // div / r // Luego de aqui un gdc normal dado que r>= TSNTABLES_CTZ_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_BIT_DEJAR_SOLO_MINUS_SIG_BYTE(prev_r); prev_r >>= TSNTABLES_CTZ_64_GET_BIT(full); //--- ahora si restamos // la idea con restar es que "esa division" normal la podemos hacer resntado x veces > 0, entonces aqui lo mismo // pero tenemos que tener cuidado con los negativos en ese caso "swap" de resta //--- // 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 -= r; } //--- return prev_r << shift; } //+------------------------------------------------------------------+ //| | //+------------------------------------------------------------------+ template bool BigUInteger::IsProbablePrime(int rounds) const { // 1 es primo if(this < 2) return false; // 2 es primo // 3 para evitar que (n-2 = 1 y generar un numero [0,0] aletaorio // co sa que no tiene sntido asi que lo descartamos aqui) if(this == 2 || this == 3) return true; // todo par no es primro (>2) if(BIGNUMERBYLEO_UINTEGER_IZ_PAR) return false; // Ahora si empezemos primero lo descomponemos // copia #1 const BigUInteger n_menos1 = this - 1; // copia #2 const BigUInteger n_menos2 = n_menos1 - 1; // copia #3 // CTZ seguro dado qeu mnoes como minimo sera 4 (5-1) const ulong s = n_menos1.Ctz(); // ahora aplicamos dicho s a d (d>>s) const BigUInteger d = n_menos1 >> s; // assing //---- // copia #4 BigUInteger a(EMPTY_INITIAL_RESERVE, n_menos2.m_v_s); // reservamos exacta para a for(int i = 0; i < rounds; i++) { // [0, n-2] excl, (a = res) // intemante no modifca tamaño solo llena (nada de resize) //TRandom::RandomBigRange(n_menos2, a); a.FillRandomRange(n_menos2); // ajustamos 2> a += 2; // a=base // d=Exp // this=n a.PowMod(d, this); // inplace if(a == 1 || a == n_menos1) continue; bool compuesto = true; for(ulong r = 1; r < s; r++) { a.PowMod(2, this); // a = a^2 mod n , inplace if(a == n_menos1) { compuesto = false; break; } } //--- if(compuesto) return false; } return true; } //+------------------------------------------------------------------+ //| | //+------------------------------------------------------------------+ // pow mod inplace void BigUInteger::PowMod(const ulong e, const BigUInteger &n) { } //+------------------------------------------------------------------+ void BigUInteger::PowMod(const BigUInteger& e, const BigUInteger &n) { } //--- end namespace } //+------------------------------------------------------------------+ //| | //+------------------------------------------------------------------+ /* a b = A * c d = B - - (Carry) (a*d+Carry)(b*d) (c*a) (c*b) -------------------------- */ //+------------------------------------------------------------------+ // #endif // BIGNUMBERSBYLEO_SRC_BASE_UINT_MQH // a += b