Fakultät in Java

[javagast]

Hi, ich hab ein kleines prob wsa die berechnung von fakultäten angeht ( ich sag gleich dazu dass ich ein anfänger in programmierung bin )

und zwar muss das programm in dieser form laufen ( also ohne math class oder anderes zeug:

import Prog1Tools.IOTools; // Das is für die Tastatureingabe
public class Fak2

{
public static void main(String[] args)

{


int z = IOTools.readInteger("Eingeben: "); // auch das für tasta
int e = 0; // soll ergebnis sein
int d = 0; // für for schleife


for (d= z-1 ; (d > 0 ) ; d-- ) {

System.out.println (d ) ; // hier stehen praktisch die faktoren für die multiplikation

}

System.out.println (e);
}

}


so .. zum problem : wie mach ich es dass der dann auch die faktoren multipliziert .. also z*z-1*z-2 usw. bis 1 ( nicht 0 )

[Silpion]

Am einfachsten geht es vermutlich so:
import Prog1Tools.IOTools;
public class Fak2 {
public static void main(String[] args) {
int z = IOTools.readInteger("Eingeben: ");
int e = 1;

for (int d = z; d > 0; d--) {
System.out.println(d);
e = e * d;
}

System.out.println(e);
}
}

[SGT.Hawk]

Hm, das ist ja ein klassisches Bsp für eine Rekursion, man kann es auch iterativ lösen.

[whatever]

ich hab zwar keine ahnung von java, aber theoretisch sollte das so klappen:

int z = IOTools.readInteger("Eingeben: "); // auch das für tasta
int e = z; // soll ergebnis sein
int d = 0; // für for schleife

for (d= z-1 ; (d > 0 ) ; d-- ) {
e = e * d;
}

System.out.println (e);

[Pinoccio]

1.) Bitte die Code-Tags nutzen, ohne liest sich das sehr unbequem.
2.) Aussagekräftige Variablennamen nehmen
3.) Zählvariablen werden i.A. erst in den for-Schleifen angelegt
4.) Die Bedingung in der for-Schleife ohne Klammern, dafür gibt es ja das Semikolon.
5.) Bei for-Schleifen folgt das De-/Inkrement erst nach dem Durchlauf, siehe zb hier (http://www.galileocomputing.de/openbook/javainsel3/javainsel_020006.htm#Rxxjavainsel_020006443DieforSchleife), insofern geht deine Schleife nicht weit genug.

6.) Fakultät wächst sehr schnell, normales int reicht bis 11! (wenn ich mich nicht vertan habe), insofern ist das Programm außer zu Lehrzwecken sinnlos. ;-)import Prog1Tools.IOTools; // Das is für die Tastatureingabe

public class Fakulatät {
public static void main(String[] args) {

int eingabewert = IOTools.readInteger("Eingeben: "); // auch das für tasta
int ergebnis = 1; // soll ergebnis sein
for ( i = eigabewert ; i > 0 ; i-- ) {
System.out.println (d ) ; // hier stehen praktisch die faktoren für die multiplikation
ergebnis=ergebnis*i;
}
System.out.println(ergebnis);
}
}

hth, mfg Sebastian

/edit: natürlich muß man ergebnis mit eins initialisieren ...

[michl]

Ich hab's vielleicht ein bißchen übertrieben, aber man sieht auch gleich
eine Anwendung des Singleton-Patterns und von Junit-Tests.

Zuerst einmal die Klasse Fakultaet.


import java.util.*;

/**
* Klasse zur Berechnung der Fakultaet.
*
* Zwecks Effizienz werden berechnete Werte für späteren Zugriff
* in einer Hashtabelle gespeichert.

* @author michl
*
*/
public class Fakultaet {

/**
* Singleton-Objekt der Klasse Fakultaet.
*/
private static final Fakultaet fakultaet = new Fakultaet();
/**
* Hashtabelle zur effizienten Speicherung von Fakultaeten.
*/
private static Hashtable<Long, Long> fakHash = new Hashtable<Long, Long>();

/**
* Minimal- und Maximalwerte für den Parameter.
*/
public static final int MIN_PARAM = 0;
public static final int MAX_PARAM = 25;

/**
* Liefert die Singleton-Instanz dieser Klasse.
* @return Singleton-Objekt dieser Klasse
*/
public static Fakultaet getInstance() {
return fakultaet;
}

/**
* Privater Konstruktor.
*
*/
private Fakultaet() {}

/**
* Berechnet die Fakultaet einer nicht-negativen ganzen Zahl.
* @param n
* @return die Fakultaet von n
* @throws IllegalArgumentException wenn der Parameter kleiner als 0 ist.
*/
public long getFakultaetOf(long n) {
if (n < MIN_PARAM || n > MAX_PARAM)
throw new IllegalArgumentException("Argument muss größer oder gleich "+MIN_PARAM+" und kleiner oder gleich "+MAX_PARAM+" sein!");

Long result = fakHash.get(n);
if (result == null) {
result = calcFakultaet(n);
fakHash.put(n, result);
}
return result;
}

/**
* Rekursive Berechnung der Fakultaet.
* @param n
* @return die Fakultaet von n
*/
private long calcFakultaet(long n) {
if (n <= 1)
return 1;
return n*calcFakultaet(n-1);
}
}


Und jetzt die dazugehörige Testklasse.
Damit diese auch compiled, muss JUnit installiert sein.


import junit.awtui.*;
import junit.framework.*;

/**
* Test-Klasse zum Testen von Fakultaet.
*
* @author michl
*
*/

public class TestFakultaet extends TestCase {

private Fakultaet fak;

public TestFakultaet(String name) {
super(name);
}

@Override
protected void setUp() {
fak = Fakultaet.getInstance();
}

public void testFakultaet() {
assertEquals(fak.getFakultaetOf(0), 1);
assertEquals(fak.getFakultaetOf(1), 1);
assertEquals(fak.getFakultaetOf(2), 2);
assertEquals(fak.getFakultaetOf(3), 6);
assertEquals(fak.getFakultaetOf(5), 120);
assertEquals(fak.getFakultaetOf(10), 3628800);
assertEquals(fak.getFakultaetOf(10), 3628800);
assertEquals(fak.getFakultaetOf(20), 2432902008176640000L);
try {
System.out.println(fak.getFakultaetOf(26));
fail("IllegalArgumentException not thrown");
} catch(IllegalArgumentException e) {}
try {
System.out.println(fak.getFakultaetOf(-1));
fail("IllegalArgumentException not thrown");
} catch(IllegalArgumentException e) {}
}

/**
* Main-Methode
* @param args
*/
public static void main(String[] args) {
TestRunner.run(TestFakultaet.class);
}

}


michl

[Pinoccio]

Ich hab's vielleicht ein bißchen übertrieben, aber man sieht auch gleich
eine Anwendung des Singleton-Patterns und von Junit-Tests.Du hats es ganz sicher deutlichst übertrieben ... selbst in long sind 22! das Ende, da bist du am allerschnellsten (Laufzeit), wenn du das mit nem switch machst und die Werte bis meinetwegen 1000* fest einprogrammierst.

mfg Sebastian



* 1000!=40238726007709377354370243392300398571937486421071463254379991042993851239 86290205920442084869694048004799886101971960586316668729948085589013238296699445 90997424504087073759918823627727188732519779505950995276120874975462497043601418 27809464649629105639388743788648733711918104582578364784997701247663288983595573 54325131853239584630755574091142624174743493475534286465766116677973966688202912 07379143853719588249808126867838374559731746136085379534524221586593201928090878 29730843139284440328123155861103697680135730421616874760967587134831202547858932 07671691324484262361314125087802080002616831510273418279777047846358681701643650 24153691398281264810213092761244896359928705114964975419909342221566832572080821 33318611681155361583654698404670897560290095053761647584772842188967964624494516 07653534081989013854424879849599533191017233555566021394503997362807501378376153 07127761926849034352625200015888535147331611702103968175921510907788019393178114 19454525722386554146106289218796022383897147608850627686296714667469756291123408 24392081601537808898939645182632436716167621791689097799119037540312746222899880 05195444414282012187361745992642956581746628302955570299024324153181617210465832 03678690611726015878352075151628422554026517048330422614397428693306169089796848 25901254583271682264580665267699586526822728070757813918581788896522081643483448 25993266043367660176999612831860788386150279465955131156552036093988180612138558 60030143569452722420634463179746059468257310379008402443243846565724501440282188 52524709351906209290231364932734975655139587205596542287497740114133469627154228 45862377387538230483865688976461927383814900140767310446640259899490222221765904 33990188601856652648506179970235619389701786004081188972991831102117122984590164 19210688843871218556461249607987229085192968193723886426148396573822911231250241 86649353143970137428531926649875337218940694281434118520158014123344828015051399 69429015348307764456909907315243327828826986460278986432113908350621709500259738 98635542771967428222487575867657523442202075736305694988250879689281627538488633 96909959826280956121450994871701244516461260379029309120889086942028510640182154 39945715680594187274899809425474217358240106367740459574178516082923013535808184 00969963725242305608559037006242712434169090041536901059339838357779394109700277 53472000000000000000000000000000000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000000000000000000000000000000000 00000000000000

[Gast]

um gottes willen das is ja hochkomplex :) ich glaub ich nehm einfach long und dann hat sich die geschichte ich bin im 1. semester ;)

aber eins blick ich da grad nicht.. wenn ich die zahl 0 eingebe kommt richtig 1 raus ( 0! = 1 ) aber warum wenn doch das d gar nich 0 sein kann??

[michl]

Du hats es ganz sicher deutlichst übertrieben ... selbst in long sind 22! das Ende, da bist du am allerschnellsten (Laufzeit), wenn du das mit nem switch machst und die Werte bis meinetwegen 1000* fest einprogrammierst.

mfg Sebastian

Um Laufzeit geht es hier aber nicht, sondern um die Implementierung mittels Rekursion.

Und wie Du zu die 1000 fest einprogrammierten Werte kommst, musst Du mir auch noch erklären. Vor allem was ist das Ergebnis deiner Switch-Statements? Vielleicht ein String, der die Zahl repräsentiert? Absolut unpraktikabel.

Ausserdem ist deine Methode nicht gerade wartungsfreundlich.
Es sollte kein allzu großes Problem darstellen, den Code auf BigInteger umzuschreiben.

michl

[Pinoccio]

Um Laufzeit geht es hier aber nicht, sondern um die Implementierung mittels Rekursion.Davon steht da nix ;-)
Und meine switch-Vorschlag war sicher unpraktisch (und auch siche nicht ernst gemeint).aber eins blick ich da grad nicht.. wenn ich die zahl 0 eingebe kommt richtig 1 raus ( 0! = 1 ) aber warum wenn doch das d gar nich 0 sein kann??Auf wessen Verison beziehst du dich?

mfg Sebastian

[zeckensack]

Hat's einen speziellen Grund, warum ihr alle die Schleife rückwärts laufen lasst?

Ich würde das eher so ...int ergebnis=1; //jaja, von mir aus auch was größeres
for (int i=2;i<=eingabewert;++i)
{
ergebnis*=i;
}:|

[michl]

Und jetzt noch die Version mit BigInteger.
btw: 1000! stimmt mit dem Ergebnis von Pinoccio überein :smile:


import java.math.*;

/**
* Klasse zur Berechnung der Fakultaet.
* Diese Klasse verwendet BigInteger-Zahlen, damit kann z.B. problemlos
* die Fakultät von 2000 berechnet werden.
*
* @author michl
*
*/
public class FakultaetBigInteger {

/**
* Singleton-Objekt der Klasse Fakultaet.
*/
private static final FakultaetBigInteger fakultaet = new FakultaetBigInteger();

/**
* Minimalwert für den Parameter.
*/
public static final int MIN_PARAM = 0;

/**
* Liefert die Singleton-Instanz dieser Klasse.
* @return Singleton-Objekt dieser Klasse
*/
public static FakultaetBigInteger getInstance() {
return fakultaet;
}

/**
* Privater Konstruktor.
*
*/
private FakultaetBigInteger() {}

/**
* Berechnet die Fakultaet einer nicht-negativen ganzen Zahl.
* @param n
* @return die Fakultaet von n
* @throws IllegalArgumentException wenn der Parameter kleiner als 0 ist.
*/
public BigInteger getFakultaetOf(long n) {
if (n < MIN_PARAM)
throw new IllegalArgumentException("Argument muss größer oder gleich "+MIN_PARAM+" sein!");

BigInteger result = calcFakultaet(BigInteger.valueOf(n));
return result;
}

/**
* Rekursive Berechnung der Fakultaet.
* @param n
* @return die Fakultaet von n
*/
private BigInteger calcFakultaet(BigInteger n) {
if (n.compareTo(BigInteger.ONE) <= 0)
return BigInteger.ONE;
return n.multiply(calcFakultaet(n.add(BigInteger.ONE.negate())));
}
}


michl

[Gast]

aber eins blick ich da grad nicht.. wenn ich die zahl 0 eingebe kommt richtig 1 raus ( 0! = 1 ) aber warum wenn doch das d gar nich 0 sein kann??


Auf wessen Verison beziehst du dich?


ich beziehe mich da auf das von silpion ;)
sry dafür dass ich es nich so schön mache wie ihr mit zitat und code aber ich weiß nicht wie das geht :(

[Pinoccio]

Hat's einen speziellen Grund, warum ihr alle die Schleife rückwärts laufen lasst?Jein. Bei Integer sollte es egal sein, da int*int einen Takt benötigt (oder?) egal, aob da 1 oder 10000000 drin steht.
Nimmt man BigInteger, so sollte man sich, spezielll für große Fakultäten schon was einfallen lassen. Braucht man das Exakte Ergebnis? Wenn nein: Stirling-Formel (http://de.wikipedia.org/wiki/Stirling-Formel).
Kostet Rechenzeit viel und Speicherplatz wenig? Wenn ja, immer zwei Werte multiplizieren und speichern. Wenn nein, wenigstens, wie Zeckensack vorschlägt, von unten Anfangen, denn bei BigInteger dauert die Multiplikation großer Zahlen länger als kleiner.
btw: gab es hier nichtmal nen Thread, wo wer sagte, runterzählen ist schneller wegen irgendeiner Flag?

mfg Sebastian

[Gast]

hi.. zeckensack, (cooler name) aber kannst du mir bitte erklären was

ergebnis*=i; genau bedeutet, bzw. womit ich das ersetzen kann?
klingt so als würdest du damit was zuweisen und zugleich rechnen...gibts da eine für anfänger logischere schreibweise?

[Legolas]

hi.. zeckensack, (cooler name) aber kannst du mir bitte erklären was

ergebnis*=i; genau bedeutet, bzw. womit ich das ersetzen kann?
klingt so als würdest du damit was zuweisen und zugleich rechnen...gibts da eine für anfänger logischere schreibweise?

ergebnis *= i;

ist äquivalent zu

ergebnis = ergebnis * i;

[Senior Sanchez]

btw: gab es hier nichtmal nen Thread, wo wer sagte, runterzählen ist schneller wegen irgendeiner Flag?

mfg Sebastian

Das habe ich auch mal gehört, dass runterzählen schneller ist, als hochzählen, aber in meinen kleinen performancetests dazu konnte ich nie einen unterschied feststellen.

Ich denke eher, dass es z.B. bei Arrays (bla sei jetzt mal nen array) oft an folgendem liegt:

for(int a=0; a < bla.length; a++) {}

bzw.

for(int a=bla.length-1; a >= 0; a--) {}

Das Prüfen der >= 0 bedingung geht schneller, als jedesmal vom array die länge zu erfragen, da der test auf das literal so einfach schneller ist da unnötige Zugriffe auf andere Objekte entfallen. Somit könnte man dann davon ausgehen, runterzuzählen sei schneller.

[michl]

btw: gab es hier nichtmal nen Thread, wo wer sagte, runterzählen ist schneller wegen irgendeiner Flag?

mfg Sebastian
Die Idee ist die, dass beim runterzählen immer nur auf 0 geprüft werden muss,
beim Hinaufzählen aber mit einer Zahl != 0 verglichen wird.
Und da für die CPU i.A. ein Test auf 0 schneller ist (es wird eine Subtraktion
gespart), ist die Schleife mit runterzählen effizienter.


aber kannst du mir bitte erklären was

ergebnis*=i; genau bedeutet, bzw. womit ich das ersetzen kann?
klingt so als würdest du damit was zuweisen und zugleich rechnen...gibts da eine für anfänger logischere schreibweise?


das mit zuweisen und zugleich rechnen ist richtig.
a OP = b ist äquivalent zu a = a OP b, wobei OP für eine beliebige
binäre Operation steht. z.B. a*=b <=> a=a*b

mfg
michl

[Gast]

danke für die antworten, noch eine kleine frage die ich zum verständnis habe

public class Fakultaet {
public static void main(String[] args) {
long z = IOTools.readLong("Eingeben: ");
long e = 1;

for (long d = z; d > 0; d--) {

e = e * d;
}

System.out.println(e);
}
}

so stimmt es ja und es wird die richtige fakultät ausgegeben (halt im bereich vom integer), aber was rechnet er intern?

ich würde halt behaupten: (am beispiel der eingegebenen zahl 4):
I. -> e = 1*4 = 4
II -> e = 4 * 3 = 12
III -> e = 12 * 2 = 24
IV -> e = 24 * 1 = 24
V -> e = 24 * 0 -> Ende der schleife da d=0 --> Ausgabe --> 24

hab ich das so richtig verstanden ? :) oder macht er doch was anderes?

btw: gibt es eine möglichkeit dass man ein ergebnis von system.out.print gleichzeitig irgendwo ablegt und wiederholen kann?

[Senior Sanchez]

danke für die antworten, noch eine kleine frage die ich zum verständnis habe

public class Fakultaet {
public static void main(String[] args) {
long z = IOTools.readLong("Eingeben: ");
long e = 1;

for (long d = z; d > 0; d--) {

e = e * d;
}

System.out.println(e);
}
}

so stimmt es ja und es wird die richtige fakultät ausgegeben (halt im bereich vom integer), aber was rechnet er intern?

ich würde halt behaupten: (am beispiel der eingegebenen zahl 4):
I. -> e = 1*4 = 4
II -> e = 4 * 3 = 12
III -> e = 12 * 2 = 24
IV -> e = 24 * 1 = 24
V -> e = 24 * 0 -> Ende der schleife da d=0 --> Ausgabe --> 24

hab ich das so richtig verstanden ? :) oder macht er doch was anderes?

btw: gibt es eine möglichkeit dass man ein ergebnis von system.out.print gleichzeitig irgendwo ablegt und wiederholen kann?

Dein fünfter Schritt stimmt nicht ganz.
Es kommt gar nicht sowei das e = 24 * 0 ausgerechnet wird, sondern vorher, bevor er den neuen Schleifendurchlauf beginnt, prüft er ob die Bedingung noch gilt.
Da aber 0 > 0 ist, stimmt die bedingung nicht mehr und die abarbeitung geht nach der schleife weiter.

Wie meinst du das mit gleichzeitig ablegen und wiederholen?!?

[Gast]

beispiel...

man hat am ende System.out.print ( e ) ;

und dieses e wird durch eine schleife mehrfach ausgegeben.. d.h. in der konsole steht z.B.

6
5
4
3
2
1
0


kann man dann das ganze in einem array zusammenfassen?

aber wahrscheinlich müsste man das schon vorher machen. egal is jetzt nich so wichtig. ich versuch lieber erstmal das andere zu blicken
danke trotzdem ;)

[zeckensack]

Jein. Bei Integer sollte es egal sein, da int*int einen Takt benötigt (oder?) egal, aob da 1 oder 10000000 drin steht.Ist hier schwerstens OT ... aber das ist mir egal :D

Jein. Es kommt darauf an.
Auf manchen Prozessoren braucht Multiplikation ~konstante Zeit. ZB auf dem K8 3 Takte (im 32 Bit-Modus).
Auf anderen nicht. Auf'm ARM7TDMI dauert das irgendwo zwischen 2 und 5 Takten, je nachdem wie groß die Faktoren sind.

[Senior Sanchez]

Ist hier schwerstens OT ... aber das ist mir egal :D

Jein. Es kommt darauf an.
Auf manchen Prozessoren braucht Multiplikation ~konstante Zeit. ZB auf dem K8 3 Takte (im 32 Bit-Modus).
Auf anderen nicht. Auf'm ARM7TDMI dauert das irgendwo zwischen 2 und 5 Takten, je nachdem wie groß die Faktoren sind.

Immernoch OT, aber ich frage einfach mal woran das liegt ;) Weißte das?
Hat nen ARM7TDMI vllt zum Teil zu kleine Register und es muss dann mehr aufgesplittet werden? Obwohl es ja eigentlich quatsch wäre, weil sich Integer doch meist nach der normalen Registergröße richtet, oder?

[Coda]

Immernoch OT, aber ich frage einfach mal woran das liegt Weißte das?
Hat nen ARM7TDMI vllt zum Teil zu kleine Register und es muss dann mehr aufgesplittet werden? Obwohl es ja eigentlich quatsch wäre, weil sich Integer doch meist nach der normalen Registergröße richtet, oder?Hat nichts mit der Registergröße zu tun sondern mit dem Algorithmus der für die Multiplikation verwendet wird. Man muss viele Transistoren benützen um das konstant schnell zu bekommen.

ZB auf dem K8 3 Takte (im 32 Bit-Modus).OT: Und im 64bit Modus? 4 Takte oder sogar nicht konstant?

[Senior Sanchez]

Hat nichts mit der Registergröße zu tun sondern mit dem Algorithmus der für die Multiplikation verwendet wird. Man muss viele Transistoren benützen um das konstant schnell zu bekommen.

OT: Und im 64bit Modus? 4 Takte oder sogar nicht konstant?

Das war ja schon meine Vermutung, dass es daran nicht liegt, aber es war halt einfach mal ins blaue gedacht *g*

[zeckensack]

Immernoch OT, aber ich frage einfach mal woran das liegt ;) Weißte das?
Hat nen ARM7TDMI vllt zum Teil zu kleine Register und es muss dann mehr aufgesplittet werden? Obwohl es ja eigentlich quatsch wäre, weil sich Integer doch meist nach der normalen Registergröße richtet, oder?Nein, das ist schon ein echter 32-Bitter mit 32 Bit-Registern. Aber eben einer der auf niedrigstmögliche Transistorenzahl ausgelegt ist.

Das Teil hat einen 8 Bit-Hardwaremultiplizierer, und stückelt sich größere Produkte damit zusammen. Es gibt "early outs" für Faktoren die <=8 Bit, <=16 Bit oder <=24 Bit sind.

Einige kennen sowas wohl noch aus der Schule ...

123*4
-----------
4
8
12
-----------
+ 492

###

123*45
-----------
492
615
-----------
+ 5535Usw.
Wenn man mindestens einstellige Zahlen korrekt addieren und multiplizieren kann (was mitunter zweistellige Zwischenergebnisse bedeutet), kann man sich daraus beliebig breite Multiplikation zusammenbasteln. Dass das im Dezimalsystem funktioniert, habe ich gerade eben bewiesen :)
Im Binärsystem geht's genauso.

OT: Und im 64bit Modus? 4 Takte oder sogar nicht konstant?Ich könnte jetzt sagen es sind konstant fünf Takte für 64Bit*64Bit=128 Bit.
Aber ich habe gerade nochmal nachgelesen, und es ist doch etwas komplizierter. Außerdem sind's 4 Takte für 32Bit*32Bit=64 Bit ;(

Der K8 hat unterschiedliche Latenzen für die Multiplikation in Abhängigkeit der Breite der Quellregister (oder Speicheroperanden). Dh man kann eine Multiplikation zweier 8 Bit-Register(teile) schneller haben (3T) als mit vollen 32 Bit-Registern (4T). 16 Bit-Multiplikationen kosten ebenfalls 4T aber sind Vector Path und somit böse. Das zu durchleuchten ist mir jetzt aber wirklich zu OT.

Der ARM dagegen schert sich einen Shice drum wie breit die Operanden sind. Wie es einem RISC-Design gebührt kann er sowieso nur volle 32 Bit-Register als Operanden benutzen. Wie schnell die Multiplikation ist hängt hier nicht vom Format sondern vom Inhalt der Operanden ab.

Das ist ein Unterschied. Der K8 wird stur die vollen 4 Takte beschäftigt sein, selbst wenn er gerade 0*1 ausrechnet. Der ARM nicht.

[Coda]

16 Bit-Multiplikationen kosten ebenfalls 4T aber sind Vector Path und somit böse.Iiih. Naja es wird eh fast nur char und int verwendet.

[Senior Sanchez]

Danke für die Aufklärung, zeckensack.
Was sindn Vector Path und warum sind denn die böse?

[Pinoccio]

Um mal wieder ein bißchen aufs eigentliche Thema zu kommen: michl, deine Version steigt (zumindest auf meinem Rechner mit den Standardeisntellungen für den Speicher) bei ungefähr 5360! aus, leider nicht exakt reproduzierbar, wo genau, das variiert. Geht übrigens überraschend schnell, für 5000! benötigt er nur ~0,2 Sekunden.
Iterartiv gehts natürlich viel weiter, die Grenze teste ich gerade aus. Aber vemrutlich limitiert meine Geduld auf das Ergebnis zu warten und nichts programmtechnisches, da BigInteger so groß wie nötig werden können.
Was noch länger dauert als das eigentlich Rechnen: das ganze in Dezimaldarstelung umzurechnen. :-( Aber eigentlich auch kein Wunder ...

btw: 100.000! dauert ungefähr 130 Sekunden bei iterativer, aufsteigender Berechnung und hätte ~ 450.000 Dezimalstellen, wer will PM oder so ^^. Maple ist übrigens um den Faktor 20 schneller. :-(
Iterativ absteigend ist 20 Sekunden langamer.

mfg Sebastian

/edit: 200000 Fakultät iterativ absteigend dauerte 1.002.161 Millisekunden. :-/

[Uni]

beispiel...

man hat am ende System.out.print ( e ) ;

und dieses e wird durch eine schleife mehrfach ausgegeben.. d.h. in der konsole steht z.B.

6
5
4
3
2
1
0

kann man dann das ganze in einem array zusammenfassen?

aber wahrscheinlich müsste man das schon vorher machen. egal is jetzt nich so wichtig. ich versuch lieber erstmal das andere zu blicken
danke trotzdem ;)

schreib ma das printout in die schleife rein. am besten am schluss.

[michl]

Um mal wieder ein bißchen aufs eigentliche Thema zu kommen: michl, deine Version steigt (zumindest auf meinem Rechner mit den Standardeisntellungen für den Speicher) bei ungefähr 5360! aus, leider nicht exakt reproduzierbar, wo genau, das variiert. Geht übrigens überraschend schnell, für 5000! benötigt er nur ~0,2 Sekunden.
Iterartiv gehts natürlich viel weiter, die Grenze teste ich gerade aus. Aber vemrutlich limitiert meine Geduld auf das Ergebnis zu warten und nichts programmtechnisches, da BigInteger so groß wie nötig werden können.
Was noch länger dauert als das eigentlich Rechnen: das ganze in Dezimaldarstelung umzurechnen. :-( Aber eigentlich auch kein Wunder ...

btw: 100.000! dauert ungefähr 130 Sekunden bei iterativer, aufsteigender Berechnung und hätte ~ 450.000 Dezimalstellen, wer will PM oder so ^^. Maple ist übrigens um den Faktor 20 schneller. :-(
Iterativ absteigend ist 20 Sekunden langamer.

mfg Sebastian

/edit: 200000 Fakultät iterativ absteigend dauerte 1.002.161 Millisekunden. :-/

Also das mein Programm bei ca. 5360 aufgibt, hängt mit der rekursiven Struktur des Codes zusammen. Die VM bricht bei mir mit einem StackOverflowError ab.
Probier mal aus, das Ganze mit der Option -Xss100M zu starten, da schaff ich die Fakultät von 50000 zu berechnen.

lg
michl

[Trap]

Also das mein Programm bei ca. 5360 aufgibt, hängt mit der rekursiven Struktur des Codes zusammen. Die VM bricht bei mir mit einem StackOverflowError ab.
Wenn Java Endrekursion beseitigen würde ginge das:
public final static int fac(int n,int accum) {
if(n==0)
return 1*accum;
else return fac(n-1,accum*n);
}
bzw. das ganze mit BigIntegers

Macht aber weder der Java-Compiler noch der JIT Compiler.

[andr_gin]

Also ich habe mir jetzt nicht alle Lösungen durchgelesen, aber das sieht mir irgendwie alles zu kompliziert aus. Ich würde einfach folgendes verwenden:

public static int fak(int fak)
{
if(fak==0)
return 1;

if(fak<0)
return -1;

int ret = 1;
for(int i=1;i<=fak;i++)
ret *= i;

return ret;
}

Diese Funktion rufst du dann einfach von deinem Programm auf mit den richtigen Parametern. Wenn dir ein Integer (ca. 2 Mrd.) zu klein ist, musst du bei ret eben einen long nehmen.

Außerdem muss auch bedacht werden, dass 0! 1 ergibt und das Programm ohne diese Abfrage ins Endlose rechnen würde bzw. bei Java eine Exception wirft, dann ret zu groß wird.
Bei allen Werten < 0, sollte ein Fehlercode gegeben werden (bei mir -1).

[Senior Sanchez]

Wenn Java Endrekursion beseitigen würde ginge das:
public final static int fac(int n,int accum) {
if(n==0)
return 1*accum;
else return fac(n-1,accum*n);
}
bzw. das ganze mit BigIntegers

Macht aber weder der Java-Compiler noch der JIT Compiler.

Hmm, ich dachte der Java Compiler überführt eine primitiv-rekursive Funktion automatisch in eine Iteration? Is ja blöde :(

[Monger]

Wenn Java Endrekursion beseitigen würde ginge das:
public final static int fac(int n,int accum) {
if(n==0)
return 1*accum;
else return fac(n-1,accum*n);
}
bzw. das ganze mit BigIntegers

Macht aber weder der Java-Compiler noch der JIT Compiler.

Nochmal für mich zum mitschreiben: warum geht das nicht?!? Der Stack hat doch immer nur eine endliche Größe, oder?
Und was ist mit "Endrekursion" gemeint?

[Senior Sanchez]

Nochmal für mich zum mitschreiben: warum geht das nicht?!? Der Stack hat doch immer nur eine endliche Größe, oder?
Und was ist mit "Endrekursion" gemeint?

Mit Endrekursion ist eine endständige Rekursion gemeint, sprich der Selbstaufruf erfolgt am Ende. Gibt auch noch ne anfangsständige Rekursion und ne mittelständige Rekursion. Was die bedeuten kann man sich ja denken ;)

Endrekursionen sind meist primitiv-rekursiv aufgebaut und ermöglichen damit Compilern, sofern sie es nutzen, das ganze in eine Iteration umzuwandeln, was performance-Vorteile bringt.

[Neomi]

for(int i=1;i<=fak;i++)
ret *= i;

Außerdem muss auch bedacht werden, dass 0! 1 ergibt und das Programm ohne diese Abfrage ins Endlose rechnen würde bzw. bei Java eine Exception wirft, dann ret zu groß wird.

Bei 0 wäre die Schleifenbedingung direkt für den ersten Durchlauf schonmal nicht erfüllt, die Schleife wird also gar nicht durchlaufen. Die Abfrage auf 0 ist unnötig und deine Begründung für die Abfrage falsch.

[Pinoccio]

Also ich habe mir jetzt nicht alle Lösungen durchgelesen, aber das sieht mir irgendwie alles zu kompliziert aus. Ich würde einfach folgendes verwendenHättets du mal ein bißchen gelesen! ;-) int reicht kaum, selbst long reicht nur bis 22!. Wir reden hier aber über 5000!, was in JAVA ungefähr die Grenze bei rekursiver Berechnung darstellt. Itereativ komme ich wie gesagt auf 200.000!, aber das dauert schon ~12 Minuten und das Ergebnis hat rund eine Million Dezimalstellen (wobei wir hier nicht mit Dezimalzahlen rechnen können, das würde deutlichst länger dauern).
Nichtsdestotrotz ist deine Lösung im Prinzip brauchbar, aber halt nur für sehr sehr kleine Werte. Und steht im Prinzip auch so im 6. Beitrag.

/BTW: momentan denke ich, daß ich heute noch mit einigen Tricks auf 1.000.000! kommen werde und das Ergebniss dann über Nacht in Dezimaldarstellung umwandeln (lassen) werde.

mfg Sebastian

[Uni]

warum nimmt eigentlich keiner ne while-schleife?

[Pinoccio]

warum nimmt eigentlich keiner ne while-schleife?Was soll das großartig bringen? Beid derartig großen Zahlen ist die Berechnung des Produktes vermittels der BigInteger der zeitaufwendigste Vorgang.
Mein Rechner benötigt (siehe oben) für 100.000! 130 Sekunden, obwohl es nur 100.000 Schleifendurchläufe sind.

mfg Sebastian

[Uni]

ka was es bringen soll. ich habs so gelernt. was aber nich heissen soll, dass es die einzige/beste möglichkeit is.
nach etwas längerem überlegen bin ich nu zu dem schluss gekommen, dass es mit der forschleife doch geschickter is.

[Trap]

Basiskonvertierung ist in den meisten BigNum-Implementierungen nicht besonders optimiert. Wohl auch bei Java nicht.

Wie es schneller geht ist beschrieben auf http://www.swox.com/gmp/manual/Binary-to-Radix.html#Binary%20to%20Radix

Forschleife oder endrekursive Funktion macht keinen Unterschied im generierten Code in Sprachen mit gutem optimierendem Compiler. Ist ne Stilfrage. Ich find endrekursive Funktionen für Funktionen die in der Mathematik rekursiv definiert werden hübscher.

[Pinoccio]

Ich find endrekursive Funktionen für Funktionen die in der Mathematik rekursiv definiert werden hübscher.Die Fakultät ist ja nur ner Verallgemeinerung der Gamma-Funktion, welche nicht rekursiv definiert werden muss, auf natürliche Argumente. ;D (scnr)
/edit: @michl (will nicht extra nen neien Beitrag spammen) Ist mir schon klar, deshalb ja die Entschuldigung für diese Bemerkung, aber ich konnte nicht anders. (Hab wohl nen Clown gefrühstückt, meine Freundin hat sich heute auch schon beschwert).
/Edit2: ach ja, jetzt seh ich das auch. Ich meinte in der Tat Spezialfall. Danke Coda.

Wie es schneller geht ist beschrieben auf http://www.swox.com/gmp/manual/Binary-to-Radix.html#Binary%20to%20RadixIst das ein Text über Bahnhöfe? Wenn ja hab ich ihn verstanden ... :frown:
/noch am verstehen versuchen.

mfg Sebastian

[michl]

Die Fakultät ist ja nur ner Verallgemeinerung der Gamma-Funktion, welche nicht rekursiv definiert werden muss, auf natürliche Argumente. ;D (scnr)

mfg Sebastian
Umgekehrt, die Gamma-Funktion erweitert die Fakultät-Funktion, die nur für natürliche Zahlen definiert ist, auf den Bereich der reellen Zahlen, mit Ausnahme der negativen ganzen Zahlen, wo die Gamma-Funktion Pole besitzt.

lg
michl

[Coda]

Ich denke er meinte "Spezialfall" nicht "Verallgemeinerung".

[Pinoccio]

Wie es schneller geht ist beschrieben auf http://www.swox.com/gmp/manual/Binary-to-Radix.html#Binary%20to%20Radix.Versteh den text immernoch nicht ganz, aber egal. Aber GMP ist krank: 100.000! in 183 Millisekunden. :-/
Das ist doch also mal ein Ziel ... ^^

mfg Sebastian

[Coda]

Ich denke das wirst du ihn Java wohl kaum erreichen, auch wenn ich mir damit wieder Feinde machen werde...

[Trap]

Ich denke das wirst du ihn Java wohl kaum erreichen, auch wenn ich mir damit wieder Feinde machen werde...
Doch: Einfach mit JNI die GMP-Lib benutzen ;)

Der Entwickler von GMP schreibt übrigens für jede Architektur von Hand in Assembler den Basisfall der Multiplikation und Addition. Hab am Samstag einen Vortrag von ihm gehört, war etwas trocken aber interessant.

[Pinoccio]

Ich denke das wirst du ihn Java wohl kaum erreichen, auch wenn ich mir damit wieder Feinde machen werde...Naja, gegen teilweise handoptimierte Assembler-routinen werde ich sicher nicht ankommen! Und da GMP explitzit eine Funktion zur Fakultät hat werde ich durch clevere Programmierung wohl auch nichts machen können.
Ein geeigneter (http://www.cs.cmu.edu/~jch/java/benchmarks.html) Kompiler (oder Interpreter?) und ein schneller Rechner sollten es aber möglich machen im Prinzip diese Zeit zu erreichen. Ich selber werde das vermutlich nicht schaffen.

Aber Warum sollte JAVA da soviel langsamer sein? Auch ohne Profiler weiß ich, daß ich über 95% der Zeit in einer Zeile hänge:BigInteger erg=BigInteger.ONE;
BigInteger temp=BigInteger.ONE;
for (long i=1;i<l;i++){
erg=erg.multiply(temp);
temp=temp.add(BigInteger.ONE);
}Und das wird sicherlich durch ein C/C++ oder gar FORTRAN-Bibliothek gemacht.

mfg Sebastian

[Coda]

Ich meinte wenn man GMP in Java implementieren würde ;)

[Pinoccio]

Ich meinte wenn man GMP in Java implementieren würde ;)Naja, das ist klar. GMP schert sich ja beispielsweise nicht um Speicherprobleme. "No memory management is performed; the caller must ensure enough space is available for the results."
Ich bin habe nie was anderes als JAVA gelernt, ich genieße es, mich auf den/die gc (Garbage Collection oder Collector?) verlassen zu können. Das sowas zur Laufzeit Performance kostet ist mir da egal.

mfg Sebastian

[Coda]

Klar, für alles das richtige Werkzeug ;)

Man sollte nur nicht mit Biegen und Brechen versuchen alles mit Java zu erschlagen.