# Zwei Integer Arrays multiplizieren



## DennOO (28. Nov 2009)

Hallo,

ich habe schon den ein oder anderen Thread hier gelesen, auch den einen etwas längeren zum Thema Array Multiplikation.
Trotzdem komme ich absolut nicht auf irgendeinen Lösungsweg.

Ziel ist es zwei Integer Arrays die eine Aufgesplittete Zahl enthalten,
z.B.

array 1 [1,4,5] für 145
array 2 [3,5,6] für 356

miteinander zu multiplizieren und das Ergebnis wieder in einem Integer Array zurückzuliefern.
Wie stell ich das am besten an und ist es sinnvoll irgendwelche Unterfunktionen zu schreiben die mir Einzelschritte der Berechnung erleichtern? :O

Als Lösungsansatz (falls man es so bezeichnen kann), würde ich ja die "Streifenmethode" sehen, wie auf dieser Seite hier ganz unten: Multiplikation

Danke für Eure Hilfe, ich steh echt auf dem Schlauch damit.


----------



## eRaaaa (28. Nov 2009)

*>> und das Ergebnis wieder in einem Integer Array zurückzuliefern*

hmm, eine zahl in ein array zu packen ist irgendwie sinnfrei ?! aber na gut 

*>> Als Lösungsansatz (falls man es so bezeichnen kann), würde ich ja die "Streifenmethode" sehen*

ist das eine vorgabe, oder eine überlegung deiner seits?

also ich würds vllt so machen:

array von hinten durchlaufen und aufsummieren. dabei merkt man sich immer die aktuelle stelle.

int stelle = 1;

5*stelle = 5; 
stelle*10;
4*stelle = 40;
stelle*10;
1*stelle = 100;

summeA = 100+40+5 = 145;

das gleiche mit dem anderen array (oder wenn sie immer gleich groß sind, kann man das auch in einem abwasch machen)
und dann halt miteinander multiplizieren.


gruß


----------



## DennOO (28. Nov 2009)

Ja das wäre quasi der einfache Weg um das Array wieder zusammenzusetzen, normal zu multiplizieren und am Ende wieder zu splitten. So soll es leider nicht laufen, sondern das neue Array soll direkt gebildet werden ohne das man das erste vorher zusammensetzt. Für extrem große Zahlen die den Integer Spielraum überschreiten muss es ja auch funktionieren und das würde beim Zusammensetzen und multiplizieren nicht klappen. :/
Danke dennoch.


Achja, diese "Streifenmethode" war eine Überlegung meinerseits, weil es ja das Ziel erfüllen würde. Wie ich sie umsetzen soll: keine Ahnung. :/


----------



## chri (28. Nov 2009)

wenn man sichs mit stift und papier den vorgang aufzeichnet kommt man auf folgendes

```
/*
	 * (m,n sind rechteste/niedrigwertigste stellen, =lenght-1)
	 * Stelle
	 * 0.  [n]*[m]
	 * 1.  [n]*[m-1] + [n-1]*[m] + Übertrag
	 * 2.  [n]*[m-2] + [n-1]*[m-1] + [n-2]*[m] + Übertrag
	 * 
	 * daraus kann gefolgt werden: (im obrigen fehlen eben die out of bounds teile)
	 * 0.  [n]*[m]   + [n-1]*[m+1] + [n-2]*[m+2] + Übertrag
	 * 1.  [n]*[m-1] + [n-1]*[m]   + [n-2]*[m+1] + Übertrag
	 * 2.  [n]*[m-2] + [n-1]*[m-1] + [n-2]*[m] + Übertrag
	 */
```

D.h. es gibt zwei Schleifen.
Die erste durchläuft die stellen des ergebnis-arrays und berechnet dabei die summe in der zweiten schleife.
In dieser wird array N in die eine richtung durchlaufen und array M in die andere, wobei diese mit einem Element abhängig von der derzeitigen Stelle beginnt.


----------

