Subversion Repositories distributed

Rev

Rev 7 | Go to most recent revision | Blame | Last modification | View Log | RSS feed

  1. package de.viathinksoft.immortable.gen2;
  2.  
  3. import java.math.BigInteger;
  4.  
  5. import de.viathinksoft.immortable.gen2.math.CoPrimeExpectedException;
  6. import de.viathinksoft.immortable.gen2.math.MathUtils;
  7. import de.viathinksoft.immortable.gen2.math.MathUtils2;
  8.  
  9. /**
  10.  * Immortable Number Generator (ING)
  11.  *
  12.  * @author Daniel Marschall
  13.  */
  14.  
  15. public class Immortable {
  16.  
  17.         /**
  18.          * Calculates M5 or M6
  19.          *
  20.          * @param base
  21.          * @param u
  22.          * @return
  23.          */
  24.         public static BigInteger M(ImmortableBase base, BigInteger u) {
  25.                 BigInteger p, q;
  26.  
  27.                 if (base == ImmortableBase.M5) {
  28.                         p = BigInteger.ONE;
  29.                         q = BigInteger.ZERO;
  30.                 } else if (base == ImmortableBase.M6) {
  31.                         p = BigInteger.ZERO;
  32.                         q = BigInteger.ONE;
  33.                 } else {
  34.                         p = null;
  35.                         q = null;
  36.                 }
  37.  
  38.                 BigInteger a = MathUtils2.pow(new BigInteger("2"), u);
  39.                 BigInteger b = MathUtils2.pow(new BigInteger("5"), u);
  40.  
  41.                 // To calculate M5:
  42.                 // x = 2^u = a mod 1
  43.                 // x = 5^u = b mod 0
  44.  
  45.                 // To calculate M6:
  46.                 // x = 2^u = a mod 0
  47.                 // x = 5^u = b mod 1
  48.  
  49.                 try {
  50.                         return MathUtils.chineseRemainder(p, a, q, b);
  51.                 } catch (CoPrimeExpectedException e) {
  52.                         // Can never happen since 2^u and 5^u are always coprimes.
  53.                         return null;
  54.                 }
  55.         }
  56.  
  57.         /**
  58.          * Gets M5(u)
  59.          *
  60.          * @param u
  61.          *            Length of number
  62.          * @return
  63.          */
  64.         public static BigInteger M5(BigInteger u) {
  65.                 return M(ImmortableBase.M5, u);
  66.         }
  67.  
  68.         /**
  69.          * Gets M6(u)
  70.          *
  71.          * @param u
  72.          *            Length of number
  73.          * @return
  74.          */
  75.         public static BigInteger M6(BigInteger u) {
  76.                 return M(ImmortableBase.M6, u);
  77.         }
  78.  
  79.         /**
  80.          * Toggles between M5 and M6 base.
  81.          *
  82.          * @param cur
  83.          *            Number
  84.          * @param u
  85.          *            Length of number (because of possible leading zeros)
  86.          * @return Number in opposide base.
  87.          * @throws Exception
  88.          */
  89.         public static BigInteger toggleBase(BigInteger cur, BigInteger u)
  90.                         throws Exception {
  91.                 // Converts M6(u) <-> M5(u)
  92.                 // M6(u) = 1 + 10^u - M5(u)
  93.                 // M5(u) = 1 + 10^u - M6(u)
  94.                
  95.                 if (u.compareTo(MathUtils2.length(cur)) < 0) {
  96.                         throw new InvalidLengthException();
  97.                 }
  98.  
  99.                 return BigInteger.ONE.add(MathUtils2.pow(BigInteger.TEN, u)).subtract(cur);
  100.         }
  101.  
  102.         /**
  103.          * Toggles between M5 and M6 base. The length of the current number is
  104.          * assumed (and no leading zero).
  105.          *
  106.          * @param cur
  107.          * @return
  108.          * @throws Exception
  109.          */
  110.         public static BigInteger toggleBase(BigInteger cur) throws Exception {
  111.                 try {
  112.                         return toggleBase(cur, MathUtils2.length(cur));
  113.                 } catch (InvalidLengthException e) {
  114.                         // Should never happen
  115.                         return null;
  116.                 }
  117.         }
  118.        
  119.         public static boolean isImmortable(BigInteger num) {
  120.                 // Alternativ: n²%10^m == n%10^m
  121.                 return num.pow(2).toString().endsWith(num.toString());
  122.         }
  123.        
  124.         public static String findNextImmortable(String num) {
  125.                 if (!isImmortable(new BigInteger(num))) {
  126.                         return null;
  127.                 }
  128.                 for (int i=1; i<=9; i++) {
  129.                         String s = i+num;
  130.                         if (isImmortable(new BigInteger(s))) {
  131.                                 return s;
  132.                         }
  133.                 }
  134.                 return "0"+num;
  135.         }
  136.  
  137.         private Immortable() {
  138.         }
  139.  
  140. }
  141.