M1n021
Utente Attivo
- Messaggi
- 210
- Reazioni
- 91
- Punteggio
- 42
Credo di essere riuscito ad implementarlo:
C++:
#include <iostream>
#include <cstdint>
using namespace std;
struct integer_square_root_t
{
uint64_t s;
uint64_t r;
};
integer_square_root_t integer_square_root(const uint64_t n)
{
if(!n)
{
return {0, 0};
}
uint8_t i = 64;
while(!((uint64_t)1 << --i & n));
i -= i % 2;
for(uint64_t a = 0, b = 0, s = 0; ; i -= 2)
{
a = (a - b) * 4 + (n >> i & 3);
b = s * 4 + 1;
s = s * 2 + (b <= a ? 1 : b = 0);
if(!i)
{
return {s, a - b};
}
}
}
int main()
{
uint64_t n = 3'827'305'971'502'837'649;
integer_square_root_t a = integer_square_root(n);
cout << "\n " << n << " = " << a.s << "^2 + " << a.r << endl;
}sqrt(). A questo punto il prossimo passo sarà quello di modificare opportunamente il suddetto algoritmo per inserirlo nella mia libreria sui big_int, in modo da poter calcolare con precisione la radice intera di numeri anche maggiori di 2^64. Inoltre, come nella divisione in colonna, dove si mette la virgola e si aggiungono gli zeri per calcolare i decimali, questo algoritmo può essere utilizzato per calcolare qualsiasi numero di decimali della radice.Se vuoi, puoi implementare un test nell'ambito degli interi a 64 bit per fare un confronto tra i due metodi!
ho sicuramente pasticciato con gli indici, lo faccio sempre
) di conseguenza n=2^k, che sostituito in O(Log2(n)) porta in realtà a O(k), cioè ad una complessità lineare, che è ovviamente peggiore di una complessità logaritmica (e log^2).