Fakultät1000

J

JavaNoob77

Mitglied
Hallo erstmal,

ich traue mich eigentlich garnicht so richtig, nach so manchen Kommentaren die hier gepostet wurden, mein Problem zu beschreiben.
Ich habe jetzt schon mehrere Stunden und Tage das Forum und Google durchstöbert, aber ich komme mit meiner Problemstellung nicht voran.

Zuerst einmal, ich bin blutiger Anfänger im Bereich JAVA oder besser gesagt im Programmieren allgemein.
Unsere erste Gruppenaufgabe lautet die Fakultät von 1000, ohne auf BigInteger zurückzugreifen, auszurechnen.

Das ganze soll über ein erstelltes Array funktionieren, allerdings hört genau da mein Verständnis auf und das Problem beginnt.

Das was ich bisher geschrieben habe, rechnet die Fakultät bis 20 aus, aber dann werden die Zahlen einfach zu groß und es kommt falsche Werte als Ergebnis heraus.

Java: 
public class Fakultät1000 
{
	
	public static void main(String[] args) {
		
		long i = 1;		// i bezeichnet den Faktor des vorangegangen Wertes ("1"ist Startwert)
		long n = 1;		// n bezeichnet den Faktor mit dem multipliziert wird   ( -""- )
		long z = i*n;		// z steht für Fakultät
		
		long [] Feld1;			// Das "Feld1" soll
		Feld1 = new int[(int) (z+1)];	// eine Stelle mehr als die Variable z haben
		
		while (n<20)
		
		{ n++; i=z; z=i*n;}
		
		System.out.println (z);
	
	}
}

Was muss ich ändern, damit Fakultät 1000 ausrechenbar ist?
Ich hoffe mal, es kann mir jemand helfen?!
 
Landei

Landei

Top Contributor
Du benutzt doch dein Array gar nicht in der Rechnung, dann ist auch der Überlauf kein Wunder. Da die Fakultät zu groß wird, sollst du das Array als BigInteger-Ersatz verwenden. Eine einfache Variante wäre, jede Ziffer in ein einzelnes Feld zu schreiben, so dass aus 4711 das Feld [4,7,1,1] wird (wahrscheinlich ist umgedreht bequemer zu handhaben, also [1,1,7,4]). Dann musst du nur noch eine Funktion schreiben, die dir eine Array-Zahl mit einem normalen int multipliziert (die Faktoren passen ja jeweils in ein int). Wie die schriftliche Multiplikation arbeitet, weißt du ja.

Java: 
...
public static void main(String[] args) {
   int[] array = new int[] {1};
   for(int i = 1; i <= 100; i++) {
       array = multiply(array, i);
   }
   //die "Ziffen" von array ausgeben
}
...

public int[] multiply(int[] array, int factor) {
    //das musst du schon selber machen...
}

Natürlich könnte man auch andere Zahlensysteme in Erwägung ziehen. Sehr verschwenderisch, aber bezüglich der Multiplikation viel einfacher wäre eine binäre Darstellung. Man könnte auch die ints "maximal ausnutzen", und im 2^31-er System rechnen, aber ich glaube, das wäre keine gute Idee.
 
Zuletzt bearbeitet:
H

Hansdampf

Bekanntes Mitglied
du könntest beim Zwischenergebnis die hinteren Nullen abschneiden und in einer anderen Variablen addieren.
934000 zu 934 , Anzahl Nullen+=3.
War nur ein schneller Einfall, nicht sicher, ob es so funktioniert.

weitergedacht: durch Primfaktorzerlegung. Am Ende hättest du ein Ergebnis wie 123123*2^234*3^123*5^888...
 
Zuletzt bearbeitet:
J

JavaNoob77

Mitglied
Da sag ich doch glatt mal Danke @ Landei. :toll:
Ich bin echt begeistert!
Verstehe sogar, wo mein Fehler war und wie es funktioniert.

Wie man schriftlich multipliziert weiß ich, allerdings bin ich mir noch nicht ganz sicher,
wie ich das in JAVA umsetzen soll. Ich will aber erstmal ein bisschen selbst rumgrübeln.
Zur Not kann ich mich ja immer noch melden um mir einen Denkanstoss abzuholen
 
M

Marco13

Top Contributor
Landei hat gesagt.:
Man könnte auch die ints "maximal ausnutzen", und im 2^31-er System rechnen, aber ich glaube, das wäre keine gute Idee.
Zum Vergrößern anklicken....

(abgesehen davon, dass das ganze unabhängig vom Zahlensystem für einen Anfänger nicht gerade trivial ist) : Eigentlich sollte man die zugrundeliegenen Variablen schon so ausnutzen. Man könnte jetzt philosophieren welchen Arraytyp man nimmt, aber es könnte sein, dass char am günstigsten wäre: Man rechnet mit ints, hat keine lästigen Vorzeichen, der Überlauf passt auch in einen int... hm :reflect:
 
A

Andi_CH

Top Contributor
Eigentlich ist das was ich jetzt mache ein RFC :D

MyBigInt kann im Moment nicht mehr als zwei beliebig grosse Integer miteinander multiplizieren.
(Motivation ist ja logischerweise die Fakultät von 1000)

Erst hab ich es mit einem Array implementiert (das war MyBigInt1), das ist aber suboptimal wegen der fixen Länge.

Der Vector ist auch suboptimal, weil der mit v.set(x) nicht automatisch erweitert wird, wenn er zu kurz ist. (die beiden Exceptions brauchen in einem produktiven Einsatz zu viel Rechenzeit!)

Es gibt sicher optimalere Lösungen --- welche?

(die vielen Zwischenvariablen kommen vom debuggen - in meinem Code hat es noch diverse "sysouts" drinnen - soooo komliziert programmiere ich im Normalfall doch nicht :D )

Java: 
import java.util.Vector;

public class MyBigInt2 {
	private Vector<Integer> mValue = null;

	public MyBigInt2(){
		mValue = new Vector<Integer>();
	}

	@SuppressWarnings("unchecked")
	public MyBigInt2(MyBigInt2 pValue) {
		mValue = (Vector<Integer>) pValue.value().clone();
	}

	public MyBigInt2(int[] pValue) {
		mValue = new Vector<Integer>();
		set(pValue);
	}

	public int size() { return mValue.size();}

	public void set(int[] pValue) {
		mValue.clear();
		for (int i=0; i<pValue.length; i++)
			mValue.add(pValue[i]);
	}

	public Vector<Integer> value() {
		return mValue;
	}

	public void mult(MyBigInt2 pBigInt) {
		MyBigInt2 lValue = new MyBigInt2(this);
		MyBigInt2 rValue = pBigInt;
		mValue.clear();
		int uebertrag = 0;
		int tmp = 0;
		int li = 0;
		int ri = 0;
		int wI = 0;
		for (Integer lVal : lValue.value()) {
			for (Integer rVal : rValue.value()) {
				try {
					tmp = mValue.elementAt(li+ri);
				} catch (ArrayIndexOutOfBoundsException e) {
					tmp = 0;
				}
				tmp = lVal * rVal + uebertrag + tmp;
				uebertrag = tmp / 10;
				tmp %= 10;
				wI = li+ri;
				try {
					mValue.set(wI, tmp);
				} catch (ArrayIndexOutOfBoundsException e) {
					mValue.setSize(wI+1);
					mValue.set(wI, tmp);
				}
				ri++;
			}
			ri = 0;
			li++;
		}
		if (uebertrag != 0)
			mValue.add(uebertrag);
	}

	public String toString() {
		String format = "%1d";
		String tmp = "";
		for (int i=mValue.size()-1; i>=0; i--)
			tmp += String.format(format, mValue.elementAt(i)); 
		return tmp;
	}
}

Main:
Java: 
	private static void main(String[] args) {
		int[] a = {1,2,3};
		int[] b = {3,2,1};
		MyBigInt2 mbi1 = new MyBigInt2(a);
		MyBigInt2 mbi2 = new MyBigInt2(b);
		System.out.println("lValue = " + mbi1);
		System.out.println("rValue = " + mbi2);
		mbi2.mult(mbi1);
		System.out.println("Resultat = " + mbi2);
	}

Output:
lValue = 321
rValue = 123
Resultat = 39483
 
Zuletzt bearbeitet:
timbeau

timbeau

Gesperrter Benutzer
Hi Andy,

für mich schon fast zu hoch. Verbesserungen kann ich da nicht anstellen. Hab auch mal was gebastelt und läuft leider nicht sonderlich performant. Allerdings hab ich da auch wenig Vergleichswerte.
100! => 32ms
200! => 258ms
500! => 10s 135ms
1000! lass sich in der Mittagspause mal durchlaufen

edith:

1000! : 2Min 11Sek 569ms

Alles auf nem 3Ghz P-D

Ein ganz klares Minus sind meine Arrayoperationen. Die hast du mit dem Vector sicherlich etwas besser gelöst.


Mein zugegeben nicht so toller Versuch aber er funktioniert :/

Java: 
package javaforum;

import java.text.SimpleDateFormat;
import java.util.ArrayList;
import java.util.Calendar;

public class fakultaet1000 {

	public static void main(String[] args) {
		long time = System.currentTimeMillis();

		int i = 1;
		int n = 1;
		int z = i * n;

		int[] feld = new int[1];
		feld[0] = z;

		while (n < 500) {
			n++;
			i = z;
			feld = multiplyArray(n * i, feld);
		}

		for (int j = 0; j < feld.length; j++) {
			System.out.print(feld[j]);
		}
		System.out.println();

		time = System.currentTimeMillis() - time;
		String sdf = new SimpleDateFormat("HH:mm:ss.SSS").format(time
				- Calendar.getInstance().getTimeZone()
						.getOffset(Calendar.ZONE_OFFSET));

		System.out.println("Dauer: " + sdf);
	}

	private static int[] multiplyArray(int number, int[] startArray) {
		int productOneField;
		int lines = startArray.length + 2;
		int zmp[] = new int[startArray.length * 2];
		int[][] writtenArray = new int[lines][startArray.length * 2];
		int nextDecimalUnit = 0; // decimal number system
		for (int i = startArray.length - 1; i >= 0; i--) {
			int endOfInt = Math.abs((i) - startArray.length);
			productOneField = startArray[i] * number;
			if (productOneField != 0) {
				ArrayList<Integer> list = new ArrayList<Integer>();
				for (int x = ("" + productOneField).length(); x > 0; x--) {
					list.add(0, productOneField % 10);
					productOneField = (productOneField - productOneField % 10) / 10;
				}

				// insert list in array
				for (int j = list.size() - 1; j >= 0; j--) {
					writtenArray[nextDecimalUnit][writtenArray[nextDecimalUnit].length
							- endOfInt] = writtenArray[nextDecimalUnit][writtenArray[nextDecimalUnit].length
							- endOfInt]
							+ list.get(j);
					endOfInt++;
				}
			}
                        nextDecimalUnit++;
		}

		// Output of each Array
//		System.out.println();
//		for (int zeilen = 0; zeilen < writtenArray.length; zeilen++) {
//			for (int spalten = 0; spalten < writtenArray[zeilen].length; spalten++) {
//				System.out.print(writtenArray[zeilen][spalten]);
//			}
//			System.out.println();
//		}

		// Add - overflow
		int f = 0;
		for (int column = writtenArray[lines - 1].length - 1; column >= 0; column--) {
			for (int rows = writtenArray.length - 1; rows >= 0; rows--) {
				f = f + writtenArray[rows][column];
				if (f > 9) {
					writtenArray[writtenArray.length - 1][column - 1]++;
					f = f - 10;
				}
			}
			zmp[column] = f;
			f = 0;
		}
		zmp = reduceNullInts(zmp);
		return zmp;
	}

	private static int[] reduceNullInts(int[] array) {
		int counter = 0;
		for (int i = 0; i < array.length; i++) {
			if (array[i] == 0) {
				counter++;
			} else
				break;
		}
		int[] tmp = new int[array.length - counter];
		System.arraycopy(array, counter, tmp, 0, tmp.length);

		return tmp;
	}

}
 
Zuletzt bearbeitet:
A

Andi_CH

Top Contributor
Hm Fakultät von 1000 dauert etwa 5 Sekunden - aus dem Eclipse gestartet.
Ich weiss nicht was es ausmacht, aber ich habe eine 64 Bit Maschine die ziemlich schnell ist ...

Ich baue noch eine mult - routine die den BigInt mit einem int multipilizieren kann.
Damit kann allerdings nur die Fakultät von MAXINT berechnet werden :D
aber das ist ja wohl eine theoretische Grenze - vorher geht wohl das Memory aus.

Edit:
oops - hab soeben festgestellt, dass meine mult Routine vermutlich einen Fehler hat ...
 
Zuletzt bearbeitet:
timbeau

timbeau

Gesperrter Benutzer
Aber du hast es ausgerechnet?

Was kommt denn raus?

Der Kürze halber bei 500! =

1220136825991110068701238785423046926253574342803192842192413588385845373153881997605

4964475022032818630136164771482035841633787220781772004807852051593292854779075719393

3060377296085908627042917454788242491272634430567017327076946106280231045264421887878

9465754777149863494367781037644274033827365397471386477878495438489595537537990423241

0612713269843277457155463099772027810145610811883737095310163563244329870295638966289

1165897476957208792692887128178007026517450776841071962439039432253642260523494585012

9918571501248706961568141625359056693423813008856249246891564126775654481886506593847

9517753608940057452389403357984763639449053130623237490664450488246650759467358620746

3792518420045936969298102226397195259719094521782333175693458150855233282076282002340

2626907898342451712006207714640979456116127629145951237229913340169552363850942885592

0187274337951730145863575708283557801587354327688886801203998823847021514676054454076

6353598417443048012893831389688163948746965881750450692636533817505547812864000000000

0000000000000000000000000000000000000000000000000000000000000000000000000000000000000

000000000000000000000000000000

klar soweit?

:D
 
J

JavaNoob77

Mitglied
So Leute, wir haben das Problem endlich gelöst.:rtfm:

Dann werde ich mal mit dem entsprechenden Code den Thread hier schließen.

Danke an alle, vor allem Landei, die ihre Hilfe angeboten haben.:applaus:


Java: 
public class Faku_4 {


    public static void main(String[] args)
    {
 
       
       int[] array = new int[1000];           
       array [0]=1;       
                       
       for(int i = 1; i <= 1000; i++)        
                                            
          
       {array = multiply(array, i);}
      
       boolean zahlgesehen=false;      
                                
       for (int index=999; index>=0; index--)

       {
           if (zahlgesehen){
               if (array[index]==0){
                  
                   System.out.print(".000");
               }
               else
                   if (array[index]<10) {
                       System.out.print(".00"+array[index]);
                   }
               else
                   if (array[index]<100) {
                       System.out.print (".0"+array[index]);
                   }
               else
                   {System.out.print ("."+array[index]);}
           
                  
           }
          
           else {
               if (array[index]!=0){
                   System.out.print (array[index]); zahlgesehen=true;
               }
              
           }
       }
      
    }

    private static int[] multiply(int []array, int i) {
           
        int uebertrag = 0;
           
            for(int index = 0; index<1000; index++){
            int ergebnis = array[index]*i + uebertrag;
            array[index] = ergebnis % 1000;
            uebertrag = ergebnis /1000;


   
}
            return array;
}
   
}
 
Zuletzt bearbeitet:
J

JavaNoob77

Mitglied
Den Code haben wir bis auf die Ausgabe soweit allein hinbekommen, unser Dozent hat uns lediglich den Tip mit %1000 gegeben und uns nen Flussdiagramm machen lassen.
Macht sich optisch aber auch recht gut
Und bei der Ausgabe hat uns jemand von den "Fortgeschrittenen" ein wenig unter die Arme gegriffen:oops:
 
nrg

nrg

Top Contributor
sieht doch schon ganz gut aus.

würde allerdings an der Formatierung noch etwas machen.

for....
{......}

find ich jetzt nicht so schön.

Für die Ausgabe könntest du dir vllt DecimalFormat anschauen.

Java: 
import java.text.DecimalFormat;
// ....
		DecimalFormat df = new DecimalFormat("000");
		for (int i = 0; i < array.length; i++)
			System.out.print(i == 0 ? array[i] : df.format(array[i]));
 
timbeau

timbeau

Gesperrter Benutzer
Man muss das Array z.B. nicht mit 0 füllen, die hat ein int Array von alleine. Aber der Clou ist ja der Übertrag ab >1000 auf den nächsten Index und die Ausgabe von hinten anfangen. Find ich echt gut, gerade für einen Beginner.
 
nrg

nrg

Top Contributor
@Andi_CH

imho sollte "try ... catch (ArrayIndexOutOfBoundsException e)" in keinem Code stehen. Dafür gibt es doch if. Fliegt dennoch eine AIOOBE ist es schlicht und einfach ein Programmierfehler

edit: und noch was: toString() für mein Empfinden mit StringBuilder. Optimiert zwar afaik der compiler aber ich finde es schöner.
 
Zuletzt bearbeitet:
ARadauer

ARadauer

Top Contributor
gut gemacht JavaNoob...

man könnte es statt des arrays auch mit der ArrayListe lösen... das würd ungefähr so aussehen...

Java: 
public class Fakultät {
     

   public static void main(String[] args) {     
      int basis = 1000; // sollte 10^irgendwas sein
      int n = 1; 
      ArrayList<Integer> ergebnis = new ArrayList<Integer>();
      ergebnis.add(1);
      while (n<10000){
         n++;
         bigMulti(ergebnis, n, basis);
      }         
      printArrayList(ergebnis, basis);
   }   


   
   public static void bigMulti(ArrayList<Integer> ziffern, int multi, int basis){
      int uebertrag = 0;
      for(int i = 0; i < ziffern.size(); i++){
         int ergebnis = ziffern.get(i)*multi+uebertrag;         
         int rest = ergebnis %basis;
         uebertrag = ergebnis /basis;
         ziffern.set(i, rest);  
      }
      //den übertrag noch einfügen
      while(uebertrag>0){
         int rest = uebertrag %basis;
         uebertrag = uebertrag /basis;
         ziffern.add(rest);
      }      
   }
   
   
   public static void printArrayList(ArrayList<Integer> ziffern, int basis){
      String basisStr = Integer.toString(basis);
      //ich weiß, nicht ganz sauber
      DecimalFormat df = new DecimalFormat(basisStr.substring(1, basisStr.length()));  
      for(int i = ziffern.size()-1; i>=0; i--){
         System.out.print(df.format(ziffern.get(i)));   
         if((i%100) ==0)
            System.out.println();
      } 
      System.out.println();
   }
 

Aktuelle Jobs

Neue Themen


Oben