[c] realizzare programma che fa sottrazione tra 2 numeri naturali da 20 cifre

[Fenomeno85]

Originariamente inviato da Marinelli

La stringa ti serve solo per prendere l'input... poi non la utilizzi più

va buo ma se devi fare calcoli su sto numerone invece di lavorare su singolo carattere è molto + prestante lavorare direttamente su un numero intero

perchè se usi anche un array alla fine non lo puoi caricare nei registri mentre il numero si

~§~ Sempre E Solo Lei ~§~

[andbin]

Originariamente inviato da Fenomeno85

usare tre numeri interi da 32 bit ogniuno lavora su una parte del numero da 96 bit che mi sembrano che bastano

Questa soluzione non sarebbe male .... senonché bisogna preoccuparsi di parecchi dettagli di "basso livello". Bisogna implementare la sottrazione (che è quello che si vuole fare) ma anche le altre tre operazioni di somma/moltiplicazione/divisione (per le conversioni). Inoltre bisogna tenere presente che è necessario gestire il numero a 96 bit in complemento a due (e il bit di segno sta nella parola più alta) e inoltre, per somme/sottrazioni, è necessario gestire il carry/borrow che in linguaggio "C" .... non è (facilmente) direttamente gestibile.

In assembly sarebbe chiaramente moooolto più facile.

[Fenomeno85]

Originariamente inviato da andbin

Questa soluzione non sarebbe male .... senonché bisogna preoccuparsi di parecchi dettagli di "basso livello". Bisogna implementare la sottrazione (che è quello che si vuole fare) ma anche le altre tre operazioni di somma/moltiplicazione/divisione (per le conversioni). Inoltre bisogna tenere presente che è necessario gestire il numero a 96 bit in complemento a due (e il bit di segno sta nella parola più alta) e inoltre, per somme/sottrazioni, è necessario gestire il carry/borrow che in linguaggio "C" .... non è (facilmente) direttamente gestibile.

In assembly sarebbe chiaramente moooolto più facile.

si ma penso che non siano molto più complicati come gestire un array

~§~ Sempre E Solo Lei ~§~

[andbin]

Originariamente inviato da Fenomeno85

si ma penso che non siano molto più complicati come gestire un array

Se deve fare solo una semplice sottrazione è invece più semplice la sottrazione digit x digit.

Non so se conosci l'assembly x86. Questa è una somma su 96 bit in precisione multipla:

MOV   EAX,[ESI+0]
ADD   [EDI+0],EAX
MOV   EAX,[ESI+4]
ADC   [EDI+4],EAX
MOV   EAX,[ESI+8]
ADC   [EDI+8],EAX

(supponendo che ESI punti al operando1 e EDI punti al operando2/destinazione).

Prova a scriverla in "C" puro.

[Fenomeno85]

Originariamente inviato da andbin

Se deve fare solo una semplice sottrazione è invece più semplice la sottrazione digit x digit.

Non so se conosci l'assembly x86. Questa è una somma su 96 bit in precisione multipla:

MOV   EAX,[ESI+0]
ADD   [EDI+0],EAX
MOV   EAX,[ESI+4]
ADC   [EDI+4],EAX
MOV   EAX,[ESI+8]
ADC   [EDI+8],EAX

(supponendo che ESI punti al operando1 e EDI punti al operando2/destinazione).

Prova a scriverla in "C" puro.

mi fai sempre + paura anche te

~§~ Sempre E Solo Lei ~§~

[repne scasb]

Originariamente inviato da andbin

Prova a scriverla in "C" puro.

Bel quesito (a meno di errori grossolani):

#include <stdlib.h>
#include <stdio.h>
#include <time.h>

#define ADD_SIZE (96/32)

void main(void)

{
    unsigned long op1[ADD_SIZE],op2[ADD_SIZE],op3[ADD_SIZE];
    int i,c;
    time_t t;

    srand((unsigned)time(&t));

    printf(" ");
    for(i=ADD_SIZE-1;i>=0;i--)
    {
	op1[i]=rand();
	op1[i]*=op1[i]*op1[i];
	printf("%.8X",op1[i]);
    }
    printf(" +\n ");
    for(i=ADD_SIZE-1;i>=0;i--)
    {
	op2[i]=rand();
	op2[i]*=op2[i]*op2[i];
	printf("%.8X",op2[i]);
    }
    printf(" =\n"-);
    for(i=0;i<ADD_SIZE;i++)
	printf("--------");
    printf("\n");

    for(c=i=0;i<ADD_SIZE;i++)
    {
	op3[i]=op2[i]+op1[i]+c;
	if(((op3[i]-c)<op2[i])||((op3[i]-c)<op1[i]))
	    c=1;
	else
	    c=0;
    }

    printf("%.1X",c);
    for(i=ADD_SIZE-1;i>=0;i--)
	printf("%.8X",op3[i]);
}

Nota: per aumentare la precisione modificare il 96 con un multiplo di 32 maggiore di 96.

[The3DProgrammer]

Originariamente inviato da Andre_Santarell

ciao a tutti
per l'università devo realizzare un programma in c (non in c++ o altro)

premesso che le mie conoscenze sono molto limitate, ilprogramma deve fare la sottrazione tra due numeri naturali di 20 cifre. o meglio da un numero di massimo 20 cifre ne va sottratto un altro qualsiasi


ho già realizzato un semplice programma di sottrazione tra due numeri, il problema e' che se inserisco numeri di oltre dieci cifre mi sballa tutto quanto

come posso fare per risolvere il problema?
potete aiutarmi ?

ma xkè nn provi con l'algoritmo "carta e penna" usando gli array?

anche a me ai suoi tempi hanno fatto questo quesito (con la differenza che i numeri potevano avere un numero di cifre indefinito) e la richiesta era di risolverlo espressamente in quel modo

ciauz

[The3DProgrammer]

Originariamente inviato da ilsensine

E' un problema di dinamica...i numeri interi hanno in genere un range di 2^31 (2^32 gli unsigned), quindi fino a circa 2 (4) giga.

Gli interi a 64 bit arrivano a 2^63 (2^64 gli unsigned), ancora non sufficienti per gestire numeri decimali di venti cifre (2^64 = ~ 1.8*10^19)

Non puoi quindi risolvere il tuo problema con i numeri nativi del c; devi operare direttamente sulle stringhe ed "emulare" la matematica (ringrazia che ti hanno chiesto solo sottrazioni). Probabilmente il problema è studiato ad hoc per obbligarti a usare le stringhe per risolverlo.

credo che anche ilsensine si riferisca a questo

[Energy++]

bisognerebbe fare qualche piccola() modifica però funziona (questo fa la somma)


#include <iostream>
#include <conio.h>
#include <cstdlib>

#define P 20

using namespace std;
char s1[P], s2[P];
int n1[P], n2[P], n3[P];

main(){
cout <<"Inserire il primo numero\n--> ";
gets(s1);
cout <<"\n\nInserire il secondo numero\n--> ";
gets(s2);
int l = strlen(s1), j=0;

for(int i=(P-l); i<P; i++){
n1[i] = s1[j]-48;
n2[i] = s2[j]-48;
j++;}

for(int i=(P-1); i>1; i--){
if(n1[i]+n2[i]>10){
n3[i] = (n1[i]+n2[i])-10;
n1[i-1] += 1;
}
else
n3[i] = n1[i]+n2[i];}
cout <<"risultato: ";
for(int i=0; i<P; i++)
cout <<n3[i];
cout <<"\n\n";
system("pause");
}


ciao ciao

[andbin]

Originariamente inviato da repne scasb

Bel quesito (a meno di errori grossolani):

    ....

    for(c=i=0;i<ADD_SIZE;i++)
    {
	op3[i]=op2[i]+op1[i]+c;
	if(((op3[i]-c)<op2[i])||((op3[i]-c)<op1[i]))
	    c=1;
	else
	    c=0;
    }

    ....

Ehm ... mi risulta che il calcolo del 'carry' è sbagliato.

Dati 2 valori a 96 bit (li scrivo in base 16):

00000000 FFFFFFFF FFFFFFFF +
00000000 00000000 00000001

La tua funzione produce il risultato:
00000000 00000000 00000000

mentre invece il risultato corretto è:
00000001 00000000 00000000

[repne scasb]

Originariamente inviato da andbin

Ehm ... mi risulta che il calcolo del 'carry' è sbagliato.

Vero. Questa "sembrerebbe" funzionare:

#include <stdlib.h>
#include <stdio.h>
#include <time.h>

#define ADD_SIZE (96/32)

void main(void)

{
    unsigned long op1[ADD_SIZE],op2[ADD_SIZE],op3[ADD_SIZE];
    int i,c;
    time_t t;

    srand((unsigned)time(&t));

    printf(" ");
    for(i=ADD_SIZE-1;i>=0;i--)
    {
	op1[i]=rand();
	op1[i]*=op1[i]*op1[i];
	printf("%.8X",op1[i]);
    }
    printf(" +\n ");
    for(i=ADD_SIZE-1;i>=0;i--)
    {
	op2[i]=rand();
	op2[i]*=op2[i]*op2[i];
	printf("%.8X",op2[i]);
    }
    printf(" =\n-");
    for(i=0;i<ADD_SIZE;i++)
	printf("--------");
    printf("\n");

    for(c=i=0;i<ADD_SIZE;i++)
    {
	op3[i]=op2[i]+op1[i]+c;
	if((op3[i]-c)>op3[i])
	    c=1;
	else
	{
	    if(((op3[i]-c)<op2[i])||((op3[i]-c)<op1[i]))
	        c=1;
	    else
	        c=0;
	}
    }

    printf("%.1X",c);
    for(i=ADD_SIZE-1;i>=0;i--)
	printf("%.8X",op3[i]);
}

NOTA: Versione corretta.

[andbin]

Originariamente inviato da repne scasb

Vero. Questa "sembrerebbe" funzionare:

    ...

    for(c=i=0;i<ADD_SIZE;i++)
    {
	op3[i]=op2[i]+op1[i]+c;
	if((op3[i]<op2[i])||(op3[i]<op1[i]))
	    c=1;
	else
	    c=0;
    }

    ...

Non è per romperti le scatole ... ma non è ok nemmeno così.

00000000 FFFFFFFF FFFFFFFF +
00000000 FFFFFFFF 00000001
-----------------------------
00000001 FFFFFFFF 00000000

La tua funzione produce:
00000000 FFFFFFFF 00000000

[Andre_Santarell]

ciao, scusate per il ritardo, l'idea dei 96 bit potrebbe essere buona.. ma il mio prof non la appezzerebbe xké appunto mi ha datoil tutto apposta per farmi lavorare conlestringhe..



in questi giorni con l'aiuto di un mio amico siamo riusciti a fare quasi tutto, seguendo li spunti che mi dette Marinelli.

tuttavia il problema principale arriva quando si fa la sottrazione carattere x carattere

mettiamo che ad esempio si voglia fare 123 meno 4

sarebbe necessario che il programma legga i due numeri come 123 meno 004 e non come 123 meno 400
il problema infatti e' far partire ilprogramma a fare la sottrazione dall'ultima cifra e non dalla prima.. te hai consigli per fare ciò?


viceversa avevamo pensato di fare leggere al programma 123 come
00000000000000000123
meno
00000000000000000003

ossia aggiungendo all'inizio del numero tanti zeri quanti sono le cifre mancanti per arrivare a 20.
ma come fare questo?


una volta che si hanno i due numeri a 20 cifre complete si pensava di fargli fare una sottrazione tra prima cifra da sinistra del primo numero e prima cifra da sinistra del secondo numero. e che quindi controllasse che:
se la cifra del primo numero e' maggiore o uguale aquella del secondo faccia la semplice sottrazione tra due numeri e la memorizzi
se invece la cifra del primo numero è minore di quella del secondo consideri la prima cifra con l'aggiunta di 10, quindi faccia la normale sottrazione e scali il risultato dell' operazione delle due cifre precedenti di uno.

ci sono modi più rapidi?
grazie mille
ciao
Andrea

[Andre_Santarell]

Originariamente inviato da Energy++

bisognerebbe fare qualche piccola() modifica però funziona (questo fa la somma)


#include <iostream>
#include <conio.h>
#include <cstdlib>

#define P 20

using namespace std;
char s1[P], s2[P];
int n1[P], n2[P], n3[P];

main(){
cout <<"Inserire il primo numero\n--> ";
gets(s1);
cout <<"\n\nInserire il secondo numero\n--> ";
gets(s2);
int l = strlen(s1), j=0;

for(int i=(P-l); i<P; i++){
n1[i] = s1[j]-48;
n2[i] = s2[j]-48;
j++;}

for(int i=(P-1); i>1; i--){
if(n1[i]+n2[i]>10){
n3[i] = (n1[i]+n2[i])-10;
n1[i-1] += 1;
}
else
n3[i] = n1[i]+n2[i];}
cout <<"risultato: ";
for(int i=0; i<P; i++)
cout <<n3[i];
cout <<"\n\n";
system("pause");
}


ciao ciao

grazie provo alavorare anche su questo
ciao
Andrea

[Qu@ker]

Relativamente ai 96 bit, non si potrebbero utilizzare i long long per le somme intermedie, es.:

	for (c = i = 0; i < ADD_SIZE; i++) {
		unsigned long long tmp = (unsigned long long)op2[i] + op1[i] + c;
		c = (tmp > ULONG_MAX);
		op3[i] = (unsigned long)tmp;
	}

Nell'ipotesi, ovviamente, di long di 32 bit e long long di 64...

[a2000.1]

Sub aaa()

 a$ = "10000000000000000000"
 b$ = "00000000000000000001"
 c$ = "00000000000000000000"
 
 ir = 0
 For i = Len(a$) To 1 Step -1
  ci = Val(Mid$(a$, i, 1)) + ir - Val(Mid$(b$, i, 1))
  ir = (ci < 0)
  ci = ci - ir * 10
  Mid$(c$, i, 1) = Format$(ci)
 Next i

End Sub

[Fenomeno85]

minchia da quanto tempo a

ma dove eri finito?

ci mancava il vb

~§~ Sempre E Solo Lei ~§~

[a2000.1]

36 h ?



HPF is better

[a2000.1]

http://www.google.it/search?hl=it&q=HPF&meta=

[Fenomeno85]

Originariamente inviato da a2000.1

36 h ?



HPF is better

ah si ... va bhe non ti avevo visto


~§~ Sempre E Solo Lei ~§~