Esercizio Assembler
Ciao a tutti come esercizio dovevo svolgere questa consegna in linguaggio c e assembly:
acquisire due numeri A e B compresi tra 0 e 64000 e calcolare la somma dei "2" presenti nei numeri compresi tra A e B.
quindi se scegliessi i numeri 2001 e 2003, la catena di numeri da prendere in considerazione sarebbe : 2001 , 2002 , 2003 (A e B compresi ). in questa catena il numero "2" ricorre 4 volte quindi la somma totale dei numeri "2" è 8.
In linguaggio c sono riuscita a svolgere l'esercizio e compila, ma in assembler ho molti problemi.
Secondo me dovrei creare un ciclo che comincia col numero A e finisce quando raggiunge il numero B compreso, all'interno dovrei impostare un altro ciclo che controlli il numero A (che sarà incrementato ogni volta dal primo ciclo) e incrementi di 1 un'altra variabile ogni volta che incontra un 2 . poi basterebbe moltiplicare questa variabile per 2 e stamparla
quello che ho scritto, escludendo la richiesta dei numeri è questo, ma non compila.. potreste aiutarmi???
MOV CX,0 ; lo uso come contatore dei "2"
LOOP1:
MOV AX,SI ; mette il numero da testare in AX
LOOP2:
XOR DX,DX ; il dividendo è in DX:AX (numero a 32 bit) DX è sempre ZERO
MOV BX,10 ; il divisore
DIV BX ; divide DX:AX per BX, quoziente in AX, resto in DX (il resto è la cifra decimale)
CMP DX,2 ; se il resto è '2' allora abbiamo la cifra '2' nel numero
JNE NOT_DUE
INC CX ; incremento il contatore dei 2
NOT_DUE:
CMP AX,0 ; se il quoziente è ZERO ho finito col numero attuale
JNE LOOP2
INC SI ; passa al prossimo numero
CMP SI,DI ; se SI è minore/uguale a DI continua
JBE LOOP1
acquisire due numeri A e B compresi tra 0 e 64000 e calcolare la somma dei "2" presenti nei numeri compresi tra A e B.
quindi se scegliessi i numeri 2001 e 2003, la catena di numeri da prendere in considerazione sarebbe : 2001 , 2002 , 2003 (A e B compresi ). in questa catena il numero "2" ricorre 4 volte quindi la somma totale dei numeri "2" è 8.
In linguaggio c sono riuscita a svolgere l'esercizio e compila, ma in assembler ho molti problemi.
Secondo me dovrei creare un ciclo che comincia col numero A e finisce quando raggiunge il numero B compreso, all'interno dovrei impostare un altro ciclo che controlli il numero A (che sarà incrementato ogni volta dal primo ciclo) e incrementi di 1 un'altra variabile ogni volta che incontra un 2 . poi basterebbe moltiplicare questa variabile per 2 e stamparla
quello che ho scritto, escludendo la richiesta dei numeri è questo, ma non compila.. potreste aiutarmi???
MOV CX,0 ; lo uso come contatore dei "2"
LOOP1:
MOV AX,SI ; mette il numero da testare in AX
LOOP2:
XOR DX,DX ; il dividendo è in DX:AX (numero a 32 bit) DX è sempre ZERO
MOV BX,10 ; il divisore
DIV BX ; divide DX:AX per BX, quoziente in AX, resto in DX (il resto è la cifra decimale)
CMP DX,2 ; se il resto è '2' allora abbiamo la cifra '2' nel numero
JNE NOT_DUE
INC CX ; incremento il contatore dei 2
NOT_DUE:
CMP AX,0 ; se il quoziente è ZERO ho finito col numero attuale
JNE LOOP2
INC SI ; passa al prossimo numero
CMP SI,DI ; se SI è minore/uguale a DI continua
JBE LOOP1
Risposte
@ellosma:
come hai strutturato nella memoria le cifre A e B. In che registri? Mostrami pure anche uno schemino con le varie suddivisioni, AX, AH, AL .... EAX.
come hai strutturato nella memoria le cifre A e B. In che registri? Mostrami pure anche uno schemino con le varie suddivisioni, AX, AH, AL .... EAX.
ciao , scusa se ti rispondo solo adesso ma purtroppo vivo in campagna, con una connessione di 56 k e il 90% delle volte internet non va , o nn mi fa caricare nemmeno la pagina di google !
come editor di testo noi usiamo : notepad, pspad, gedit, textedit, ...
-_‐ ambiente x86: DOSBOX
-_‐ compilatore assembler: Turbo Assembler
-_‐ linker assembler: Turbo Linker
-_‐ debugger: Turbo Debugger
come assemblatore usiamo tasm
ti allego , scusa per la scrittura a zampe di gallina, uno "schema" di come risolverei l'esercizio, per quello che secondo me potrebbe essere il modo più semplice (http://www.mediafire.com/?ob65kdzom6ag57z ). il professore mi aveva consigliato di scrivere prima il codice in c, cosa che ho fatto qui :
come editor di testo noi usiamo : notepad, pspad, gedit, textedit, ...
-_‐ ambiente x86: DOSBOX
-_‐ compilatore assembler: Turbo Assembler
-_‐ linker assembler: Turbo Linker
-_‐ debugger: Turbo Debugger
come assemblatore usiamo tasm
ti allego , scusa per la scrittura a zampe di gallina, uno "schema" di come risolverei l'esercizio, per quello che secondo me potrebbe essere il modo più semplice (http://www.mediafire.com/?ob65kdzom6ag57z ). il professore mi aveva consigliato di scrivere prima il codice in c, cosa che ho fatto qui :
#include <stdio.h>
#define LIM_INF 0
#define LIM_SUP 64000
#define TARGET_DIGIT 2
int main(void) {
int A, B;
int contatore, curr;
//controllo dell'input
do { //ciclo che controlla se A < B
do { //ciclo che controlla se LIM_INF <= A <= LIM_SUP
printf("Inserisci estremo inferiore: ");
scanf("%d", &A);
} while (A < LIM_INF | A > LIM_SUP);
do { //ciclo che controlla se LIM_INF <= B <= LIM_SUP
printf("Inserisci estremo superiore: ");
scanf("%d", &B);
} while (B < LIM_INF || B > LIM_SUP);
} while (A > B);
for (contatore = 0; A <= B; A++)
//scompone il numero in cifre e cerca la cifra bersaglio (2 in questo caso)
for (curr = A; curr > 0; curr /= 10)
//ottengo cifra meno significativa e faccio quel che devo fare
if (curr % 10 == TARGET_DIGIT)
contatore++;
printf("Sono stati trovati %d cifre uguali a %d\n", contatore, TARGET_DIGIT);
printf("La somma delle %d occorrenze di %d e' %d\n", contatore, TARGET_DIGIT, TARGET_DIGIT * contatore);
return 0;
}
"ellosma":
int A, B;
perchè nel codice ora sei passata ad utilizzare degli interi?
se si parla di acquisizione da tastiera e vedendo lo schema della memoria, si parla di byte. Deve esserci corrispondenza tra codice Assembly e C, se no non serve molto scrivere anche il codice C.
perciò sarà un array di char di 5 cifre + un terminatore e un numero per sapere i numeri scritti:
char* A[7]
char* B[7]
i controlli saranno su ogni singola cifra/carattere (utilizzando l'aritmetica sui caratteri con codifica ASCII).
Per non complicarsi la vita, mi baso un po' sulle idee già espresse da te e Shulz e ne facciamo un riassunto.
E' in pratica inutile farlo per un codice così semplice, ma è più comodo direi per la conversione in assembler e per capire ciò che accade in un codice a basso livello (per esperienza)...
- abbiamo due cifre da tastiera e questo lo ritengo già fatto.
-che lo si vuole o no, dobbiamo convertire A e B in interi, che sia per il controllo dei limiti od altro, dobbiamo farlo.
- per ogni elemento del vettore A[1]-A[5] sarà convertitie nelle cifre 0-9 tramite l'aritmetica di ASCII
- ogni cifra significativa sarà sommata con quella successiva, moltiplicando per la sua posizione.
(A[1]-'0')*10^((A[0]-'0')-1) prima cifra
(A[2]-'0')*10^((A[0]-'0')-2) seconda cifra...
es. il numero 41234
si sommano e si salvano.
si comporta come la funzione atoi() del C.
- controlliamo i limiti
- se il controllo fallisce ripartiamo dall'input da tastiera oppure EXIT (cosa vuoi fare?)
ORA: abbiamo tutte le strutture sia la conversione di A e B in interi, che A e B in caratteri.
Direi che per risolvere il problema ci sono più strade:
per il momento consideriamo l'algoritmo di Shulz, che valuta tutti i due di ogni cifra, da $B$ ad $A$ (o contrario) perciò avrà omplessità massima $O(|A-B|^2)$
- verifichiamo chi è il maggiore dei due (per farlo diventare il limite inferiore).
- il ciclo partirà da il max facciamo $A$ e diminuira di ogni volta fino a $B$ compreso.
- ogni valore di A sarà valutato e si conteranno i vari due presenti
- alla fine si avranno i due di |A-B|
- per saper la somma di tutti i due, basta moltiplicare il risultato sopra per $2$.
ok, questo è più o meno tutto. Non è il miglior algoritmo, ma in assembler meglio rimanere con costrutti semplici e già qui ci son moltiplicazioni non troppo semplici...
Vedi cosa è chiaro e cosa no e ne discutiamo.
EDIT:
già che c'ero ho aggiunto il codice
PS: scusa Shulz se ti nomino invano nel post, ma visto che il tuo codice era pronto ne ho approfittato
E' in pratica inutile farlo per un codice così semplice, ma è più comodo direi per la conversione in assembler e per capire ciò che accade in un codice a basso livello (per esperienza)...
- abbiamo due cifre da tastiera e questo lo ritengo già fatto.
char* A[7] char* B[7]
-che lo si vuole o no, dobbiamo convertire A e B in interi, che sia per il controllo dei limiti od altro, dobbiamo farlo.
- per ogni elemento del vettore A[1]-A[5] sarà convertitie nelle cifre 0-9 tramite l'aritmetica di ASCII
- ogni cifra significativa sarà sommata con quella successiva, moltiplicando per la sua posizione.
(A[1]-'0')*10^((A[0]-'0')-1) prima cifra
(A[2]-'0')*10^((A[0]-'0')-2) seconda cifra...
es. il numero 41234
A[5,'4','1','2','3','4','\0'] (A[1]-'0')*10^((A[0]-'0')-1) = 40000 (A[2]-'0')*10^((A[0]-'0')-2) = 1000
si sommano e si salvano.
si comporta come la funzione atoi() del C.
- controlliamo i limiti
INF LIMIT <= A <= SUP LIMIT INF LIMIT <= B <= SUP LIMIT
- se il controllo fallisce ripartiamo dall'input da tastiera oppure EXIT (cosa vuoi fare?)
ORA: abbiamo tutte le strutture sia la conversione di A e B in interi, che A e B in caratteri.
Direi che per risolvere il problema ci sono più strade:
per il momento consideriamo l'algoritmo di Shulz, che valuta tutti i due di ogni cifra, da $B$ ad $A$ (o contrario) perciò avrà omplessità massima $O(|A-B|^2)$
- verifichiamo chi è il maggiore dei due (per farlo diventare il limite inferiore).
- il ciclo partirà da il max facciamo $A$ e diminuira di ogni volta fino a $B$ compreso.
- ogni valore di A sarà valutato e si conteranno i vari due presenti
- alla fine si avranno i due di |A-B|
- per saper la somma di tutti i due, basta moltiplicare il risultato sopra per $2$.
ok, questo è più o meno tutto. Non è il miglior algoritmo, ma in assembler meglio rimanere con costrutti semplici e già qui ci son moltiplicazioni non troppo semplici...
algoritmo di Shulz modificato{
//consideriamo sempre A il massimo
if(A<B){
swap(A,B)
}
//consideriamo il maggiore stretto per evitare il caso B=0
while(A>B)
count = count + shulz(A) //da vedere come modificare
A--
}
sum = count*2
}Vedi cosa è chiaro e cosa no e ne discutiamo.
EDIT:
già che c'ero ho aggiunto il codice
PS: scusa Shulz se ti nomino invano nel post, ma visto che il tuo codice era pronto ne ho approfittato
Grazie mille ad entrambi , davvero ! Il codice in c l'ho capito 
ora mi metto li e cerco di convertirlo !!
ora mi metto li e cerco di convertirlo !!
Il codice finale dovrebbe essere una cosa del genere, considera che in assembler si possono fare molte ottimizzazioni con i registri e i loop. Io ho considerato il tutto come una chiamata a funzione dove in input si hanno i caratteri letti, che dovresti possedere già.
se non riesci a partire proviamo a scrivere il codice relativo.
EDIT:
quella che chiamo "simulazione della potenza di 10" è sbagliata lo ho scritta in pochi minuti quella parte. Vedi l'edit del posto sottostante, ho corretto anche il ciclo while nel codice di shulz, così è corretto e funzionante.
unsigned short alg(char* A,char* B){
unsigned short a,b,count,temp,
unsigned char i,j;
a=b=count=temp=0;
//conversiona ascii to int
i=A[0]; //numero di cifre lette di A
j=0;
while(i>0){
a = a + ((A[i]-'0')*pow(10,j));
/* simulazione della potenza di 10, massimo 10^4*/
/* if(j==0){*/
/* count = 1;*/
/* }*/
/* else {*/
/* */
/* temp=j;*/
/* while(temp>0){*/
/* count = count + 10*temp;*/
/* temp--;*/
/* }*/
/* }*/
/* a = a + ((A[i]-'0')*count);*/
j++;
i--
}
i=B[0]; //numero di cifre lette di B
j=0;
while(i>0){
b = b + ((B[i]-'0')*pow(10,j));
j++;
i--
}
//confronto sui limiti
if(a<LIM_INF || a>LIM_SUP){
EXIT //assumo che si esca, non avendomi risposto nel post
}
if(b<LIM_INF || b>LIM_SUP){
EXIT //assumo che si esca, non avendomi risposto nel post
}
//consideriamo A il massimo
if(a<b){
temp=a;
a=b;
b=temp;
}
//evitiamo che il while iteri all'infinito nel caso del confronto (a=0) >= (0=b)
if(b==0){
b=1;
}
//codice per il conto dei due
while(a>=b){
temp=a;
while(temp>0){
//conto dei due di una singola cifra
if (temp % 10 == 2){
count++;
}
temp = temp/10; //ottimizzazione in assembly possibile con una sola div
}
a--;
}
//somma di tutti i due
count = count*2;
return count;
}se non riesci a partire proviamo a scrivere il codice relativo.
EDIT:
quella che chiamo "simulazione della potenza di 10" è sbagliata lo ho scritta in pochi minuti quella parte. Vedi l'edit del posto sottostante, ho corretto anche il ciclo while nel codice di shulz, così è corretto e funzionante.
Visto che avevo un po' voglia di giocare, mi ero ripromesso di trovare un algoritmo migliore, più "efficiente" di quello che avevate proposto (te e shulz), anche se funziona senza problemi ovviamente, ho comunque cercato una formula chiusa per risolvere il problema.
Sapendo che la rapprezentazione di un numero è posizionale.
Nelle posizione $0$:
- nei primo 10 c'è $1$ solo due
- nei primi 20 ci sono $2$ due
- nei primi 30 ci sono $3$ due (nota che corrisponde al $3$ di $30$...)
...
- $90$ ci sono $9$ due
- $99$ ci son 10 due in posizione $0$
nella posizione $1$ ci sono $10$ due rappresentati dai numeri $[20-29]$. Perciò nei primi 100 numeri ci sono $10+10=20$ due.
Più complicato nei primi 300 numeri, abbiamto tre volte i primi cento perciò $20*3=60$ due. Ci sono però da sommare i due presenti nella posizione decimale $2$ ($10^2$), cioè tra $[200-299]$ che sono $100=10^2$ due. Perciò $20*3 + 10^2 = 160$ due nei primi 300 numeri
Generalizziamo, siano $[c_p,....c_0]$ un numero decimale con $p$ posizione massima.
il numero 300 corrisponde a $p=2$ e $[3,0,0]$.
se prendiamo il calcolo precedente, $20*3 + 10^2$ si può generalizzare utilizzando la posizione dei decimali:
$20*3 + 10^2 = (2*10^1)*3 + 10^2 = (p*10^(p-1))*c_p + 10^p$
Considerando il numero $111$ non esiste la somma $+ 10^p$ perchè non ci sono $2$ nelle varie posizioni.
Se prendiamo numeri più significativi come $43211$ sarà la somma per ogni posizione da $4$ a $0$, una sommatoria.
perciò:
\[ C(c_i\ |\ i=0..p ) = \begin{cases} 1 & \mbox{if } c_0>1 \\\ i*10^{i-1}*c_i + {\begin{cases} 1 & \mbox{if } c_i=2 \\\ 10^i & \mbox{if } c_i>2 \\\ 0 & \mbox{other} \end{cases} } \mbox{if } i>0\\\ 0 & \mbox{other} \end{cases}\]
In codice, lo si può scrivere sia ricorsivamente che iterativamente, è più veloce con un ciclo while:
Il discorso sui limiti si può semplificare. Se dici che sono fissi:
- Il limite inferiore è gratuito perchè se sono interi senza segno non si può andare sotto la soglia dello $0$, al massimo si andrebbe overflow. Perciò è un controllo inutile
- il limite superiore ha senso solo quando ci sono $5$ cifre lette, perciò con $4$ il limite è già rispettato. Cioè i bit di rappresentazione sono $2^4=8$ e $2^5=16$ perciò l'unico caso è il $2^16=65535$. Qui si può utilizziare lo stesso metodo sopra per non inventarsi altro, cioè conversione ad interi solo se A[0]==5.
ma possiamo sempre utilizzare i metodi dell'altro post sopra per i limiti, senza complicarci la vita.
Per trovare la somma totale dei due basta calcolarsi separatamente i due di $A$ e di $B$, alla fine basta sottrarre e si avranno i due dell'intervallo.
Il codice rispetto al precedente non compie $5*64000 = 32000$ divisioni circa nel caso pessimo, ma in pratica fai circa $20*5 = 120$ moltiplicazioni nel peggiore dei casi SEMPRE.
ADD:
alla fine il codice dovrebbe essere questo, lo ho separato in funzioni, ma si può sempre raggrupparlo, è solo per evitare di scrivere due volte lo stesso codice modificandolo prima per A e poi per B:
codice per la conversione di caratteri in stringhe:
algoritmo che abbiamo descitto sopra per contare i due (in alternativa utilizziamo algoritmo_Shulz)
codice da aggiungere al programma principale, ci si aspetta che da tastiera ci siano cifre e non valori speciali, come caratteri speciali, maiuscole, punti esclamativi...
Ora il codice assembler come complessità di scrittura non cambia, è più efficiente in termini di calcolo questa versione.
Se si usa una o l'altra versione le prime parti sono identiche, per il momento prova te a scrivere la parti che riesci senza paura, es. il primo ciclo della convert_string() senza guardare il passaggio di funzioni. Appena avrò un po' di tempo, al massimo, ti scrivo io le prime parti per farti partire.
EDIT:
visto che la potenza di 10 è chiamata più volte meglio estrapolarla e creare una fun a parte.
corretti anche alcuni errori. Ho compilato anche il codice cosa che non avevo fatto e corretto alcune cose.
L'algoritmo è sì nei principi corretto, ma non è perfetto sarebbe da rivedere se il numero da calcolare se è pieno di $2$. Però non ho voglia di rivederlo. Utilizza quello di Shulz (con la correzione della potenza), anche se è stato un bel gioco...
Sapendo che la rapprezentazione di un numero è posizionale.
Nelle posizione $0$:
- nei primo 10 c'è $1$ solo due
- nei primi 20 ci sono $2$ due
- nei primi 30 ci sono $3$ due (nota che corrisponde al $3$ di $30$...)
...
- $90$ ci sono $9$ due
- $99$ ci son 10 due in posizione $0$
nella posizione $1$ ci sono $10$ due rappresentati dai numeri $[20-29]$. Perciò nei primi 100 numeri ci sono $10+10=20$ due.
Più complicato nei primi 300 numeri, abbiamto tre volte i primi cento perciò $20*3=60$ due. Ci sono però da sommare i due presenti nella posizione decimale $2$ ($10^2$), cioè tra $[200-299]$ che sono $100=10^2$ due. Perciò $20*3 + 10^2 = 160$ due nei primi 300 numeri
Generalizziamo, siano $[c_p,....c_0]$ un numero decimale con $p$ posizione massima.
il numero 300 corrisponde a $p=2$ e $[3,0,0]$.
se prendiamo il calcolo precedente, $20*3 + 10^2$ si può generalizzare utilizzando la posizione dei decimali:
$20*3 + 10^2 = (2*10^1)*3 + 10^2 = (p*10^(p-1))*c_p + 10^p$
Considerando il numero $111$ non esiste la somma $+ 10^p$ perchè non ci sono $2$ nelle varie posizioni.
Se prendiamo numeri più significativi come $43211$ sarà la somma per ogni posizione da $4$ a $0$, una sommatoria.
perciò:
\[ C(c_i\ |\ i=0..p ) = \begin{cases} 1 & \mbox{if } c_0>1 \\\ i*10^{i-1}*c_i + {\begin{cases} 1 & \mbox{if } c_i=2 \\\ 10^i & \mbox{if } c_i>2 \\\ 0 & \mbox{other} \end{cases} } \mbox{if } i>0\\\ 0 & \mbox{other} \end{cases}\]
In codice, lo si può scrivere sia ricorsivamente che iterativamente, è più veloce con un ciclo while:
unsigned short count = 0
unsigned short i,j,p;
j=p=A[0];
//la posizione 0 la contiamo separatamente per evitare la sottrazione 10^(0-1)
if(A[j]>1)}
count = 1;
}
j--;
i=1;
while(i<p){
//somma dei due nella varie posizioni decimali 10^i-1 e 10^0
count = count + (i*pow(10,i-1))*(A[j]-'0');
//somma dei due nella varie posizioni decimali 10^i
if(A[j]-'0'==2){
count = count + 1;
}
if(A[j]-'0'>2){
count = count + pow(10,i);
}
//se A[j] è 0 OR 1 non facciamo nulla perchè si somma 0 non ci sono due
i++;
j--;
}Il discorso sui limiti si può semplificare. Se dici che sono fissi:
- Il limite inferiore è gratuito perchè se sono interi senza segno non si può andare sotto la soglia dello $0$, al massimo si andrebbe overflow. Perciò è un controllo inutile
- il limite superiore ha senso solo quando ci sono $5$ cifre lette, perciò con $4$ il limite è già rispettato. Cioè i bit di rappresentazione sono $2^4=8$ e $2^5=16$ perciò l'unico caso è il $2^16=65535$. Qui si può utilizziare lo stesso metodo sopra per non inventarsi altro, cioè conversione ad interi solo se A[0]==5.
ma possiamo sempre utilizzare i metodi dell'altro post sopra per i limiti, senza complicarci la vita.
Per trovare la somma totale dei due basta calcolarsi separatamente i due di $A$ e di $B$, alla fine basta sottrarre e si avranno i due dell'intervallo.
Il codice rispetto al precedente non compie $5*64000 = 32000$ divisioni circa nel caso pessimo, ma in pratica fai circa $20*5 = 120$ moltiplicazioni nel peggiore dei casi SEMPRE.
ADD:
alla fine il codice dovrebbe essere questo, lo ho separato in funzioni, ma si può sempre raggrupparlo, è solo per evitare di scrivere due volte lo stesso codice modificandolo prima per A e poi per B:
codice per la conversione di caratteri in stringhe:
unsigned short convert_string(char* A){
unsigned short count;
unsigned short i,j;
count = 0;
//conversione di A[] in un intero di A[0] cifre
j=A[0];
i=0;
while(i<A[0]){
A[j]=A[j]-'0';//passaggio per rendere i caratteri ascii cifre nel range 0-9
count = count + (A[j]*pow101(i));
j--;
i++;
}
return count;
}algoritmo che abbiamo descitto sopra per contare i due (in alternativa utilizziamo algoritmo_Shulz)
unsigned short count_two(char* A){
unsigned short count = 0;
unsigned short i,j,p;
p=A[0];
count = 0;
if(p>0){
j=p;
//la posizione 0 la contiamo separatamente per evitare la sottrazione 10^(0-1)
if(A[j]>1){
count = 1;
}
j--;
i=1;
while(i<p){
//somma dei due nella varie posizioni decimali 10^i-1 e 10^0
count = count + (i*pow101(i-1)*A[j]);
//somma dei due nella varie posizioni decimali 10^i
if(A[j]==2){
count = count + A[j-1];
}
if(A[j]>2){
count = count + pow101(i);
}
//se A[j] è 0 OR 1 non facciamo nulla perchè si somma 0 non ci sono due
i++;
j--;
}
}
//ritornerà 0 in tutti i casi non descritti
return count;
}codice da aggiungere al programma principale, ci si aspetta che da tastiera ci siano cifre e non valori speciali, come caratteri speciali, maiuscole, punti esclamativi...
//convertiamo a e b, e controlliamo i limiti, il limite inferiore se 0 è inutile controllarlo
//se i limiti sono variabili ha senso
a = convert_string(A);
if(a<LIM_INF||a>LIM_SUP){
EXIT
}
b = convert_string(B);
if(b<LIM_INF||b>LIM_SUP){
EXIT
}
if(a<b){
a = count_two(B);
b = count_two(A);
}
else{
a = count_two(A);
b = count_two(B);
}
sum = 2*(a-b);
return a;
Ora il codice assembler come complessità di scrittura non cambia, è più efficiente in termini di calcolo questa versione.
Se si usa una o l'altra versione le prime parti sono identiche, per il momento prova te a scrivere la parti che riesci senza paura, es. il primo ciclo della convert_string() senza guardare il passaggio di funzioni. Appena avrò un po' di tempo, al massimo, ti scrivo io le prime parti per farti partire.
EDIT:
visto che la potenza di 10 è chiamata più volte meglio estrapolarla e creare una fun a parte.
//simulazione della potenza di 10, massimo 10^4
unsigned short pow10(unsigned short i){
unsigned short temp;
temp=1;
while(i>0){
temp = 10*temp;
i--;
}
return temp;
}corretti anche alcuni errori. Ho compilato anche il codice cosa che non avevo fatto e corretto alcune cose.
L'algoritmo è sì nei principi corretto, ma non è perfetto sarebbe da rivedere se il numero da calcolare se è pieno di $2$. Però non ho voglia di rivederlo. Utilizza quello di Shulz (con la correzione della potenza), anche se è stato un bel gioco...
Ok , perfetto grazie ancora !!! Intanto mi studio per vene anche l'ultima versione dell'algoritmo !
grazie ancora !!! Intanto mi studio per vene anche l'ultima versione dell'algoritmo !
Non ho letto con molta attenzione la discussione ma vedo se riesco a dare qualche contributo. Nel seguito \(x\) e \(y\) sono due numeri naturali e \(y \ge x\). Se \(x > y\), si può semplicemente scambiare i due numeri.
Sia \(F(x, y)\) la funzione che restituisce il numero di cifre uguali a due nei naturali compresi tra \(x\) e \(y\) (estremi inclusi). \(F(n) = F(n,n)\) è quindi la funzione che conta il numero di cifre decimali uguali a due in \(n\). Abbiamo ovviamente che \( F(x,y) = \sum_{n = x}^y F(n)\), \( F(0,y) \ge F(0,x) \) e \( F(x, y) = F(0, y) - F(0, x) + F(x,x) \) (ricordo che sto assumendo che valga \(y \ge x\).
\(F(x,x)\) sappiamo già calcolarlo.. Vediamo quindi come calcolare \( F(0, n) \). Sia \( n = c_m\,10^m + d \) dove \( 0 < c_m < 10 \) e \( d < 10^m \). Siccome la nostra funzione è additiva, \( F(0,n) = F(0, c_m\,10^m) + F(c^m\,10^m, n) - F(c^m\,10^m) \). \(F(c^m\,10^m)\) è facilmente calcolabile essendo uguale a \(1\) se \(c_m = 2\) e \(0\) in caso contrario.
\[ F(0, c^m\,10^m) = F(c_m\,10^m) + g(c_m)\,10^m + c_m\,m\,10^{m-1} \]
dove \( g(c_m) = 1 \) se \( c_m > 2 \) e uguale a zero in caso contrario.
Se ora diamo un'occhiata a \(F(c^m\,10^m, n)\) osserviamo che tutti i numeri in questo intervallo hanno come prima cifra \(c_m\) e poi tutte le cifre che compaiono nell'intervallo \((0, d)\). Se \(c_m\) è diverso da due, allora \(F(c^m\,10^m, n) = F(0, d) \). Se \(c_m\) è uguale a due, allora \(F(c^m\,10^m, n) = (d + 1) + F(0, d)\). Ricordandoci di come è definito \(F(c^m\,10^m)\) possiamo allora riscrivere \(F(c^m\,10^m, n) = (d + 1)\,F(c^m\,10^m) + F(0, d)\).
Abbiamo quindi dimostrato la seguente espressione:
\[ F(0, n) = F\bigl(0, c_m\,10^m + d \bigr) = g\bigl(c_m\bigr)\,10^m + c_m\,m\,10^{m-1} + (d+1)\,F(c^m\,10^m) + F(0, d). \]
Questa relazione ci permette di calcolare il nostro valore molto più velocemente rispetto al conteggio di ogni singola cifra nei numeri interni all'intervallo. Il problema principale consiste nel dover partire dalla cifra più significativa. Conviene probabilmente fare direttamente il calcolo quando il numero è ancora scritto come stringa, oppure considerare anche il caso in cui \(c_m\) sia zero e partire da \(10^5\) che è comunque la potenza del \(10\) più alta che si può considerare con gli short.
[EDIT] @hamming_burst: ma perché non memorizzi le potenze di 10 o altre costanti in un array? Sono solo 5 numeri nel nostro caso e in assembly è decisamente più facile leggere un numero da un array che richiamare e implementare la funzione relativa.
[EDIT 2] Corretto un errore in una delle formule.
[EDIT 3] @hamming_burst: Le nostre formule saranno la stessa? Forse sì ma non ho tempo di verificarlo che sto per uscire...
Sia \(F(x, y)\) la funzione che restituisce il numero di cifre uguali a due nei naturali compresi tra \(x\) e \(y\) (estremi inclusi). \(F(n) = F(n,n)\) è quindi la funzione che conta il numero di cifre decimali uguali a due in \(n\). Abbiamo ovviamente che \( F(x,y) = \sum_{n = x}^y F(n)\), \( F(0,y) \ge F(0,x) \) e \( F(x, y) = F(0, y) - F(0, x) + F(x,x) \) (ricordo che sto assumendo che valga \(y \ge x\).
\(F(x,x)\) sappiamo già calcolarlo.. Vediamo quindi come calcolare \( F(0, n) \). Sia \( n = c_m\,10^m + d \) dove \( 0 < c_m < 10 \) e \( d < 10^m \). Siccome la nostra funzione è additiva, \( F(0,n) = F(0, c_m\,10^m) + F(c^m\,10^m, n) - F(c^m\,10^m) \). \(F(c^m\,10^m)\) è facilmente calcolabile essendo uguale a \(1\) se \(c_m = 2\) e \(0\) in caso contrario.
\[ F(0, c^m\,10^m) = F(c_m\,10^m) + g(c_m)\,10^m + c_m\,m\,10^{m-1} \]
dove \( g(c_m) = 1 \) se \( c_m > 2 \) e uguale a zero in caso contrario.
Se ora diamo un'occhiata a \(F(c^m\,10^m, n)\) osserviamo che tutti i numeri in questo intervallo hanno come prima cifra \(c_m\) e poi tutte le cifre che compaiono nell'intervallo \((0, d)\). Se \(c_m\) è diverso da due, allora \(F(c^m\,10^m, n) = F(0, d) \). Se \(c_m\) è uguale a due, allora \(F(c^m\,10^m, n) = (d + 1) + F(0, d)\). Ricordandoci di come è definito \(F(c^m\,10^m)\) possiamo allora riscrivere \(F(c^m\,10^m, n) = (d + 1)\,F(c^m\,10^m) + F(0, d)\).
Abbiamo quindi dimostrato la seguente espressione:
\[ F(0, n) = F\bigl(0, c_m\,10^m + d \bigr) = g\bigl(c_m\bigr)\,10^m + c_m\,m\,10^{m-1} + (d+1)\,F(c^m\,10^m) + F(0, d). \]
Questa relazione ci permette di calcolare il nostro valore molto più velocemente rispetto al conteggio di ogni singola cifra nei numeri interni all'intervallo. Il problema principale consiste nel dover partire dalla cifra più significativa. Conviene probabilmente fare direttamente il calcolo quando il numero è ancora scritto come stringa, oppure considerare anche il caso in cui \(c_m\) sia zero e partire da \(10^5\) che è comunque la potenza del \(10\) più alta che si può considerare con gli short.
[EDIT] @hamming_burst: ma perché non memorizzi le potenze di 10 o altre costanti in un array? Sono solo 5 numeri nel nostro caso e in assembly è decisamente più facile leggere un numero da un array che richiamare e implementare la funzione relativa.
[EDIT 2] Corretto un errore in una delle formule.
[EDIT 3] @hamming_burst: Le nostre formule saranno la stessa? Forse sì ma non ho tempo di verificarlo che sto per uscire...
Sia \(T(P)\) la funzione che restituisce \(1\) se la proposizione \(P\) è vera e \(0\) altrimenti. Definisco inoltre \(n_m = n \mod 10^m \) e \(c_m(n) = (n_{m+1} - n_m)/10^m\). Abbiamo allora che la relazione dello scorso post diventa
\[ F(0, n) = T(c_m(n) > 2)\,10^m + c_m(n)\,m\,10^{m-1} + (n_m + 1)\,T(c_m(n) = 2) + F(0, n_m) \]
dove \(c_m(n)\) è la cifra più significative di \(n\). Esplicitando i calcoli vediamo che la relazione diventa
\[ F(0, n) = T\bigl(c_0(n) \ge 2\bigr) + \sum_{i=1}^m \Bigl( T\bigl(c_i(n) > 2\bigr)\,10^i + c_i(n)\,i\,10^{i-1} + (n_i+1)\,T\bigl(c_i(n) = 2\bigr) \Bigr). \]
\[ F(0, n) = T(c_m(n) > 2)\,10^m + c_m(n)\,m\,10^{m-1} + (n_m + 1)\,T(c_m(n) = 2) + F(0, n_m) \]
dove \(c_m(n)\) è la cifra più significative di \(n\). Esplicitando i calcoli vediamo che la relazione diventa
\[ F(0, n) = T\bigl(c_0(n) \ge 2\bigr) + \sum_{i=1}^m \Bigl( T\bigl(c_i(n) > 2\bigr)\,10^i + c_i(n)\,i\,10^{i-1} + (n_i+1)\,T\bigl(c_i(n) = 2\bigr) \Bigr). \]
ciao apatriarca
forse. La mia è in parte sbagliata, manca un parametro nel conteggio.
Es. con il numero 23 conterà 4
perchè somma i due nei primi 20 numeri che sono 3 + i due nei primi 3 numeri che è 1. Per quello che ho scritto sotto nell'EDIT che è nei principi corretto ma è da rivedere, ma non ne ho molta voglia.
Se la tua funziona tanto meglio, domani gli do un occhio e vedo dove è l'errore nella mia versione.
Per il codice non ho considerato ottimizzazioni od altro. Visto che nei principio contavo di vedermi un po' di sintassi Intel tanto per passarmi il tempo (io conosco l'AT&T per compilatore gcc come scrissi, che è della stessa famiglia, perciò nn è così complesso), e così apportare anche ottimizzazione possibili con assembly ed il relativo codice C. Ma dato che non ho più tempo e la pigrizia vacanziera ha preso il sopravvento, se ellosma vorrà contribuire direttamente con Intel e compilatore TASM, bene, se no io me ne chiamo fuori per questa settimana
[EDIT 3] @hamming_burst: Le nostre formule saranno la stessa? Forse sì ma non ho tempo di verificarlo che sto per uscire...
forse. La mia è in parte sbagliata, manca un parametro nel conteggio.
Es. con il numero 23 conterà 4
perchè somma i due nei primi 20 numeri che sono 3 + i due nei primi 3 numeri che è 1. Per quello che ho scritto sotto nell'EDIT che è nei principi corretto ma è da rivedere, ma non ne ho molta voglia.
Se la tua funziona tanto meglio, domani gli do un occhio e vedo dove è l'errore nella mia versione.
Per il codice non ho considerato ottimizzazioni od altro. Visto che nei principio contavo di vedermi un po' di sintassi Intel tanto per passarmi il tempo (io conosco l'AT&T per compilatore gcc come scrissi, che è della stessa famiglia, perciò nn è così complesso), e così apportare anche ottimizzazione possibili con assembly ed il relativo codice C. Ma dato che non ho più tempo e la pigrizia vacanziera ha preso il sopravvento, se ellosma vorrà contribuire direttamente con Intel e compilatore TASM, bene, se no io me ne chiamo fuori per questa settimana
L'ultima formula che ho scritto sembrerebbe corretta. Ho provato a scrivere una implementazione veloce in haskell e questo è il codice di test:
Il numero di test era "solo" 1000, però immagino che se ci fosse stato un qualche problema sarebbe uscito. Tecnicamente una specie di dimostrazione è comunque contenuta nel mio scorso post anche se probabilmente ho saltato dei passaggi. Mi sento comunque di dire che il metodo è abbastanza "sicuro". La seguente dovrebbe essere una implementazione corretta del metodo in C. Non l'ho però testata molto per cui potrebbero esserci errori.
import Data.List
import Data.Word
import Test.QuickCheck
import Test.QuickCheck.Test
digits :: Word16 -> [Word16]
digits 0 = [0]
digits n = digits' n []
digits' :: Word16 -> [Word16] -> [Word16]
digits' 0 xs = xs
digits' n xs = digits' rest (lastDigit : xs)
where (rest, lastDigit) = quotRem n 10
twos :: Word16 -> Word32
twos n = fromIntegral $ length $ filter (==2) $ digits n
f1 :: Word16 -> Word16 -> Word32
f1 x y = if x > y
then f1 y x
else sum $ map twos [x..y]
f2 :: Word16 -> Word16 -> Word32
f2 0 n = c + fun2 (fromIntegral rest) 10 1 (fromIntegral lastDigit)
where c = if lastDigit >= 2 then 1 else 0
(rest, lastDigit) = quotRem n 10
f2 x y = if x > y
then f2 y x
else f2 0 y - f2 0 (x-1)
fun2 :: Word32 -> Word32 -> Word32 -> Word32 -> Word32
fun2 0 _ _ _ = 0
fun2 q p i r = c1*p + (div (lastDigit*i*p) 10) + (r+1)*c2 + fun2 rest (p*10) (i+1) (lastDigit*p + r)
where c1 = if lastDigit > 2 then 1 else 0
c2 = if lastDigit == 2 then 1 else 0
(rest, lastDigit) = quotRem q 10
main = do
quickCheckWith (stdArgs { maxSuccess = 1000 }) ((\(x, y) -> f1 x y == f2 x y) :: (Word16, Word16) -> Bool)
Il numero di test era "solo" 1000, però immagino che se ci fosse stato un qualche problema sarebbe uscito. Tecnicamente una specie di dimostrazione è comunque contenuta nel mio scorso post anche se probabilmente ho saltato dei passaggi. Mi sento comunque di dire che il metodo è abbastanza "sicuro". La seguente dovrebbe essere una implementazione corretta del metodo in C. Non l'ho però testata molto per cui potrebbero esserci errori.
#include <inttypes.h>
#include <stdint.h>
#include <stdio.h>
uint32_t g(uint16_t n)
{
uint32_t digit = n % 10;
uint32_t quotient = n / 10;
uint32_t rest = digit;
uint32_t power10 = 10;
uint32_t index = 1;
uint32_t result = digit >= 2 ? 1 : 0;
while (quotient != 0) {
digit = quotient % 10;
quotient = quotient / 10;
result += digit > 2 ? power10 : 0;
result += digit * index * power10 / 10;
result += digit == 2 ? rest + 1 : 0;
rest += digit*power10;
power10 *= 10;
++index;
}
return result;
}
uint32_t f(uint16_t x, uint16_t y)
{
if (x > y) {
uint16_t z = x;
x = y;
y = z;
}
uint32_t ret = g(y);
if (x > 0) {
ret -= g(x-1);
}
return ret;
}
int main(void)
{
puts("Inserisci due numeri naturali minori di 2^16.");
uint16_t x = 0, y = 0;
int ret = scanf("%" SCNu16 "%" SCNu16, &x, &y);
if (ret != 2) {
fputs("Errore durante la lettura dei numeri.\n", stderr);
return 1;
}
printf("Il risultato e' %" SCNu32 "\n", f(x, y));
return 0;
}
ok, forse è la volta buona. mi sono accorta che avevo lacune nel linguaggio in assembly vero e proprio, più che nel c, quindi ho usato un po di vacanze per riguardare il libro e cercare di scrivere il codice. questo è quello che ho scritto :
http://www.mediafire.com/?dc06vuhmyd9tt3e
perdonate ancora se ci sono errori , ho passato un pomeriggio ha correggerlo ma ogni volta ne salta fuori uno nuovo ._.
http://www.mediafire.com/?dc06vuhmyd9tt3e
perdonate ancora se ci sono errori , ho passato un pomeriggio ha correggerlo ma ogni volta ne salta fuori uno nuovo ._.
rompo sempre le scatole ! allora IL PROGRAMMA L'HO SCRITTO, E' MODIFICATO RISPETTO A QUELLO PRECEDENTE E ORA COMPILA!!!!!!!!!!!!!!! PER I NUMERI PIU' PICCOLI FUNZIONA ANCHE! IL PROBLEMA E' PER I NUMERI GRANDI, PER QUELLI VA IN OVERFLOW --____--??? https://www.dropbox.com/s/65ib6mq0m3rhd ... mpleta.asm
Ciao,
che algoritmo hai tradotto quello di apatriarca o quello di Shulz?
cmq hai fatto del debug? in che punto del codice (in che registro...) si ha overflow?
"ellosma":
PER I NUMERI PIU' PICCOLI FUNZIONA ANCHE! IL PROBLEMA E' PER I NUMERI GRANDI, PER QUELLI VA IN OVERFLOW --____--
che algoritmo hai tradotto quello di apatriarca o quello di Shulz?
cmq hai fatto del debug? in che punto del codice (in che registro...) si ha overflow?
per il conteggio dei 2, ho utilizzato una funzione basata sull'utilizzo delle potenze negative del 10. in pratica ottengo un overflow dato che mi è concesso utilizzare solo registri a 16 bit ( inparticolare DX:AX) per le divisioni. i risultati dunque non ci stanno dato che abbiamo un divisore troppo piccolo. il programma funziona fino a quando non raggiungo il valore binario 11111111 nella divisione per 10, dopo in AX non ci sta più nulla.
a posto, ho risolto da sola. ora funziona
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo