Wie kann man eine eigende Divisionsmethode für einen eigenen Datentyp programmieren?

[Lord Nikon]

Hi,
ich habe mir gerade einen Datentyp gebastelt, der aus einem Char Array existiert.Dieses Feld hat 3000 Stellen.Pro Stelle wird eine Ziffer gespeichert.Eine Additions,Multiplikations und Subtraktionsmethode habe ich schon geschrieben, nur habe ich zur Zeit keine Ahnung wie ich eine Division programmieren könnte.
Es wäre nett wenn jemand Lösungvorschläge liefern könnte:)
EDIT:
Hab vergessen zu erwähnen, dass Ganzzahl Ergebnisse rauskommen sollen.

[Gast]

Donald E. Knuth, The Art of Computer Programming 2 - Seminumerical Algorithms

[ethrandil]

Also, meine einfachste Idee wäre, dass man einfach das schriftliche Dividieren in Software gießt...

ich versuchs mal , aber ich glaub da reichen meine Datentypen nicht.... Meins kann maximal durch ein char teilen, aber vielleicht reichts dir ja.

Das wird recht uneffizient sein.

Ich gehe davon aus, dass dein selbstgebastelter Prototyp mit 3 char-elementen etwa diesen wert hat:

256²*[2]+256*[1]+[0]

korrekt?


public class LangeZahl
{
public char[] werte;

public LangeZahl divide(char divisor){
long rest = 0;
char[] ergebnis = new char[werte.length];

for(int actIndex = werte.length-1; actIndex>=0; actIndex--){
rest *= 256;
rest += werte[actIndex];
ergebnis[actIndex] = (char)(rest/divisor);
rest %= divisor;
}

//Der aktuelle 'rest' wird vergessen. Ich weiß nicht
//ob du ein fp-Format in chars implementiert hast...
return new LangeZahl(ergebnis);
}
}

wie gesagt ungetestet. ich testes mal eben ;)

- Eth

EDIT: leicht korrigiert, blöde Vertipper. aber es geht.

[Lord Nikon]

Hi,
danke für die Antwort.
Also die 100 wird z.B so abgespeichert:
[0]=1
[1]=0
[2]=0

Ich habs mir das so vorgestellt,dass ich eigentlich jede Zahl,die in meinem Datentyp ist, dividieren kann.

uint3000 zahl(50);
uint3000 zahl2(25);
zahl=zahl/zahl2;
//oder
uint3000 zahl(150);
uint3000 zahl2(55);
zahl=zahl/zahl2;

Ich versuch mal deinen Code darauf anzupassen.
EDIT:
Rechtschreibung

[ethrandil]

Original geschrieben von Lord Nikon
Ich versuch mal deinen Code darauf anzupassen.
Durch ein char teilen geht noch auf meine Art und Weise, eine weitere variable Zahl aber nicht wirklich... zumindestens schaff ichs ned...

- Eth

[Pinoccio]

Evtl mal hier (http://www.forum-3dcenter.org/vbulletin/showthread.php?s=&threadid=49075) ein bißchen reinlesen und Zeckensacks Programm downloaden, der hat einen eigenen Datentyp drin und per Assembler optimiert. Wenn du genug Ahnung hast, sollte dir das helfen.

hth, mfg Sebastian


/edit: Link vergessen

[Obligaron]

Division = Wie häufig passt eine Zahl in eine andere.
Also warum so kompliziert?

int count = 0;
while(zahl >= divisor)
{
count++;
zahl -= divisor;
}

zahl = count;

Also ohne Nachkommastellen.

MfG,
Obligaron

[mrdigital]

Original geschrieben von Obligaron
Division = Wie häufig passt eine Zahl in eine andere.
Also warum so kompliziert?

int count = 0;
while(zahl >= divisor)
{
count++;
zahl -= divisor;
}

zahl = count;

Also ohne Nachkommastellen.

MfG,
Obligaron
kein besonders effizientes Verfahren, wenn man Zahlen mit mehreren hundert Stellen durch eine einstellige teilt....

[Obligaron]

Ich habe auch nicht behauptet das es effizient ist.
Aber es ist zumindest einmal der erste Lösungsansatz mit beliebig langen Zahlen oder?

MfG,
Obligaron

[Lord Nikon]

Original geschrieben von Obligaron
Division = Wie häufig passt eine Zahl in eine andere.
Also warum so kompliziert?

int count = 0;
while(zahl >= divisor)
{
count++;
zahl -= divisor;
}

zahl = count;

Also ohne Nachkommastellen.

MfG,
Obligaron
Also wenn ich das richtig verstanden muss ich jetzt Methode programmieren die erstmal prüft ob eine Zahler größer ist als eine andere und dann true oder false zurückliefert.Dannach kann ich alles einfach in einer While Schleife abarbeiten.

[mrdigital]

Original geschrieben von Obligaron
Ich habe auch nicht behauptet das es effizient ist.
Aber es ist zumindest einmal der erste Lösungsansatz mit beliebig langen Zahlen oder?

MfG,
Obligaron
aber wenn man wirklich mit den langen Zahlen rechnen will, ist diese Art der Division wirklich ein Schuss ins Knie, und ich denke mal, das Nikon nicht nur eine Division machen will, sonder ein paar mehr ;)
Für eine schnellere Division sollte man ein bisschen cleverer vorgehen. Die "shift" Operation (">>" in C) bietet sich an, da dies in Hardware sehr schnell geht (einmal rechts shiften ist eine Division durch 2). D.h. man sollte versuchen erstmal möglichst oft shiften und erst dann abzuziehen...

[ethrandil]

Original geschrieben von Obligaron
Division = Wie häufig passt eine Zahl in eine andere.
Also warum so kompliziert?

int count = 0;
while(zahl >= divisor)
{
count++;
zahl -= divisor;
}

zahl = count;

Also ohne Nachkommastellen.

MfG,
Obligaron

Ehrm, vielelicht ist das da schneller?


Zahl count = new Zahl(0);
Zahl zahl = new Zahl(deineZahlHalt);
int stellen = (zahl.getStellen()-divisor.getStellen()-1);

while(zahl-divisor.shiftLeft(stellen) >= 0)
{
zahl -= divisor.shiftLeft(stellen);
count += new Zahl(1).shiftLeft(stellen); //10^stellen
stellen = (zahl.getStellen()-divisor.getStellen()-1);
if(stellen == -1)
stellen = 0;
}

//Dein Ergebnis steht nun in count.


Weiß nur grad nicht ob das funktioniert :freak:

Zahl.getStellen() gibt die anzahl der Stellen wieder...
Zahl.shiftLeft(x) fügt einfach x neue Stellen rechts hinzu. Aus der Zahl 10 wird nach shiftLeft(2) die Zahl 1000. Das ist leichter zu implementieren als die Multiplikation mit 100 :)

Die Annahme ist, dass eine Zahl mit 5 Stellen durch eine Zahl mit 3 Stellen garantiert 10^(5-3-1) = 10 mal teilen lässt. Ich weiß nicht, ob das wirklich so stimmt, aber ich könnt mich mal dransetzen das zu beweisen ;-)

- Eth

EDIT:
Original geschrieben von mrdigital
Die "shift" Operation (">>" in C) bietet sich an, da dies in Hardware sehr schnell geht (einmal rechts shiften ist eine Division durch 2). D.h. man sollte versuchen erstmal möglichst oft shiften und erst dann abzuziehen...
Da war doch glatt jemand schneller als ich ;-)
Das shiften auf der Zahlenebene ist in diesem Fall aber in Hardware nicht machbar, da kein byte-kompatibles System verwendet wird. Hier ist ein Software-shift halt eine multiplikation / division mit 10.

[Obligaron]

mrdigital:
Naja der Datentyp besteht aus char. char ist 8 bit und wir benützen von denen gerademal 4. Also da gibts noch mehr zu optimieren oder? :)

Außerdem verwende mal den Shift Operator bei char, da bist du schnell nicht mehr im Bereich zwischen '0' und '9'.

[GloomY]

Wie wär's wenn man den komischen Zahlentyp (Array von Chars) ersteinmal in ein Integer umwandelt und dann die normale Division nutzt?
unsigned int chararray_to_int(char *dividend, unsigned int length) {
unsigned int temp=0;
unsigned int i;
for (i=0; i<length; ++i)
temp+=(*(dividend+i)-48)*pow(10,length-i-1);
// Assume ASCII '0' = 48, '1' = 49 usw.
return temp;
}


unsigned int divide(char *dividend, char *divisor, unsigned int length1, unsigned int length2) {
return chararray_to_int(dividend, length1) / chararray_to_int(divisor, length2);
}^^ noch nicht getestet. :eyes:

[ethrandil]

Original geschrieben von GloomY
Wie wär's wenn man den komischen Zahlentyp (Array von Chars) ersteinmal in ein Integer umwandelt und dann die normale Division nutzt?
Die char-Zahlen können größer sein als ein int.

- Eth

[Pinoccio]

Welche Programiersprache nutzt du denn? In Java zB gibt es dafür schon eine Klasse (IIRC BigDecimal), evtl findet man dazu den Sourcecode irgendwo.

mfg Sebastian

[Lord Nikon]

Hi,
@ Pinoccio
ich nutze c++.
@ Obligaron
Deine Methode klappt perfekt:)
@ ethrandil
Ich probiert mal deine Methode jetzt aus.

[GloomY]

Original geschrieben von ethrandil
Die char-Zahlen können größer sein als ein int.

- Eth Für Große Zahlen gibt es Bibliothekten, so z.B. LINT (Large INTegers) für C/C++. Dann würde ich die Konvertierung eben nicht nach int sondern nach LINT machen ;)

Prinzipiell ist das Zahlenformat des Threadstarters aber ungeeignet, da es ineffizient codiert ist.

[mrdigital]

Original geschrieben von ethrandil
Die char-Zahlen können größer sein als ein int.

- Eth
er hatte aber den char "0" als Wert 0 und den char "1" als Wert 1 etc. interpretiert, d.h. GloomYs Umwandlung geht. Aber in der Tat, das ist eine sehr ineffiziente codierung der Zahl, wenn man auf jeder Stelle nur 10 der 256 Möglichkeiten nutzt (3,9% des Zahlenraumes ausgenutzt). Eine mögliche Codierung für grosse Ints (wenn man es denn selbst machen muss / will) steht hier: RFC 2440 - im Abschnitt Data formats - MPI Multi Precission Integers

[ethrandil]

Ich glaube es geht hier nicht um die Effiziens, sondern eher um das technische, oder?

Warum sollte man sonst auf die Idee kommen das selber zu programmieren? =)
Und da ist halt das Teilen mithilfe eines anderen Datentyps auch nicht okay, denn es geht ja darum zu lernen wie man am besten ne Division macht, ohne externe Hilfe...

- Eth

P.S.: Ich kann mich natürlich täuschen.

[mrdigital]

Original geschrieben von ethrandil
Ich glaube es geht hier nicht um die Effiziens, sondern eher um das technische, oder?

Warum sollte man sonst auf die Idee kommen das selber zu programmieren? =)
Und da ist halt das Teilen mithilfe eines anderen Datentyps auch nicht okay, denn es geht ja darum zu lernen wie man am besten ne Division macht, ohne externe Hilfe...

- Eth

P.S.: Ich kann mich natürlich täuschen.
Wenn man Aufgrund des falschen Datenformates einen "kranken" Divisionsalgorithmus entwirft, ist das doch schon eine Frage des Lerneffektes, oder nicht? Das man durch wiederholte Subtraktion dividieren kann, sollte einem ab der 4. Klasse eigentlich bekannt sein, d.h. das dann zu implementieren ist dann ja eher eine Trivialaufgabe ;)

[Lord Nikon]

Original geschrieben von ethrandil
Ich glaube es geht hier nicht um die Effiziens, sondern eher um das technische, oder?

Warum sollte man sonst auf die Idee kommen das selber zu programmieren? =)
- Eth

P.S.: Ich kann mich natürlich täuschen.
Du hast es genau erfasst=)
Es geht um das technische und um den Lerneffekt.

[D-Swat]

Kan man die Division nicht auf die Multiplikation zurückführen?

also mul(x) = div(1/x)?

[mrdigital]

Original geschrieben von D-Swat
Kan man die Division nicht auf die Multiplikation zurückführen?

also mul(x) = div(1/x)?
ja schon, aber damit das was bringt, braucht man eine Hardware, die schnell den Kehrwert bilden kann, denn sonst hat man damit nichts gewonnen. Ich dachte, dass viele Divisionsalgorithmen (in einer CPU) genau so funktionieren. Das Probelm ist nun halt, dass das nur bis zur Wortbreite der CPU geht (z.B. 32bit), und da der Threadsteller aber mit grösseren Zahlen rechnen will, müsste man erst einen Kehrwertbildungsalorithmus für grosse Zahlen schreiben. Es ist nun die Frage, was nacher schneller funktioniert, erst Kehrwert mit anschliessender Multiplikation (die ja bei so extralangen Zahlen auch Aufwendig ist) oder "direkte" Division.

[zeckensack]

Original geschrieben von Pinoccio
Evtl mal hier (http://www.forum-3dcenter.org/vbulletin/showthread.php?s=&threadid=49075) ein bißchen reinlesen und Zeckensacks Programm downloaden, der hat einen eigenen Datentyp drin und per Assembler optimiert. Wenn du genug Ahnung hast, sollte dir das helfen.

hth, mfg Sebastian


/edit: Link vergessen Die xFloat-Klasse kennt keine Division :naughty: ;(

Lord Nikon,
Es wäre wesentlich einfacher, wenn du nicht eine Dezimalstelle pro char speichern würdest, sondern wenn jedes char voll genutzt werden würde (oder zumindest eine Wertigkeit entsprechend einer Zweierpotenz hätte).

Mit Bits geht eine Integerdivision nämlich relativ locker flockig:
1)man setze den Quotienten auf Null.
2)man finde das höchstwertige Bit von Dividend und Divisor. Dies bezeichne ich mal als n (Dividend) und m (Divisor). Wenn m>n ist, dann bleibt der Quotient Null, und wir sind fertig.

3)man erstelle temporäre Kopien von Dividend und Divisor
4)man schiebe die temporäre Kopie des Divisors um (n-m) Stellen nach links. m brauchen wir nun nicht mehr. n setzen wir auf n:=n-m

5)Schleife, solange n>=0 ist
5a)Wenn die Kopie des Dividenden >= Kopie des Divisors, dann: Subtrahiere die Kopie des Divisors von der Kopie des Dividenden und setze das Bit des Quotienten an der Stelle n auf 1.
5b)Immer: Schiebe die Kopie des Divisors um ein Bit nach rechts und setze n:=n-1



Beispiel:
101101 Dividend
/ 110 Divisor

1)Quotient:=0
2)n:=5, m:=2 (ich zähle hier ab null, nicht ab eins)
m>n? nein, wir müssen weiter machen. Wir setzen n:=n-m=5-2=3

3)Kopieren.
4)Schieben:
101101 Kdividend
110000 Kdivisor

5)
5a)Kdividend>=Kdivisor? nein. Wir tun nichts.
5b)n:=n-1 => n:=2
und verschieben
101101 Kdividend
11000 Kdivisor

5a)Kdividend>=Kdivisor? ja. Subtrahieren:
101101 Kdividend
- 11000 Kdivisor
________
10101 Kdividend (neu)Bit 2 des Quotienten setzen:
100 Quotient
5b)n:=n-1 => n:=1
und verschieben der Divisor-Kopie
10101 Kdividend
1100 Kdivisor

5a)Kdividend>=Kdivisor? ja. Subtrahieren:
10101 Kdividend
- 1100 Kdivisor
________
1001 Kdividend (neu)Bit 1 des Quotienten setzen:
110 Quotient
5b)n:=n-1 => n:=0
und verschieben der Divisor-Kopie
1001 Kdividend
110 Kdivisor

5a)Kdividend>=Kdivisor? ja. Subtrahieren:
1001 Kdividend
- 110 Kdivisor
________
11 Kdividend (neu)Bit 0 des Quotienten setzen:
111 Quotient


n ist nun null, die Schleife wird beendet. Das Ergebnis haben wir bereits.


Probe:
Der Dividend war binär 101101, also dezimal 45. Der Divisor war binär 110, also dezimal 6. Wir haben als Quotienten binär 111 erhalten, das ist dezimal 7.

6*7=42, was für eine Integerdivision das korrekte Ergebnis ist. Wir können btw als "Rest" den letzten Wert von Kdividend ausgeben, binär 11, dezimal 3.

6*7+3=45

qed

[Gast]

O. Forster, Algorithmische Zahlentheorie

[Lord Nikon]

Original geschrieben von zeckensack
Die xFloat-Klasse kennt keine Division :naughty: ;(

Lord Nikon,
Es wäre wesentlich einfacher, wenn du nicht eine Dezimalstelle pro char speichern würdest, sondern wenn jedes char voll genutzt werden würde (oder zumindest eine Wertigkeit entsprechend einer Zweierpotenz hätte).

Mit Bits geht eine Integerdivision nämlich relativ locker flockig:
1)man setze den Quotienten auf Null.
2)man finde das höchstwertige Bit von Dividend und Divisor. Dies bezeichne ich mal als n (Dividend) und m (Divisor). Wenn m>n ist, dann bleibt der Quotient Null, und wir sind fertig.

3)man erstelle temporäre Kopien von Dividend und Divisor
4)man schiebe die temporäre Kopie des Divisors um (n-m) Stellen nach links. m brauchen wir nun nicht mehr. n setzen wir auf n:=n-m

5)Schleife, solange n>=0 ist
5a)Wenn die Kopie des Dividenden >= Kopie des Divisors, dann: Subtrahiere die Kopie des Divisors von der Kopie des Dividenden und setze das Bit des Quotienten an der Stelle n auf 1.
5b)Immer: Schiebe die Kopie des Divisors um ein Bit nach rechts und setze n:=n-1



Beispiel:
101101 Dividend
/ 110 Divisor

1)Quotient:=0
2)n:=5, m:=2 (ich zähle hier ab null, nicht ab eins)
m>n? nein, wir müssen weiter machen. Wir setzen n:=n-m=5-2=3

3)Kopieren.
4)Schieben:
101101 Kdividend
110000 Kdivisor

5)
5a)Kdividend>=Kdivisor? nein. Wir tun nichts.
5b)n:=n-1 => n:=2
und verschieben
101101 Kdividend
11000 Kdivisor

5a)Kdividend>=Kdivisor? ja. Subtrahieren:
101101 Kdividend
- 11000 Kdivisor
________
10101 Kdividend (neu)Bit 2 des Quotienten setzen:
100 Quotient
5b)n:=n-1 => n:=1
und verschieben der Divisor-Kopie
10101 Kdividend
1100 Kdivisor

5a)Kdividend>=Kdivisor? ja. Subtrahieren:
10101 Kdividend
- 1100 Kdivisor
________
1001 Kdividend (neu)Bit 1 des Quotienten setzen:
110 Quotient
5b)n:=n-1 => n:=0
und verschieben der Divisor-Kopie
1001 Kdividend
110 Kdivisor

5a)Kdividend>=Kdivisor? ja. Subtrahieren:
1001 Kdividend
- 110 Kdivisor
________
11 Kdividend (neu)Bit 0 des Quotienten setzen:
111 Quotient


n ist nun null, die Schleife wird beendet. Das Ergebnis haben wir bereits.


Probe:
Der Dividend war binär 101101, also dezimal 45. Der Divisor war binär 110, also dezimal 6. Wir haben als Quotienten binär 111 erhalten, das ist dezimal 7.

6*7=42, was für eine Integerdivision das korrekte Ergebnis ist. Wir können btw als "Rest" den letzten Wert von Kdividend ausgeben, binär 11, dezimal 3.

6*7+3=45

qed
Guter Post=)
Dann werde ich mal die Codierung entsprechend einer Zweierpotenz programmieren und anschließend mal deinen Vorschlag nachprogrammieren.Meinst du das durch die binäre Codierung die Geschwindigkeit im Vergleich zur vorherigen Codierung schneller wird?

[zeckensack]

Original geschrieben von Lord Nikon
Guter Post=)
Dann werde ich mal die Codierung entsprechend einer Zweierpotenz programmieren und anschließend mal deinen Vorschlag nachprogrammieren.Meinst du das durch die binäre Codierung die Geschwindigkeit im Vergleich zur vorherigen Codierung schneller wird? Nicht unbedingt ...
Du sparst auf jeden Fall Speicher, aber ob das so ins Gewicht fällt, kommt natürlich darauf an wieviele dieser grossen Zahlen du benutzt.

Umwandlung ins Dezimalformat (zwecks menschenlesbarer Anzeige) ist bei der Binärform natürlich schwieriger. Ebenso die Umwandlung von einem menschenlesbaren Format in das Binärformat. Die Arithmetik ist IMO allerdings im Binärformat leichter.

Du kannst btw obigen Algorithmus theoretisch auch mit einem Dezimalformat bauen, allerdings wird dir dann auffallen, dass du keine Bit-Shifts benutzen kannst, sondern stattdessen entweder mit 10 mutliplizieren, oder durch 10 dividieren musst. Beides ist ungleich teurer als Bitshifts, und bei der Division wirst du dann vor ziemlich grossen Problemen stehen ;)

Ist irgendwie shice, wenn man eine funktionierende Divisionsmethode braucht, um die Division zu implementieren :freak:

[Lord Nikon]

Wenn ich direkt versuche ins binär Format umzurechnen gibt es Probleme, wenn ich den Integer Bereich verlasse, weil der Datentyp abschneidet oder falsch rechnet wenn ich 2 hoch Anzahl der Bits rechne.Gibts eine Methode, die nicht auf auf das 2 hoch Anzahl der Bits angewissen ist?
Ich gehe so vor:

void uint3000::make_table()
{ // Create a Table with value

for (int i=0;i<this->bits;i++)
{
this->table[i]=pow(2,i);


}

}


void uint3000::setvalue(long val)
{

// Calculate the binary Value
// Binary: 1 2 4 8 16 32 64 128 256 512 usw.
// Vor hinten nach vorne Prüfunge

int zahler=0;
long size=val;

int backwarts_counter=this->bits;

int forward_counter=0;
this->make_table(); // Wird normalerweise nur beim
//Laden des Formulars einmal ausgeführt
while (size!=0)
{
if(size/this->table[backwarts_counter-1]!=0)
{
size=size-this->table[backwarts_counter-1];
}
else
{
this->value[forward_counter]=0;
}


forward_counter++;
backwarts_counter--;

}
for (int i=forward_counter;i<42;i++)
{
this->value[i]=0;
}
}

[ethrandil]

Das brauchst du doch garnicht?
d.D. wenn du long hast, dann reichen die int-Werte nicht mehr, ja?

pow(i, 2) ist identisch mit 1 << i

Letzteres müsste auch mit long funktionieren.

Anosnsten ist ja nur die Umwandlung int/long -> char[] wichtig. Andersrum musst du ja ohnehin davon ausgehen, dass die ranges gesprengt werden.

- Eth

[Lord Nikon]

[SIZE=1]Original geschrieben von ethrandil
Das brauchst du doch garnicht?

Für die Methode von Zeckensack schon:)

d.D. wenn du long hast, dann reichen die int-Werte nicht mehr, ja?

jep, wenn ich eine Integerzahl nehme reicht, es manchmal nicht trotz long.

pow(i, 2) ist identisch mit 1 << i
Letzteres müsste auch mit long funktionieren.

Ich rechne nicht pow(i,2) sondern pow(2,i).

Anosnsten ist ja nur die Umwandlung int/long -> char[] wichtig. Andersrum musst du ja ohnehin davon ausgehen, dass die ranges gesprengt werden.

Da die Ausgabe sinnvoller Weise in binär erfolgen sollte, müsste ich die genauen Wert von 2 hoch x kennen da meine Methode darauf passiert.

AnsiString uint3000::calculate_binary_to_decimal()
{ long long erg=0;
long zuruck;
zuruck=this->bits-1;
AnsiString back="";
for (int i=0;i<this->bits;i++)
{

if (this->value[i]!=0)

erg=erg+this->table[zuruck];
}
zuruck--;
}
back=AnsiString(erg);
ShowMessage(back);
return back;
}