Periodenberechnung von Dezimalbrüchen

Fiete · Beiträge: 601 Erhaltene Danke: 339 W7 Delphi 6 pro

Das Programm berechnet die Periode von Dezimalbrüchen.
Zähler und Nenner werden eingegebe, als Ergenis erhält man die Periodenlänge.
z.B.
1:109=0,009174311926605504587155963302752293577981651376146788990825688073394495412844036697247706422018348623853211
Periodenlänge = 108
Periode von der 1-ten bis zur 108-ten Stelle

Zähler und Nenner können maximal acht Ziffern lang sein!
Gruß Fiete

Einloggen, um Attachments anzusehen!

_________________
Fietes Gesetz: use your brain (THINK)

Horst_H · Verfasst: Mi 21.03.12 19:20

Hallo,

wau, dass ist schon fast 10 Jahre her, dass ich das mal probiert habe:
www.webplain.de/fore...1,3861,3861#msg-3861
Aber das beschriebene Verfahren aus
www.mathematik-online.de/F103.htm
habe ich nicht probiert.
Irgendwelche KGV bilden
Dein Beispiel mit dem Nenner 1094 und dessen Teiler 2 und 547

Zitat:

Aufgrund des Satzes von Joseph Lagrange wissen wir außerdem, dass die Ordnung eines Elementes einer Gruppe G die Ordnung von G teilt. Folglich ist m ein Teiler der Gruppenordnung 22 von Z*23, und damit gilt: m = 1, 2, 11 oder 22.

Hier ist die Gruppenordnung von Teiler1 = 2 -1= 1 mit dem Teiler: 1
und die von Teiler2 = 547 -1=> 546 mit den Teilern: 1,2,3,91
Die Periode kann maximal so lang wie der größte Teiler sein, dass beschränkt schon einmal das KGV, aber warum hier nun die 91 zum tragen kommt??
ganz unten www.mathematik-online.de/F103.htm

Zitat:

Wegen der leicht zu überprüfenden Aussagen: 10 1 ≠ 1, 1 02 ≠ 1 und 10 11 ≠ 1 muss m = 22 sein. Analog berechnet man für 3 ∈ Z*7 die Ordnung k = 6.

Bahnhof! Ich will zu meiner Gruppe ;-)

Gruß Horst

Horst_H · Verfasst: Do 22.03.12 23:58

Hallo,

@Fiete:
ich habe mir das Programm nochmals zu Gemüte geführt.
Du hast ja auch, wie ich damals, einfach in einem Feld der Größe Divisor-1 gemerkt, wann ein Rest wieder aufgetreten ist.
Jetzt ist mir die Idee gekommen, mal festzustellen, wann die Periode spätestens beginnt.
Mein Gedanke war nun der, dass wenn der Rest wieder auftaucht, sich die Abfolge der Reste ja komplett wiederholt.
Wenn ich mir den 100.sten Rest merke und dann einfach nur teste, wann dieser wieder auftaucht, habe ich die Periode auch bestimmt.
Ergo, wenn ich weiß, das bei der Zahl x die Periode spätestens nach y Berechnungen beginnt, merke ich mir stur den Rest der y.ten Berechnung und rechne weiter bis dieser Rest wieder auftaucht.
Damit brauche ich das ganze Feld nicht mehr :-)

Das Schönste kommt aber noch:
Ich kann vorher bestimmen, wann spätestens die Periode beginnt.
Die Folge ist ganz simpel

markieren

Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:

Zahl   max. Periodenbeginn nach y Stellen
3      1
6      2
12     3
...
x2     +1
..     ..
24576   14
24576x2  14+1
...

y = ln(Zahl/3)/ln(2)+1
Für Divisor = High(Longint) ist y = 30.
Also brauche ich mir nur den Rest der 30.ten Berechnung merken und solange weiterrechnen, bis dieser Rest wieder auftaucht, dass ist gegenüber dem abspeichern von 2 Milliarden Zahlen schon ein kleiner Gewinn.
Für die richtige Ausgabe muss ich mir aber doch die ersten 30 Berechungen speichern und mit den letzten 30 abgleichen.
Mal schauen, ob ich dies in ein Programm packe.

Gruß Horst

Horst_H · Verfasst: Fr 30.03.12 06:18

Hallo,

Arndt Brünner hat es wesentlich besser erklärt.Insbesondere die Euler Phi-Funktion.
www.arndt-bruenner.d...s/periodenlaenge.htm
Wozu das Ganze?
Bei mir verklemmmte sich Fiete's Version unter Linux mit wine.
Das lag wahrscheinlich mehr an der Speicherverwaltung bei Stringverlängerung.
Zeile := Zeile+Ziffer;
Ausserdem hat es mich nun gestört, dieses riesige und letztlich unnütze Restfeld zu benutzen.

Gruß Horst

Fiete · Beiträge: 601 Erhaltene Danke: 339 W7 Delphi 6 pro

Moin Horst_H,
mit meinem Programm wollte ich nicht nur die Periodenlänge sondern auch die Periode explizit errechnen.
Meine erste Version arbeitet mit der Phi-Funktion:

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
102:
103:
104:
105:
106:
107:
108:
109:
110:
111:
112:
113:
114:
115:
116:
117:
118:
119:
120:
121:
122:
123:
124:
125:
126:
127:
128:
129:
130:
131:
132:
133:
134:
135:
136:
137:
138:
139:
140:
141:
142:
143:
144:

{$R+,Q+}
 procedure TPeriode.Potenziere(Basis,Exponent,Modul:Int64;Var Ergebnis:Int64);
  begin
   Ergebnis:=1;
   While Exponent>0 DO
    begin
     if Exponent mod 2>0 then Ergebnis:=Ergebnis*Basis mod Modul;
     Basis:=Basis*Basis mod Modul;
     Exponent:=Exponent div 2
    end
  end;

 procedure TPeriode.RechneClick(Sender: TObject);
  const Max=447;
        Prim:Array[1..Max]of Integer=(
             2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59,
             61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131,
             137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197,
             199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271,
             277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353,
             359, 367, 373, 379, 383,389, 397, 401, 409, 419, 421, 431, 433,
             439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509,
             521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601,
             607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677,
             683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769,
             773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859,
             863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953,
             967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021, 1031, 1033,
             1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103,
             1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193,
             1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279,
             1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361,
             1367, 1373, 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447,
             1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511,
             1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597,
             1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667,
             1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747, 1753,
             1759, 1777, 1783, 1787, 1789, 1801, 1811, 1823, 1831, 1847, 1861,
             1867, 1871, 1873, 1877, 1879, 1889, 1901, 1907, 1913, 1931, 1933,
             1949, 1951, 1973, 1979, 1987, 1993, 1997, 1999, 2003, 2011, 2017,
             2027, 2029, 2039, 2053, 2063, 2069, 2081, 2083, 2087, 2089, 2099,
             2111, 2113, 2129, 2131, 2137, 2141, 2143, 2153, 2161, 2179, 2203,
             2207, 2213, 2221, 2237, 2239, 2243, 2251, 2267, 2269, 2273, 2281,
             2287, 2293, 2297, 2309, 2311, 2333, 2339, 2341, 2347, 2351, 2357,
             2371, 2377, 2381, 2383, 2389, 2393, 2399, 2411, 2417, 2423, 2437,
             2441, 2447, 2459, 2467, 2473, 2477, 2503, 2521, 2531, 2539, 2543,
             2549, 2551, 2557, 2579, 2591, 2593, 2609, 2617, 2621, 2633, 2647,
             2657, 2659, 2663, 2671, 2677, 2683, 2687, 2689, 2693, 2699, 2707,
             2711, 2713, 2719, 2729, 2731, 2741, 2749, 2753, 2767, 2777, 2789,
             2791, 2797, 2801, 2803, 2819, 2833, 2837, 2843, 2851, 2857, 2861,
             2879, 2887, 2897, 2903, 2909, 2917, 2927, 2939, 2953, 2957, 2963,
             2969, 2971, 2999, 3001, 3011, 3019, 3023, 3037, 3041, 3049, 3061,
             3067, 3079, 3083, 3089, 3109, 3119, 3121, 3137, 3163);

  var K,Nenner,PFIndex,PrimIndex,TeilerIndex,PhiVonNenner,Vergleich,
      Zwei,Fuenf,Nachkommastellen,Periode:Integer;
      Rest:Int64;
      PrimFaktorListe,TeilerListe:Array of Integer;
      Zeile:String;
      Rein:Boolean;
  begin
   if EditNenner.Text='' then
    begin
     MessageDlg('Der Nenner ist undefiniert!',mtError,[mbOk],0);
     Exit
    end;
   Nenner:=StrToInt(EditNenner.Text);
   PFIndex:=0;PrimIndex:=1;
   Ausgabe.Clear;
   repeat
    if Nenner mod Prim[PrimIndex]=0 then
     begin
      Nenner:=Nenner div Prim[PrimIndex];
      inc(PFIndex);
      SetLength(PrimFaktorListe,PFIndex);
      PrimFaktorListe[PFIndex-1]:=Prim[PrimIndex];
     end
    else inc(PrimIndex);
   until (Nenner=1) or (PrimIndex>Max);
   if PrimIndex>Max then
    begin
     inc(PFIndex);
     SetLength(PrimFaktorListe,PFIndex);
     PrimFaktorListe[PFIndex-1]:=Nenner;
    end;
   Zeile:='';
   for K:=0 to PFIndex-1 do
    Zeile:=Zeile+Format('%6d',[PrimFaktorListe[K]]);
   Ausgabe.Lines.Add('Primfaktoren:'+Zeile);
   if (PrimFaktorListe[PFIndex-1]=2) or (PrimFaktorListe[PFIndex-1]=5) then
    begin // abbrechender Dezimalbruch
     Zwei:=0;Fuenf:=0;
     for K:=0 to PFIndex-1 do
      if PrimFaktorListe[K]=2 then inc(Zwei) else inc(Fuenf);
     if Zwei>Fuenf then Nachkommastellen:=Zwei else Nachkommastellen:=Fuenf;
     LabelErg.Caption:='abbrechender Dezimalbruch mit '+
                       IntToStr(Nachkommastellen)+' Nachkommastellen';
    end
   else
    begin
     PhiVonNenner:=1;Vergleich:=0;Nenner:=1;Rein:=True;
     for K:=0 to PFIndex-1 do
      if (PrimFaktorListe[K]<>2) and (PrimFaktorListe[K]<>5) then
       begin
        Nenner:=Nenner*PrimFaktorListe[K];
        if Vergleich=PrimFaktorListe[K] then
         PhiVonNenner:=PhiVonNenner*PrimFaktorListe[K]
        else PhiVonNenner:=PhiVonNenner*(PrimFaktorListe[K]-1);
        Vergleich:=PrimFaktorListe[K];
       end
      else Rein:=False;
     Zeile:='Phi('+IntToStr(Nenner)+')='+IntToStr(PhiVonNenner);
     Ausgabe.Lines.Add(Zeile);
     TeilerIndex:=1;
     SetLength(TeilerListe,TeilerIndex);
     TeilerListe[TeilerIndex-1]:=1;
     for K:=2 to PhiVonNenner div 2 do
      if PhiVonNenner mod K=0 then
       begin
        inc(TeilerIndex);
        SetLength(TeilerListe,TeilerIndex);
        TeilerListe[TeilerIndex-1]:=K;
       end;
     inc(TeilerIndex);
     SetLength(TeilerListe,TeilerIndex);
     TeilerListe[TeilerIndex-1]:=PhiVonNenner;
     Zeile:='';
     for K:=0 to TeilerIndex-1 do
      Zeile:=Zeile+Format('%7d',[TeilerListe[K]]);
     Ausgabe.Lines.Add('Teiler:'+Zeile);
     for K:=0 to TeilerIndex-1 do
      begin
       Potenziere(10,TeilerListe[K],Nenner,Rest);
       if Rest=1 then
        begin
         Periode:=TeilerListe[K];
         Break;
        end;
      end;
     if Rein then LabelErg.Caption:='reinperiodischer Dezimalbruch mit '
     else LabelErg.Caption:='gemischtperiodischer Dezimalbruch mit ';
     LabelErg.Caption:=LabelErg.Caption+'der Periodenlänge '+IntToStr(Periode);
    end;
  end;

Das vollständige Programm ist im Anhang
Gruß Fiete

Einloggen, um Attachments anzusehen!

_________________
Fietes Gesetz: use your brain (THINK)

Horst_H · Verfasst: Mi 04.04.12 12:48

Hallo,

ich habe es mal in Freepascal für die Konsole komponiert und beides zusammengefügt.
Statt um die 67 Sekunden, mit Ausgabe, für 99999989 mit 99999988 Stellen dauert es etwa 2 Sekunden, ohne Ausgabe , dadurch, dass die Stringlänge zuvor festliegt.

Gruß Horst

Einloggen, um Attachments anzusehen!

Lelf · Beiträge: 42 Erhaltene Danke: 21

Vor Jahren habe ich auch einmal ein solches Programm entwickelt. Hier in Kürze, was noch hängen geblieben ist:

Es sei Bruch = 1 / Nenner
- zunächst werden die vorhandenen Faktoren 2 und 5 vom Nenner entfernt (Dezimal-System).
- man erhält eine Zahl N = p1*p2*...*pn. (Primzahlzerlegung).
- dann gilt:

- Periodenlänge = kleinste Zahl r für die gilt: 10^r == 1(mod N)
- für r = Phi(N) = (p1-1)*(p2-1)*...*(pn-1)

1.Beispiel: Nenner = 1094 = 2*547 | /2 (2 und 5, falls vorhanden entfernen)
N = 547
Phi(N) = 546 = 2*3*7*13 = r

10^r mod N == 1 mod N

10^546 mod 547 == 1 | 546 : 2 = 273

10^273 mod 547 == 1 | 273 : 3 = 91

10^91 mod 547 == 1 | 91 : 7 = 13

10^13 mod 547 == 544

also ist 91 die Periodenlänge von 1094

2.Beispiel:

Nenner = 1.393.125 = 3 * (5^4) * 743 | /625 (2 und 5, falls vorhanden entfernen)
N = 2229 = 3 * 743
Phi(N) = 1484 = 2 * 742 = (2^2) * 7 * 53 = r

10^r mod N == 1 mod N
10^1484 mod 2229 == 1 | 1484 : 2 = 742
10^ 742 mod 2229 == 1 | 742 : 7 = 106
10^ 106 mod 2229 == 592

also ist 742 die PeriodenLänge von 1.393.125

Horst_H · Verfasst: Mi 04.04.12 20:34

Hallo,

genau so, wie es Fiete in seinem zweiten geposteten Programm gemacht hat.
Ich habe es nur kompbinert weil 99999989 irgendetwas um 800 Mb unterweges belete und bei 631 stehen blieb.Das schaffte mein Linux Notebook mit 1 Gbyte Ram unter wine nicht ohne auslagern, was mir wie ein hängenbleiben vorkam.

Gruß Horst

Lelf · Beiträge: 42 Erhaltene Danke: 21

@ Horst_H

Deine Idee, festzustellen, wann eine Periode spätestens beginnt, ist zwar richtig, aber nicht ganz zu Ende gedacht bzw. unklar formuliert. Das, was Du vermutlich meinst, nennt man: "Vorziffern eines gemischt-periodischer Dezimalbruchs" oder "reiner Teil" = Anzahl der Vorziffern, (daran anschließend die Anzahl der Ziffern des "periodischen Teils" = Periodenlänge.)

=============================================================================
Anzahl der Vorziffern = max(Exponent von 2, Exponent von 5) im Dezimal-System
=============================================================================

Beispiele (Bruch = 1 / Nenner):

Nenner \\ Primzahlzerlegung \\ Vorziffern
3 \\ 3 \\ 0
6 \\ 2 * 3 \\ 1
12 \\ (2^2) * 3 \\ 2
40 \\ (2^3) * 5 \\ 3 (endlicher Dezimalbruch. Periodenlänge = 0)
120 \\ (2^3) * 3 * 5 \\ 3
175 \\ (5^2) * 7 \\ 2 1/175 = 0,00 571428... 117/175 = 0,66 857142...
15.000 \\ (2^3) * 3 * (5^4) \\ 4
24.576 \\ (2^13) * 3 \\ 13
755.849 \\ 23 * 59 * 557 \\ 0
3.662.109.375 \\ 3 * (5^13) \\ 13

high(longint) ist übrigends +2.147.483.647 = (2^31) - 1 = Primzahl

Gruß
Lelf

Horst_H · Verfasst: Do 12.04.12 19:15

Hallo,

ich habe das in dem Programm periode.pas doch schon berücksichtigt.
Ich habe es nun etwas geändert, es wird ein '_' eingefügt, wo die Periode beginnt und endet und zum verständlich machen noch 5 Ziffern mehr ausgegeben.

Gruß Horst
Bei 175 startet die Periode 2 Stellen nach dem Komma und hat eine Länge von 6
Bei 176 startet die Periode 4 Stellen nach dem Komma und hat eine Länge von 2

markieren

Quelltext

1:
2:
3:
4:

StartWert      175         2         6
0.00_571428_57142
StartWert      176         4         2
0.0056_81_81818

Einloggen, um Attachments anzusehen!

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme