Program dziesiętny rozwijany działa bardzo wolno dla dużych wejść

Question

Piszę program do obliczania dziesiętnego rozszerzenia na numer 103993/33102 i chcę wydrukować wszystkie końcowe znaki dziesiętne w zależności od tego, jaki numer użytkownik wprowadza. Działa szybko dla wszystkich numerów do 10^5, ale jeśli wejście 10^6 do programu zajmuje około 5 minut, aby wydrukować odpowiedź. Jak mogę przyspieszyć? Próbowałem dwa różne podejścia jeden przy użyciu BigDecimal i innych przy użyciu ciągów i żaden z nich nie działa skutecznie.

public static void main(String[] args) throws NumberFormatException, 
     IOException { 
    // BigDecimal num1 = new BigDecimal(103993); 
    // BigDecimal num2 = new BigDecimal(33102); 
    String repNum = "415926530119026040722614947737296840070086399613316"; 
    // pw.println(num.toString()); 
    String sNum = "3.1"; 
    // pw.println(repNum.length()); 
    int cases = Integer.parseInt(br.readLine()); 
    int dec; 
    for (int i = 0; i < cases; i++) { 
     sNum = "3.1"; 
     dec = Integer.parseInt(br.readLine()); 

     if (dec == 0) 
      pw.println("3"); 
     else if (dec <= 52) { 
      sNum += repNum.substring(0, dec - 1); 
      pw.println(sNum); 
     } else { 
      while (dec > 52) { 
       sNum += repNum; 
       dec -= 51; 
      } 
      sNum += repNum.substring(0, dec - 1); 
      pw.println(sNum); 

     } 

     // pw.println(num1.divide(num2, dec, 
     // RoundingMode.FLOOR).toString()); 
    } 
} 

Answer 1

Zamiast tworzyć długi ciąg cyfr, po prostu wydrukuj cyfry. Na przykład:

 while (dec > 52) { 
      System.out.print(repNum); 
      dec -= 51; 
     } 
     pw.println(repNum.substring(0, dec - 1)); 

Tworzenie długiego łańcucha w pętli przez konkatenację jest bardzo szkodliwe dla wydajności, ponieważ łańcuchy są niezmienne. Program spędza cały czas tworząc nowe łańcuchy, jeden dłuższy niż drugi, i kopiuje znaki ze starego do nowego, zasadniczo wdrażając Schlemiel the Painter's algorithm.