große Zahlen in 1 Byte Blöcke aufteilen und Rest ausrechnen

[Sunny]

Hi@all,
ich hab das Problem, dass ich 2 sehr große Zahlen in 1-Byte-Blöcke aufteilen möchte und mit diesen 1-Byte-Blöcken möchte ich dann ausrechnen, was der Rest ist, wenn man die eine Zahl durch die andere Teilt. Dazu am besten mal ein Beispiel, das ich z.Z. auch in Excel zum rumprobieren verwende (mit etwas kleineren Zahlen um den überblick zu behalten):

also sagen wir mal ich habe die Zahl 2.462.293 welche binär so aussieht: 010101011001001000100101
Diese Zahl unterteile ich jetzt in 3 1-Byte-Blöcke:
01010101 (= 85)
10010010 (= 146)
00100101 (= 37)

die 2. Zahl lautet 623.122 diese sieht binär so aus: 000100101000001000001001
Auch diese Zahl wird nun wieder in 3 1-Byte-Blöcke unterteilt:
00010010 (= 18)
10000010 (= 130)
00001001 (= 9)

Wenn man 2.462.293 / 623.122 rechnet, bleibt ein Rest von 592.927 (= 10010000110000011111)
Wie schon gesgt, möchte ich nun wissen, wie der Rechenweg für die einzelnen 1-Byte-Blöcke aussieht, um hinterher diese errechneten Werte wieder zusammensetzen zu können und auf den Wert 592.927 zu kommen?

Ich weiß... mit 3 Byte großen Werten ist das nicht unbedingt sinnvoll, da man diese Werte problemlos in einen Integer speichern und normal rechnen könnte, da ich das aber später mit Werten machen möchte, die 300 Byte und größer sind, ist diese Unterteilung in Blöcke nötig.

Ich hoffe dass ich mein Anliegen halbwegs verständlich erklärt habe und mir jemand bei meinem Problem helfen kann.

Schonmal danke im voraus.

[STARGÅTE]

Hier eine mögliche Vorgehensweise:
002.462.293 / 623.122
Du fängst vorne an und dividierst die vordersten Byte löcke:
002 / 623 = 000 -> speichern
Ein Byte mehr:
002.462 / 623 = 003 -> speichern
Nun wird das Ergebnis * kompleten Divisor gerechnet und vom Dividend abgezogen:
003 * 623.122 = 001.869.366
002.462.293 - 001.869.366 = 592.927 -> neuer Dividend
592 / 623 = 000 -> fertig, da voller Dividend < voller Divisor
also wäre 592.927 der Rest.

Für dieses Vorgehen brauchst du also noch eine multiplikation großer Zahlen.

Nun wäre es aber äußerst uneffizient, wenn du es mit Bytes machst.

Wenn es dir einfach nur darum geht, den Rest zwei großer Zahlen (in Binärform) zu erhalten. Kann ich dir eine Procedure anbieten, die mit ASM arbeitet und sehr schnell ist.
Diese arbeitet dann unter x86 mit 4-Byte Blöcken und unter x64 mit 8-Byte Blöcken.

[Sunny]

Wenn es dir einfach nur darum geht, den Rest zwei großer Zahlen (in Binärform) zu erhalten. Kann ich dir eine Procedure anbieten, die mit ASM arbeitet und sehr schnell ist.
Diese arbeitet dann unter x86 mit 4-Byte Blöcken und unter x64 mit 8-Byte Blöcken.

Naja, ich hatte eigentlich vor mir selbst eine Procedure dafür zu schreiben aber wenn du schon eine parat hast, die auf einer etwas tieferen Ebene arbeitet und sich dadurch mehr auf's Wesentliche konzentriert, dann würde ich doch gern mal einen kleinen Blick drüber werfen ^^

Aber nachher werde ich trotzdem nochmal versuchen, deine Erklärung Schritt für Schritt nachzuvollziehen. Denn wenn ich etwas in meinen Programmen nutze, dann möchte ich auch gern wissen, wie das was ich da nutze eigentlich funktioniert.

P.S.: Du hast nicht zufällig noch Proceduren für andere Berechnungen die man mit übergroßen Zahlen anstellen kann?

[STARGÅTE]

Ich habe mir ein Include für unlimitierte Ganzzahlen geschrieben mit dem ich alle möglichen Rechenoperationen machen kann.
Ich möchte jedoch ungern das ganze Include veröffentlichen, da es mich inzwischen mehrere Jahre gekostet hat, den ASM-Code so zu optimieren, dass es mit anderen Sprachen wie Mathematica mithalten kann.

Was ich dir geben kann ich eine DLL-Version, mit dem entsprechenden PB-Import-Include, müsste ich allerdings ers vorbereiten.

[Sunny]

Erstmal dankeschön, dass du bereit wärst dir solche Mühe zu machen. Das ist allerdings nicht nötig, denn für mich wäre das wahrscheinlich nur etwas, das ich mal so nebenbei nutzen würde und mir auch selber zurecht Coden kann, es ist dann zwar nicht auf ASM-Basis aber mit dem Geschwindigkeitsverlust kann ich leben.

[STARGÅTE]

Erstmal dankeschön, dass du bereit wärst dir solche Mühe zu machen. Das ist allerdings nicht nötig, denn für mich wäre das wahrscheinlich nur etwas, das ich mal so nebenbei nutzen würde und mir auch selber zurecht Coden kann, es ist dann zwar nicht auf ASM-Basis aber mit dem Geschwindigkeitsverlust kann ich leben.

Oke, dann trotzdem noch als Hinweis:
Arbeite mit Long-Blöcken, statt mit Bytes.
Da es in PB ja Quads gibt, kannst du somit (auch ohne ASM) zwei LONGs addieren (neue LONG + Carry) und zwei LONGs multiplizieren (neue QUAD bzw. LONG1 und LONG2)
Durch Schleifen kannst du dann Long für Long abarbeiten und den Übertrag mit durchziehen.

Als Hinweis fürs Dividieren noch:
"normiere" den Divisor, soll heißen:
875.345.234 / 9.535 ist "uneffizient",
verschiebe (mit Shiftbefehlen) den Divisor soweit nach vorne, bis das höchste Bit besetzt ist:
Im Beispiel des 100er Systems:
87.534.523.400 / 953.500
So kannst du immer n große Zahl zum dividieren nutzen und musst weniger korrigieren.

[Sunny]

Danke für deine Hilfe und deine Hinweise, ich werd am WE gleich mal loslegen, mir die passenden Proceduren zurechtzubasteln.

Aber mal noch eine kleine Frage...
Wo du schonmal das Thema ASM angeschnitten hattest.
Kennst du zufällig irgendwelche guten Assembler-Tutorials? Ich hab schon ein wenig gegoogelt aber das was man da findet, ist meistens mehr als mager beschrieben.

[CSHW89]

Hab das Thema gerade erst gesehen. Falls du einen Ansatz brauchst, oder doch nicht selber schreiben willst:
http://www.purebasic.fr/german/viewtopi ... BigDecimal

Allerdings ist es nicht so schnell wie Stargates. Wir hatten damals Speedtests zu gemacht

lg Kevin

[Sunny]

Habs mir grad mal angeschaut aber das is irgendwie noch ein Level zu hoch für mich ^^