Dividieren ohne zu dividieren

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

Dividieren ohne zu dividieren

Beitrag von Dirty Oerti » Do Dez 24, 2009 1:24 pm

Tag und frohe Weihnachten zusammen :)

Ich stehe vor folgendem Problem:
Ich hab Zahlen, die durch Integer-Arrays definiert sind. Diese Zahlen kann ich addieren, multiplizieren, dividieren, subtrahieren und vergleichen. Die Zahlen können auch negativ sein.
Eine solche Zahl sieht im Speicher dann z.B. so aus:

12 | 45 | 234 | 4567

Sie belegt damit 4 Speicherfelder und lautet (voll ausgeschrieben):

12004502344567

Nun möchte ich diese Zahl dividieren.
Z.B. durch diese Zahl:

34 | 1234 = 341234

Klar ist, dass ich nicht einfach die jeweiligen Speicherfelder dividieren kann, denn wie bekannt ist Integerdivision nicht unbedingt gerade genau, was sich dann auf die anderen Felder auswirken würde und zu starken Abweichungen führen würde.


Jetzt kommt der Einfall, den ich hatte: Ich erinnere mich an ein Buch, das ich mal in einem Thalia-Buchhandel gesehen (und angelesen) habe, in dem von einer (sehr effizienten) Möglichkeit die Rede war, Zahlen zu dividieren, in dem man irgendwie durch Multiplikation und Vergleiche zum Ziel kommt. Damals hab ich das Verfahren verstanden und mir gedacht, das merkst du dir leicht. Jetzt merke ich, dass dem nicht so ist ^^
Ich hab keine Ahnung mehr, wie das gehen könnte.

Deswegen jetzt schließlich meine Frage: Wie dividiere ich eine Zahl, ohne den / Operator zu verwenden?

:)
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.

nufan
Wiki-Moderator
Beiträge: 2557
Registriert: Sa Jul 05, 2008 3:21 pm

Re: Dividieren ohne zu dividieren

Beitrag von nufan » Do Dez 24, 2009 1:50 pm

Dirty Oerti hat geschrieben:Jetzt kommt der Einfall, den ich hatte: Ich erinnere mich an ein Buch, das ich mal in einem Thalia-Buchhandel gesehen (und angelesen) habe, in dem von einer (sehr effizienten) Möglichkeit die Rede war, Zahlen zu dividieren, in dem man irgendwie durch Multiplikation und Vergleiche zum Ziel kommt. Damals hab ich das Verfahren verstanden und mir gedacht, das merkst du dir leicht. Jetzt merke ich, dass dem nicht so ist ^^
Ich hab keine Ahnung mehr, wie das gehen könnte.

Deswegen jetzt schließlich meine Frage: Wie dividiere ich eine Zahl, ohne den / Operator zu verwenden?
Mir fällt dazu nur eine rekursive Lösung ein:

Code: Alles auswählen

#include <stdio.h>
#include <stdlib.h>

int divideRec (int dividend, int divisor, int quotient);

int main ()
{

  int dividend = 1, divisor = 3, quotient;
  
  quotient = divideRec (dividend, divisor, 0);
  printf ("Result: %d\n", quotient);
  
  return 0;

}


int divideRec (int dividend, int divisor, int quotient)
{

  int product = abs (divisor * quotient);                         // Produkt aus Divisor und aktuellem Quotienten bilden

  if (product < abs (dividend))                                       // Quotient noch nicht hoch genug
    quotient++;                                                              // Quotient erhöhen
    
  else if (product > abs (dividend))                                 // Quotient zu hoch
  {
  
    --quotient;                                                               // voriger Quotient ist am nähesten am Ergebnis dran
  
    if ((divisor < 0 && dividend > 0) || (divisor > 0 && dividend < 0))  // prüfen ob eine der beiden Zahlen negativ ist
      return -quotient;                                                      // negativen Quotienten zurückgeben
    return quotient;                                                        // normalen Quotienten zurückgeben
    
  }
    
  else if (product == abs (dividend))                                 // Quotient passt genau
  {
    if ((divisor < 0 && dividend > 0) || (divisor > 0 && dividend < 0))  // prüfen ob eine der beiden Zahlen negativ ist
      return -quotient;                                                      // negativen Quotienten zurückgeben
    return quotient;                                                        // normalen Quotienten zurückgeben
  }
    
  return divideRec (dividend, divisor, quotient);               // Quotient ist zu klein -> rekursiver Aufruf mit erhöhtem Quotienten

}
Funktioniert mit negativen und positiven Zahlen, hab das aber gerade erst geschrieben und noch nicht auf Herz und Nieren getestet :)
Glaube aber nicht, dass das effizienter als / ist ^^
Dass die Werte in Arrays gespeichert werden habe ich jetzt aber nicht berücksichtigt...

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

Re: Dividieren ohne zu dividieren

Beitrag von Xin » Do Dez 24, 2009 1:53 pm

Ich würde die Zahl, die Du teilen willst, verschieben (operator <<) und gucken, so dass sie gerade eben noch reinpasst.

37 / 4

Code: Alles auswählen

  100101
/    100
-----------
          ?
Verschieben, geht 3 mal, bei 4x ist die Zahl größer.

Code: Alles auswählen

  100101
- 100000   Subtraktion !
-----------
     101  ( Rest )
2^3 sind 8, Rest 5.

Der Rest ist größer als 4, also teilen wir den Rest weiter:
101 - ( 100 << 0 ) => 1 Rest 1 + 8, die wir schon ausgerechnet haben.
9 Rest 1.

Nun teilen wir weiter: Damit die Zahl passt, muss nun der >> Opertator verwendet werden. Und zwar 2 mal ^^

Code: Alles auswählen

   1
-  1
-----
   0 
9 + ( 1 / 2^2 ) => 9 + 1/4.

37 / 4 ist also 9+1/4.
Und das ganze ohne Division.
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 » Do Dez 24, 2009 2:08 pm

Tag :)

Schonmal danke für deine Idee. Das die Werte in Arrays gespeichert sind ist auch nicht so wichtig, alle anderen Rechenarten außer dividieren (und modulo sowie der Bitverschiebungen) stehen zur Verfügung.
Einziges Manko ist, dass Multiplizieren mit großen Zahlen immer langsamer wird (es sind N*M Multiplikationen notwendig, wobei N die Anzahl der Arrayelemente der einen und M die der anderen Zahl ist)

Deine Methode funktioniert denke ich auch effizient, wenn die beiden Zahlen annähernd gleich groß oder zumindest in der selben Größenordnung liegen :)
Problem ist nur: Was mache ich, wenn ich z.B. eine Zahl wie 10^200 durch 15 dividiere. Das würde so sehr lange dauern.

Ich hatte auch schon überlegt, ob es mit Subtrahieren möglich ist. Sprich:

Code: Alles auswählen


Zahl test = divident;
Zahl quotient = 0;
while( test >= divisor )
{
   test -= divisor;
   quotient++;
}

Dauert halt auch Recht lange bei großen Zahlen.

-------------

Also diese verschiebe-Möglichkeit gefällt mir sehr gut.
EInziges Problem ist: Um sie anwenden zu können, muss ich den Verschiebeoperator implementieren.

Bleibt also die Frage, wie ich den auf mein Array anwende.
Eigentlich müsste es ja funktionieren, wenn ich die Verschiebung auf das erste Element des Arrays anwende, das "Herausgeschobene Bit" (ich gehe mal von einer Rechtsverschiebung aus, links geht analog vom letzten Element her) im 2. Element nach dessen Verschiebung an der Spitze einfüge etc ...

Mal überlegen (jedes Element kann im Beispiel mal nur die Zahlen von 0-9 annehmen und ich nehme mal 8 Bit Werte)

Zahl test = 1 | 2

= 00000001 | 00000010

= 0000000100000010 != 12

Damit geht die Verschiebung so auch nicht :(

Ich müsste die Verschiebung also auf 10er Basis durchführen können... ?

*edit* Jetzt wenn ich so überlege, dann könnte es sich bei der gesuchten Möglichkeit um genau das von Xin beschriebene gehandelt haben, nur eben nicht auf Basis 2, sondern auf Basis 10 ... ?
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
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 » Do Dez 24, 2009 2:31 pm

Ok, ich hab das jetzt mal durchgedacht.
<< heißt ja eigentlich nur *2
Eine Verschiebung auf Basis 10 ist also analog *10 (ist auch logisch, wenn man die Zahl 23 eins nach links verschiebt kommt 230 raus..)

Nun das ganze mal durchgedacht:

370 / 4

nun verschiebe ich die 4 so lange, wie das Ergebnis kleiner als der Dividend ist.

4 <<(10) = 40 -> ist kleiner als 370
40<<(10) = 400 -> ist größer als 370

Heißt ich hab eine Verschiebung um eine Stelle
Nun ziehe ich die verschobene Zahl so lange vom Dividend ab, wie es eben geht.

370 - 4 * 10^1 = 330
330 - 4 * 10^1 = 290
etc

Das kann ich 9 mal machen, dann bleibt mir 10 übrig, davon kann ich keine 40 mehr abziehen.

Heißt ich hab als vorläufiges Ergebnis 9 * 10^1 Rest 10
Also 90 Rest 10

10 kann ich nun aber noch durch 4 teilen, bzw ich kann 4 so oft von 10 abziehen, wie es eben geht.
10 - 4*10^0 = 6
6 - 4*10^0 = 2
-> 2 Rest 2

Das addier ich nun zu meinem vorherigen Ergebnis und erhalte damit

92 Rest 2, was dann auch die Lösung ist (ich könnte noch weiter machen, bis der Rest == 0 ist oder die maximale Genauigkeit ausreicht, ich rechne aber nur mit Integern, also reicht das)


Die einzige Frage, die nun bleibt, ist, ob das effizient auch bei sehr großen Zahlen abläuft :)
Dazu muss die Verschiebung effizient laufen (sollte möglich sein, das zu implementieren) und der Vergleich muss effizient ablaufen, was soweit ich weiß auch der Fall ist.
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: 8858
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

Re: Dividieren ohne zu dividieren

Beitrag von Xin » Do Dez 24, 2009 3:07 pm

Wenn Du im 10er Zahlensystem rechnest, was für Computer eher ungewöhnlich wäre, dann ist Dein Worst-Case 9*Anzahl der Stellen der zu teilenden Zahl.
Im Binärsystem gibt es weniger Stellen, dafür mehr Ziffern.

Eine dreistellige Zahl ist im BestCase 111, also 3 Subtraktionen. 111 binär sind 7 Bit breit, also mehr Divisionen bei gleicher Zahl.
der WorstCase wäre 999. Das sind 27 Subtraktionen. Im Binärsystem, wäre die Zahl 10 Bit breit, also maximal 10 Subtraktionen.
Im Schnitt hast Du im Dezimalsystem 5 Subtraktionen pro Stelle. Im Binärsystem 0,5, dafür aber mehr Stellen für die gleiche Zahl...

Kurz: Alles hängt von der Größe der Zahlen ab... aber der Aufwand explodiert dabei nicht.
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 » Fr Dez 25, 2009 12:46 am

Hm, mehr Ziffern ist für mich eher schlecht, da mehr Ziffern mehr Multiplikationen heißt was in dem Fall heißt mehr Aufwand.
Subtrahieren geht schneller als multiplizieren.

Auf jeden Fall funktioniert es nun auf 10er Basis, den Code poste ich morgen mal :)
Muss jetzt erstmal ins Bett, damit ich morgen mein neues Bett (= Weihnachtsgeschenk) aufbaun kann^^

Frohes Fest :)
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: 8858
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

Re: Dividieren ohne zu dividieren

Beitrag von Xin » Fr Dez 25, 2009 9:11 am

Dirty Oerti hat geschrieben:Hm, mehr Ziffern ist für mich eher schlecht, da mehr Ziffern mehr Multiplikationen heißt was in dem Fall heißt mehr Aufwand.
Subtrahieren geht schneller als multiplizieren.
Das macht die Sache eben etwas aufwendiger.
Dirty Oerti hat geschrieben:Auf jeden Fall funktioniert es nun auf 10er Basis, den Code poste ich morgen mal :)
Schön. Beschreibe doch, was Du verstanden hast und kombiniere Deinen Code für einen Artikel für's Wiki draus.
Dirty Oerti hat geschrieben:Muss jetzt erstmal ins Bett, damit ich morgen mein neues Bett (= Weihnachtsgeschenk) aufbaun kann^^
Aber wie ich mich kenne, hätte ich das Bett abends noch aufgebaut. ^^
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.

AnGaiNoR
Beiträge: 212
Registriert: Sa Jul 19, 2008 7:07 pm
Wohnort: Dresden

Re: Dividieren ohne zu dividieren

Beitrag von AnGaiNoR » Fr Dez 25, 2009 5:52 pm

Ich denke mal ein großes Problem in deiner Idee steckt darin, dass keine eineindeutige Zuordnung vorliegt.

Wenn man mit binären und dezimalen Zahlen arbeitet, dann kann man jeder Binärzahl genau eine Dezimalzahl zuordnen und umgekehrt:
12d = 1100b
1100b = 12d

In deinem System geht das nicht:
1 | 2 = 12d
0 | 12 = 12d
12d = ?
Physics is like sex: sure, it may give some practical result, but that's not why we do it.
(Richard P. Feynman)

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 8:51 am

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) :)

------------------------
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):

Code: Alles auswählen

xint xint::operator/(xint num)
{
	xint ret;
	ret = 1;
	xint tmp3 = *this;
	bool neg = false;
// Hier kommt erst einmal die Abhandlung ob der Quotient + oder - wird und dann auch der Test, ob man die Division nicht einfach schnell beenden kann
	if (num.n_sign != tmp3.n_sign) {
		ret *=-1;
		neg = true;
	}
	if (num.n_sign == MINUS) num*=-1;
	if (tmp3.n_sign == MINUS) tmp3 *=-1;
	if (num > tmp3) {
		ret = 0;
		return ret;
	} else if ( num == tmp3 ) {
		return ret;
	}
// Wenn hier angelangt wird, dann muss WIRKLICH dividiert werden
// WAS genau WELCHE "tmp"-Zahl tut ist das Rätsel ;)
	ret = 0;
	xint tmp = num;
	xint tmp2 = num;
	int count;
	do {
		count = 0;
		tmp = num;
		tmp2 = num;
// Wie oft kann ich den Divisor auf Basis 10 nach links verschieben?
		while ( tmp <= tmp3) {
			tmp2 = tmp;
			tmp*=10;
			count++;
		}
		count--;
		tmp = tmp3;
// val ist der Wert, der zum Quotienten addiert werden wird (und den "Grad der Verschiebung" repräsentiert)
		xint val;
		val = 1;
		for (unsigned int i = 0; i < count; i++) {
			val*=10;
		}
// Hier ist die Subtraktion
		while ( tmp >= tmp2 ) {
			tmp-=tmp2;
			ret+=val;
		}
// Neuer "Dividend" ist der Rest des Durchgangs
		tmp3 = tmp;
// Ist der Rest == 0 oder passt der Divisor nicht mehr in den Dividenden, dann sind wir fertig
	} while (count != 0 && tmp3 != 0);
// Vorzeichen anpassen
	if (neg) ret*=-1;
	return ret;
}
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 :)
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