[GELÖST] Multiplikation in Stacks?

Übersicht

Sonstiges

Smalltalk

	CO2 ehemals "SirMO" Betreff: [GELÖST] Multiplikation in Stacks?	Sa, März 15, 2014 17:44 Antworten mit Zitat
Hallo, ich gebe zu, dass der Titel nicht ganz zum Problem passt, aber ein besserer fiel mir leider nicht ein Folgendes Problem: Ich habe einen Stack (LIFO), der pro Element ein Byte speichern kann. Er ist Größentechnisch unbegrenzt, er kann also theoretisch unendlich viele Bytes speichern. Außerdem habe ich einen "RAM", dieser ist begrenzt: Er kann maximal ein Byte speichern. Für den Stack habe ich folgende Optionen: - Oberstes Element im Stack in den RAM legen (dabei wird das Element aus dem Stack gelöscht), - Element aus RAM in Stack, - oberstes Element im Stack um 1 inkrementieren, - oberstes Element im Stack um 1 dekrementieren, - oberstes Element im Stack auf 0 prüfen, - Byte im RAM um 1 inkrementieren, - Byte im RAM um 1 dekrementieren, - Byte im RAM auf 0 prüfen. Eine Addition sähe also prinzipiell wie folgt aus: 1.) Zwei Variablen in den Stack legen (push) (beide Summanden) 2.) Oberste Variable im Stack in den RAM (dabei wird sie gelöscht, die nachfolgende rückt nach) 3.) Die Variable im Stack solange um 1 erhöhen und die im RAM um 1 verringern, bis die Variable im RAM gleich 0 ist. 4.) Ergebnis befindet sich als oberstes Element im Stack Bei der Subtraktion ist es ähnlich, nur der 3. Schritt muss angepasst werden: 3.) Die Variable im Stack solange um 1 verringern und die im RAM um 1 verringern, bis die Variable im RAM gleich 0 ist. Das soweit zur Theorie. Nun habe ich allerdings ein Problemchen: Kann man mit dieser "Stackmaschine" eine Multiplikation durchführen, und wenn ja, wie?
mfG, CO² Sprachen: BlitzMax, C, C++, C#, Java Hardware: Windows 7 Ultimate 64-Bit, AMX FX-6350 (6x3,9 GHz), 32 GB RAM, Nvidia GeForce GTX 750 Ti

CO2

ehemals "SirMO"

Betreff: [GELÖST] Multiplikation in Stacks?

Sa, März 15, 2014 17:44
Antworten mit Zitat

Hallo,
ich gebe zu, dass der Titel nicht ganz zum Problem passt, aber ein besserer fiel mir leider nicht ein Embarassed

Folgendes Problem:
Ich habe einen Stack (LIFO), der pro Element ein Byte speichern kann. Er ist Größentechnisch unbegrenzt, er kann also theoretisch unendlich viele Bytes speichern. Außerdem habe ich einen "RAM", dieser ist begrenzt: Er kann maximal ein Byte speichern. Für den Stack habe ich folgende Optionen:
- Oberstes Element im Stack in den RAM legen (dabei wird das Element aus dem Stack gelöscht),
- Element aus RAM in Stack,
- oberstes Element im Stack um 1 inkrementieren,
- oberstes Element im Stack um 1 dekrementieren,
- oberstes Element im Stack auf 0 prüfen,
- Byte im RAM um 1 inkrementieren,
- Byte im RAM um 1 dekrementieren,
- Byte im RAM auf 0 prüfen.

Eine Addition sähe also prinzipiell wie folgt aus:
1.) Zwei Variablen in den Stack legen (push) (beide Summanden)
2.) Oberste Variable im Stack in den RAM (dabei wird sie gelöscht, die nachfolgende rückt nach)
3.) Die Variable im Stack solange um 1 erhöhen und die im RAM um 1 verringern, bis die Variable im RAM gleich 0 ist.
4.) Ergebnis befindet sich als oberstes Element im Stack

Bei der Subtraktion ist es ähnlich, nur der 3. Schritt muss angepasst werden:
3.) Die Variable im Stack solange um 1 verringern und die im RAM um 1 verringern, bis die Variable im RAM gleich 0 ist.

Das soweit zur Theorie. Nun habe ich allerdings ein Problemchen: Kann man mit dieser "Stackmaschine" eine Multiplikation durchführen, und wenn ja, wie?

mfG, CO²

Sprachen: BlitzMax, C, C++, C#, Java
Hardware: Windows 7 Ultimate 64-Bit, AMX FX-6350 (6x3,9 GHz), 32 GB RAM, Nvidia GeForce GTX 750 Ti

Zuletzt bearbeitet von CO2 am Fr, März 28, 2014 23:49, insgesamt 4-mal bearbeitet

	PhillipK	Sa, März 15, 2014 21:16 Antworten mit Zitat
Intressante aufgabenstellung. Leider fällt mir dazu grade keine wirkliche idee ein. Allerdings: Zitat: 1.) Zwei Variablen in den Stack legen (push) (beide Summanden) Wenn dies möglich ist, kannst du auch auch n Variablen in den Stack puschen? Genauer: Wenn du die rechnung 47 hast, kannst du die "4" insgesamt 7 mal hineinpuschen? Wenn ja, sähe eine multiplikation dann nicht so aus: 1) eine 0 auf den Stack puschen 2) n mal die erste varible der multipaktion in den stack puschen (beispiel: die 4 muss 7 mal hinein, wenn die rechnung 47 heißt.) 3) Variable von stack in den ram 4) Obersten stack um 1 erhöhen, variable im ram um 1 verringern 5) solange weitermachen, bis variable im Ram auf 0 ist 6) Obersten stack in ram 7) Wenn die nächste variable im stack = 0, dann zuletzt nochmal den ram in den stack schreiben. - Alternativ zurück zu 4) Ich weiß nicht, ob du diese "ist oberster stack = 0" operation durchführen kannst. Ich vermute einfach mal das es geht, da du auch an stack in soweit rankommst, das du sie incrementieren kannst. Eine andere alternative fällt mir mit den genannten rahmenbedingungen nicht ein oO

PhillipK

Sa, März 15, 2014 21:16
Antworten mit Zitat

Intressante aufgabenstellung.

Leider fällt mir dazu grade keine wirkliche idee ein.
Allerdings:
Zitat:

1.) Zwei Variablen in den Stack legen (push) (beide Summanden)

Wenn dies möglich ist, kannst du auch auch n Variablen in den Stack puschen?

Genauer:

Wenn du die rechnung 4*7 hast, kannst du die "4" insgesamt 7 mal hineinpuschen?
Wenn ja, sähe eine multiplikation dann nicht so aus:

1) eine 0 auf den Stack puschen
2) n mal die erste varible der multipaktion in den stack puschen (beispiel: die 4 muss 7 mal hinein, wenn die rechnung 4*7 heißt.)
3) Variable von stack in den ram
4) Obersten stack um 1 erhöhen, variable im ram um 1 verringern
5) solange weitermachen, bis variable im Ram auf 0 ist
6) Obersten stack in ram
7) Wenn die nächste variable im stack = 0, dann zuletzt nochmal den ram in den stack schreiben. - Alternativ zurück zu 4)

Ich weiß nicht, ob du diese "ist oberster stack = 0" operation durchführen kannst. Ich vermute einfach mal das es geht, da du auch an stack in soweit rankommst, das du sie incrementieren kannst.

Eine andere alternative fällt mir mit den genannten rahmenbedingungen nicht ein oO

	BladeRunner Moderator	So, März 16, 2014 7:13 Antworten mit Zitat
Woher kommen denn die Variablen die Du in den Stack pushst? Hast Du eine Funktion PushStack(var) oder muss das über das eine Byte RAM erfolgen? Anders gesprochen, gibt es eine Eingabe von extern? Und hat der Nutzer zur Laufzeit Zugriff darauf oder muss das alles schon vordefiniert sein? Bei einer Multiplikation zweier Bytes kann das Ergebnis ja auch über einem Byte in der Länge liegen. Hast Du die Möglichkeit auf den stackpointer zuzugreifen, sprich festzulegen welches element gepopt wird, oder wird wirklich strikt nur das letzt gepushte Byte auch gepopt?
Zu Diensten, Bürger. Intel T2300, 2.5GB DDR 533, Mobility Radeon X1600 Win XP Home SP3 Intel T8400, 4GB DDR3, Nvidia GF9700M GTS Win 7/64 B3D BMax MaxGUI Stolzer Gewinner des BAC#48, #52 & #92

BladeRunner

Moderator

So, März 16, 2014 7:13
Antworten mit Zitat

Woher kommen denn die Variablen die Du in den Stack pushst? Hast Du eine Funktion PushStack(var) oder muss das über das eine Byte RAM erfolgen?
Anders gesprochen, gibt es eine Eingabe von extern?
Und hat der Nutzer zur Laufzeit Zugriff darauf oder muss das alles schon vordefiniert sein?
Bei einer Multiplikation zweier Bytes kann das Ergebnis ja auch über einem Byte in der Länge liegen. Hast Du die Möglichkeit auf den stackpointer zuzugreifen, sprich festzulegen welches element gepopt wird, oder wird wirklich strikt nur das letzt gepushte Byte auch gepopt?

Zu Diensten, Bürger.
Intel T2300, 2.5GB DDR 533, Mobility Radeon X1600 Win XP Home SP3
Intel T8400, 4GB DDR3, Nvidia GF9700M GTS Win 7/64
B3D BMax MaxGUI
Stolzer Gewinner des BAC#48, #52 & #92

	CO2 ehemals "SirMO"	So, März 16, 2014 22:39 Antworten mit Zitat
Zunächst danke für die Antworten @ PhillipK: Zitat: Wenn dies möglich ist, kannst du auch auch n Variablen in den Stack puschen? Der Stack ist unbegrenzt, was seine Kapazität angeht, also ich kann so viele Bytes hineinpushen, wie ich will. Zitat: Wenn du die rechnung 4*7 hast, kannst du die "4" insgesamt 7 mal hineinpuschen? Prinzipiell Ja, allerdings gibt es da das Problem, dass ich nebenbei zählen muss, wie oft und welche Zahl schon in den Stack gepusht wurde, d.h. bei dem Beispiel: Ich muss speichern, dass ich zum einen die Zahl 7 in den Stack speichern muss und außerdem muss ich speichern, wie oft ich diese schon in den Stack gepusht habe. Zitat: ist oberster stack = 0 Verzeihung, das hatte ich vergessen: Ich kann zu den o.g. Optionen auch noch Vergleiche mit gleich Null durchführen, für das Byte im RAM und für das oberste Element im Stack, wird oben nachgetragen... Zitat: Eine andere alternative fällt mir mit den genannten rahmenbedingungen nicht ein Ich bin schon seit 5 Tagen am rumgrübeln, ob es unter den Umständen überhaupt möglich ist zu multiplizieren... @ BladeRunner: Zitat: Woher kommen denn die Variablen die Du in den Stack pushst? Es gibt zum einen eine Eingabe von Extern, aber auch die Möglichkeit, das vor der Ausführung festzulegen. In beiden Fällen geschieht dies RAM unabhängig, d.h. die Variablen werden direkt in den Stack gepusht, der RAM bleibt während der ganzen Aktion "leer". Zitat: Und hat der Nutzer zur Laufzeit Zugriff darauf oder muss das alles schon vordefiniert sein? Worauf? Auf die Variablen, die im Stack liegen? Zitat: (...) oder wird wirklich strikt nur das letzt gepushte Byte auch gepopt? Es ist ein strikter Last-In-First-Out-Stack, ich kann nicht definieren, welches Element im Stack als nächstes gepopt wird, außer ich pushe sie vorher entsprechend.
mfG, CO² Sprachen: BlitzMax, C, C++, C#, Java Hardware: Windows 7 Ultimate 64-Bit, AMX FX-6350 (6x3,9 GHz), 32 GB RAM, Nvidia GeForce GTX 750 Ti

CO2

ehemals "SirMO"

So, März 16, 2014 22:39
Antworten mit Zitat

Zunächst danke für die Antworten Wink

@ PhillipK:
Zitat:

Wenn dies möglich ist, kannst du auch auch n Variablen in den Stack puschen?

Der Stack ist unbegrenzt, was seine Kapazität angeht, also ich kann so viele Bytes hineinpushen, wie ich will.

Zitat:

Wenn du die rechnung 4*7 hast, kannst du die "4" insgesamt 7 mal hineinpuschen?

Prinzipiell Ja, allerdings gibt es da das Problem, dass ich nebenbei zählen muss, wie oft und welche Zahl schon in den Stack gepusht wurde, d.h. bei dem Beispiel: Ich muss speichern, dass ich zum einen die Zahl 7 in den Stack speichern muss und außerdem muss ich speichern, wie oft ich diese schon in den Stack gepusht habe.

Zitat:

ist oberster stack = 0

Verzeihung, das hatte ich vergessen: Ich kann zu den o.g. Optionen auch noch Vergleiche mit gleich Null durchführen, für das Byte im RAM und für das oberste Element im Stack, wird oben nachgetragen...

Zitat:

Eine andere alternative fällt mir mit den genannten rahmenbedingungen nicht ein

Ich bin schon seit 5 Tagen am rumgrübeln, ob es unter den Umständen überhaupt möglich ist zu multiplizieren...

@ BladeRunner:
Zitat:

Woher kommen denn die Variablen die Du in den Stack pushst?

Es gibt zum einen eine Eingabe von Extern, aber auch die Möglichkeit, das vor der Ausführung festzulegen. In beiden Fällen geschieht dies RAM unabhängig, d.h. die Variablen werden direkt in den Stack gepusht, der RAM bleibt während der ganzen Aktion "leer".

Zitat:

Und hat der Nutzer zur Laufzeit Zugriff darauf oder muss das alles schon vordefiniert sein?

Worauf? Auf die Variablen, die im Stack liegen?

Zitat:

(...) oder wird wirklich strikt nur das letzt gepushte Byte auch gepopt?

Es ist ein strikter Last-In-First-Out-Stack, ich kann nicht definieren, welches Element im Stack als nächstes gepopt wird, außer ich pushe sie vorher entsprechend.

mfG, CO²

Sprachen: BlitzMax, C, C++, C#, Java
Hardware: Windows 7 Ultimate 64-Bit, AMX FX-6350 (6x3,9 GHz), 32 GB RAM, Nvidia GeForce GTX 750 Ti

	BladeRunner Moderator	Mo, März 17, 2014 8:02 Antworten mit Zitat
Wenn Du externe Eingaben hast / Vordefinieren kannst ist die einzig valide Möglichkeit die von PhillipK, wobei dem Nutzer dann die Vorarbeit des Pushens der Summanden für die Multiplikation bleibt. Das Problem des Überlaufs des Ergebnisses lässt sich so nicht lösen.
Zu Diensten, Bürger. Intel T2300, 2.5GB DDR 533, Mobility Radeon X1600 Win XP Home SP3 Intel T8400, 4GB DDR3, Nvidia GF9700M GTS Win 7/64 B3D BMax MaxGUI Stolzer Gewinner des BAC#48, #52 & #92

BladeRunner

Moderator

Mo, März 17, 2014 8:02
Antworten mit Zitat

Wenn Du externe Eingaben hast / Vordefinieren kannst ist die einzig valide Möglichkeit die von PhillipK, wobei dem Nutzer dann die Vorarbeit des Pushens der Summanden für die Multiplikation bleibt. Das Problem des Überlaufs des Ergebnisses lässt sich so nicht lösen.

Zu Diensten, Bürger.
Intel T2300, 2.5GB DDR 533, Mobility Radeon X1600 Win XP Home SP3
Intel T8400, 4GB DDR3, Nvidia GF9700M GTS Win 7/64
B3D BMax MaxGUI
Stolzer Gewinner des BAC#48, #52 & #92

	ZEVS	Mo, März 17, 2014 22:00 Antworten mit Zitat
Die Frage sieht ziemlich stark nach einer Frage der Theoretischen Informatik aus, wo ich davon ausgehen würde, dass "Byte" eine beliebig große natürliche Zahl meint, ist das so? Wenn dem so ist, müsste m.E. die Unmöglichkeit der Multiplikation bewiesen werden können, auch wenn ich daran schon ein paarmal verzweifelt bin. Andernfalls wäre für die Multiplikation zweier Bytes ja eine Fallunterscheidung von den 256x256 verschiedenen möglichen Faktoren möglich (indem man immer dekrementiert und schaut, wann man bei 0 ist). Ich gehe nicht davon aus, dass du darauf nach fünf Tagen rumgrübeln nicht gekommen bist, also gehe ich davon aus, dass die betrachteten Zahlen beliebig groß werden dürfen. Recht einfach kam ich auf einen Algorithmus zum Quadrieren: 0. Die zu quadrierende Zahl n liegt im Stack. 1. Entferne das oberste Stack-Element und schreibe es in den RAM (Pop). 2. Schiebe ein neues Element mit dem Inhalt vom RAM auf den Stack (Push). 3. Push. 4. Solange das oberste Stack-Element nicht Null ist, dekrementiere es. (Dann sieht es so aus: Stack (rechts = oben): n 0 RAM: n) 5. Wenn der RAM gleich 0 ist, gehe zu 9. 6. Push 7. Dekrementiere den RAM 8. Goto 5. (Dann sieht es so aus: Stack: n 0 n (n-1) (n-2) ... 1 RAM: 0 9. Wenn das oberste Stack-Element gleich 0 ist, gehe zu 14. 10. Addiere den Inhalt des RAMs zum obersten Stack-Element. 11. Pop. 12. Goto 9. (Dann sieht es so aus: Stack: n 0 RAM: n + (n-1) + ... + 1. Nach dem kleinen Gauß ist der Inhalt des RAMs gleich (n²+n)/2 ). 13. Push 14. Addiere den Inhalt des RAMs zum obersten Stack-Element. (Inhalt des ersten Stack-Elements: n²+n) 15. Pop (addiere nun die 0 dazu) 16. wie 14. 17. wie 15. 18. Subtrahiere das oberste Stack-Element vom RAM. 19. Terminiere. Im RAM liegt n². Soweit ganz schön, aber das klappt nur mit der Zahl im RAM. Da bei der Multiplikation wenigstens einer der Faktoren im Stack bleiben muss, hilft das hier nicht viel. Das Blöde ist aber, dass man die Unmöglichkeit der Multiplikation nicht darüber beweisen kann, dass diese (bzw. die damit berechenbare Fakultät) zu stark wächst. Dies ist ein ziemlich beliebtes Konzept der Berechenbarkeitstheorie, hier aber nicht anwendbar, denn der durchaus berechenbare Term (a+b)² ist größer als ab. Ich versuche mich gerade daran, zu untersuchen, welche Eigenschaften die berechenbaren Funktionen haben müssen, aber das scheint ein sehr fehleranfälliges und frustrierendes Unterfangen zu sein. ZEVS edit: Ich habe eine Methode zum Multiplizieren (bei unbegrenzten "Bytes") gefunden: Da man auf drei Variablen zurgreifen muss, um a+a+a+a...+a (b-mal) zu berechnen (man muss a, die Zwischensumme und das dekrementierte b speichern), erschien mir diese Berechnung zunächst unmöglich, aber dem ist nicht so. Man kann den obersten Wert im Stack (nennen wir ihn s) und den Inhalt des Rams r zu einem einzelnen Wert zusammenfassen die Ursprungswerte daraus wieder gewinnen. Der Term (2r+1) * 2^s dient hier als Zwischenwert. Der folgende Algorithmus berechnet (2r+1) 2^s: 1. Verdopple den RAM (d.h. Push, addiere den Inhalt des RAMs zum obersten Stack-Element, Pop). 2. Inkrementiere den RAM um 1 3. Wenn das oberste Stack-Element gleich 0 ist, gehe zu 7. 4. Dekrementiere das oberste Stack-Element um 1. 5. Verdopple den RAM. 6. Goto 3. 7. (das oberste Stack-Element ist nun 0 und der RAM enthält den gewünschten Wert) Addiere den RAM zum obersten Stack-Element. 8. Pop. Die Anweisungen 1. und 2. errechnen 2r+1 und speichern diesen Wert im RAM, die Anweisungen 3.-6. verdoppeln den RAM s-mal. Die Umkehrung geht, indem man den Wert möglichst oft durch 2 dividiert, denn 2r+1 ist ungerade, also kann man genau s-mal durch 2 dividieren. Liegt (2r+1) 2^s im RAM bringt der folgende Algorithmus s in den Stack und r in den RAM: 1. Push. 2. Solange das oberste Stack-Element nicht Null ist, dekrementiere es. (Zustand dann: Stack: 0 RAM: (2r+1) 2^s. 3. (prüfe, ob der RAM einen geraden Wert enthält) Push (Sicherungskopie). 4. Wenn der RAM gleich 0 ist, gehe zu 9. 5. Dekrementiere den RAM um 1. 6. Wenn der RAM gleich 0 ist, gehe zu 13. 7. Dekrementiere den RAM. 8. Goto 4. 9. (RAM gerade) Pop (RAM wiederherstellen). 10. Halbiere den Inhalt des RAM (s.u.). 11. Inkrementiere das oberste Stack-Element um 1. 12. Goto 3. 13. Pop (RAM wiederherstellen). 14. (RAM ungerade, s liegt im obersten Stack-Element und (2r+1) im RAM) Dekrementiere den RAM um 1. 15. Halbiere den Inhalt des RAMs. Die Anweisungen 4.-8. verringern den RAM immer um 2 und prüfen damit, ob dieser gerade oder ungerade ist. In erstem Fall wird er halbiert und das oberste Stack-Element inkrementiert (9.-12.). Das Halbieren des RAMs geht wie folgt: 1. Push 2. Wenn der RAM gleich 0 ist: Pop, Terminiere. 3. Dekrementiere das oberste Stack-Element um 1 4. Dekrementiere den RAM um 1 5. Dekrementiere den RAM um 1 6. Goto 2. Mit diesem Algorithmen zum Zusammenfassen von Werten ist es möglich, ohne Informationsverlust auch Werte zu verarbeiten, die nicht im RAM bzw. an erster Stelle im Stack stehen. Wenn man die beiden Werte aus Stack und RAM zusammenfassen kann, geht die Multiplikation: 0. Die beiden Faktoren (a, b) sind die beiden Stack-Elemente. 1. Pop. 2. Push. 3. Solange das oberste Stack-Element nicht null ist, dekrementiere es um 1. (Zustand dann: Stack: a 0 RAM: b) 4. Fasse oberstes Stack-Element und RAM zu einem Wert im RAM zusammen (s.o.) 5. Wenn das oberste Stack-Element gleich 0 ist, gehe zu 10. 6. Dekrementiere das oberste Stack-Element um 1. 7. Stelle die beiden unter 4. zusammengefassten Werte wieder her. 8. Addiere den Wert im RAM zu dem im Stack, ohne den RAM zu verändern (s.u.). 9. Goto 4. 10. Stelle die beiden unter 4. zusammengefassten Werte wieder her. (Zustand dann: Stack: 0 ab RAM: b) 11. Pop 12. Addiere den RAM zum obersten Stack-Element 13. Pop. Terminiere. Der Stack ist leer und der RAM enthält ab. Die Anweisungen 4.-9. verarbeiten die drei Werte a, x und b, wobei a und b die Parameter sind und x (die Zwischensumme, zunächst 0) a-mal um b addiert wird (hierzu wird a stets dekrementiert). x und b werden in 4. zusammengefasst, um auf a zuzugreifen. Als letztes muss die Anweisung zum Addieren des RAMs zum ersten Stack-Element ohne Null-Setzen des RAMs geklärt werden. Auch diese geht mit dem Trick zum Zusammenfassen: 0. Im Stack liegt die Zahl x und im RAM die Zahl y. Am Ende soll im Stack x+y liegen und im RAM y. 1. Push. 2. Wenn der RAM gleich 0 ist, gehe zu 6. 3. Dekrementiere den RAM. 4. Inkrementiere das zweite Stack-Element (d.h. fasse RAM und oberstes Stack-Element zusammen, inkrementiere dann das oberste Stack-Element und mache dann die Zusammenfassung rückgängig). 5. Goto 2. 6. (Zustand dann: Stack: x+y x RAM: 0) Pop. Recht aufwändig, aber damit sollte die Multiplikation laufen.

ZEVS

Mo, März 17, 2014 22:00
Antworten mit Zitat

Die Frage sieht ziemlich stark nach einer Frage der Theoretischen Informatik aus, wo ich davon ausgehen würde, dass "Byte" eine beliebig große natürliche Zahl meint, ist das so? Wenn dem so ist, müsste m.E. die Unmöglichkeit der Multiplikation bewiesen werden können, auch wenn ich daran schon ein paarmal verzweifelt bin. Andernfalls wäre für die Multiplikation zweier Bytes ja eine Fallunterscheidung von den 256x256 verschiedenen möglichen Faktoren möglich (indem man immer dekrementiert und schaut, wann man bei 0 ist). Ich gehe nicht davon aus, dass du darauf nach fünf Tagen rumgrübeln nicht gekommen bist, also gehe ich davon aus, dass die betrachteten Zahlen beliebig groß werden dürfen.

Recht einfach kam ich auf einen Algorithmus zum Quadrieren:
0. Die zu quadrierende Zahl n liegt im Stack.
1. Entferne das oberste Stack-Element und schreibe es in den RAM (Pop).
2. Schiebe ein neues Element mit dem Inhalt vom RAM auf den Stack (Push).
3. Push.
4. Solange das oberste Stack-Element nicht Null ist, dekrementiere es.
(Dann sieht es so aus: Stack (rechts = oben): n 0 RAM: n)
5. Wenn der RAM gleich 0 ist, gehe zu 9.
6. Push
7. Dekrementiere den RAM
8. Goto 5.
(Dann sieht es so aus: Stack: n 0 n (n-1) (n-2) ... 1 RAM: 0
9. Wenn das oberste Stack-Element gleich 0 ist, gehe zu 14.
10. Addiere den Inhalt des RAMs zum obersten Stack-Element.
11. Pop.
12. Goto 9.
(Dann sieht es so aus: Stack: n 0 RAM: n + (n-1) + ... + 1. Nach dem kleinen Gauß ist der Inhalt des RAMs gleich (n²+n)/2 ).
13. Push
14. Addiere den Inhalt des RAMs zum obersten Stack-Element.
(Inhalt des ersten Stack-Elements: n²+n)
15. Pop
(addiere nun die 0 dazu)
16. wie 14.
17. wie 15.
18. Subtrahiere das oberste Stack-Element vom RAM.
19. Terminiere. Im RAM liegt n².

Soweit ganz schön, aber das klappt nur mit der Zahl im RAM. Da bei der Multiplikation wenigstens einer der Faktoren im Stack bleiben muss, hilft das hier nicht viel. Das Blöde ist aber, dass man die Unmöglichkeit der Multiplikation nicht darüber beweisen kann, dass diese (bzw. die damit berechenbare Fakultät) zu stark wächst. Dies ist ein ziemlich beliebtes Konzept der Berechenbarkeitstheorie, hier aber nicht anwendbar, denn der durchaus berechenbare Term (a+b)² ist größer als a*b.

Ich versuche mich gerade daran, zu untersuchen, welche Eigenschaften die berechenbaren Funktionen haben müssen, aber das scheint ein sehr fehleranfälliges und frustrierendes Unterfangen zu sein.

ZEVS

edit: Ich habe eine Methode zum Multiplizieren (bei unbegrenzten "Bytes") gefunden: Da man auf drei Variablen zurgreifen muss, um a+a+a+a...+a (b-mal) zu berechnen (man muss a, die Zwischensumme und das dekrementierte b speichern), erschien mir diese Berechnung zunächst unmöglich, aber dem ist nicht so. Man kann den obersten Wert im Stack (nennen wir ihn s) und den Inhalt des Rams r zu einem einzelnen Wert zusammenfassen die Ursprungswerte daraus wieder gewinnen. Der Term (2*r+1) * 2^s dient hier als Zwischenwert.
Der folgende Algorithmus berechnet (2*r+1) * 2^s:
1. Verdopple den RAM (d.h. Push, addiere den Inhalt des RAMs zum obersten Stack-Element, Pop).
2. Inkrementiere den RAM um 1
3. Wenn das oberste Stack-Element gleich 0 ist, gehe zu 7.
4. Dekrementiere das oberste Stack-Element um 1.
5. Verdopple den RAM.
6. Goto 3.
7. (das oberste Stack-Element ist nun 0 und der RAM enthält den gewünschten Wert) Addiere den RAM zum obersten Stack-Element.
8. Pop.

Die Anweisungen 1. und 2. errechnen 2*r+1 und speichern diesen Wert im RAM, die Anweisungen 3.-6. verdoppeln den RAM s-mal.

Die Umkehrung geht, indem man den Wert möglichst oft durch 2 dividiert, denn 2*r+1 ist ungerade, also kann man genau s-mal durch 2 dividieren. Liegt (2*r+1) * 2^s im RAM bringt der folgende Algorithmus s in den Stack und r in den RAM:
1. Push.
2. Solange das oberste Stack-Element nicht Null ist, dekrementiere es.
(Zustand dann: Stack: 0 RAM: (2*r+1) * 2^s.
3. (prüfe, ob der RAM einen geraden Wert enthält) Push (Sicherungskopie).
4. Wenn der RAM gleich 0 ist, gehe zu 9.
5. Dekrementiere den RAM um 1.
6. Wenn der RAM gleich 0 ist, gehe zu 13.
7. Dekrementiere den RAM.
8. Goto 4.
9. (RAM gerade) Pop (RAM wiederherstellen).
10. Halbiere den Inhalt des RAM (s.u.).
11. Inkrementiere das oberste Stack-Element um 1.
12. Goto 3.
13. Pop (RAM wiederherstellen).
14. (RAM ungerade, s liegt im obersten Stack-Element und (2r+1) im RAM) Dekrementiere den RAM um 1.
15. Halbiere den Inhalt des RAMs.

Die Anweisungen 4.-8. verringern den RAM immer um 2 und prüfen damit, ob dieser gerade oder ungerade ist. In erstem Fall wird er halbiert und das oberste Stack-Element inkrementiert (9.-12.).

Das Halbieren des RAMs geht wie folgt:
1. Push
2. Wenn der RAM gleich 0 ist: Pop, Terminiere.
3. Dekrementiere das oberste Stack-Element um 1
4. Dekrementiere den RAM um 1
5. Dekrementiere den RAM um 1
6. Goto 2.

Mit diesem Algorithmen zum Zusammenfassen von Werten ist es möglich, ohne Informationsverlust auch Werte zu verarbeiten, die nicht im RAM bzw. an erster Stelle im Stack stehen.

Wenn man die beiden Werte aus Stack und RAM zusammenfassen kann, geht die Multiplikation:
0. Die beiden Faktoren (a, b) sind die beiden Stack-Elemente.
1. Pop.
2. Push.
3. Solange das oberste Stack-Element nicht null ist, dekrementiere es um 1.
(Zustand dann: Stack: a 0 RAM: b)
4. Fasse oberstes Stack-Element und RAM zu einem Wert im RAM zusammen (s.o.)
5. Wenn das oberste Stack-Element gleich 0 ist, gehe zu 10.
6. Dekrementiere das oberste Stack-Element um 1.
7. Stelle die beiden unter 4. zusammengefassten Werte wieder her.
8. Addiere den Wert im RAM zu dem im Stack, ohne den RAM zu verändern (s.u.).
9. Goto 4.
10. Stelle die beiden unter 4. zusammengefassten Werte wieder her.
(Zustand dann: Stack: 0 a*b RAM: b)
11. Pop
12. Addiere den RAM zum obersten Stack-Element
13. Pop. Terminiere. Der Stack ist leer und der RAM enthält a*b.

Die Anweisungen 4.-9. verarbeiten die drei Werte a, x und b, wobei a und b die Parameter sind und x (die Zwischensumme, zunächst 0) a-mal um b addiert wird (hierzu wird a stets dekrementiert). x und b werden in 4. zusammengefasst, um auf a zuzugreifen.

Als letztes muss die Anweisung zum Addieren des RAMs zum ersten Stack-Element ohne Null-Setzen des RAMs geklärt werden. Auch diese geht mit dem Trick zum Zusammenfassen:

0. Im Stack liegt die Zahl x und im RAM die Zahl y. Am Ende soll im Stack x+y liegen und im RAM y.
1. Push.
2. Wenn der RAM gleich 0 ist, gehe zu 6.
3. Dekrementiere den RAM.
4. Inkrementiere das zweite Stack-Element (d.h. fasse RAM und oberstes Stack-Element zusammen, inkrementiere dann das oberste Stack-Element und mache dann die Zusammenfassung rückgängig).
5. Goto 2.
6. (Zustand dann: Stack: x+y x RAM: 0) Pop.

Recht aufwändig, aber damit sollte die Multiplikation laufen.

	CO2 ehemals "SirMO"	Fr, März 21, 2014 23:54 Antworten mit Zitat
Entschuldigung, dass ich jetzt erst antworte, momentan ist es bei mir etwas kompliziert, unter der Woche das Internet zu benutzen... @ BladeRunner: Zitat: (...) wobei dem Nutzer dann die Vorarbeit des Pushens der Summanden (...) Das wäre natürlich eine Lösung, schöner wäre es aber, wenn der Benutzer z.B. 4 und 3 in den Stack pusht und als Ergebnis der Multiplikation 12 erhält. Zitat: Das Problem des Überlaufs des Ergebnisses lässt sich so nicht lösen Darum muss sich dann der Benutzer kümmern, indem er nur dafür sorgt, dass das Produkt der Multiplikation <= 255 bleibt... @ ZEVS: Zitat: (...) dass "Byte" eine beliebig große natürliche Zahl meint, ist das so? Eigentlich ist damit schon das Byte an sich gemeint, das Prinzip des multiplizieren in einem Stack lässt sich natürlich auch auf eine beliebig große natürliche Zahl erweitern, bzw. von dort auf das Byte übertragen. Ein Überlauf des Ergebnisses gilt es primär nicht systemtechnisch auszuschließen, falls du damit meinst, ob das Ergebnis beliebig groß sein darf. Zitat: Ich gehe nicht davon aus, dass du darauf nach fünf Tagen rumgrübeln nicht gekommen bist, also gehe ich davon aus, dass die betrachteten Zahlen beliebig groß werden dürfen. Inwiefern würde es einen Unterschied machen, ob ich alle natürlichen Zahlen zulasse oder nur einen Teilbereich (Für die beiden Faktoren)? Das Ergebnis an sich muss wie geschrieben weder auf Überlauf getestet, noch muss dieser verhindert werden. Zitat: Verdopple den RAM. Dafür ist meines Wissens zumindest ein Left- bzw. Right-Shift der Binärdaten nötig... Oder gibt es dort eine andere Möglichkeit? Zitat: Recht aufwändig, aber damit sollte die Multiplikation laufen. Ja, das könnte funktionieren, vereinfachen könnte man das ganze natürlich, falls der RAM "größer" wäre - aber einfach kann ja jeder . Ich danke für alle Antworten.
mfG, CO² Sprachen: BlitzMax, C, C++, C#, Java Hardware: Windows 7 Ultimate 64-Bit, AMX FX-6350 (6x3,9 GHz), 32 GB RAM, Nvidia GeForce GTX 750 Ti

CO2

ehemals "SirMO"

Fr, März 21, 2014 23:54
Antworten mit Zitat

Entschuldigung, dass ich jetzt erst antworte, momentan ist es bei mir etwas kompliziert, unter der Woche das Internet zu benutzen...

@ BladeRunner:
Zitat:

(...) wobei dem Nutzer dann die Vorarbeit des Pushens der Summanden (...)

Das wäre natürlich eine Lösung, schöner wäre es aber, wenn der Benutzer z.B. 4 und 3 in den Stack pusht und als Ergebnis der Multiplikation 12 erhält.

Zitat:

Das Problem des Überlaufs des Ergebnisses lässt sich so nicht lösen

Darum muss sich dann der Benutzer kümmern, indem er nur dafür sorgt, dass das Produkt der Multiplikation <= 255 bleibt... Wink

@ ZEVS:
Zitat:

(...) dass "Byte" eine beliebig große natürliche Zahl meint, ist das so?

Eigentlich ist damit schon das Byte an sich gemeint, das Prinzip des multiplizieren in einem Stack lässt sich natürlich auch auf eine beliebig große natürliche Zahl erweitern, bzw. von dort auf das Byte übertragen. Ein Überlauf des Ergebnisses gilt es primär nicht systemtechnisch auszuschließen, falls du damit meinst, ob das Ergebnis beliebig groß sein darf.

Zitat:

Ich gehe nicht davon aus, dass du darauf nach fünf Tagen rumgrübeln nicht gekommen bist, also gehe ich davon aus, dass die betrachteten Zahlen beliebig groß werden dürfen.

Inwiefern würde es einen Unterschied machen, ob ich alle natürlichen Zahlen zulasse oder nur einen Teilbereich (Für die beiden Faktoren)? Das Ergebnis an sich muss wie geschrieben weder auf Überlauf getestet, noch muss dieser verhindert werden.

Zitat:

Verdopple den RAM.

Dafür ist meines Wissens zumindest ein Left- bzw. Right-Shift der Binärdaten nötig... Oder gibt es dort eine andere Möglichkeit?

Zitat:

Recht aufwändig, aber damit sollte die Multiplikation laufen.

Ja, das könnte funktionieren, vereinfachen könnte man das ganze natürlich, falls der RAM "größer" wäre - aber einfach kann ja jeder Wink

.

Ich danke für alle Antworten.

mfG, CO²

Sprachen: BlitzMax, C, C++, C#, Java
Hardware: Windows 7 Ultimate 64-Bit, AMX FX-6350 (6x3,9 GHz), 32 GB RAM, Nvidia GeForce GTX 750 Ti

	BladeRunner Moderator	Sa, März 22, 2014 9:32 Antworten mit Zitat
Zitat: Eigentlich ist damit schon das Byte an sich gemeint... Nur der Form halber: "das Byte" an sich gibt es so nicht mal wirklich. Die ersten Rechnergenerationen hatten die wildesten Architekturen und Wortgrößen, und ein jeder nannte seine Architekturbreite ein Byte. Erst in den letzten 20-30 Jahren hat sich das Byte für 8 bit etabliert, aber vom Bedeutungsursprung war es einfach nur "Verarbeitungseinheit dieses Rechners".
Zu Diensten, Bürger. Intel T2300, 2.5GB DDR 533, Mobility Radeon X1600 Win XP Home SP3 Intel T8400, 4GB DDR3, Nvidia GF9700M GTS Win 7/64 B3D BMax MaxGUI Stolzer Gewinner des BAC#48, #52 & #92

BladeRunner

Moderator

Sa, März 22, 2014 9:32
Antworten mit Zitat

Zitat:

Eigentlich ist damit schon das Byte an sich gemeint...

Nur der Form halber: "das Byte" an sich gibt es so nicht mal wirklich. Die ersten Rechnergenerationen hatten die wildesten Architekturen und Wortgrößen, und ein jeder nannte seine Architekturbreite ein Byte. Erst in den letzten 20-30 Jahren hat sich das Byte für 8 bit etabliert, aber vom Bedeutungsursprung war es einfach nur "Verarbeitungseinheit dieses Rechners".

Zu Diensten, Bürger.
Intel T2300, 2.5GB DDR 533, Mobility Radeon X1600 Win XP Home SP3
Intel T8400, 4GB DDR3, Nvidia GF9700M GTS Win 7/64
B3D BMax MaxGUI
Stolzer Gewinner des BAC#48, #52 & #92

	ZEVS	Sa, März 22, 2014 12:01 Antworten mit Zitat
Danke für die Antwort. Das Verdoppeln des RAMs habe ich in folgender Anweisung erklärt zu haben gehofft: Zitat: 1. Verdopple den RAM (d.h. Push, addiere den Inhalt des RAMs zum obersten Stack-Element, Pop). Man addiert den RAM zu sich selbst, das verdoppelt ihn (Shifts sind natürlich schneller und toller, aber nicht gegeben). Zum Begriff Byte: Die Einwände gelten unabhängig von der Beschränkung auf ein Oktett. Allgemein nehme ich ein Byte als begrenzter Speicher, der N (default: 256) unterscheidbare Werte natürlicher Zahlen annehmen kann. Die Sache mit den begrenzten Bytes: Es ist nicht möglich, zwei Bytes in einem zu speichern, wenn nur endlich viele Werte für ein Byte möglich sind. Damit sind meine beiden Zusammenfassungs-Algorithmen auf vergleichsweise winzige Zahlenwerte beschränkt, denn der Term (2a+1)2^b sprengt bereits für b>=8 (bzw. 2^b >= N) die Überlauf-Grenze und nimmt unvorhergesehene Werte an. Man kann aber durch einfaches Überprüfen alles 256 (bzw. N) Werte alle Fälle abdecken: 0. Ein Faktor liegt im Stack, einer im RAM 1. Wenn der Stack gleich 0 ist, Pop, Terminiere. 2. Dekrementiere den Stack um 1 3. Wenn der Stack gleich 0 ist (dann war er am Anfang 1): Addiere alle Werte, Terminiere. 4. Dekrementiere den Stack um 1 5. Wenn der Stack gleich 0 ist (dann war er am Anfang 2): Push, Addiere alle Werte, Terminiere. 6. Dekrementiere den Stack um 1 7. Wenn der Stack gleich 0 ist (dann war er am Anfang 3): 2x Push, Addiere alle Werte, Terminiere. 8. Dekrementiere den Stack um 1 9. Wenn der Stack gleich 0 ist (dann war er am Anfang 4): 3x Push, Addiere alle Werte, Terminiere. usw. 2n. Dekrementiere den Stack um 1 2*n+1. Wenn der Stack gleich 0 ist (dann war er am Anfang n): (n-1) x Push, Addiere alle Werte, Terminiere. bis n=255 (bzw. n = N-1). Da nur endlich viele Werte berücksichtigt werden, geht es so. Sind alle natürlichen Zahlen als Eingabe zugelassen, kann ein Algorithmus wie der obige nur endlich viele abdecken. Für diesen Fall funktioniert aber mein Algorithmus vom letzten Beitrag. ZEVS

ZEVS

Sa, März 22, 2014 12:01
Antworten mit Zitat

Danke für die Antwort. Das Verdoppeln des RAMs habe ich in folgender Anweisung erklärt zu haben gehofft: Zitat:

1. Verdopple den RAM (d.h. Push, addiere den Inhalt des RAMs zum obersten Stack-Element, Pop).

Man addiert den RAM zu sich selbst, das verdoppelt ihn (Shifts sind natürlich schneller und toller, aber nicht gegeben).

Zum Begriff Byte: Die Einwände gelten unabhängig von der Beschränkung auf ein Oktett. Allgemein nehme ich ein Byte als begrenzter Speicher, der N (default: 256) unterscheidbare Werte natürlicher Zahlen annehmen kann.

Die Sache mit den begrenzten Bytes: Es ist nicht möglich, zwei Bytes in einem zu speichern, wenn nur endlich viele Werte für ein Byte möglich sind. Damit sind meine beiden Zusammenfassungs-Algorithmen auf vergleichsweise winzige Zahlenwerte beschränkt, denn der Term (2a+1)*2^b sprengt bereits für b>=8 (bzw. 2^b >= N) die Überlauf-Grenze und nimmt unvorhergesehene Werte an.
Man kann aber durch einfaches Überprüfen alles 256 (bzw. N) Werte alle Fälle abdecken:
0. Ein Faktor liegt im Stack, einer im RAM
1. Wenn der Stack gleich 0 ist, Pop, Terminiere.
2. Dekrementiere den Stack um 1
3. Wenn der Stack gleich 0 ist (dann war er am Anfang 1): Addiere alle Werte, Terminiere.
4. Dekrementiere den Stack um 1
5. Wenn der Stack gleich 0 ist (dann war er am Anfang 2): Push, Addiere alle Werte, Terminiere.
6. Dekrementiere den Stack um 1
7. Wenn der Stack gleich 0 ist (dann war er am Anfang 3): 2x Push, Addiere alle Werte, Terminiere.
8. Dekrementiere den Stack um 1
9. Wenn der Stack gleich 0 ist (dann war er am Anfang 4): 3x Push, Addiere alle Werte, Terminiere.
usw.
2*n. Dekrementiere den Stack um 1
2*n+1. Wenn der Stack gleich 0 ist (dann war er am Anfang n): (n-1) x Push, Addiere alle Werte, Terminiere.

bis n=255 (bzw. n = N-1).

Da nur endlich viele Werte berücksichtigt werden, geht es so. Sind alle natürlichen Zahlen als Eingabe zugelassen, kann ein Algorithmus wie der obige nur endlich viele abdecken. Für diesen Fall funktioniert aber mein Algorithmus vom letzten Beitrag.

ZEVS

	CO2 ehemals "SirMO"	Fr, März 28, 2014 23:48 Antworten mit Zitat
Ok, vielen Dank für die hilfreichen Antworten, Ich werde dieses Thema damit als [GELÖST] taggen. @ BladeRunner: Ich meine das 8-Bit-Byte @ ZEVS: Zitat: (...) sprengt bereits für b>=8 (bzw. 2^b >= N) die Überlauf-Grenze und nimmt unvorhergesehene Werte an. Das ist dann das Problem des Benutzers Zitat: Für diesen Fall funktioniert aber mein Algorithmus vom letzten Beitrag. Danke
mfG, CO² Sprachen: BlitzMax, C, C++, C#, Java Hardware: Windows 7 Ultimate 64-Bit, AMX FX-6350 (6x3,9 GHz), 32 GB RAM, Nvidia GeForce GTX 750 Ti