Rechnen mit mehrstelligen Zahlen

DirkB schrieb:

... bedenke das 0 was anderes ist als '0'.

Ich habe den Algorythmus jetzt nicht durchgesehen aber:
In deinen Arrays ErsteZahl und ZweiteZahl stehen Texte drin und da ist '0' was anderes als 0.

printf(" mit': %d ;ohne': %d\n",'0',0);

Darum musst du bei deinen Zahlen immer '0' abziehen oder dazurechnen.

Du musst das Array Result initialisieren.
Am Ende muß eine '\0' hin.

Und bei printf("\nResultat: %d\n", Resultat); funktioniert %d sicher nicht (das gibt int aus).

Auch wenn das nur eine Übung ist; gewöhne dir an, eine Struktur für die einzelnen Zahlen zu erstellen (die vllt. nur ein Array enthält) und eine Funktion fürs Einlesen und Multiplizieren zu schreiben. Es ist nicht nur für uns ästhetischer, es hilft auch dir beim Denken.

Nur so nebenbei: wenn du es wirklich performant haben willst, musst du mit der Fourier-Transformation arbeiten. Dann kannst du die Zahlen in O(n·log(n)) anstatt O(n²) wie jetzt multiplizieren. Aber so wie du fragst, wird dich das nicht kümmern.

volkard

Furie schrieb:

Nur so nebenbei: wenn du es wirklich performant haben willst, musst du mit der Fourier-Transformation arbeiten. Dann kannst du die Zahlen in O(n·log(n)) anstatt O(n²) wie jetzt multiplizieren. Aber so wie du fragst, wird dich das nicht kümmern.

eMaNu3L schrieb:

Der Knackpunkt dabei ist, dass die beiden Zahlen bis zu 30 Stellen und mehr haben können!

eMaNu3L schrieb:

bis zu 30 Stellen und mehr

http://xkcd.com/870/

eMaNu3L

Also im Moment siehts so aus:

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

#define MAXSTELLEN 31
#define RESULTATMAXSTELLEN 166
int main()
 {
  /* VARIABLEN (lokal) --------- */
  char ErsteZahl[MAXSTELLEN];
  char ZweiteZahl[MAXSTELLEN];

  char Resultat[RESULTATMAXSTELLEN];
  int i, j = 0;

  /* Intro --------------------- */
  printf("Dieses Programm multipliziertz zwei %i-Stellige Zahlen\n", MAXSTELLEN-1);
  printf("------------------------------------------------------\n\n\n");

  printf("Geben Sie ihre erste Zahl ein: ");
  scanf("%s", &ErsteZahl);

  printf("Geben Sie ihre zweite Zahl ein: ");
  scanf("%s", &ZweiteZahl);

  /* Berechnung ---------------- */
     for (i = 0; i < strlen(ErsteZahl); i++)
     {
            for (j = 0; j < strlen(ZweiteZahl); j++)
            {
                 Resultat[i + j] += (ErsteZahl[i]-'\0') * (ZweiteZahl[j]-'0');
                 if (Resultat[i + j] > '9')
                 {
                      Resultat[i + j + 1] = (Resultat[i + j]-'0') / 10 + '0';
                      Resultat[i + j] = (Resultat[i + j]-'0') % 10 + '0'; 
                 }
            }
      }
  }

  /* Ausgabe ------------------- */
  printf("\nResultat: %s\n", Resultat);

  system("PAUSE");   
  return 0;
 }

leider funzts immer noch nicht :(( (Kann es nicht starten..) Irgendein Conflicting Type printf und noch ne andere Fehlermeldung spuckt er aus

Was hab ich den falsch? Hab echt kein Plant

Hoffe ihr könnt mir helfen

MfG

eMaNu3L

ok debuggen klappt.. (ne klammer zuviel gehabt :D), doch ergebnis immer wieder falsch.. gibt immer welche smileys oder sonstiges aus

Du solltest schon bei den Einerstellen anfangen zu rechnen. Im Augenblick fängst du bei der höchsten Stelle an (ganz links).

Du musst die Strings irgendwie umdrehen oder von rechts nach links rechnen.
Das betrifft auch das Ergebnis. (Habe ich aber schon in meinem ersten Post erwähnt )

Einmal hast du '\0' statt '0' stehen.

Resultat sollte mit "000000000.....000" vorbesetzt sein, sonst klappt die Zeile 30 nicht.. (Mach eine Schleife).

Bei der Eingabe von Strings brauchst du bei scanf kein & !

EVIL_ENT

Ich arbeite grade an was Ähnlichem (allerdings mit linked lists und integern, was aber im Endeffekt aufs gleiche rauskommen sollte).

Addition funktioniert, aber mir ist noch kein Ansatz eingefallen um bei Multiplikation nen overflow zu vermeiden. Wenn ich zum Beispiel 999999... mit 99999999.... multipliziere könnte der Übertrag ziemlich groß werden (wenn man das schriftliche Multiplikationsverfahren benutzt).

Ich hab mir mal den Wikipedia-Artikel zu Fourier-Transformation angesehen, aber außer kryptischen Zeichen sehe ich da nicht viel.
Hat jemand vielleicht nen anderen Ansatz oder kann das mit der Fourier-Transformation erklären?

Wenn du ein N-stellige mal M-stellige Zahl multiplizierst hat das Ergebnis max. N+M Stellen (min. N+M-1 Stellen) . Egal ob schriftlich oder sonst wie multipliziert.

Den Überlauf kannst du vermeiden, wenn du für das Ergebnis N+M Stellen reservierst.

CStoll

Beim Multiplizieren zweier Ziffern hast du maximal den Übertrag 8 (9*9=81), das ist noch leicht zu verarbeiten. Daher müsstest du die Multiplikation in mehrere Teilschritte zerlegen:

zahl mult(zahl a,zahl b)
{
  zahl result;
  for(int i=0;i<a.length;++i)
  {
    zahl subresult = multziffer(a[i],b);
    verschiebe(subresult,i);// Multiplikation mit 10^i -> i Nullen an den Anfang anhängen
    result = add(result,subresult);
  }
  return result;
}

zahl multziffer(int z, zahl b)
{
  int carry=0;
  assert(ziffer<10);
  zahl result;
  for(int i=0;i<b.length;++i)
  {
    int value = b[i]*z + carry;
    result[i] = value%10;
    carry = value/10;
  }
  if(carry>0)
    result[b.length]=carry;
  return result;
}

(ist natürlich alles nur Pseudocode und ungetestet)

EVIL_ENT

ahja stimmt

ich dachte, dass ich carry nocheinmal mit 9 multiplizieren müsste, aber das ist natürlich schwachsinn

Vielen Dank