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