Dividieren ohne zu dividieren

[Xin]

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.

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?

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 ^^

[Dirty Oerti]

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" .. ^^ )

[Xin]

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

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.

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. ^^

[Dirty Oerti]

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^^

[Xin]

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.

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. ^^

[Dirty Oerti]

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

[Xin]

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?

[Dirty Oerti]

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

[Xin]

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?

[Dirty Oerti]

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