[java] Nachkommastellen von Wurzel 2 ...bis 11 Stellen oder so gehts danach nur noch 99999999...also ok bis: 1.41421356237

WurzelStellen.java

/**
 * WurzelStellen.java
 */
import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;


/**
 * 
 *
 * @author Erik
 *
 */
public class WurzelStellen
{
    
    public class BigLinkedNumber
    {
        public LinkedList<Integer> vorrkomma = new LinkedList<Integer>();
        public LinkedList<Integer> nachkomma = new LinkedList<Integer>();
        public LinkedList<Integer> ohnekomma = new LinkedList<Integer>();
        
        public BigLinkedNumber createCopy()
        {
            BigLinkedNumber bln = new BigLinkedNumber();
            bln.vorrkomma.addAll(this.vorrkomma);
            bln.nachkomma.addAll(this.nachkomma);
            bln.ohnekomma.addAll(this.ohnekomma);
            return bln;
        }
        
        @Override
        public String toString()
        {
            StringBuilder sb = new StringBuilder();
            
            sb.append('[');
            
            for (int i : this.vorrkomma)
                sb.append(i);
            sb.append('.');
            for (int i : this.nachkomma)
                sb.append(i);
            
            sb.append('|');
            
            for (int i : this.ohnekomma)
                sb.append(i);
            
            sb.append(']');
            
            return sb.toString();
        }
    }
    
    public void multNAufListe(int n, LinkedList<Integer> liste)
    {
        if ((n >= 0) && (n <= 9)) {
            int u = 0;
            for (int i = liste.size() - 1; i >= 0; i --) {
                if (i == 0) {
                    int wert = liste.get(i);
                    liste.set(i, (wert * n + u) % 10);
                    if (((wert * n + u) / 10) > 0) {
                        liste.addFirst((wert * n + u) / 10);
                    }
                } else {
                    int wert = liste.get(i);
                    liste.set(i, (wert * n + u) % 10);
                    u =  (wert * n) / 10;
                }
            }
        }
    }
    
    public void addListeAufListe(LinkedList<Integer> ergebnis, LinkedList<Integer> wert)
    {
        int u = 0;
        for (int i = wert.size() - 1, j = ergebnis.size() - 1; Math.max(i, j) >= 0; i --, j --)
        {
            // ergebnis länge kleiner als wert
            if (j < 0) {
                ergebnis.addFirst(wert.get(i));
            } else if (i < 0) {
                if (u > 0) {
                    int stelle = ergebnis.get(j);
                    ergebnis.set(j, (stelle + u) % 10);
                    u = (stelle + u) / 10; // übertrag
                } else {
                    break;
                }
            } else {
                int stelle = ergebnis.get(j);
                ergebnis.set(j, (stelle + wert.get(i) + u) % 10);
                u = (stelle + wert.get(i) + u) / 10; // übertrag
            }
        }
    }
    
    public int vergleiche2Nummern(BigLinkedNumber erwartet, BigLinkedNumber aktuell)
    {
        // vorkommastellen vergleichen
        if (erwartet.vorrkomma.size() != aktuell.vorrkomma.size()) {
            if (erwartet.vorrkomma.size() > aktuell.vorrkomma.size()) {
                return -1;
            } else {
                return +1;
            }
        } else {
            for (int i = 0; i < erwartet.vorrkomma.size(); i ++) {
                if (erwartet.vorrkomma.get(i) > aktuell.vorrkomma.get(i)) {
                    return -1;
                } else if (erwartet.vorrkomma.get(i) < aktuell.vorrkomma.get(i)) {
                    return +1;
                }
            }
        }
        
        // nachkommastellen vergleichen
        int i = erwartet.nachkomma.size();
        if (erwartet.nachkomma.size() > aktuell.nachkomma.size()) {
            i = aktuell.nachkomma.size();
        } else if (erwartet.nachkomma.size() < aktuell.nachkomma.size()) {
            i = erwartet.nachkomma.size();
        }
        
        for (int j = 0; j < i; j ++) {
            if (erwartet.nachkomma.get(j) > aktuell.nachkomma.get(j)) {
                return -1;
            } else if (erwartet.nachkomma.get(j) < aktuell.nachkomma.get(j)) {
                return +1;
            }
        }
        // falls eine länger
        if (erwartet.nachkomma.size() > aktuell.nachkomma.size()) {
            return -1;
        } else if (erwartet.nachkomma.size() < aktuell.nachkomma.size()) {
            return +1;
        }
        
        // sonst gleich
        return 0;
    }
    
    public int berProduktUndVergleiche(BigLinkedNumber erwartetesErgebnis, BigLinkedNumber faktor)
    {
        BigLinkedNumber ergebnis = new BigLinkedNumber();
        List<BigLinkedNumber> liste = new ArrayList<BigLinkedNumber>(10);
        
        // alle 10 berechnungen vorberechnen
        for (int i = 0; i < 10; i ++)
        {
            liste.add(new BigLinkedNumber());
            liste.get(i).ohnekomma.addAll(faktor.ohnekomma);
            multNAufListe(i, liste.get(i).ohnekomma); // faktoren vorberechnen
        }
        
        // multiplizieren
        Iterator<Integer> iter = faktor.ohnekomma.iterator();
        while (iter.hasNext())
        {
            ergebnis.ohnekomma.addLast(0);
            addListeAufListe(ergebnis.ohnekomma, liste.get(iter.next()).ohnekomma);
        }
        
        // nachkommastellen berechnen und setzen
        int nachkommastellen = faktor.nachkomma.size() * 2;
        iter = ergebnis.ohnekomma.descendingIterator();
        while (iter.hasNext())
        {
            if (nachkommastellen > 0) {
                ergebnis.nachkomma.addFirst(iter.next());
                nachkommastellen --;
            } else {
                ergebnis.vorrkomma.addFirst(iter.next());
            }
        }
        
        return vergleiche2Nummern(erwartetesErgebnis, ergebnis);
    }
    
    public int algorithmusNachkommaWurzelZahl(BigLinkedNumber zahl, BigLinkedNumber faktor)
    {
        int[] ergebnisse = new int[10];
        BigLinkedNumber[] blns = new BigLinkedNumber[10];
        
        for (int i = 0; i < ergebnisse.length; i ++)
        {
            blns[i] = faktor.createCopy();
            blns[i].nachkomma.addLast(i);
            blns[i].ohnekomma.addLast(i);
            
            ergebnisse[i] = berProduktUndVergleiche(zahl, blns[i]);
            if (ergebnisse[i] > 0) {
                return i-1;
            }
        }
        
        return 9;
    }
    
    public void start()
    {
        BigLinkedNumber zwei = new BigLinkedNumber();
        zwei.vorrkomma.add(2);
        zwei.ohnekomma.add(2);
        System.out.print(2);
        System.out.print(" ==> ");
        
        BigLinkedNumber faktor = new BigLinkedNumber();
        faktor.vorrkomma.add(1);
        faktor.ohnekomma.add(1);
        System.out.print(1);
        System.out.print('.');
        
        int stelle = algorithmusNachkommaWurzelZahl(zwei, faktor);
        System.out.print(stelle);
        
        for (int i = 0; i < 10; i ++)
        {
            faktor.nachkomma.addLast(stelle);
            faktor.ohnekomma.addLast(stelle);
            stelle = algorithmusNachkommaWurzelZahl(zwei, faktor);
            System.out.print(stelle);
        }
        
        for (int i = 0; i < 10; i ++)
        {
            faktor.nachkomma.addLast(stelle);
            faktor.ohnekomma.addLast(stelle);
            stelle = algorithmusNachkommaWurzelZahl(zwei, faktor);
            System.out.print(stelle);
        }
        System.out.println();
    }

    /**
     * @param args
     */
    public static void main(String[] args)
    {
        WurzelStellen ws = new WurzelStellen();
        ws.start();

    }

}