Fakultät berechnen

[Lehmar]

Ich wollte ein Programm schreiben bei dem man eine Zahl eingeben kann
und was dann auf Button druck die Fakultät berechnet bei nietregen
Zahlen funktioniert es ganz gut, doch bei Zahlen über 70 bekomme ich nur ne
Fehlermeldung von wegen „Gleitkommazahl“ kann mir jemand helfen hier ist der
Quellcode.

Delphi-Quellcode:

var
  Form1: TForm1;
  n : integer;
  F : Double;
  k : Integer;
implementation

{$R *.DFM}

procedure TForm1.Beenden1Click(Sender: TObject);
begin
close;
end;

function Fakult1(k : integer): Double;
var
i : Integer;
a : Integer;
begin
result := 1;
a := i;
for a := 2 to k do
result := a*result;
end;

function Fakult2(k : integer): Double;
begin
if k = 0 then
Fakult2 := 1 else Fakult2 := k*Fakult2(k-1);
end;

procedure Fakult3(k: Integer; var f : double);
begin
if k=0 then f:=1 else
begin
Fakult3(k-1,f);
f:=k*f;
end;
end;



procedure TForm1.Button1Click(Sender: TObject);
begin
k := Spinedit1.Value;
Fakult1(k);
Fakult2(k);
Fakult3(k,f);
Edit1.Text := Floattostr(F);
end;

[edit=alcaeus]Delphi-Tags eingefuegt. Spaet, aber doch... Mfg, alcaeus[/edit]

[flomei]

Umklammer deinen Quelltext bitte zunächst mit

Delphi-Quellcode:

 und

Danke!

MfG Florian :hi:

[Lehmar]

Wenn es denn hilft...

Delphi-Quellcode:

var
  Form1: TForm1;
  n : integer;
  F : Double;
  k : Integer;
implementation

{$R *.DFM}

procedure TForm1.Beenden1Click(Sender: TObject);
begin
close;
end;

function Fakult1(k : integer): Double;
var
i : Integer;
a : Integer;
begin
result := 1;
a := i;
for a := 2 to k do
result := a*result;
end;

function Fakult2(k : integer): Double;
begin
if k = 0 then
Fakult2 := 1 else Fakult2 := k*Fakult2(k-1);
end;

procedure Fakult3(k: Integer; var f : double);
begin
if k=0 then f:=1 else
begin
Fakult3(k-1,f);
f:=k*f;
end;
end;



procedure TForm1.Button1Click(Sender: TObject);
begin
k := Spinedit1.Value;
Fakult1(k);
Fakult2(k);
Fakult3(k,f);

[flomei]

Es hätte gereicht wenn du den ersten Beitrag editiert hättest... :roll:

MfG Florian :hi:

[BeerBear]

Die Fakultät von 70 ist eine 101-stellige Zahl.

Dann wird wohl dein Ergebnis einfach zu groß sein.

[hanselmansel]

HiHo,

aus von flomei genanntem Grund habe ich mir die Berechnung deiner Fakultäten nicht auf Richtigkeit hin angesehen, aber beim Dechiffrieren des unformatierten Codes fiel mir auf, dass du

1. nichts mit den ersten beiden Funktionen anstellst, ausser sie aufzurufen, und
2. 70! schon so groß sein dürfte, dass Double das Ergebnis nicht mehr aufnehmen kann.

Mit vielen Grüßen (aus dem Krankenbett :cry: )

hanselmansel

[Lehmar]

Meint ihr echt es wäre zu groß...
Aber irgendwie muss es gehen mit dem Taschenrechner (unter Zubehör) geht es ja auch
und das Ergebnis des Rechenaufwandes ist einfach faszinierend!
Habt ihr mit ihm schon einmal 100000000 Fakultät (n!) gerechnet?

[Dax]

Zitat:

Zitat von Lehmar

100000000 Fakultät (n!) gerechnet?

Ich bin doch nicht bescheuert unsterblich ;)

[hanselmansel]

Okey, Double geht bis irgendwas mit 10^300. 70! ist aber nur etwas größer als 10^100. Sollte also eigentlich passen. An dieser Stelle wäre also die genaue Fehlermeldung von Vorteil.

[BeerBear]

Stimmt, Double kann einen Wert zwischen 5.0x10^-324 und 1.7x10^308 annehmen.
Aber wenns mit kleineren Zahlen funzt, wirds wohl in irgendeiner Weise an der größe der Zahl liegen.

[Michael Leyhe]

Problem bei Integer ist auch, dass der Wert dann irgendwann wieder negativ wird. *deutet auf die Signatur*

[himitsu]

Eventuell liegt es daran, daß bei Double nur etwa die ersten 8 Stellen relevant sind ... die hinteren Stellen sind nicht wirklich vorhanden und können Fehler in der Berechnug hervorrufen :)

Extendet wird da mit seinen 10 (oder waren es 18 :gruebel: - aber egal, an die nötigen 101 Stellen komt es so, oder so nicht ran) relevanten Stellen auch nicht hilfreich sein.
also bleibt da nur noch der Weg über eine BigMath-Lib -.-''

[tigerman33]

Wozu willst du die Fakultät überhaupt als Gleitkommazahl berechnen? Das Ergebnis ist doch sowieso ganzzahlig. :gruebel:

[himitsu]

Weil die vielleicht nicht in einen Interger reinpaßt?
Nichtmal ein Int64 kann 101 Stellen aufnehmen :zwinker:


Wie gesagt Lehmar ... versuch es mal mit 'ner BigMath-Lib, die mit soooo großen Zahlen ohne Rechnenfehler arbeiten kann ;)

[ripper8472]

doubles haben 52 bit signifikante bits, das entspricht 15-16 stellen

ein int64 hat 19-20 stellen

[log(2) / log(10) * bits]

20000! hat 77338 stellen.
50000! hat 213237 stellen und braucht bei mir (mit python) 20,9 sekunden zur berechnung.

schon 21! sprengt die 64bit grenzen. (21! = 51090942171709440000)

[Ultimator]

@ripper:
[log(2) / log(10) * bits] geht auch kürzer: [log(2) * bits], denn lgo(10) ist 1 ;)

[ripper8472]

wer sagt, dass ich den logarithmus zur basis 10 meine? koennte ja auch der natuerliche sein... :tongue:

[tigerman33]

Hmm, da habt ihr natürlich Recht. Dann stellt sich mir allerdings die Frage, wieso ein 64-Bit-Fließkommatyp größere Werte annehmen kann als ein 64-Bit-Ganzzahltyp. Selbst wenn man das Vorzeichenbit abzieht. (Wo speichert die Fließkommazahl eigentlich die Kommaposition?)

[Kidix]

hagen hatte doch da mal eine schöne unit zur berechnung von fakultäten die auch was größer sind.

[Dax]

http://de.wikipedia.org/wiki/Gleitkommazahl sagt alles ;)

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

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