Rev 7 | Go to most recent revision | Details | Compare with Previous | Last modification | View Log | RSS feed
| Rev | Author | Line No. | Line |
|---|---|---|---|
| 5 | daniel-mar | 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. |
||
| 7 | daniel-mar | 87 | * @throws Exception |
| 5 | daniel-mar | 88 | */ |
| 89 | public static BigInteger toggleBase(BigInteger cur, BigInteger u) |
||
| 7 | daniel-mar | 90 | throws Exception { |
| 5 | daniel-mar | 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 |
||
| 7 | daniel-mar | 108 | * @throws Exception |
| 5 | daniel-mar | 109 | */ |
| 7 | daniel-mar | 110 | public static BigInteger toggleBase(BigInteger cur) throws Exception { |
| 5 | daniel-mar | 111 | try { |
| 112 | return toggleBase(cur, MathUtils2.length(cur)); |
||
| 113 | } catch (InvalidLengthException e) { |
||
| 114 | // Should never happen |
||
| 115 | return null; |
||
| 116 | } |
||
| 117 | } |
||
| 6 | daniel-mar | 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 | } |
||
| 5 | daniel-mar | 136 | |
| 137 | private Immortable() { |
||
| 138 | } |
||
| 139 | |||
| 140 | } |