WebSVN – distributed – Blame – /ViaThinkSoft Distributed/src/de/viathinksoft/immortal/gen2/math/MathUtils2.java

Rev	Author	Line No.	Line
30	daniel-mar	1	package de.viathinksoft.immortal.gen2.math;
5	daniel-mar	2
		3	import java.math.BigInteger;
		4
		5	public class MathUtils2 {
		6
7	daniel-mar	7	public static BigInteger length(BigInteger x) throws Exception {
5	daniel-mar	8	// TODO: gr��er als MAX_INTEGER erlauben!
7	daniel-mar	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;
5	daniel-mar	16	}
		17
		18	public static BigInteger pow(BigInteger base, BigInteger exponent) {
7	daniel-mar	19	if (exponent.signum() == -1) {
5	daniel-mar	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
7	daniel-mar	50	if (b.signum() == 0) {
5	daniel-mar	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) {
7	daniel-mar	67	if (b.signum() == 0) {
5	daniel-mar	68	return new BigInteger[] { BigInteger.ONE, BigInteger.ZERO };
		69	}
		70
		71	BigInteger rem = divRem(a, b).getRemainder();
7	daniel-mar	72	if (rem.signum() == 0) {
5	daniel-mar	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=alphaa+betab
		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
7	daniel-mar	95	if (a.signum() == -1) {
5	daniel-mar	96	aa = new BigInteger("-1");
		97	a = a.negate();
		98	}
		99
7	daniel-mar	100	if (b.signum() == -1) {
5	daniel-mar	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,
13	daniel-mar	124	BigInteger b, BigInteger m) throws CRTException {
5	daniel-mar	125
		126	// Frage: Ist es notwendig, dass wir divRem() verwenden, das von a%0==0 ausgeht?
		127
7	daniel-mar	128	if (a.signum() == -1) {
5	daniel-mar	129	a = a.negate();
		130	}
		131
7	daniel-mar	132	if (b.signum() == -1) {
5	daniel-mar	133	b = b.negate();
		134	}
		135
7	daniel-mar	136	if (n.signum() == -1) {
5	daniel-mar	137	n = n.negate();
		138	}
		139
7	daniel-mar	140	if (m.signum() == -1) {
5	daniel-mar	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 - yn((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
7	daniel-mar	166	while (x.signum() == -1) {
5	daniel-mar	167	x = x.add(N);
		168	}
		169
		170	return x;
		171	}
		172
		173	private MathUtils2() {
		174	}
		175
		176	}

Subversion Repositories distributed

distributed/ViaThinkSoft Distributed/src/de/viathinksoft/immortal/gen2/math/MathUtils2.java – Rev 30