vict85 ha scritto:Per trovare i coefficienti si può usare penso una ricerca binaria. Siccome moltiplicazione e confronto hanno peso \( (O(n_b) \) e la ricerca ha un costo \( O(\log_2(b)) \) allora il costo è \( O(\log_2(b)n_b) \).D'altra parte \( n_{10^9} = 9^{-1} n_{10} \) e \( \log_2(10^9) = 9\log_2(10) \), quindi mi sembra che il calcolo del coefficiente ha complessità costante al cambio della base. Però il numero di coefficienti dovrebbe essere 9 volte più piccolo, e così anche la sottrazione. Quindi mi aspetterei performance migliori al crescere della base.
Purtroppo so poco o nulla di teoria della complessità computazionale, ma in linea di massima credo di aver capito quello che intendi dire. In ogni caso non so quanto lo scenario generale da te prospettato possa applicarsi nello specifico ai due algoritmi che ho implementato.
Se può essere utile provo a descriverli per sommi capi:
1) nel vecchio algoritmo con le stringhe, opero la classica divisione in base $10$.
Per esempio:
$\overbrace{\underbrace{34}_(a_1)\underbrace{5}_(r_3)201}^R8743566:\overbrace{\underbrace{8}_(d_1)7154}^D$
- se $R<D$ allora $q_i=0$ e $R=R$ (ovviamente poi $R$ "avanza" lungo il dividendo);
- se $R=D$ allora $q_i=1$ e $R=0$;
- altrimenti (ossia $R>D$) $q_iin[1;q_(i,max)]=[1;a_1//d_1]$ e $R=R-q_i*D$.
Per determinare $q_i$ parto da un valore di primo tentativo pari a $q_(i,T)=q_(i,max)$ a scendere. Per testare $q_(i,T)$ non vado a fare il calcolo per intero verificando che $R<=q_(i,T)*D$, ma avanzo una cifra alla volta.
Cerco di spiegare meglio quello che intendo... detti $b_i=q_(i,T)*d_i$ e $a_i=(a_(i-1)-b_(i-1))*10+r_(i+2)$:
* se $a_i<b_i$, allora deduco che $q_(i,T)>q_i$ e diminuisco $q_(i,T)$ di un'unità;
* se $a_i-b_i>=q_(i,T)$, allora deduco che $q_i=q_(i,T)$.
Riprendendo l'esempio numerico sopra postato per la determinazione di $q_1$ si ha:
# $q_(1,T)=a_1//d_1=34//8=4$ :
## $a_1=34$ e $b_1=q_(1,T)*d_1=4*8=32$, essendo $a_1>b_1$ $\wedge$ $a_1-b_1<q_(1,T)$ continuo;
## $a_2=(a_1-b_1)*10+r_3=25$ e $b_2=q_(1,T)*d_2=4*7=28$, essendo $a_2<b_2$ diminuisco $q_(1,T)$;
# $q_(1,T)=4-1=3$ :
## $a_1=34$ e $b_1=q_(1,T)*d_1=3*8=24$, essendo $a_1-b_1>q_(1,T)$ posso concludere che $q_1=3$.
------------------------------------------------------------------------------------
2) nel nuovo algoritmo con i vettori di bool (lo so, nello specifico utilizzo
vector<bitset<32>>, ma ai fini della spiegazione meglio parlare in termini di vector<bool>), opero invece la divisione direttamente in base $2$:- se $R<D$ allora $q_i=0$ e $R=R$;
- altrimenti $q_i=1$ e $R=R-D$.
Per esempio:
$\overbrace{110100}^R10001010$ $:$ $=>q_1=0$
$\underbrace{111001}_D$
$\overbrace{1101001}^R0001010$ $:$ $=>q_2=1$
$\text{_}\underbrace{111001}_D$
$0\overbrace{1100000}^R001010$ $:$ $=>q_3=1$ $...$
$\text{__}\underbrace{111001}_D$
$R<D$ si verifica quando $R$ ha lo stesso numero di cifre di $D$ e partendo da sinistra la prima coppia di cifre corrispondenti diverse presenta un $1$ in $D$.
Per la sottrazione invece mi limito, partendo da destra, ad invertire, per ogni bit di $R$ in corrispondenza di un $1$ in $D$, i bit di $R$ finché andando verso sinistra non incontro un $1$.
------------------------------------------------------------------------------------
Detto ciò, è vero che il vettore di bool è circa 3,3 volte più lungo della stringa, ma nella versione con le stringhe ci sono varie operazioni con interi che internamente operano comunque su sequenza di più bit, senza dimenticare poi la parte relativa ai "tentativi".
Probabilmente non mi resta che arrendermi all'evidenza, ma nella mia ignoranza trovo questa differenza nelle prestazioni abbastanza controintuitiva.
