Subversion Repositories distributed

Compare Revisions

No changes between revisions

Regard whitespace Rev 29 → Rev 30

/ViaThinkSoft Distributed/src/de/viathinksoft/immortal/genX/FileUtils.java
0,0 → 1,30
package de.viathinksoft.immortal.genX;
 
import java.io.*;
import java.nio.channels.*;
 
/**
*
* @see http://www.rgagnon.com/javadetails/java-0064.html
*
*/
public class FileUtils {
public static void copyFile(File in, File out) throws IOException {
FileChannel inChannel = new FileInputStream(in).getChannel();
FileChannel outChannel = new FileOutputStream(out).getChannel();
try {
inChannel.transferTo(0, inChannel.size(), outChannel);
} catch (IOException e) {
throw e;
} finally {
if (inChannel != null)
inChannel.close();
if (outChannel != null)
outChannel.close();
}
}
 
public static void main(String args[]) throws IOException {
FileUtils.copyFile(new File(args[0]), new File(args[1]));
}
}
Property changes:
Added: svn:mime-type
+text/plain
\ No newline at end of property
/ViaThinkSoft Distributed/src/de/viathinksoft/immortal/genX/ByteArray.java
0,0 → 1,74
package de.viathinksoft.immortal.genX;
 
/**
*
* @author Daniel Marschall
*
*/
public class ByteArray {
 
private int expansionSize;
private byte[] a;
private int top = -1;
 
public ByteArray() {
this(100, 1000);
}
 
public ByteArray(int initialSize, int expansionSize) {
this.a = new byte[initialSize];
this.expansionSize = expansionSize;
}
 
private void expand() {
byte[] b = a;
 
a = new byte[b.length + expansionSize];
 
for (int i = 0; i < b.length; i++) {
a[i] = b[i];
}
}
 
public void add(byte x) {
top++;
if (top >= a.length) {
expand();
}
a[top] = x;
}
 
public byte remove() {
return a[top--];
}
 
public byte get(int i) {
return a[i];
}
 
public void set(int i, byte x) {
a[i] = x;
}
 
public int count() {
return top + 1;
}
 
public void clear() {
top = -1;
}
 
public boolean isEmpty() {
return top == -1;
}
 
@Override
public String toString() {
StringBuilder x = new StringBuilder();
for (int i = 0; i <= top; i++) {
x.append("" + a[i]);
}
return x.toString();
}
 
}
Property changes:
Added: svn:mime-type
+text/plain
\ No newline at end of property
/ViaThinkSoft Distributed/src/de/viathinksoft/immortal/genX/MainUnit.java
0,0 → 1,11
package de.viathinksoft.immortal.genX;
 
public class MainUnit {
 
public static void main(String[] args) throws ImmortableException {
ImmortableNumberSearch x = new ImmortableNumberSearch("data.txt");
x.calcIterate(-1);
// x.calcIterate(10);
}
 
}
Property changes:
Added: svn:mime-type
+text/plain
\ No newline at end of property
/ViaThinkSoft Distributed/src/de/viathinksoft/immortal/genX/ImmortableException.java
0,0 → 1,23
package de.viathinksoft.immortal.genX;
 
public class ImmortableException extends Exception {
 
private static final long serialVersionUID = -2350754871091479027L;
public ImmortableException() {
super();
}
 
public ImmortableException(Throwable cause) {
super(cause);
}
 
public ImmortableException(String message) {
super(message);
}
 
public ImmortableException(String message, Throwable cause) {
super(message, cause);
}
 
}
Property changes:
Added: svn:mime-type
+text/plain
\ No newline at end of property
/ViaThinkSoft Distributed/src/de/viathinksoft/immortal/genX/ImmortableNumberSearch.java
0,0 → 1,370
package de.viathinksoft.immortal.genX;
 
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.math.BigInteger;
 
/**
* Immortable Iterator
*
* @author Daniel Marschall, Big thanks to the users of MatheBoard.de
* @see http://www.matheboard.de/archive/435725/thread.html
*/
public class ImmortableNumberSearch {
 
private static final String SIGNATURE = "Immortal Number Report File Version 2.02";
private static final String SIGNATURE_MINOR = "Iterator GenX Java (100k save-interval, load-integrity-check, int32-r, array-object) r29";
private static final String END_SIG = "END OF REPORT";
private static final int SOFTBREAK = 76;
 
private ByteArray a;
private String filename;
private int saveInterval = 100000;
private int u = -1;
private int r = -1; // FUTURE: r als BigInteger
private String creation_time;
private String backupDir = "backup";
 
private static final int INITIAL_SIZE = 1000000;
private static final int EXPANSION_SIZE = 1000000;
 
private boolean do_integrity_test = false;
private boolean verbose = false;
 
public boolean isDo_integrity_test() {
return do_integrity_test;
}
 
public void setDo_integrity_test(boolean doIntegrityTest) {
do_integrity_test = doIntegrityTest;
}
 
public boolean isVerbose() {
return verbose;
}
 
public void setVerbose(boolean verbose) {
this.verbose = verbose;
}
 
protected void log(String s) {
if (verbose) {
String timestamp = DateUtils.now("EEE, d MMM yyyy HH:mm:ss Z");
System.out.println(timestamp + " - " + s); // FURUE: In eine
// Log-Datei schreiben
}
}
 
public ImmortableNumberSearch(String filename) throws LoadException {
this.filename = filename;
load();
}
 
public String getBackupDir() {
return backupDir;
}
 
public void setBackupDir(String backupDir) {
this.backupDir = backupDir;
}
 
public int getSaveInterval() {
return this.saveInterval;
}
 
public ByteArray getA() {
return a;
}
 
public int getU() {
return u;
}
 
public int getR() {
return r;
}
 
public String getFilename() {
return filename;
}
 
public void setSaveInterval(int saveInterval) {
this.saveInterval = saveInterval;
}
 
private boolean savePointExists() {
return new File(filename).exists();
}
 
private void load() throws LoadException {
if (!savePointExists()) {
this.a = new ByteArray(INITIAL_SIZE, EXPANSION_SIZE);
return;
}
 
BufferedReader f;
try {
f = new BufferedReader(new FileReader(filename));
} catch (FileNotFoundException e) {
// Will not happen because of savePointExists().
return;
}
 
u = -1;
r = -1;
 
try {
try {
String s = f.readLine();
if (!s.equals(SIGNATURE)) {
throw new LoadException("Corrupt: Wrong signature");
}
 
f.readLine(); // Minor. signature
f.readLine(); // ""
 
f.readLine(); // "(Starting time)"
creation_time = f.readLine();
f.readLine(); // ""
 
f.readLine(); // "(Save timestamp)"
f.readLine(); // Timestamp
f.readLine(); // ""
 
f.readLine(); // "(Digits)"
s = f.readLine();
u = Integer.parseInt(s) - 1;
f.readLine(); // ""
 
f.readLine(); // "(r)"
s = f.readLine();
r = Integer.parseInt(s); // FUTURE: (1) Multi-Line-Support?
f.readLine(); // ""
 
this.a = new ByteArray(u + 1 + EXPANSION_SIZE, EXPANSION_SIZE);
 
f.readLine(); // "(M5 reversed)"
do {
s = f.readLine();
for (int i = 0; i < s.length(); i++) {
a.add(Byte.parseByte(s.substring(i, i + 1)));
}
} while (!s.equals(""));
 
if (u + 1 != a.count()) {
throw new LoadException(
"Corrupt: Formal and actual length mismatch!");
}
 
s = f.readLine();
if (!s.equals(END_SIG)) {
throw new LoadException("Corrupt: End-signature mismatch.");
}
} finally {
f.close();
}
} catch (IOException e) {
throw new LoadException(e);
}
}
 
private void save(boolean integrityTest) throws SaveException {
if ((integrityTest) && (do_integrity_test)) {
log("Beginne Selbsttest vor erster Speicherung...");
 
if (!integryTest()) {
throw new SaveException(
"Integrity test failed. (Loaded file broken?) Will not save.");
}
}
 
log("Speichere bei u=" + (u + 1));
 
String timestamp = DateUtils.now("EEE, d MMM yyyy HH:mm:ss Z");
String timestamp_filename = DateUtils.now("dd-MM-yyyy_HH-mm-ss");
 
try {
BufferedWriter f = new BufferedWriter(new FileWriter(filename));
 
try {
f.write(SIGNATURE + "\r\n");
 
f.write(SIGNATURE_MINOR + "\r\n");
f.write("\r\n");
 
f.write("(Starting time)\r\n");
f.write(creation_time + "\r\n");
f.write("\r\n");
 
f.write("(Save timestamp)\r\n");
f.write(timestamp + "\r\n");
f.write("\r\n");
 
f.write("(Digits)\r\n");
f.write((u + 1) + "\r\n");
f.write("\r\n");
 
f.write("(r)\r\n");
f.write(r + "\r\n"); // FUTURE: (1) Multi-Line-Support?
f.write("\r\n");
 
f.write("(M5 reversed)\r\n");
int i;
for (i = 0; i < a.count(); i++) {
byte xa = a.get(i);
f.write("" + xa);
if ((i + 1) % SOFTBREAK == 0) {
f.write("\r\n");
}
}
if ((i + 1) % SOFTBREAK != 0) {
f.write("\r\n");
}
f.write("\r\n");
 
f.write(END_SIG);
} finally {
f.close();
}
} catch (IOException e) {
throw new SaveException("Could not save master file.", e);
}
 
// Make backup
 
new File(backupDir).mkdir();
String bak_filename = backupDir + "/immortal_" + timestamp_filename
+ "_" + (u + 1) + ".txt";
try {
FileUtils.copyFile(new File(filename), new File(bak_filename));
} catch (IOException e) {
throw new SaveException("Could not make backup", e);
}
 
if ((integrityTest) && (do_integrity_test)) {
log("Erste Speicherung absolviert. Stabile Phase hat begonnen.");
}
}
 
public void calcIterate(int amount) throws SaveException {
log("Beginn der Rechenarbeit...");
 
int cnt = 0;
 
// Wir führen beim ersten Speichern einen weiteren
// integrity-Test durch. Grund: Wäre bei einer Fortsetzung einer
// Datei das "r" falsch (der Datenteil aber korrekt), dann würde
// diese Datei beim Speichern ungültige Daten enthalten (Zahl
// nicht immortabel).
boolean firstSave = true;
 
if (a.isEmpty()) {
creation_time = DateUtils.now("EEE, d MMM yyyy HH:mm:ss Z");
a.add((byte) 5);
a.add((byte) 2);
u = 1;
r = 2;
cnt += 2;
}
 
int s, m, k;
 
do {
r = (r /* - a.get(u) */) / 10 + a.get(u);
s = 0;
for (m = 1, k = u; m < k; m++, k--) {
s += a.get(m) * a.get(k);
}
r += 2 * s;
if (m == k) {
r += a.get(m) * a.get(m);
}
u++;
a.add((byte) (r % 10));
 
cnt++;
if (cnt % saveInterval == 0) {
save(firstSave);
firstSave = false;
}
} while (cnt != amount);
 
// Wir brauchen nicht zwei Mal zu speichern
if (cnt - 1 % saveInterval != 0) {
log("Letzte Speicherung vor Ende...");
save(firstSave);
// firstSave = false;
}
 
log("Ende der Rechenarbeit...");
}
 
public byte getDigitReverse(int u) {
return a.get(u);
}
 
public StringBuilder M5_StringBuilder(int u) {
StringBuilder s = new StringBuilder();
for (int i = 0; i < a.count(); i++) {
byte xa = a.get(i);
s.append("" + xa);
}
s.reverse();
return s;
}
 
public String M5_String(int u) {
return M5_StringBuilder(u).toString();
}
 
public BigInteger M5_BigInteger(int u) {
return new BigInteger(M5_String(u));
}
 
public StringBuilder M6_StringBuilder(int u) {
StringBuilder s = new StringBuilder();
for (int i = 0; i < a.count(); i++) {
byte xa = a.get(i);
if (i > 0) {
s.append("" + (9 - xa));
} else {
s.append("" + (11 - xa));
}
}
s.reverse();
return s;
}
 
public String M6_String(int u) {
return M6_StringBuilder(u).toString();
}
 
public BigInteger M6_BigInteger(int u) {
return new BigInteger(M6_String(u));
}
 
protected static boolean isImmortable(BigInteger num, int m) {
// Alternativ
// return num.pow(2).toString().endsWith(num.toString());
 
// n² === n (mod 10^m) <===> n²%10^m == n%10^m == n
 
BigInteger m_pow = BigInteger.TEN.pow(m);
return num.pow(2).mod(m_pow).equals(num);
}
 
protected static boolean isImmortable(BigInteger num) {
int m = num.toString().length();
return isImmortable(num, m);
}
 
public boolean integryTest() {
// return isImmortable(M5_BigInteger(u), a.count());
return isImmortable(M6_BigInteger(u), a.count());
}
}
Property changes:
Added: svn:mime-type
+text/plain
\ No newline at end of property
/ViaThinkSoft Distributed/src/de/viathinksoft/immortal/genX/SaveException.java
0,0 → 1,23
package de.viathinksoft.immortal.genX;
 
public class SaveException extends ImmortableException {
 
private static final long serialVersionUID = 6676069625825930604L;
 
public SaveException() {
super();
}
 
public SaveException(Throwable cause) {
super(cause);
}
 
public SaveException(String message) {
super(message);
}
 
public SaveException(String message, Throwable cause) {
super(message, cause);
}
 
}
Property changes:
Added: svn:mime-type
+text/plain
\ No newline at end of property
/ViaThinkSoft Distributed/src/de/viathinksoft/immortal/genX/DateUtils.java
0,0 → 1,20
package de.viathinksoft.immortal.genX;
 
import java.text.SimpleDateFormat;
import java.util.Calendar;
import java.util.Locale;
 
/**
* @see http://www.rgagnon.com/javadetails/java-0106.html (modified)
*/
public class DateUtils {
public static String now(String format) {
Calendar cal = Calendar.getInstance();
Locale lok = Locale.ENGLISH;
SimpleDateFormat sdf = new SimpleDateFormat(format, lok);
return sdf.format(cal.getTime());
}
 
private DateUtils() {
}
}
Property changes:
Added: svn:mime-type
+text/plain
\ No newline at end of property
/ViaThinkSoft Distributed/src/de/viathinksoft/immortal/genX/LoadException.java
0,0 → 1,23
package de.viathinksoft.immortal.genX;
 
public class LoadException extends ImmortableException {
 
private static final long serialVersionUID = 5556229109549989469L;
 
public LoadException() {
super();
}
 
public LoadException(Throwable cause) {
super(cause);
}
 
public LoadException(String message) {
super(message);
}
 
public LoadException(String message, Throwable cause) {
super(message, cause);
}
 
}
Property changes:
Added: svn:mime-type
+text/plain
\ No newline at end of property
/ViaThinkSoft Distributed/src/de/viathinksoft/immortal/genX/original.txt
0,0 → 1,23
/* Berechnet a[0]..a[n-1], also bis einschliesslich M_5(n) . */
/* Es wird vorausgesetzt, dass das Feld a auf einen genuegend grossen Platz fuer n Bytes zeigt! */
void BerechneUnsterblich (unsigned char *a, int n)
{
int r,s,u,m,k;
if (n <= 0) return;
a[0] = 5;
if (n <= 1) return;
a[1] = 2;
r = 2;
u = 1;
while (u < n-1)
{
r = (r-a[u])/10 + a[u];
s = 0;
for (m = 1, k = u; m < k; m++,k--) s += a[m]*a[k];
r += 2*s;
if (m == k) r += a[m]*a[m];
a[++u] = r % 10;
}
}
 
"5 Mal editiert"
Property changes:
Added: svn:mime-type
+text/plain
\ No newline at end of property
/ViaThinkSoft Distributed/src/de/viathinksoft/immortal/gen2/math/CoPrimeExpectedException.java
0,0 → 1,7
package de.viathinksoft.immortal.gen2.math;
 
public class CoPrimeExpectedException extends CRTException {
 
private static final long serialVersionUID = 8804691690532130114L;
 
}
Property changes:
Added: svn:mime-type
+text/plain
\ No newline at end of property
/ViaThinkSoft Distributed/src/de/viathinksoft/immortal/gen2/math/CRTNotSolveableException.java
0,0 → 1,7
package de.viathinksoft.immortal.gen2.math;
 
public class CRTNotSolveableException extends CRTException {
 
private static final long serialVersionUID = -2550866943316039887L;
 
}
Property changes:
Added: svn:mime-type
+text/plain
\ No newline at end of property
/ViaThinkSoft Distributed/src/de/viathinksoft/immortal/gen2/math/CRTException.java
0,0 → 1,7
package de.viathinksoft.immortal.gen2.math;
 
public class CRTException extends Exception {
 
private static final long serialVersionUID = 1040331240918766268L;
 
}
Property changes:
Added: svn:mime-type
+text/plain
\ No newline at end of property
/ViaThinkSoft Distributed/src/de/viathinksoft/immortal/gen2/math/ExtEuclResult.java
0,0 → 1,30
package de.viathinksoft.immortal.gen2.math;
 
import java.math.BigInteger;
 
public class ExtEuclResult {
private BigInteger alpha; // inverse
private BigInteger beta;
private BigInteger gcd; // ggT
 
public ExtEuclResult(BigInteger alpha, BigInteger beta, BigInteger gcd) {
super();
this.alpha = alpha;
this.beta = beta;
this.gcd = gcd;
}
public BigInteger getAlpha() {
return alpha;
}
public BigInteger getBeta() {
return beta;
}
public BigInteger getGcd() {
return gcd;
}
 
}
Property changes:
Added: svn:mime-type
+text/plain
\ No newline at end of property
/ViaThinkSoft Distributed/src/de/viathinksoft/immortal/gen2/math/MathUtils.java
0,0 → 1,140
package de.viathinksoft.immortal.gen2.math;
 
import java.math.BigInteger;
 
public class MathUtils {
 
/**
* Division with remainder method - based on the original Java<br>
* 'divideAndRemainder' method<br>
* returns an object of results (of type BigInteger):<br>
* -> the division result (q=a/b)<br>
* result[1] -> the remainder (r=a-q*b)
*
* @param a
* @param b
* @return
* @see http://tupac.euv-frankfurt-o.de/www/kryptos/demos/Demos.java
**/
 
public static DivisionAndRemainderResult divRem(BigInteger a, BigInteger b) {
// if (b==0) {
// -> divideAndRemainder() throws ArithmeticException when b==0
if ((b.compareTo(BigInteger.ZERO)) == 0) {
return new DivisionAndRemainderResult(BigInteger.ZERO,
BigInteger.ZERO);
}
 
BigInteger[] x = a.divideAndRemainder(b);
return new DivisionAndRemainderResult(x[0], x[1]);
}
 
/**
* The Extended Euclidean Algorithm
*
* @param a
* @param gcd
* @return Object of "alpha" (inverse), "beta" and gcd (of type BigInteger).
* @see http://tupac.euv-frankfurt-o.de/www/kryptos/demos/Demos.java
*/
 
public static ExtEuclResult extEucl(BigInteger a, BigInteger gcd) {
 
// Coefficients
BigInteger alpha_0 = new BigInteger("1");
BigInteger alpha_1 = new BigInteger("0");
BigInteger beta_0 = new BigInteger("0");
BigInteger beta_1 = new BigInteger("1");
BigInteger alpha = new BigInteger("0");
BigInteger beta = new BigInteger("1");
 
if (gcd.compareTo(BigInteger.ZERO) == 0) {
alpha = BigInteger.ONE;
beta = BigInteger.ZERO;
gcd = a;
} else if (a.compareTo(BigInteger.ZERO) != 0) {
DivisionAndRemainderResult qr = divRem(a, gcd);
 
while (qr.getRemainder().compareTo(BigInteger.ZERO) != 0) {
alpha = alpha_0.subtract(qr.getDivisionResult().multiply(
alpha_1));
beta = beta_0.subtract(qr.getDivisionResult().multiply(beta_1));
 
alpha_0 = alpha_1;
beta_0 = beta_1;
 
alpha_1 = alpha;
beta_1 = beta;
 
a = gcd;
gcd = qr.getRemainder();
qr = divRem(a, gcd);
}
}
 
return new ExtEuclResult(alpha, beta, gcd);
}
 
/**
* Determinates wheter p and q are coprimes or not.
*
* @param p
* @param q
* @return
*/
public static boolean isCoprime(BigInteger p, BigInteger q) {
return p.gcd(q).compareTo(BigInteger.ONE) == 0;
}
 
/**
* Solves the simultaneous congruences by means of the CR-Theorem:<br>
* M = Mp mod P and M = Mq mod Q<br>
* M = (Mq*Yp*P + Mp*Yq*Q) mod N<br>
* (Yp, Yq -> Ext.Eucl: Yp*P + Yq*Q = 1)
*
* @param Mp
* @param P
* @param Mq
* @param Q
* @return
* @throws CoPrimeExpectedException
* @see http://tupac.euv-frankfurt-o.de/www/kryptos/demos/Rsa.java
*/
 
public static BigInteger chineseRemainder(BigInteger Mp, BigInteger P, BigInteger Mq,
BigInteger Q) throws CoPrimeExpectedException {
 
if (!isCoprime(P, Q)) {
throw new CoPrimeExpectedException();
}
 
// 1) yiMi = 1 mod mi -> computing Inverses yi (extended
// Euclides):
// yp*P = 1 mod Q -> yp (inverse)
// yq*Q = 1 mod P -> yq (inverse)
 
BigInteger yq = extEucl(Q, P).getAlpha();
BigInteger yp = extEucl(P, Q).getAlpha();
 
// 2) collecting 'M = (Mp*yq*Q + Mq*yp*P) mod N':
 
BigInteger psum = Mp.multiply(yq).multiply(Q);
BigInteger qsum = Mq.multiply(yp).multiply(P);
BigInteger sum = psum.add(qsum);
 
// computing 'sum mod m'
BigInteger N = P.multiply(Q); // common modulus
BigInteger M = divRem(sum, N).getRemainder();
 
// if remainder (a/b) is negative (cause 'a' negative) then:
if (M.compareTo(BigInteger.ZERO) < 0) {
M = M.add(N);
}
 
return M;
}
private MathUtils() {
}
 
}
Property changes:
Added: svn:mime-type
+text/plain
\ No newline at end of property
/ViaThinkSoft Distributed/src/de/viathinksoft/immortal/gen2/math/RemainderNotSmallerThanModulusException.java
0,0 → 1,7
package de.viathinksoft.immortal.gen2.math;
 
public class RemainderNotSmallerThanModulusException extends CRTException {
 
private static final long serialVersionUID = -1361245285354281472L;
 
}
Property changes:
Added: svn:mime-type
+text/plain
\ No newline at end of property
/ViaThinkSoft Distributed/src/de/viathinksoft/immortal/gen2/math/MathUtils2.java
0,0 → 1,176
package de.viathinksoft.immortal.gen2.math;
 
import java.math.BigInteger;
 
public class MathUtils2 {
public static BigInteger length(BigInteger x) throws Exception {
// TODO: größer als MAX_INTEGER erlauben!
BigInteger z = new BigInteger(""+x.toString().length());
if (z.signum() == -1) {
throw new Exception("Integer overflow! (BigInteger-Length)");
}
return z;
}
public static BigInteger pow(BigInteger base, BigInteger exponent) {
if (exponent.signum() == -1) {
throw new ArithmeticException("Negative exponent");
}
 
BigInteger i = new BigInteger("0");
BigInteger res = new BigInteger("1");
while (i.compareTo(exponent) != 0) {
i = i.add(BigInteger.ONE);
res = res.multiply(base);
}
return res;
}
 
/**
* Division with remainder method - based on the original Java<br>
* 'divideAndRemainder' method<br>
* returns an object of results (of type BigInteger):<br>
* -> the division result (q=a/b)<br>
* result[1] -> the remainder (r=a-q*b)<br>
* If b==0 then result will be 0. No ArithmeticException!
*
* @param a
* @param b
* @return
* @see http://tupac.euv-frankfurt-o.de/www/kryptos/demos/Demos.java
**/
public static DivisionAndRemainderResult divRem(BigInteger a, BigInteger b) {
// if (b==0) {
// -> divideAndRemainder() throws ArithmeticException when b==0
if (b.signum() == 0) {
return new DivisionAndRemainderResult(BigInteger.ZERO,
BigInteger.ZERO);
}
 
BigInteger[] x = a.divideAndRemainder(b);
return new DivisionAndRemainderResult(x[0], x[1]);
}
 
/**
*
* @param a
* @param b
* @return
* @see http://www.arndt-bruenner.de/mathe/scripts/chineRestsatz.js
*/
private static BigInteger[] extGGT(BigInteger a, BigInteger b) {
if (b.signum() == 0) {
return new BigInteger[] { BigInteger.ONE, BigInteger.ZERO };
}
 
BigInteger rem = divRem(a, b).getRemainder();
if (rem.signum() == 0) {
return new BigInteger[] { BigInteger.ZERO, BigInteger.ONE };
}
 
BigInteger[] c = extGGT(b, rem);
BigInteger x = c[0];
BigInteger y = c[1];
 
return new BigInteger[] { y, x.subtract(y.multiply(a.divide(b))) };
}
 
/**
* Erweiterter euklidscher Algorithmus
*
* @param a
* @param b
* @return Erzeugt Objekt mit mit gcd=ggT(a,b) und gcd=alpha*a+beta*b
* @see http://www.arndt-bruenner.de/mathe/scripts/chineRestsatz.js
*/
private static ExtEuclResult erwGGT(BigInteger a, BigInteger b) {
BigInteger aa = new BigInteger("1");
BigInteger bb = new BigInteger("1");
 
if (a.signum() == -1) {
aa = new BigInteger("-1");
a = a.negate();
}
 
if (b.signum() == -1) {
bb = new BigInteger("-1");
b = b.negate();
}
 
BigInteger[] c = extGGT(a, b);
BigInteger g = a.gcd(b);
 
return new ExtEuclResult(c[0].multiply(aa), c[1].multiply(bb), g);
}
 
/**
* Allgemeines Lösen zweier Kongruenzen (Chinesischer Restsatz)
*
* @param a
* @param n
* @param b
* @param m
* @return
* @throws CRTNotSolveableException
* @throws RemainderNotSmallerThanModulusException
* @see http://de.wikipedia.org/wiki/Chinesischer_Restsatz#Direktes_L.C3.B6sen_von_simultanen_Kongruenzen_ganzer_Zahlen
*/
public static BigInteger chineseRemainder(BigInteger a, BigInteger n,
BigInteger b, BigInteger m) throws CRTException {
// Frage: Ist es notwendig, dass wir divRem() verwenden, das von a%0==0 ausgeht?
if (a.signum() == -1) {
a = a.negate();
}
if (b.signum() == -1) {
b = b.negate();
}
if (n.signum() == -1) {
n = n.negate();
}
if (m.signum() == -1) {
m = m.negate();
}
if ((a.compareTo(n) >= 0) || (b.compareTo(m) >= 0)) {
throw new RemainderNotSmallerThanModulusException();
}
 
// d = ggT(n,m)
BigInteger d = n.gcd(m);
 
// a === b (mod d) erfüllt?
if (!divRem(a, d).getRemainder().equals(divRem(b, d).getRemainder())) {
throw new CRTNotSolveableException();
}
 
// ggT(n,m) = yn + zm
BigInteger y = erwGGT(n, m).getAlpha();
 
// x = a - y*n*((a-b)/d) mod (n*m/d)
BigInteger N = n.multiply(m).divide(d);
BigInteger x = divRem(
a.subtract(y.multiply(n).multiply(a.subtract(b).divide(d))), N)
.getRemainder();
x = a.subtract(y.multiply(n).multiply(a.subtract(b).divide(d)));
 
while (x.signum() == -1) {
x = x.add(N);
}
 
return x;
}
 
private MathUtils2() {
}
 
}
Property changes:
Added: svn:mime-type
+text/plain
\ No newline at end of property
/ViaThinkSoft Distributed/src/de/viathinksoft/immortal/gen2/math/DivisionAndRemainderResult.java
0,0 → 1,25
package de.viathinksoft.immortal.gen2.math;
 
import java.math.BigInteger;
 
public class DivisionAndRemainderResult {
private BigInteger divisionResult;
private BigInteger remainder;
 
public DivisionAndRemainderResult(BigInteger divisionResult,
BigInteger remainder) {
super();
this.divisionResult = divisionResult;
this.remainder = remainder;
}
 
public BigInteger getDivisionResult() {
return divisionResult;
}
 
public BigInteger getRemainder() {
return remainder;
}
 
}
Property changes:
Added: svn:mime-type
+text/plain
\ No newline at end of property
/ViaThinkSoft Distributed/src/de/viathinksoft/immortal/internal/Endzeitpunkt.java
0,0 → 1,39
package de.viathinksoft.immortal.internal;
 
import java.math.BigInteger;
 
public class Endzeitpunkt {
 
// Allgemeine Daten zum Test (GenX)
private static final BigInteger TEST_BEGINN = new BigInteger("1291006160");
 
// Der alte Algorithmus (r19)
// private static final int ABSCHNITT_STEP = 3;
// private static final BigInteger ABSCHNITT_BEGINN = new BigInteger("789");
// private static final BigInteger ABFALL_MEDIAN = new BigInteger("199");
 
// Der neue Algorithmus (r20)
private static final int ABSCHNITT_STEP = 29;
private static final BigInteger ABSCHNITT_BEGINN = new BigInteger("94923");
private static final BigInteger ABFALL_MEDIAN = new BigInteger("30");
 
private static BigInteger f(int u) {
BigInteger res = ABSCHNITT_BEGINN;
for (int i = ABSCHNITT_STEP + 1; i <= u; i++) {
res = res.add(ABFALL_MEDIAN.multiply(BigInteger.valueOf(i)));
}
return res;
}
 
private static BigInteger u(int u) {
return f(u).add(TEST_BEGINN);
}
 
public static void main(String[] args) {
int max_step = Integer.MAX_VALUE / 100000;
 
System.out.println("End time for step: " + max_step);
System.out.println(u(max_step));
}
 
}