Dividieren ohne zu dividieren

Fragen zu mathematischen Problemen
Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8735
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

Re: Dividieren ohne zu dividieren

Beitrag von Xin » Mo Dez 28, 2009 9:58 am

Dirty Oerti hat geschrieben:Doch doch :)
Da hast du mich (und mein System) falsch verstanden.
Es handelt sich um ein Stellensystem, sprich wie im Zehnersystem kann jede Ziffer eine gewisse Anzahl unterschiedlicher Werte annehmen. Im "normalen" Zehnersystem sind das Werte von 0-9
Bei mir sind es Werte von 0-9999

1 | 2 ist also nicht gleich 12 sondern 10002 was ungleich 0 | 12 ist (das ist dann wirklich 12) :)
Warum nimmst Du nicht das Binärsystem?
Wenn Du Dich auf 9999 beschränkst, nimmst Du vermutlich shorts (Warum eigentlich?). Shorts gehen bis 65536. Also wenn das Problem die maximale Stellenzahl ist. Wenn Du signed und Überlauf berücksichtigst, geht ein Short von -16384 bis +16383. Damit ist der Ziffernraum dreimal größer als Deiner.
Dirty Oerti hat geschrieben:
Schön. Beschreibe doch, was Du verstanden hast und kombiniere Deinen Code für einen Artikel für's Wiki draus.
Das kann ich mal versuchen :) Jetzt kommt auf jeden Fall erstmal der Code (der zu verstehen sein dürfte, zumindest nach einiger Auseinandersetzung damit):
Wäre klasse.

Code: Alles auswählen

xint xint::operator/(xint num)
{
	if (num.n_sign == MINUS) num*=-1;[/quote]
Offenbar berücksichtigst das Vorzeichen nicht in der eigentlichen Zahl, sondern getrennt?

[code]// Wenn hier angelangt wird, dann muss WIRKLICH dividiert werden
// WAS genau WELCHE "tmp"-Zahl tut ist das Rätsel ;)
Woher kommt der Code?
Dirty Oerti hat geschrieben:
Aber wie ich mich kenne, hätte ich das Bett abends noch aufgebaut. ^^
Hätte ich auch, wenn es nur das aufbauen gewesen wäre ^^ Zuerst durfte ich ja das alte Bett abbauen und dazu auch die komplette Ecke, in der das alte Bett stand entrümpeln, was bei mir als "Sammler" recht lange Zeit in Anspruch genommen hat :)
;-)

In Ermangelung eines Bettes bleibt mir dieses Schicksal erspart, wenn ich mir ein Bett kaufe oder schenken lasse ^^
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.

Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.

Benutzeravatar
Dirty Oerti
Beiträge: 2229
Registriert: Di Jul 08, 2008 5:05 pm
Wohnort: Thurndorf / Würzburg

Re: Dividieren ohne zu dividieren

Beitrag von Dirty Oerti » Mo Dez 28, 2009 5:54 pm

Warum nimmst Du nicht das Binärsystem?
Wenn Du Dich auf 9999 beschränkst, nimmst Du vermutlich shorts (Warum eigentlich?). Shorts gehen bis 65536. Also wenn das Problem die maximale Stellenzahl ist. Wenn Du signed und Überlauf berücksichtigst, geht ein Short von -16384 bis +16383. Damit ist der Ziffernraum dreimal größer als Deiner.
Ich rechne im Zehnersystem, weil die Ausgabe im Zehnersystem dann deutlich einfacher geht. (Oder wie berechne ich sonst eine Zahl, von der ich nicht weiß, wie sie heißt, und sie aus 128 Bit besteht, mir jedoch keine 128 Bit zur Verfügung stehen?)
Und nein, ich nehme keine shorts, sondern unsigned ints :) Warum der Rahmen nur bis 9999 geht? naja, weil 10000 * 10000 = 100000000 = 10^8 , was die größte Zahl 10^x ist, die in einen unsigned int passt. ;)
Lasse ich größere Werte in den einzelnen Speicherfeldern zu, dann riskiere ich einen Überlauf bei der Multiplikation.
Offenbar berücksichtigst das Vorzeichen nicht in der eigentlichen Zahl, sondern getrennt?
Das ist richtig :) Denn ich nehme ja unsigned ints (ok, das wäre nicht unbedingt notwendig)
Hauptsächlicher Grund ist jedoch einfach: Es ist einfacher ^^
Ich könnte nat. auch das erste "Arrayfeld" mit dem Vorzeichen behaften, das zwingt mich aber zu Überprüfungen, die jetzt nicht notwendig sind.
Deswegen die getrennte Speicherung von Zahl und Vorzeichen :)
Woher kommt der Code?
Wie woher? Ich hab ihn an Weihnachten, nachmittags, geschrieben :)
Der Hinweis galt nur der Namensgebung (ich verwende iwie gerne den Ausdruck "tmp" .. ^^ )
Bei Fragen einfach an daniel[ät]proggen[Punkt]org
Ich helfe gerne! :)
----------
Wenn du ein Licht am Ende des Tunnels siehst, freu dich nicht zu früh! Es könnte ein Zug sein, der auf dich zukommt!
----
It said: "Install Win95 or better ..." So I installed Linux.

Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8735
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

Re: Dividieren ohne zu dividieren

Beitrag von Xin » Mo Dez 28, 2009 9:34 pm

Dirty Oerti hat geschrieben:
Warum nimmst Du nicht das Binärsystem?
Wenn Du Dich auf 9999 beschränkst, nimmst Du vermutlich shorts (Warum eigentlich?). Shorts gehen bis 65536. Also wenn das Problem die maximale Stellenzahl ist. Wenn Du signed und Überlauf berücksichtigst, geht ein Short von -16384 bis +16383. Damit ist der Ziffernraum dreimal größer als Deiner.
Ich rechne im Zehnersystem, weil die Ausgabe im Zehnersystem dann deutlich einfacher geht. (Oder wie berechne ich sonst eine Zahl, von der ich nicht weiß, wie sie heißt, und sie aus 128 Bit besteht, mir jedoch keine 128 Bit zur Verfügung stehen?)
Ehrlich gesagt... keine Ahnung...
Nehmen wir an, wir könnten nur 4 Bit als Zahl ausgeben, als 0-15. Nun haben wir zwei vier Bit Register, für die gilt 0..15 * 16 + 0..15.

Nehmen wir 0x23, das sind zwei Register zu je 4 Bit, also Wert 35.

Nun nehmen wir ein 3 Chars und initialisieren sie jeweilt mit '0': "000"

Jeder Ziffer steht für "16".
Wir rechnen also den Abstand '6'-'0' auf die rechte '0'. => "006" - Überlauf? und dann den Abstand '1'-'0' auf die mittlere '0': "016"
Bleibt 13.
Wir rechnen also den Abstand '6'-'0' auf die rechte Ziffer. => "00C" - Überlauf? Jow - 10 abziehen und +1 auf die mittlere Ziffer: 022 - Überlauf? Nopes. Und dann den Abstand '1'-'0' auf die mittlere Ziffer: "032"
Bleibt 03 - größeres Register erledigt. :-)
Das kleinere Register steht für 1.
Wir rechnen also 1 auf die Rechte Ziffer: "033", bleibt 02 in beiden Registern. Überlauf? Nopes. Abbruch? Nopes.
Wir rechnen also 1 auf die Rechte Ziffer: "034", bleibt 01 in beiden Registern. Überlauf? Nopes. Abbruch? Nopes.
Wir rechnen also 1 auf die Rechte Ziffer: "035", bleibt 00 in beiden Registern. Überlauf? Nopes. Abbruch? Yepp.

Im Char-Array steht nun "035".
Und obwohl Du nie mit Registern gearbeitet hast, die größer als 4 Bit waren, konntest Du die Zahl in einen String umrechnen.

Wenn Du nun wissen willst, wie Du an den String des nächsten Registers kommst... dann addiere doch die Strings.
Das rechte Register schafft den Wert 16, also "16", dem entspricht der Wert des linken Registers. Brauchst Du nun 3 Register, machst Du einen String und initialisierst ihn mit dem Register-Wert 01: "16".
Nun nimmst Du die Zahl "0F" und addierst den Wert "16" 0F mal drauf, das ergibt den String "256". Und schon kannst Du drei 4 Bit-Register zu Strings verrechnen.
(Optimierungen mit 4 (Bit) mal die Zahl auf sich selbst addieren gehen natürlich auch: "016" << 4 == "016"+"016" << 3 => "032" << 3 == "032"+"032" << 2=> "064" <<2 == "064"+"064" << 1=> "128" << 1 == "128"+"128" << 0 => "256".

Soviel dazu... nun habe ich beim Schreiben des Beitrags doch Ahnung bekommen ^^ Bißerl Phantasie... Computer können nicht alle Probleme lösen, aber das hier geht gerade noch ;-)
Dirty Oerti hat geschrieben:Und nein, ich nehme keine shorts, sondern unsigned ints :) Warum der Rahmen nur bis 9999 geht? naja, weil 10000 * 10000 = 100000000 = 10^8 , was die größte Zahl 10^x ist, die in einen unsigned int passt. ;)
Lasse ich größere Werte in den einzelnen Speicherfeldern zu, dann riskiere ich einen Überlauf bei der Multiplikation.
Warum nimmst Du die unsigned ints nicht zu zwei unsigned shorts auseinander, wenn Du multiplizierst?

Nehmen wir an, Du hast 8 Bit Register und teilst sie in 4 Bit Register auf, damit Du ohne 16 Bit Register multiplizieren kannst.
20 * 20 => 0001|0100 * 0001|0100 => (0001 << 4) * (0001 << 4) + (0100 << 0) * (0001 << 4) + (0001 << 4) * (0100 << 0) + (0100 << 0) * (0100 << 0)
=> 0001 << 8 + 0100 << 4 + 0100 << 4 + 10000 << 0
=> 0001 << 8 + 0100 << 4 + 0100 << 4 + 0001 << 4
=> 0001 << 8 + 1001 << 4
=> 0001|1001|0000
=> 256 + 128 + 16 => 400.
Dirty Oerti hat geschrieben:
Offenbar berücksichtigst das Vorzeichen nicht in der eigentlichen Zahl, sondern getrennt?
Das ist richtig :) Denn ich nehme ja unsigned ints (ok, das wäre nicht unbedingt notwendig)
Hauptsächlicher Grund ist jedoch einfach: Es ist einfacher ^^
Ich könnte nat. auch das erste "Arrayfeld" mit dem Vorzeichen behaften, das zwingt mich aber zu Überprüfungen, die jetzt nicht notwendig sind.
Deswegen die getrennte Speicherung von Zahl und Vorzeichen :)
Verbraucht aber mehr Speicher. ^^
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.

Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.

Benutzeravatar
Dirty Oerti
Beiträge: 2229
Registriert: Di Jul 08, 2008 5:05 pm
Wohnort: Thurndorf / Würzburg

Re: Dividieren ohne zu dividieren

Beitrag von Dirty Oerti » Di Dez 29, 2009 12:10 am

Verbraucht aber mehr Speicher. ^^
Warum nimmst Du die unsigned ints nicht zu zwei unsigned shorts auseinander, wenn Du multiplizierst?
Speicher hab ich zu genüge, was fehlt ist die Rechenleistung. Wenn ich jeden Wert noch auseinander nehmen muss in 2 Teile kommen dabei pro Wertepaar 4 Multiplikationen raus.
Heißt bei Zahlen der Größe M und N komme ich auf (M*N)*(4) Multiplikationen, was das 4-fache vom jetzigen Wert ist...
Also 4 mal "mehr Rechenaufwand".
Nehmen wir an, wir könnten nur 4 Bit als Zahl ausgeben, als 0-15. Nun haben wir zwei vier Bit Register, für die gilt 0..15 * 16 + 0..15.
Soweit ist es noch klar :) Das danach müsstest du mir mal genauer erklären ... dann könnte ich den Wertebereich auf 65536 erhöhen :)
Vielleicht an einem Beispiel (und auch sagen, was jeweils in den Feldern steht) oder einfach noch ein Beispiel. Noch hab ichs nämlich nicht gerafft^^
Bei Fragen einfach an daniel[ät]proggen[Punkt]org
Ich helfe gerne! :)
----------
Wenn du ein Licht am Ende des Tunnels siehst, freu dich nicht zu früh! Es könnte ein Zug sein, der auf dich zukommt!
----
It said: "Install Win95 or better ..." So I installed Linux.

Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8735
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

Re: Dividieren ohne zu dividieren

Beitrag von Xin » Di Dez 29, 2009 10:51 am

Dirty Oerti hat geschrieben:
Verbraucht aber mehr Speicher. ^^
Warum nimmst Du die unsigned ints nicht zu zwei unsigned shorts auseinander, wenn Du multiplizierst?
Speicher hab ich zu genüge, was fehlt ist die Rechenleistung. Wenn ich jeden Wert noch auseinander nehmen muss in 2 Teile kommen dabei pro Wertepaar 4 Multiplikationen raus.
Heißt bei Zahlen der Größe M und N komme ich auf (M*N)*(4) Multiplikationen, was das 4-fache vom jetzigen Wert ist...
Also 4 mal "mehr Rechenaufwand".
Och, das wird auch noch mehr... das ist nicht anderes als binomische Formeln (ja, es gibt tatsächlich Anwendungsfälle für die Mathematik, die man damals mal gelernt hat ^^).

M und N sind in zwei Registern nichts anders als M = a+b und N = x+y. Und wenn man beides multipliziert:
(a+b)*(x+y) => a*x+b*x+b*y+b*y.

Brauchst Du mehr Register: M = a+b+c und N = x+y+z
(a+b+c)*(x+y+z) => a*x+b*x+b*y+b*y + ( a*z+b*z +c*x+c*y+c*z )

Ein Register mehr, verdoppelt auch die Multiplikationen. Multiplikationen sind heute aber nicht mehr so teuer wie früher. Heißt: Man muss ausprobieren, ob eine Sonderfallbetrachtung noch soviel Effizienz herausholt, dass die inzwischen recht preiswerten Multiplikationen zurückbleiben.
Zumal die Betrachtung von Dezimalzahlen weitere Sonderbedingungen mit sich bringen. Schließlich wüsste ich nicht, was an der Zahl 10011100010000 so jetzt spannend ist... scheint mir eher ein Sonderfall zu sein.
Dirty Oerti hat geschrieben:
Nehmen wir an, wir könnten nur 4 Bit als Zahl ausgeben, als 0-15. Nun haben wir zwei vier Bit Register, für die gilt 0..15 * 16 + 0..15.
Soweit ist es noch klar :) Das danach müsstest du mir mal genauer erklären ... dann könnte ich den Wertebereich auf 65536 erhöhen :)
Vielleicht an einem Beispiel (und auch sagen, was jeweils in den Feldern steht) oder einfach noch ein Beispiel. Noch hab ichs nämlich nicht gerafft^^
Vielleicht begründen wir beide mal einen Namensraum für softwaregetriebene Integers, dann gieße ich Dir das mal in Code. ;-)
Das hat nur den Nachteil, dass ich bisher in C++:*, c:lib:*, c:*, dbs:mysql:* und svn:* schon beschäftigt bin. Könnte also dauern. ^^
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.

Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.

Benutzeravatar
Dirty Oerti
Beiträge: 2229
Registriert: Di Jul 08, 2008 5:05 pm
Wohnort: Thurndorf / Würzburg

Re: Dividieren ohne zu dividieren

Beitrag von Dirty Oerti » Di Jan 05, 2010 11:33 am

Ok, wie nennen wir den Bereich dann?
Ich werde ihn dann sicherlich schnell mit allerlei Informationen füllen, immerhin will ich den Bereich ja dann in meiner Facharbeit zitieren ;)
Bei Fragen einfach an daniel[ät]proggen[Punkt]org
Ich helfe gerne! :)
----------
Wenn du ein Licht am Ende des Tunnels siehst, freu dich nicht zu früh! Es könnte ein Zug sein, der auf dich zukommt!
----
It said: "Install Win95 or better ..." So I installed Linux.

Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8735
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

Re: Dividieren ohne zu dividieren

Beitrag von Xin » Di Jan 05, 2010 11:42 am

Dirty Oerti hat geschrieben:Ok, wie nennen wir den Bereich dann?
Ich werde ihn dann sicherlich schnell mit allerlei Informationen füllen, immerhin will ich den Bereich ja dann in meiner Facharbeit zitieren ;)
Du willst Dich selbst zitieren? ^^

In meinen Augen gehören softwaregetriebene Integers in den Bereich math:

Was wären denn die anderen Informationen? Vielleicht verteilen die sich ja woanders hin?
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.

Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.

Benutzeravatar
Dirty Oerti
Beiträge: 2229
Registriert: Di Jul 08, 2008 5:05 pm
Wohnort: Thurndorf / Würzburg

Re: Dividieren ohne zu dividieren

Beitrag von Dirty Oerti » Di Jan 05, 2010 11:50 am

Die anderen Informationen?
Naja, nach Abgabe & Bewertung der Facharbeit wäre das im Prinzip die komplette Facharbeit über Verschlüsselung, natürlich aufbereitet fürs Wiki.
Außerdem beschäftige ich mich ja zur Zeit mit Primzahltests, dann ist da noch die modulare Exponentiation über die man was schreiben kann.
Und natürlich eben die Software-INTs, einmal aufbauend auf diesem Stellenwertsystem (wie hier) und dann noch einmal aufbauen auf dem chinesischen Restsatz, was ich vor ein paar Monaten durchgekaut habe :)

Also maht:software_int:* oder sowas in der Art?

EDIT:

theory:math:software_int:* meinte ich :)
Bei Fragen einfach an daniel[ät]proggen[Punkt]org
Ich helfe gerne! :)
----------
Wenn du ein Licht am Ende des Tunnels siehst, freu dich nicht zu früh! Es könnte ein Zug sein, der auf dich zukommt!
----
It said: "Install Win95 or better ..." So I installed Linux.

Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8735
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

Re: Dividieren ohne zu dividieren

Beitrag von Xin » So Jan 10, 2010 11:13 pm

Dirty Oerti hat geschrieben:theory:math:software_int:* meinte ich :)
Sorry, dass ich mich erst jetzt melde, aber theory:math:software_int:positional_notation:basic_idea ist einfach etwas lang. ^^
Wir sollten das in theory:math:softint:positional:idea kürzen. Bitte keine _ in den Links. Das führt nur dazu, dass halbe Sätze in den Links.

Schonmal ein interessantes Programm, was Du da vorstellst. :-)
Planst Du auch Algorithmen für Wurzel oder Potenzen?
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.

Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.

Benutzeravatar
Dirty Oerti
Beiträge: 2229
Registriert: Di Jul 08, 2008 5:05 pm
Wohnort: Thurndorf / Würzburg

Re: Dividieren ohne zu dividieren

Beitrag von Dirty Oerti » So Jan 10, 2010 11:17 pm

Tag :)

Kein Problem, änder ich dann gleich mal.
Algorithmen für Wurzel und Potenzen sind im Prinzip dann nicht mehr allzu weit hergeholt, wobei sie mit den Interna nicht mehr viel zu tun haben, da man dass über Addition/Multiplikation/Division lösen kann (muss).
Ich dachte noch daran modulare Exponentiation reinzubringen :)
Bei Fragen einfach an daniel[ät]proggen[Punkt]org
Ich helfe gerne! :)
----------
Wenn du ein Licht am Ende des Tunnels siehst, freu dich nicht zu früh! Es könnte ein Zug sein, der auf dich zukommt!
----
It said: "Install Win95 or better ..." So I installed Linux.

Antworten