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