Subversion Repositories distributed

Rev

Rev 13 | Blame | Compare with Previous | Last modification | View Log | RSS feed

  1. package de.viathinksoft.immortal.gen2.math;
  2.  
  3. import java.math.BigInteger;
  4.  
  5. public class MathUtils2 {
  6.        
  7.         public static BigInteger length(BigInteger x) throws Exception {
  8.                 // TODO: größer als MAX_INTEGER erlauben!
  9.                 BigInteger z = new BigInteger(""+x.toString().length());
  10.                
  11.                 if (z.signum() == -1) {
  12.                         throw new Exception("Integer overflow! (BigInteger-Length)");
  13.                 }
  14.                
  15.                 return z;
  16.         }
  17.        
  18.         public static BigInteger pow(BigInteger base, BigInteger exponent) {
  19.                 if (exponent.signum() == -1) {
  20.                         throw new ArithmeticException("Negative exponent");
  21.                 }
  22.  
  23.                 BigInteger i = new BigInteger("0");
  24.                 BigInteger res = new BigInteger("1");
  25.                
  26.                 while (i.compareTo(exponent) != 0) {
  27.                         i = i.add(BigInteger.ONE);
  28.                         res = res.multiply(base);
  29.                 }
  30.                
  31.                 return res;
  32.         }
  33.  
  34.         /**
  35.          * Division with remainder method - based on the original Java<br>
  36.          * 'divideAndRemainder' method<br>
  37.          * returns an object of results (of type BigInteger):<br>
  38.          * -> the division result (q=a/b)<br>
  39.          * result[1] -> the remainder (r=a-q*b)<br>
  40.          * If b==0 then result will be 0. No ArithmeticException!
  41.          *
  42.          * @param a
  43.          * @param b
  44.          * @return
  45.          * @see http://tupac.euv-frankfurt-o.de/www/kryptos/demos/Demos.java
  46.          **/
  47.         public static DivisionAndRemainderResult divRem(BigInteger a, BigInteger b) {
  48.                 // if (b==0) {
  49.                 // -> divideAndRemainder() throws ArithmeticException when b==0
  50.                 if (b.signum() == 0) {
  51.                         return new DivisionAndRemainderResult(BigInteger.ZERO,
  52.                                         BigInteger.ZERO);
  53.                 }
  54.  
  55.                 BigInteger[] x = a.divideAndRemainder(b);
  56.                 return new DivisionAndRemainderResult(x[0], x[1]);
  57.         }
  58.  
  59.         /**
  60.          *
  61.          * @param a
  62.          * @param b
  63.          * @return
  64.          * @see http://www.arndt-bruenner.de/mathe/scripts/chineRestsatz.js
  65.          */
  66.         private static BigInteger[] extGGT(BigInteger a, BigInteger b) {
  67.                 if (b.signum() == 0) {
  68.                         return new BigInteger[] { BigInteger.ONE, BigInteger.ZERO };
  69.                 }
  70.  
  71.                 BigInteger rem = divRem(a, b).getRemainder();
  72.                 if (rem.signum() == 0) {
  73.                         return new BigInteger[] { BigInteger.ZERO, BigInteger.ONE };
  74.                 }
  75.  
  76.                 BigInteger[] c = extGGT(b, rem);
  77.                 BigInteger x = c[0];
  78.                 BigInteger y = c[1];
  79.  
  80.                 return new BigInteger[] { y, x.subtract(y.multiply(a.divide(b))) };
  81.         }
  82.  
  83.         /**
  84.          * Erweiterter euklidscher Algorithmus
  85.          *
  86.          * @param a
  87.          * @param b
  88.          * @return Erzeugt Objekt mit mit gcd=ggT(a,b) und gcd=alpha*a+beta*b
  89.          * @see http://www.arndt-bruenner.de/mathe/scripts/chineRestsatz.js
  90.          */
  91.         private static ExtEuclResult erwGGT(BigInteger a, BigInteger b) {
  92.                 BigInteger aa = new BigInteger("1");
  93.                 BigInteger bb = new BigInteger("1");
  94.  
  95.                 if (a.signum() == -1) {
  96.                         aa = new BigInteger("-1");
  97.                         a = a.negate();
  98.                 }
  99.  
  100.                 if (b.signum() == -1) {
  101.                         bb = new BigInteger("-1");
  102.                         b = b.negate();
  103.                 }
  104.  
  105.                 BigInteger[] c = extGGT(a, b);
  106.                 BigInteger g = a.gcd(b);
  107.  
  108.                 return new ExtEuclResult(c[0].multiply(aa), c[1].multiply(bb), g);
  109.         }
  110.  
  111.         /**
  112.          * Allgemeines Lösen zweier Kongruenzen (Chinesischer Restsatz)
  113.          *
  114.          * @param a
  115.          * @param n
  116.          * @param b
  117.          * @param m
  118.          * @return
  119.          * @throws CRTNotSolveableException
  120.          * @throws RemainderNotSmallerThanModulusException
  121.          * @see http://de.wikipedia.org/wiki/Chinesischer_Restsatz#Direktes_L.C3.B6sen_von_simultanen_Kongruenzen_ganzer_Zahlen
  122.          */
  123.         public static BigInteger chineseRemainder(BigInteger a, BigInteger n,
  124.                         BigInteger b, BigInteger m) throws CRTException {
  125.                
  126.                 // Frage: Ist es notwendig, dass wir divRem() verwenden, das von a%0==0 ausgeht?
  127.                
  128.                 if (a.signum() == -1) {
  129.                         a = a.negate();
  130.                 }
  131.                
  132.                 if (b.signum() == -1) {
  133.                         b = b.negate();
  134.                 }
  135.                
  136.                 if (n.signum() == -1) {
  137.                         n = n.negate();
  138.                 }
  139.                
  140.                 if (m.signum() == -1) {
  141.                         m = m.negate();
  142.                 }
  143.                
  144.                 if ((a.compareTo(n) >= 0) || (b.compareTo(m) >= 0)) {
  145.                         throw new RemainderNotSmallerThanModulusException();
  146.                 }
  147.  
  148.                 // d = ggT(n,m)
  149.                 BigInteger d = n.gcd(m);
  150.  
  151.                 // a === b (mod d) erfüllt?
  152.                 if (!divRem(a, d).getRemainder().equals(divRem(b, d).getRemainder())) {
  153.                         throw new CRTNotSolveableException();
  154.                 }
  155.  
  156.                 // ggT(n,m) = yn + zm
  157.                 BigInteger y = erwGGT(n, m).getAlpha();
  158.  
  159.                 // x = a - y*n*((a-b)/d) mod (n*m/d)
  160.                 BigInteger N = n.multiply(m).divide(d);
  161.                 BigInteger x = divRem(
  162.                                 a.subtract(y.multiply(n).multiply(a.subtract(b).divide(d))), N)
  163.                                 .getRemainder();
  164.                 x = a.subtract(y.multiply(n).multiply(a.subtract(b).divide(d)));
  165.  
  166.                 while (x.signum() == -1) {
  167.                         x = x.add(N);
  168.                 }
  169.  
  170.                 return x;
  171.         }
  172.  
  173.         private MathUtils2() {
  174.         }
  175.  
  176. }
  177.