1/3 zur Basis 2 mit beliebiger Genaugigkeit berechnen



  • Hallo.

    Die Aufgabe lautet:
    Berechnen Sie die Ziffern der rationalen Zahlen 1/3 zur Basis b=2 mit beliebiger Genauigkeit p.

    Den Algorithmus für ein bestimmtes "p" ist mir bekannt. Aber wie gehe ich das Problem mit beliebigem "p" an?

    Der Algorithmus für eine bestimmte Genauigkeit p:

    1. Multipliziere den Zähler mit bpb^{p} (Dezimalpunktverschiebung um p-Stellen nach rechts)
    2. Dividiere die so erhaltene Zahl mit dem Zähler, bis Rest < Divisor.
    3. Wandle die Zahl gegebenfalls in ein anderes Zahlensystem um.
    4. Verschiebe den Dezimalpunkt um p-Stellen nach links. Fertig.

    Jetzt soll ich das mit beliebigem p machen und stecke schon in 1. fest.



  • Wieso willst du das allgemein lösen, wenn in der Angabe genau ein Bruch, nämlich 1/3 steht?



  • Hallo hustbaer.

    Es geht darum, den Bruch in so anzuschreiben: znzn1...z1z0.z1...zmz_{n}z_{n-1}...z_{1}z{0}.z_{-1}...z_{-m}

    Also die Umwandlung von 1/3 mit Basis b=10 und Genauigkeit p=3 würde wie folgt ablaufen:

    1. 1103=10001*10^{3}=1000
    2. 1000:3=3331000:3=333 Der Rest von 1 wird verworfen.
    3. Umwandlung wird nicht durchgeführt, da b=10
    4. Den Dezimalpunkt um p-Stellen nach links: 0.3330.333

    Jetzt wird ersichtlich, dass je höher die Genauigkeit p wird, desto genauer wird die Approximation. Die Umwandlung zu Binär ist auch trivial, nur weiß ich nicht, wie ich bei "beliebigem" p vorgehen soll.



  • asfdwfwfef schrieb:

    Den Algorithmus für ein bestimmtes "p" ist mir bekannt. Aber wie gehe ich das Problem mit beliebigem "p" an?

    Der Algorithmus für eine bestimmte Genauigkeit p:
    1. Multipliziere den Zähler mit bpb^{p} (Dezimalpunktverschiebung um p-Stellen nach rechts)
    2. Dividiere die so erhaltene Zahl mit dem Zähler, bis Rest < Divisor.
    3. Wandle die Zahl gegebenfalls in ein anderes Zahlensystem um.
    4. Verschiebe den Dezimalpunkt um p-Stellen nach links. Fertig.

    Jetzt soll ich das mit beliebigem p machen und stecke schon in 1. fest.

    Das ist DER Weg? Nee. Das ist einer der möglichen Wege.

    Mach's doch einfach wie in der Schule!
    http://commons.wikimedia.org/wiki/File:Division_Schriftlich.jpg
    Nur halt binär.



  • Hallo Volkard.

    Das ist DER Weg? Nee. Das ist einer der möglichen Wege.

    Ja ich weiß, dass es mehr Wege gibt, nur diesen Weg, den ich gewählt habe, ist der Weg, den wir gerade an der Uni durchgemacht haben. Darum diesen Weg.

    Mach's doch einfach wie in der Schule!

    Wie mit "beliebigem" p?

    13\frac{1}{3} in binär wäre ja 0.010101010.....0.010101010.....
    Je höher die Genauigkeit p, desto genauer* das Ergebnis.
    0.0100.010 mit p=3p=3
    0.01010.0101 mit p=4p=4
    0.010100.01010 mit p=5p=5
    0.0101010.010101 mit p=6p=6

    *Es gilt:
    0cd(znbn+zn1bn1+...+z1b+z0+z1b1+...+zpbp)<bp0\le\frac{c}{d}-(z_{n}b^{n}+z_{n-1}b^{n-1}+...+z{1}b+z_{0}+z_{-1}b^{-1}+...+z_{-p}b^{-p})<b^{-p}



  • asfdwfwfef schrieb:

    0.0101010.010101 mit p=6p=6

    1 / 11 = 0.0101...
    0
    -
    10
     0
     -
    100
     11
     --
      10
       0
      --
      100
       11
       --
       ...
    

    Abbrechen, wenn die Stellenzahl erreicht ist.

    #include <iostream>
    using namespace std;
    
    int main(){
    	int zaehler=1;
    	int nenner=3;
    	//zaehler<nenner!
    	int nachkommastellen=0;
    	cout<<"0.";
    	while(nachkommastellen<1000){
    		zaehler*=2;
    		if(zaehler<nenner)
    			cout<<'0';
    		else{
    			cout<<'1';
    			zaehler-=nenner;
    		}
    		++nachkommastellen;
    	}
    }
    


  • Ich glaube es geht gar nicht um einen Algorithmus, sondern man soll die Periode bestimmen und das dann angeben.



  • asfdwfwfef schrieb:

    1. Multipliziere den Zähler mit [latex]b^{p}
    Jetzt soll ich das mit beliebigem p machen und stecke schon in 1. fest.

    Mach ne Schleife von 1 bis p und multipliziere in jedem Schritt mit b?



  • Danke euch allen mal für die Antworten. 🙂

    Ja in C++ kann ich das so machen, aber ich muss kein Programm schreiben, sondern das "händisch" zeigen.

    Wahrscheinlich ist die Antwort so einfach, aber ich finde sie nicht.

    Ich glaube es geht gar nicht um einen Algorithmus, sondern man soll die Periode bestimmen und das dann angeben.

    Ich glaube, die Antwort wäre fast zu einfach 🙂
    Aber ich werde sie mal so übernehmen und schauen, was der Lehrer zu dieser Antwort sagt.

    Danke euch allen für die Mithilfe 👍



  • asfdwfwfef schrieb:

    Ja in C++ kann ich das so machen, aber ich muss kein Programm schreiben, sondern das "händisch" zeigen.

    Haeh, dann musst du doch das ganze nur als eine Formel schreiben und fertig?



  • Haeh, dann musst du doch das ganze nur als eine Formel schreiben und fertig?

    Ja, aber wie? Das ist mein Problem.



  • Sone schrieb:

    asfdwfwfef schrieb:

    Ja in C++ kann ich das so machen, aber ich muss kein Programm schreiben, sondern das "händisch" zeigen.

    Haeh, dann musst du doch das ganze nur als eine Formel schreiben und fertig?

    Auf die Formel bin ich ja mal gespannt.



  • asfdwfwfef schrieb:

    Also die Umwandlung von 1/3 mit Basis b=10 und Genauigkeit p=3 würde wie folgt ablaufen:

    1. 1103=10001*10^{3}=1000
    2. 1000:3=3331000:3=333 Der Rest von 1 wird verworfen.
    3. Umwandlung wird nicht durchgeführt, da b=10
    4. Den Dezimalpunkt um p-Stellen nach links: 0.3330.333

    Jetzt wird ersichtlich, dass je höher die Genauigkeit p wird, desto genauer wird die Approximation. Die Umwandlung zu Binär ist auch trivial, nur weiß ich nicht, wie ich bei "beliebigem" p vorgehen soll.

    Aha. Wenn Du Wert darauf legst, daß Du eine "Umwandlung nach Binär von positiven Ganzzahlen" vorliegen hast und die nur aufrufen willst, dann wird es unsinnig.

    Was ich machte, ist nichts anderes als die Umwandlung nach Binär, nur bockt sie nicht.

    Ein Unfug-Vorschlag:
    0. Finde die kleinste Zweierpotent b^p, wo b^p-1 ein Vielfaches des Divisors ist.
    (damit ist p gefunden)
    1. Multipliziere den Zähler mit b^p (Dezimalpunktverschiebung um p-Stellen nach rechts)
    2. Dividiere die so erhaltene Zahl mit dem Zähler, bis Rest < Divisor.
    3. Wandle die Zahl gegebenfalls in ein anderes Zahlensystem um.
    4. Verschiebe den Dezimalpunkt um p-Stellen nach links. Fertig.

    Im Beispiel, teste 1,3,7,15,31,63,... ob sie Virlfache von 3 sind. Die 3 ist es schon. 2=2^2-1, also p=2. So kannste vor den Schritten 1-4 das p herausfinden und musst das Verfahren nicht anpassen und kannst auch darauf verzichten, das schriftliche Dividieren wieder zu erlernen.



  • @volkard:
    Wenn r die Basis des Zahlensystems ist: ((b ^ p) mod Zaehler) / r ^ p. Was gibts da so gespannt zu sein, man haengt einfach die Schritte aneinander?



  • TGGC schrieb:

    @volkard:
    Wenn r die Basis des Zahlensystems ist: ((b ^ p) mod Zaehler) / r ^ p. Was gibts da so gespannt zu sein, man haengt einfach die Schritte aneinander?

    Bitte konkreter. Hilft das, p rauszufinden? Wird die Formel Klarheit bringen?
    Oder war das schon die angedachte Formel, was rechnet sie aus (nicht das gesuchte p)?



  • Ich weiss nicht genau was der Sinn ist, was dieser Algo soll und ob er korrekt ist. Also keine Ahnung, was das ausrechnen soll. Ich weiss aber auch nicht, was das Problem sein soll den Algo anzuwenden auf ein beliebiges p. Ich weiss auch nicht, wie man da in 1.) feststecken kann.

    Aus der urspruenglichen Aufgabenstellung lese ich persoenlich folgendes raus: Bestimme eine Folge von Zahlen {z1, z2, ..., zp-1, zp} wobei zn eine Ziffer der Zahl z zur Basis b ist mit z = 1/3 und b = 2. zn zu berechnen ist aber eine voellig triviale Aufgabe, dieser Algo unnoetig und jemand haette hier das schon beantwortet. Daraus schliesse ich, das ich die Frage falsch verstehe. Ich dachte auch das p gegeben ist und nicht gesucht wird.



  • nur weiß ich nicht, wie ich bei "beliebigem" p vorgehen soll

    Ich glaube mit beliebig ist gemeint: beliebig aber fest. Dein Algrithmus hat also p als Eingabe, die beliebig sein kann. Aber fuer den konkreten Algorithmusaufruf ist p fest. Daher muss p im Algorithmus als Variable auftauchen.


Log in to reply