nique_372/BigNumberByLeo
Watch
1
0
Fork
You've already forked BigNumberByLeo
 1
Code Issues Pull requests Projects Releases Packages Wiki Activity Actions
BigNumberByLeo/Src/Base/Uint.mqh
Nique_372 a5dfc36bdc
2026-09-26 20:59:30 -05:00

2062 lines
56 KiB
MQL5
Raw Permalink Blame History

//+------------------------------------------------------------------+
//| Main.mqh |
//| Copyright 2026, Niquel Mendoza |
//| https://www.mql5.com |
//+------------------------------------------------------------------+
#property copyright "Copyright 2026, Niquel Mendoza"
#property link "https://www.mql5.com"
#property strict
#ifndef BIGNUMBERSBYLEO_SRC_BASE_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 <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
__forceinline int Cmp(const BigIBase& b) const { return CmpInt<BigUInteger>(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 <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);
//--- 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 <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..
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<<x con x grande peude hacer crecer el tamaño artificilaemtne de mvs
if(BIGNUMERBYLEO_UINTEGER_IZ_ZERO)
return BigUInteger(0ULL, 1);
//---
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)
{
//--- 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 <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
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<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
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<BigUintegerMod>(b);
}
//+------------------------------------------------------------------+
BigUInteger BigUInteger::operator%(BigUInteger& b) const
{
BigUInteger v = this;
v %= b;
return BigUInteger(v.m_v, v.m_v_s);
}
//+------------------------------------------------------------------+
void BigUInteger::operator%=(const 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)
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.<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
Reference in a new issue View git blame Copy permalink