2026-09-07 21:55:02 -05:00 | | | //+------------------------------------------------------------------+
|
| | | //| 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
|
| | |
|
| | |
|
| | | //+------------------------------------------------------------------+
|
| | | //| |
|
| | | //+------------------------------------------------------------------+
|
2026-09-09 20:01:20 -05:00 | | | #include "Common.mqh"
|
2026-09-07 21:55:02 -05:00 | | |
|
| | | //+------------------------------------------------------------------+
|
| | | //| |
|
| | | //+------------------------------------------------------------------+
|
| | | 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
|
| | |
|
| | |
|
2026-09-10 08:11:32 -05:00 | | | //+------------------------------------------------------------------+
|
| | | //| |
|
| | | //+------------------------------------------------------------------+
|
2026-09-11 12:15:57 -05:00 | | | // ahora mismo usaremos el contructor normal
|
2026-09-10 09:23:17 -05:00 | | | // dado que siempre itera al menos 1 vez
|
| | | #define BigUintegerConstCheck(v, vs) BigUInteger(v, vs)
|
2026-09-10 08:11:32 -05:00 | | |
|
2026-09-07 21:55:02 -05:00 | | | //+------------------------------------------------------------------+
|
| | | //| Clase biguinteger |
|
| | | //+------------------------------------------------------------------+
|
2026-09-09 20:01:20 -05:00 | | | struct BigUInteger : public BigIBase
|
2026-09-07 21:55:02 -05:00 | | | {
|
| | | public:
|
| | | //--- Constructores
|
2026-09-10 07:16:18 -05:00 | | | //--- tomando prestado
|
2026-09-07 21:55:02 -05:00 | | | BigUInteger(ulong& v[], const int vs_8);
|
2026-09-10 07:16:18 -05:00 | | | BigUInteger(const int vs_8, ulong& v[]);
|
2026-09-07 21:55:02 -05:00 | | |
|
2026-09-10 07:16:18 -05:00 | | | //-- valor
|
| | | BigUInteger(const ulong number, int reserve);
|
2026-09-10 08:11:32 -05:00 | | | BigUInteger(ENUM_BIGNUMBERBYLEO_STR_BASE base, const string& str);
|
2026-09-07 21:55:02 -05:00 | | |
|
2026-09-10 07:16:18 -05:00 | | | //-- desde bytes
|
2026-09-07 21:55:02 -05:00 | | | BigUInteger(const uchar& bytes[], int byteorder);
|
| | |
|
2026-09-10 07:16:18 -05:00 | | | //-- reserva \ default
|
| | | BigUInteger(int initial_reserve);
|
| | | BigUInteger();
|
| | |
|
2026-09-07 21:55:02 -05:00 | | |
|
| | | //--- 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
|
2026-09-11 14:45:51 -05:00 | | | __forceinline void operator<<=(const ulong b) { UShiftLeft(b); }
|
2026-09-07 21:55:02 -05:00 | | | 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 <typename TOp>
|
| | | void DivModInPlace(BigUInteger& b);
|
| | |
|
| | | //- div
|
| | | // nota no es const BigUInteger& b dado que como tal NO modificamso b
|
| | | // solo que nos tomoamos prestado su array para lectura noma...
|
| | | __forceinline void operator/=(BigUInteger& b);
|
| | | BigUInteger operator/(BigUInteger& b) const;
|
| | | void operator/=(const 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
|
2026-09-11 12:15:57 -05:00 | | | __forceinline int Cmp(const BigIBase& b) const { return CmpInt<BigUInteger>(b); }
|
| | |
|
2026-09-07 21:55:02 -05:00 | | | //-- 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 <typename TRandom>
|
| | | 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 <typename TRandom>
|
| | | __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);
|
| | |
|
2026-09-09 12:01:07 -05:00 | | |
|
2026-09-07 21:55:02 -05:00 | | | //--- 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;
|
2026-09-11 12:15:57 -05:00 | | |
|
| | | //----
|
| | | static __forceinline int AbsS(int v) { return v; }
|
2026-09-07 21:55:02 -05:00 | | | };
|
| | |
|
| | | //+------------------------------------------------------------------+
|
| | | //| |
|
| | | //+------------------------------------------------------------------+
|
| | | /* 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)
|
2026-09-09 20:01:20 -05:00 | | | : BigIBase(v, vs_8)
|
2026-09-07 21:55:02 -05:00 | | | {
|
| | | }
|
| | |
|
2026-09-08 21:37:36 -05:00 | | | //+------------------------------------------------------------------+
|
2026-09-10 07:16:18 -05:00 | | | BigUInteger::BigUInteger(const int vs_8, ulong& v[])
|
| | | : BigIBase(vs_8, v)
|
2026-09-08 21:37:36 -05:00 | | | {
|
| | | }
|
| | |
|
2026-09-07 21:55:02 -05:00 | | | //+------------------------------------------------------------------+
|
2026-09-10 07:16:18 -05:00 | | | BigUInteger::BigUInteger(const ulong number, int reserve)
|
| | | : BigIBase(number, reserve)
|
2026-09-07 21:55:02 -05:00 | | | {
|
| | | }
|
2026-09-09 20:01:20 -05:00 | | |
|
2026-09-07 21:55:02 -05:00 | | | //+------------------------------------------------------------------+
|
2026-09-10 07:16:18 -05:00 | | | BigUInteger::BigUInteger(int initial_reserve)
|
| | | : BigIBase(initial_reserve)
|
2026-09-07 21:55:02 -05:00 | | | {
|
| | | }
|
| | |
|
| | | //+------------------------------------------------------------------+
|
| | | BigUInteger::BigUInteger()
|
2026-09-09 20:01:20 -05:00 | | | : BigIBase()
|
2026-09-07 21:55:02 -05:00 | | | {
|
| | | }
|
| | |
|
2026-09-09 20:01:20 -05:00 | | | //+------------------------------------------------------------------+
|
| | | //| Propios contructors |
|
2026-09-07 21:55:02 -05:00 | | | //+------------------------------------------------------------------+
|
2026-09-10 08:11:32 -05:00 | | | BigUInteger::BigUInteger(ENUM_BIGNUMBERBYLEO_STR_BASE base, const string& str)
|
2026-09-07 21:55:02 -05:00 | | | {
|
2026-09-09 20:01:20 -05:00 | | | //---
|
2026-09-10 09:23:17 -05:00 | | | m_v_s = BIGNUMERBYLEO_INITIAL_SIZE_ZERO;
|
2026-09-09 20:01:20 -05:00 | | |
|
2026-09-07 21:55:02 -05:00 | | | //---
|
| | | const int digtis = g_tsn_biguinteger_base_max[base];
|
| | | if(digtis < 0)
|
| | | {
|
| | | // En caso de error lo inciamos como 0
|
2026-09-10 07:16:18 -05:00 | | | ArrayResize(m_v, BIGNUMERBYLEO_INITIAL_RESERVE, BIGNUMERBYLEO_INITIAL_RESERVE);
|
2026-09-07 21:55:02 -05:00 | | | 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)
|
2026-09-10 07:16:18 -05:00 | | | : BigIBase()
|
2026-09-07 21:55:02 -05:00 | | | {
|
| | | if(byteorder == BIGUINTEGER_LOADBYTES_BE)
|
| | | FromBytesBE(bytes);
|
| | | else
|
| | | FromBytesLE(bytes);
|
| | | }
|
| | |
|
2026-09-09 12:01:07 -05:00 | | |
|
2026-09-07 21:55:02 -05:00 | | | //+------------------------------------------------------------------+
|
| | | //| |
|
| | | //+------------------------------------------------------------------+
|
| | | template <typename TRandom>
|
| | | __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..
|
2026-09-10 08:11:32 -05:00 | | | BIGNUMBERSBYLEO_CLEAN_HIGH_ZEROS(m_v, m_v_s)
|
2026-09-07 21:55:02 -05:00 | | | }
|
| | |
|
| | |
|
| | | //+------------------------------------------------------------------+
|
| | | // 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..
|
2026-09-10 08:11:32 -05:00 | | | BIGNUMBERSBYLEO_CLEAN_HIGH_ZEROS(m_v, m_v_s)
|
2026-09-07 21:55:02 -05:00 | | | }
|
| | |
|
| | |
|
| | | //+------------------------------------------------------------------+
|
2026-09-10 08:11:32 -05:00 | | | //| DER Functions |
|
2026-09-07 21:55:02 -05:00 | | | //+------------------------------------------------------------------+
|
| | | 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..
|
| | | }
|
2026-09-10 09:23:17 -05:00 | | | /* con la convencion entonces si se peude represnetar el 0...
|
2026-09-10 07:16:18 -05:00 | | | else
|
2026-09-10 09:23:17 -05:00 | | | if(t == 1 && buf[r] == 0) // 2 pos es 0 entonces mvs 0
|
| | | {
|
| | | BIGNUMBERBYLEO_ZERO
|
| | | return ++r;
|
| | | }*/
|
2026-09-10 07:16:18 -05:00 | | |
|
2026-09-07 21:55:02 -05:00 | | | // 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)
|
| | | }
|
| | |
|
2026-09-10 08:11:32 -05:00 | | |
|
2026-09-07 21:55:02 -05:00 | | | //+------------------------------------------------------------------+
|
2026-09-10 08:11:32 -05:00 | | | int BigUInteger::DerEstimateLen(bool& is_high_encendido, int& k, uchar& lenw) const
|
| | | {
|
| | | //---
|
| | | if(BIGNUMERBYLEO_UINTEGER_IZ_ZERO)
|
| | | {
|
| | | k = 1;
|
| | | is_high_encendido = false;
|
2026-09-10 09:23:17 -05:00 | | | lenw = 1; // 1+0
|
| | | return 3;
|
2026-09-10 08:11:32 -05:00 | | | }
|
| | |
|
| | | //---
|
| | | 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 |
|
2026-09-07 21:55:02 -05:00 | | | //+------------------------------------------------------------------+
|
| | | 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;
|
| | | }
|
| | |
|
| | |
|
| | | //+------------------------------------------------------------------+
|
2026-09-10 08:11:32 -05:00 | | | //| To Str |
|
2026-09-07 21:55:02 -05:00 | | | //+------------------------------------------------------------------+
|
| | | 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];
|
2026-09-10 08:11:32 -05:00 | | | return BigUintegerConstCheck(v, m_v_s);
|
2026-09-07 21:55:02 -05:00 | | | }
|
| | |
|
| | | //+------------------------------------------------------------------+
|
| | | //| 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[];
|
2026-09-10 07:16:18 -05:00 | | | const int vs = BIGNUMERBYLEO_MIN(b.m_v_s, m_v_s);
|
2026-09-07 21:55:02 -05:00 | | |
|
| | | //---
|
| | | ArrayResize(v, vs);
|
| | |
|
| | | //---
|
| | | for(int i = 0; i < vs; i++)
|
| | | v[i] = m_v[i] & b.m_v[i];
|
| | |
|
| | | //---
|
2026-09-10 08:11:32 -05:00 | | | return BigUintegerConstCheck(v, vs);
|
2026-09-07 21:55:02 -05:00 | | | }
|
| | |
|
| | | //+------------------------------------------------------------------+
|
| | | __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)
|
2026-09-10 07:16:18 -05:00 | | | ArrayCopy(m_v, b.m_v, i, i, m_v_s);
|
2026-09-07 21:55:02 -05:00 | | | }
|
| | | }
|
| | | //+------------------------------------------------------------------+
|
| | | 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
|
2026-09-10 07:16:18 -05:00 | | | ArrayCopy(v, b.m_v, i, i, vs);
|
2026-09-07 21:55:02 -05:00 | | | }
|
| | | //---
|
2026-09-10 08:11:32 -05:00 | | | return BigUintegerConstCheck(v, vs);
|
2026-09-07 21:55:02 -05:00 | | | }
|
| | |
|
| | | //+------------------------------------------------------------------+
|
| | | BigUInteger BigUInteger::operator|(const ulong b) const
|
| | | {
|
| | | //---
|
| | | ulong v[];
|
| | | ArrayResize(v, m_v_s);
|
| | | v[0] = m_v[0] | b;
|
2026-09-10 07:16:18 -05:00 | | | ArrayCopy(v, m_v, 1, 1, m_v_s);
|
2026-09-07 21:55:02 -05:00 | | | //---
|
2026-09-10 08:11:32 -05:00 | | | return BigUintegerConstCheck(v, m_v_s);
|
2026-09-07 21:55:02 -05:00 | | | }
|
| | |
|
| | | //+------------------------------------------------------------------+
|
| | | //| 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)
|
2026-09-10 07:16:18 -05:00 | | | ArrayCopy(m_v, b.m_v, i, i, m_v_s);
|
2026-09-07 21:55:02 -05:00 | | | }
|
| | | }
|
| | | //+------------------------------------------------------------------+
|
| | | 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
|
2026-09-10 07:16:18 -05:00 | | | ArrayCopy(v, b.m_v, i, i, vs);
|
2026-09-07 21:55:02 -05:00 | | | }
|
| | | //---
|
2026-09-10 08:11:32 -05:00 | | | return BigUintegerConstCheck(v, vs);
|
2026-09-07 21:55:02 -05:00 | | | }
|
| | |
|
| | | //+------------------------------------------------------------------+
|
| | | BigUInteger BigUInteger::operator^(const ulong b) const
|
| | | {
|
| | | //--- hay data alemnos 1
|
| | | ulong v[];
|
| | | ArrayResize(v, m_v_s);
|
| | | v[0] = m_v[0] ^ b;
|
2026-09-10 07:16:18 -05:00 | | | ArrayCopy(v, m_v, 1, 1, m_v_s);
|
2026-09-07 21:55:02 -05:00 | | | //---
|
2026-09-10 08:11:32 -05:00 | | | return BigUintegerConstCheck(v, m_v_s);
|
2026-09-07 21:55:02 -05:00 | | | }
|
| | |
|
| | | //+------------------------------------------------------------------+
|
| | | //| |
|
| | | //+------------------------------------------------------------------+
|
| | | // crea uno nuevo
|
| | | BigUInteger BigUInteger::operator<<(const ulong b) const
|
| | | {
|
2026-09-10 09:23:17 -05:00 | | | //--- chekeamos 0 dado que 0<<x con x grande peude hacer crecer el tamaño artificilaemtne de mvs
|
2026-09-10 07:16:18 -05:00 | | | if(BIGNUMERBYLEO_UINTEGER_IZ_ZERO)
|
| | | return BigUInteger(0ULL, 1);
|
| | |
|
2026-09-07 21:55:02 -05:00 | | | //---
|
| | | 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 ulong b)
|
| | | {
|
2026-09-10 09:23:17 -05:00 | | | //--- neceistamos chekear dado que si size=1 pero "jalamos" 1 entonces queda en 0 (no peude ser 0 el size)
|
2026-09-07 21:55:02 -05:00 | | | const int el_sh_b = int(b >> 6);
|
| | | if(el_sh_b >= m_v_s)
|
| | | {
|
2026-09-10 07:16:18 -05:00 | | | BIGNUMBERBYLEO_ZERO
|
2026-09-07 21:55:02 -05:00 | | | 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
|
| | | }
|
2026-09-10 08:11:32 -05:00 | | | BIGNUMBERSBYLEO_CLEAN_HIGH_ZEROS(m_v, m_v_s)
|
2026-09-07 21:55:02 -05:00 | | | }
|
| | |
|
| | | //+------------------------------------------------------------------+
|
| | | BigUInteger BigUInteger::operator>>(const ulong b) const
|
| | | {
|
2026-09-10 09:23:17 -05:00 | | | //--- neceistamos chekear dado que si size=1 pero "jalamos" 1 entonces queda en 0 (no peude ser 0 el size)
|
2026-09-07 21:55:02 -05:00 | | | const int el_sh_b = int(b >> 6);
|
| | | if(el_sh_b >= m_v_s)
|
2026-09-10 07:16:18 -05:00 | | | return BigUInteger(0ULL, 1);
|
2026-09-07 21:55:02 -05:00 | | |
|
| | | //---
|
| | | 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
|
| | | }
|
2026-09-10 08:11:32 -05:00 | | | BIGNUMBERSBYLEO_CLEAN_HIGH_ZEROS(v, vs)
|
2026-09-07 21:55:02 -05:00 | | | 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
|
2026-09-10 08:11:32 -05:00 | | | BIGNUMBERSBYLEO_CLEAN_HIGH_ZEROS(m_v, m_v_s)
|
2026-09-07 21:55:02 -05:00 | | | // maneo de underflow
|
| | | }
|
| | |
|
| | | //+------------------------------------------------------------------+
|
| | | BigUInteger BigUInteger::operator-(const BigUInteger& b) const
|
| | | {
|
| | | BigUInteger v = this;
|
| | | v -= b;
|
| | | return BigUInteger(v.m_v, v.m_v_s);
|
| | | }
|
| | |
|
| | | //+------------------------------------------------------------------+
|
2026-09-10 07:16:18 -05:00 | | | // si es 0 da underflow.
|
2026-09-07 21:55:02 -05:00 | | | 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
|
2026-09-10 08:11:32 -05:00 | | | BIGNUMBERSBYLEO_CLEAN_HIGH_ZEROS(m_v, m_v_s)
|
2026-09-07 21:55:02 -05:00 | | | }
|
| | | 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;
|
| | | }
|
| | |
|
| | | //---
|
2026-09-10 08:11:32 -05:00 | | | BIGNUMBERSBYLEO_CLEAN_HIGH_ZEROS(v, m_v_s)
|
2026-09-07 21:55:02 -05:00 | | | }
|
| | | 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 <typename TOp>
|
| | | void BigUInteger::DivModInPlace(BigUInteger& b)
|
| | | {
|
| | | //--- Chekeos rapidos antes de ir a por el algoritmo com tal
|
| | | const int divisor_len = b.m_v_s;
|
| | | if(divisor_len == 1)
|
| | | {
|
| | | // Aplicamos para 1 limb
|
| | | if(sizeof(TOp) == BIGINTGERBYLEO_DIVMOD_V_MOD)
|
| | | {
|
| | | this %= b.m_v[0];
|
| | | }
|
| | | else
|
| | | {
|
| | | this /= b.m_v[0];
|
| | | }
|
| | | return;
|
| | | }
|
| | | // el dividendo this es menor que el divisor?¿ en len
|
| | | if(m_v_s < divisor_len)
|
| | | {
|
| | | if(sizeof(TOp) == BIGINTGERBYLEO_DIVMOD_V_DIV)
|
| | | {
|
| | | // cociente=0
|
2026-09-10 07:16:18 -05:00 | | | BIGNUMBERBYLEO_ZERO
|
2026-09-07 21:55:02 -05:00 | | | }
|
| | | // 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
|
2026-09-08 21:37:36 -05:00 | | | ulong bn[];
|
| | | ArraySwap(bn, b.m_v);
|
2026-09-09 12:01:07 -05:00 | | | // BigUInteger bn(b.m_v, divisor_len);
|
2026-09-07 21:55:02 -05:00 | | | ulong div[];
|
| | |
|
| | | //---
|
| | | const int shr = 64 - shift;
|
| | | if(shift > 0)
|
| | | {
|
2026-09-08 21:37:36 -05:00 | | | // Nada, entonces tenemos que modificar bn le devolvemos
|
| | | ArraySwap(b.m_v, bn);
|
2026-09-07 21:55:02 -05:00 | | | // Ahora dezplazamos y escalamos
|
| | |
|
| | | //--- Normalizamos B
|
| | | // Aplicamos .. para empzar a bn
|
2026-09-08 21:37:36 -05:00 | | | ArrayResize(bn, divisor_len);
|
2026-09-07 21:55:02 -05:00 | | | for(int i = divisor_len - 1; i > 0; i--)
|
2026-09-08 21:37:36 -05:00 | | | bn[i] = (b[i] << shift) | (b[i - 1] >> shr);
|
| | | bn[0] = b[0] << shift;
|
2026-09-07 21:55:02 -05:00 | | |
|
| | | //---- 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;
|
2026-09-08 21:37:36 -05:00 | | |
|
| | | // 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
|
2026-09-09 12:01:07 -05:00 | | | // ahora mismo div sera=m_v
|
2026-09-08 21:37:36 -05:00 | | | ArraySwap(div, m_v);
|
| | | }
|
| | |
|
| | | //---
|
2026-09-07 21:55:02 -05:00 | | | 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)
|
2026-09-08 21:37:36 -05:00 | | | ArraySwap(b.m_v, bn); // le devolvemos el valor..
|
2026-09-07 21:55:02 -05:00 | | | }
|
| | | 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");
|
2026-09-08 21:37:36 -05:00 | | | // intercambiamos ahora m_v le quita lo quie le dio a div
|
| | | ArraySwap(m_v, div);
|
2026-09-07 21:55:02 -05:00 | | |
|
2026-09-08 21:37:36 -05:00 | | | //---
|
2026-09-10 08:11:32 -05:00 | | | BIGNUMBERSBYLEO_CLEAN_HIGH_ZEROS(m_v, m_v_s)
|
2026-09-08 21:37:36 -05:00 | | |
|
| | | //---
|
2026-09-07 21:55:02 -05:00 | | | // Le devolvemos lo qeu tomamos prestado a b
|
2026-09-08 21:37:36 -05:00 | | | ArraySwap(b.m_v, bn); // le devolvemos el valor..
|
2026-09-07 21:55:02 -05:00 | | | }
|
| | | }
|
| | | }
|
| | |
|
| | | //+------------------------------------------------------------------+
|
| | | //| |
|
| | | //+------------------------------------------------------------------+
|
| | | __forceinline void BigUInteger::operator/=(BigUInteger& b)
|
| | | {
|
| | | DivModInPlace<BigUintegerDiv>(b);
|
| | | }
|
| | |
|
| | | //+------------------------------------------------------------------+
|
| | | BigUInteger BigUInteger::operator/(BigUInteger& b) const
|
| | | {
|
| | | BigUInteger v = this;
|
| | | v /= b;
|
| | | return BigUInteger(v.m_v, v.m_v_s);
|
| | | }
|
| | |
|
| | | //+------------------------------------------------------------------+
|
| | | void BigUInteger::operator/=(const 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
|
2026-09-10 08:11:32 -05:00 | | | BIGNUMBERSBYLEO_CLEAN_HIGH_ZEROS(m_v, m_v_s)
|
2026-09-07 21:55:02 -05:00 | | | }
|
| | |
|
| | | //+------------------------------------------------------------------+
|
| | | 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<BigUintegerMod>(b);
|
| | | }
|
| | |
|
| | | //+------------------------------------------------------------------+
|
| | | BigUInteger BigUInteger::operator%(BigUInteger& b) const
|
| | | {
|
| | | BigUInteger v = this;
|
2026-09-26 20:59:30 -05:00 | | | v %= b;
|
2026-09-07 21:55:02 -05:00 | | | 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<r (osea cabe en ulong)
|
| | |
|
| | | // luego
|
| | | // a = prev_r
|
| | | // b = r
|
| | |
|
| | | //--- apartir de ahora gcd entre prev_r y r
|
| | | if(r == 0ULL)
|
| | | return prev_r;
|
| | |
|
| | | // usaremos algortimo binario para esto (stein)
|
| | | // Lo primro que haremos sera calclar el ctz (baiinamte el min 2s uq ehay en amboss)
|
| | | // osea si tenemos a y b entonces ambos numeros se peuden escribri tal que
|
| | | // a = 2x+r
|
| | | // b = 2y+r
|
| | | // la idea es encontrar el minimo en ambos.. y normalzialo a esa escala
|
| | | ulong full = r | prev_r; // Or para combinar
|
| | | full = TSNTABLES_BIT_DEJAR_SOLO_MINUS_SIG_BYTE(full);
|
| | | // la idea es ver cuantos "2" comunes tenemos
|
| | | const int shift = TSNTABLES_CTZ_64_GET_BIT(full); // ya tenemos el bit exacto (cuantos 2s..)
|
| | |
|
| | | //--- ahora pelamos a (u (r))
|
| | | // gcd(u, 2v) = gcd(u, v), solo si u es impar esto dado qeu 2 no es un divisor comun entre dos
|
| | | // reduimos su valor
|
| | | full = TSNTABLES_BIT_DEJAR_SOLO_MINUS_SIG_BYTE(r);
|
| | | 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 <typename TRandom>
|
| | | 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)
|
2026-09-09 20:01:20 -05:00 | | | const ulong s = n_menos1.Ctz();
|
2026-09-07 21:55:02 -05:00 | | | // 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.<TRandom>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
|
