# keine sqrt methode für bigintegers?



## rammellaus (15. Apr 2005)

gibt es keine funktion oder möglichkeit die wurzel einer bigInteger zu ziehen?


----------



## Illuvatar (15. Apr 2005)

Hm... sieht komischerweise net so aus, ich hab auch nix gefunden ???:L


----------



## rammellaus (15. Apr 2005)

und pow geht auch net, da er n int will und 0.5 nun mal nicht int is :S
das deprimiert mich -.- 
als ich vorhin zum ersten mal von den BigIntegers gelesen habe dachte ich ich könnte endlich nen algorithmus von int auf BigInteger erweitern, aber ohne quadratische wurzel ziehen zu können bringts nichts ;(

überhaupt finde ich es voll umständlich das man nicht einfach
a+b machen kann sondern a.add(b) machen muss .....


----------



## Wildcard (15. Apr 2005)

Wurzelziehen musst du selbst...
Stell doch erstmal auf long um, vieleicht reicht das ja  :wink: 


> überhaupt finde ich es voll umständlich das man nicht einfach
> a+b machen kann sondern a.add(b) machen muss .....


Ich bin verdammt froh das es keine operatorenüberladung gibt!
(Ausser diesem sch**** string + string  :roll: )


----------



## rammellaus (15. Apr 2005)

ne long reicht mir nicht ^^
was meinst du mit "wurzel ziehen musst du selber"?


----------



## Wildcard (15. Apr 2005)

Such dir einen hübschen Algorithmus aus und implementier ihn...


----------



## 0xdeadbeef (16. Apr 2005)

Hatte mir mal einen kleinen Algorithmus implementiert. Habe ihn jetzt nicht noch mal getestet, aber eigentlich sollte er tun.


```
final private static BigInteger BigIntegerTWO     = BigInteger.valueOf(2);

    /**
     * Calculates BigInteger square root of BigInteger n
     * @param n BigInteger to calcuate squate root for
     * @return BigInteger square root of BigInteger n
     */
    private static BigInteger sqrt(BigInteger n) {
        BigInteger result = n.divide(BigIntegerTWO).add(BigInteger.ONE);
        BigInteger help = result.add(BigInteger.ONE);
        //while (result*result > x || (result+1)*(result+1)< x)
        while (result.multiply(result).compareTo(n) > 0 || help.multiply(help).compareTo(n) < 0) {
            result = result.add(n.divide(result)).divide(BigIntegerTWO);
            help = result.add(BigInteger.ONE);
        }
        return result;
    }
```


----------



## rammellaus (16. Apr 2005)

hatte gerade auch was geschrieben, allerdings etwas vereinfacht da ich für meine situation schon weiß, dass ich keine komma zahlen erhalte.........

aber warum bitte geht das hier nicht?  ???:L 


```
BigInteger b = new BigInteger("1");
for (int x = 1, x < 100, x++)
{
  b.add(BigInteger.ONE);
  System.out.println(b);
}
```

ich krich da hundert mal ne 1 ausgegeben  :bahnhof:


----------



## Beni (16. Apr 2005)

Schreib "b = b.add( BitInteger.ONE )". Die BigInteger selbst verändern sich nicht, bei solchen Operationen, aber sie kreieren neue BigInteger.


----------



## rammellaus (16. Apr 2005)

k, hier mal meine ganze absicht  :### :


```
import java.io.*;
import java.math.BigInteger;
public class primzerlegung
  {
    public static void main(String args[]) throws IOException
      {
        BigInteger produkt = new BigInteger((new BufferedReader(new InputStreamReader(System.in))).readLine());
        BigInteger counter = new BigInteger("2");
        BigInteger zwei = new BigInteger("2");
        while (produkt.mod((((counter.negate()).divide(zwei)).add(wurzel(((counter.divide(zwei)).pow(2)).add(produkt))))) != BigInteger.ZERO)
          {
            counter.add(zwei);
            System.out.println(zwei);
          }
        System.out.println(produkt.mod((((counter.negate()).divide(zwei)).add(wurzel(((counter.divide(zwei)).pow(2)).add(produkt))))));
      }
    
    public static BigInteger wurzel(BigInteger x)
      {
        BigInteger y = new BigInteger("1");
        System.out.println("In Wurzel drin: "+x);
        while (y.multiply(y) != x && y.max(x) == x)
          {
            y = y.add(BigInteger.ONE);
            //System.out.println(y);
          }
        if (y.max(x) == x)
            return y;
        else 
          return BigInteger.ZERO;
      }
  }
```


allerdings bekomme ich folgenden fehler:
arithmeticException in line 10: modulos not positive

mh wie kann denn ein modulos nicht positive sein? oO


----------



## 0xdeadbeef (16. Apr 2005)

Der obige Algorithmus liefert natürlich auch nur ganzzahlige Ergebnisse, allerdings dürfte er deutlich schneller konvergieren als die Brute-Force-Methode.


----------



## abollm (16. Apr 2005)

0xdeadbeef hat gesagt.:
			
		

> Der obige Algorithmus liefert natürlich auch nur ganzzahlige Ergebnisse, allerdings dürfte er deutlich schneller konvergieren als die Brute-Force-Methode.



Wenn man nicht richtig schaut, dann wundert man sich halt, wenn bei deinem Algorithmus z.B. hundert man eins herauskommt.

Kann passieren.

Hier einmal ein BigDecimal-Algorithmus für den OP:

```
...
  /**
   * Calculates BigDecimal square root of BigDecimal x
   * and with nd digits
   * @param x BigDecimal to calcuate squate root for
   * @param nd int number of digits for x
   * @return BigDecimal square root of BigDecimal x
   */
  private static BigDecimal sqrt(BigDecimal x, int nd)
  {
    
    BigDecimal zero = ZERO.setScale(nd + 10);
    BigDecimal one  = ONE.setScale(nd + 10);
    BigDecimal two  = TWO.setScale(nd + 10);
    BigDecimal ten = TEN.setScale(nd + 10);
    BigDecimal maxerr = one.movePointLeft(nd);
    
    BigDecimal lower = zero;
    BigDecimal upper = x.compareTo(one) <= 0 ? one : x;
    BigDecimal mid;
    while (true) {
      mid = lower.add(upper).divide(two, BigDecimal.ROUND_HALF_UP);
      BigDecimal sqr = mid.multiply(mid);
      BigDecimal error = x.subtract(sqr).abs();
      if (error.compareTo(maxerr) <= 0) {
        break;
      }
      if (sqr.compareTo(x) < 0) {
        lower = mid;
      } else {
        upper = mid;
      }
    }
    return mid;
  }
```
Diesen Schnipsel habe ich aus einem kompletten Programm herauskopiert, deshalb müssen im aufrufenden Programm selbstverständlich die angegebenen Konstanten noch gesetzt werden.

Bedienung dürfte somit klar sein, oder?


----------



## 0xdeadbeef (16. Apr 2005)

Eigentlich wollte er doch 'ne (Big-)Integer-Wurzel ziehen, oder? In diesem Fall ist die BigDecimal-Version vor allem eines: dramatisch (!) langsamer.
Unfd warum sollte bei _meinem_ Algo 100mal eine 1 rauskommen? Merke: zitieren will auch gelernt sein :roll: 

Aber naja, von mir aus: macht was ihr wollt.


----------



## abollm (16. Apr 2005)

0xdeadbeef hat gesagt.:
			
		

> Eigentlich wollte er doch 'ne (Big-)Integer-Wurzel ziehen, oder? In diesem Fall ist die BigDecimal-Version vor allem eines: dramatisch (!) langsamer.
> Unfd warum sollte bei _meinem_ Algo 100mal eine 1 rauskommen? Merke: zitieren will auch gelernt sein :roll:
> 
> Aber naja, von mir aus: macht was ihr wollt.



Stimmt, lesen und zitieren müsste man können (mea maxima culpa -> Asche auf mein Haupt!). Aber _so_ viel langsamer ist der BigDecimal-Algorithmus auch nicht.


----------



## rammellaus (16. Apr 2005)

mh naja das klappt ja alles soweit wies oben steht, aber der vergleich mit dem operator == funktioniert irgendwie nicht korrekt..... also selbst wenn da steht  
while (y.multiply(y) != x)
while (36!=36)

springt er net aus der while raus 
 ???:L


----------

