Fakultät berechnen

[ripper8472]

als beispiel mal 51090942171709440000

5.10909E19

ich habe nur 6 stellen genauigkeit, kann aber eine 20stellige zahl darstellen (wenn auch ungenau).

aus dem grund ist z.b. 1e300 + 1 = 1e300. die stellen an genauigkeit reichen nicht aus fuer unterscheidungen um 1 bei so grossen zahlen.

reicht das soweit? wikipedia kann dir unter fliesskommazahlen mehr erzaehlen.

[negaH]

Anbei mein Program zur exakten Berechnung der Fakultät. Einfach enpacken, im Menu auf \Factorial\Schönhage\ klicken, 50000 eingeben, return drücken, 89ms warten und Y drücken um die komplette Zahl zu sehen.

Wenn ihr im Menu \Factorial\Display shortest Primepower Path\ anklickt und dann 100 eingebt so seht ihr die Formel mit der man 100! am schnellsten berechnen kann.

Code:

Input N! ? 100

(((((3)^2 * 
3*5*7)^2 * 
5*11)^2 * 
13*17*19*23)^2 * 
13*29*31*37*41*43*47)^2 * 
11*13*17*19*29*31*53*59*61*67*71*73*79*83*89*97 * 2^97

Gruß Hagen

[salamahachy]

Hi, also ich soll bestimmen wie viele Endnullen 100Fakultät hat. Dafür müsste ich also 100! erstmal exakt bestimmen. Bekannticher weiße arbeitet der Computer vor meiner Nase nur auf 32 Stellen exakt, und mit integer kann ich es ja eh nicht anzeigen lassen. also hab ich mir mal gedacht, mach ich für jede ziffer/Stelle nen eigenes Feld, sodass jede integer variable nicht über 9 hinausgeht. Und am Ende soll das dann in nem Editfeld ausgegeben werden. Dazu hab ich mir diesen Quellcode ausgedacht:

Delphi-Quellcode:

procedure TForm1.Button1Click(Sender: TObject);
var Zahl:array[1..2, 1..170] of integer;
    a, b, d      : string;
    i, c, Stelle : integer;
begin
for i:= 1 to 170 do begin
    Zahl[1,i]:=0;
    Zahl[2,i]:=0;
end;
Zahl[1,1]:=1;
for i:= 1 to 11 do begin
    for Stelle:=1 to 170 do begin
        a:=inttostr(i * Zahl[1,Stelle]);
        b:=copy(a,length(a),length(a));
        c:=strtoint(b) + Zahl[2,Stelle];
        if c > 10 then begin
           d:=inttostr(c);
           d:=copy(d,length(d),length(d));
           c:=strtoint(d);
           Zahl[2,(Stelle+1)]:=Zahl[2,(Stelle+1)] + 1;
        end;
        Zahl[2,Stelle]:=c;
        b:=copy(a,(length(a)-1),(length(a)-1));
        if b = '' then b:= '0';
        c:=strtoint(b) + Zahl[2,(Stelle+1)];
        if c > 10 then begin
           d:=inttostr(c);
           d:=copy(d,length(d),length(d));
           c:=strtoint(d);
           Zahl[2,(Stelle+2)]:=Zahl[2,(Stelle+2)] + 1;
        end;
        Zahl[2,(Stelle+1)]:=c;
        b:=copy(a,(length(a)-2),(length(a)-2));
        if b = '' then b:= '0';
        c:=strtoint(b) + Zahl[2,(Stelle+2)];
        if c > 10 then begin
           d:=inttostr(c);
           d:=copy(d,length(d),length(d));
           c:=strtoint(d);
           Zahl[2,(Stelle+3)]:=Zahl[2,(Stelle+3)] + 1;
        end;
        Zahl[2,(Stelle+2)]:=c;
        if i=11 then Edit1.Text:=inttostr(Zahl[2,Stelle]) + Edit1.Text;
    end;
    for Stelle:=1 to 170 do begin
        Zahl[1,Stelle]:=Zahl[2,Stelle];
        Zahl[2,Stelle]:=0;
    end;
end;

end;

Das ganze klappt auch bis zur berechnung von 10! Tadellos aber ab 11! bekomm ich den fehler: Project Project1.exe raised exception class EAccessViolation with message 'Access violation at address 0040421E in module 'Project1.exe'. Write address 0044F3A9'. Process stopped. Use Step or Run to continue.
Dann kommt das gleiche nochmal nur die erste adresse ist 00404242 und die zweite FFFFFFFF.

Kann mir vielleicht einer helfen und mir sagen, wo ich den Fehler bzw. Denkfehler gemacht habe??
Ich hab mir das ergebnis jetzt mit dem ein post vor mir angegebenen prog angesehen, und so die aufgabe der Endnullen gelöst, wüsste trotzdem gerne mal meinen Fehler.

[Amateurprofi]

Zitat von Lehmar:

bei Zahlen über 70 bekomme ich nur ne
Fehlermeldung von wegen „Gleitkommazahl“

Ich habs mal getestet. Bei bringen alle 3 Versionen richtige Resultate ( z.B. bei k=100 ist das Ergebnis 9.3E157 ) .

Wo genau kommt denn die Fehlermeldung ?

[negaH]

@salamahachy:

die Anzahl der Nullen kannst du komplett ohne Beechnung der Fakultät ausrechnen.
Schau dir mal obige Expansion von 100! ganz genau an. Wichtig dabei sind alle Primzahlexponenten zur Basis 2 und Basis 5 denn nur diese können mit 2*5 = 0 im Resulat sein.

Vereinfacht für die Basis 10 also so:

Delphi-Quellcode:

function FactorialTrailingZerosBase10(N: Int64): Int64;
begin
  Result := 0;
  while N >= 5 do
  begin
    N := N div 5;
    Inc(Result, N);
  end;
end;

und komplizierter, dafür aber universeller, für alle Basen zwischen 2 bis 48 dann so:

Delphi-Quellcode:

function FactorialTrailingZeros(const N: Int64; Base: Cardinal): Int64;
// compute count of trailing zeros to base of factorial N!
const
  Primes: array[0..2] of Cardinal = (2,3,5);
  HighestPrime = 7;
  HighestBase = HighestPrime * HighestPrime -1;

  function PrimePower(N: Int64; Prime: Cardinal): Int64;
  begin
    Result := 0;
    while N >= Prime do
    begin
      N := N div Prime;
      Inc(Result, N);
    end;
  end;

var
  I,Multiple: Cardinal;
  Power: Int64;
begin
  if (Base < 2) or (Base > HighestBase) then
    raise Exception.CreateFmt('FactorialTrailingZeros(), Base must be between 2 upto %d', [HighestBase]);
  if (N < 0) then
    raise Exception.Create('FactorialTrailingZeros(), N must be >= 0');

  Result := $FFFFFFFF;
  for I := Low(Primes) to High(Primes) do
  begin
    Multiple := 0;
    while Base mod Primes[I] = 0 do
    begin
      Base := Base div Primes[I];
      Inc(Multiple);
    end;
    if Multiple > 0 then
    begin
      Power := PrimePower(N, Primes[I]) div Multiple;
      if Result > Power then Result := Power;
    end;
    if Base = 1 then Exit;
  end;
  Power := PrimePower(N, Base);
  if Result > Power then Result := Power;
end;

Beispiel:

100! == 2^97*3^48*5^24*7^16*11^9*13^7*17^5*19^5*23^4*29^3* 31^3
*37^2*41^2*43^2*47^2*53^1*59^1*61^1*67^1*71^1*73^1 *79^1*83^1*89^1*97^1

Wir möchten nun wissen wieviele Nullen zur Basis 10 am Ende stehen würden. Die Basis 10 zerlegt sich in 2*5. Also müssen wir obige Exponenten zu den Basen 2 und 5 berechnen. Also 2^97 und 5^24. Nur 2*5 kann eine 0 ergeben, logisch da 2*5 = 10 ergo zur Basis 10 == 0. Das bedeutet wir suchen den kleinsten gemeinsammen Exponnenten von 2^97 und 5^24 und das ist 24 da sie einmal in 24 und 4 mal in 97 reinpasst. Ergo 100! hat exakt 24 Nullen am Ende wenn wir das als Dezimalzahl darstellen wollen.

Angenommmen wir möchten nun wissen wieviele Nullen 100! zu Basis 9 hat. 9 == 3 * 3 == 3^2. Hier haben wir die Basis 3 zum Exponenten 2. Wir berechnen wieder den Primzahlexponeten von 3 in 100! wie oben gezeigt 3^48. Da wir aber die Basis 3 eben 2 mal haben -> 3^2 müssen wir den Exponenten 48 aus 3^48 durch 2 teilen. Ergibt 24, also 24 Nullen enthält 100! am Ende wenn wir 100! im 9'er Zahlensystem darstellen.
Im Zahlensystem 27 -> 3^3 müssenwir also 48 aus 3^48 durch 3 teilen ergibt dann 16 Nullen in 100! im Zahlensystem 27.

Obige Funktion FactorialTrailingZeros() zerlegt nun die Basis "Base" in ihre Primzahlexponentation, zb. 36==2^2*3^2 und berechnet dann jeweils zur Basis 2 und 3 den Exponenten aus der Fakultät von N.

Wir müssen also garnicht N! komplett ausrechnen um die Anzahl der endenden Nullen zu berechnen.

Gruß hagen

[edit]
falls du mein DECMath verwendest nutzt du nachfolgende Funktion. Sie kann mit Basen bis 2^32-1 rechnen.

Delphi-Quellcode:

function NFactorialTrailingZeros(const N: Int64; Base: Cardinal): Int64;
// compute count of trailing zeros to base of factorial N!

  function PrimePower(N: Int64; Prime: Cardinal): Int64;
  begin
    Result := 0;
    while N >= Prime do
    begin
      N := N div Prime;
      Inc(Result, N);
    end;
  end;

var
  I,Multiple,Prime,BaseRoot: Cardinal;
  Power: Int64;
begin
  if Base < 2 then
    raise Exception.Create('NFactorialTrailingZeros(), Base must be >= 2');
  if (N < 0) then
    raise Exception.Create('NFactorialTrailingZeros(), N must be >= 0');

  InitSmallPrimes;
  Result := $FFFFFFFF;
  BaseRoot := Trunc(Sqrt(Base));
  I := 0;
  repeat
    Prime := SmallPrimes[I];
    if Prime > BaseRoot then Break;
    Inc(I);
    Multiple := 0;
    while Base mod Prime = 0 do
    begin
      Base := Base div Prime;
      Inc(Multiple);
    end;
    if Multiple > 0 then
    begin
      Power := PrimePower(N, Prime) div Multiple;
      if Result > Power then Result := Power;
    end;
  until Base = 1;
  if Base > 1 then
  begin
    Power := PrimePower(N, Base);
    if Result > Power then Result := Power;
  end;
end;

[/edit]

[edit=Sharky]Zur Vermeidung eines Scrollbalken habe ich in die Zeile mit der Berechnung von 100! einen Zeilenumbruch eingefügt. Mfg, Sharky[/edit]

[negaH]

Erklären wir das mal alles an einem Beispiel.

Code:

10! = 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10

die 1 können wir entfernen sie ist die Einheit und damit irrelevant

Code:

10! = 2   *   3 *   4 *  5  *     6     *  7  *   8 *  9  *    10

Obige Zahlen setzen sich zusammen aus Primzahlen und Zusammengesetze Zahlen, wir abstrahieren mal noch weiter

Code:

10! = 2^1 * 3^1 * 2^2 * 5^1 * 2^1 * 3^1 * 7^1 * 2^3 * 3^2 * 2^1 * 5^1

Nun noch weiter abstrahieren

Code:

10! = (2^1 * 2^2 * 2^1 * 2^3 * 2^1) * (3^1 * 3^1 * 3^2) * (5^1 * 5^1) * (7^1)

und nochmal weiter

Code:

10! = 2^8 * 3^4 * 5^2 * 7^1

wir erkennen erstmal folgendes: Die Exponenten fallen immer weiter je größer die Basis wird, d.h. der Exponent zu basis 2 wird immer größer sein als die Exponenten der nachfolgenden Basen.

Aus diesem Grunde können wir wenn wir die Anzahl der Nullen im Dezimalsystem suchen -> 10 = 2*5 also sofort die Basis 2 vernächlässigen.

Ergo: nehmen wir den Exponenten zur Basis 5 und das ist die Anzahl der gesuchten Nullen im Dezimalsystem. In unserem Beispiel von 10! also 2 Nullen.

Genauer gesagt 10! hat zur Basis:
2 = 8 Nullen
3 = 4 Nullen
5 = 2 Nullen
7 = 1 Null.

Zur den Basen:

4 = 2*2 = 8/2 = 4 Nullen
6 = 2*3 = 4<8 = 4 Nullen
8 = 2*2*2 = 8/3 = 3 Nullen
9 = 3*3 = 4/2 = 2 Nullen
10 = 2*5 = 2<8 = 2 Nullen
11 = 0 Nullen
12 = 2*2*3 = 8/2=4 <= 4 = 4 Nullen
13 = 0 Nullen
14 = 2*7 = 1<8 = 1 Null
15 = 3*5 = 2<4 = 2 Nullen
16 = 2*2*2*2 = 8/4 = 2 Nullen

Um nun den Exponenten zur einer Basis zu finden geht man folgendermaßen vor. Man dividiert einfach das N aus N! mit der gesuchten Basis und addiert das auf einen Zähler.

Also beipsiel 100!

1.) 100 / 5 = 20, +20 = 20
2.) 20 / 5 = 4, + 4 = 24
3.) 4 / 5 = 0, Schleife abbrechen

Resultat = 24, ergo in 100! kommt der Term 5^24 vor.

1.) 100 / 7 = 14, +14 = 14
2.) 14 / 7 = 2, + 2 = 16
3.) 2 / 7 = 0, Schleife abbrechen

Resulat 16, ergo in 100! kommt der Term 7^16 vor.


Gruß Hagen