001/* 002 * $Id: Power.java 4056 2012-07-26 17:44:13Z kredel $ 003 */ 004 005package edu.jas.structure; 006 007 008import java.util.List; 009 010import org.apache.log4j.Logger; 011 012 013/** 014 * Power class to compute powers of RingElem. 015 * @author Heinz Kredel 016 */ 017public class Power<C extends RingElem<C>> { 018 019 020 private static final Logger logger = Logger.getLogger(Power.class); 021 022 023 private static boolean debug = logger.isDebugEnabled(); 024 025 026 private final RingFactory<C> fac; 027 028 029 /** 030 * The constructor creates a Power object. 031 */ 032 public Power() { 033 this(null); 034 } 035 036 037 /** 038 * The constructor creates a Power object. 039 * @param fac ring factory 040 */ 041 public Power(RingFactory<C> fac) { 042 this.fac = fac; 043 } 044 045 046 /** 047 * power of a to the n-th, n positive. 048 * @param a element. 049 * @param n integer exponent > 0. 050 * @return a^n. 051 */ 052 public static <C extends RingElem<C>> C positivePower(C a, long n) { 053 if (n <= 0) { 054 throw new IllegalArgumentException("only positive n allowed"); 055 } 056 if (a.isZERO() || a.isONE()) { 057 return a; 058 } 059 C b = a; 060 long i = n - 1; 061 C p = b; 062 do { 063 if (i % 2 == 1) { 064 p = p.multiply(b); 065 } 066 i = i / 2; 067 if (i > 0) { 068 b = b.multiply(b); 069 } 070 } while (i > 0); 071 return p; 072 } 073 074 075 /** 076 * power of a to the n-th, n positive. 077 * @param a element. 078 * @param n java.math.BigInteger exponent > 0. 079 * @return a^n. 080 */ 081 public static <C extends RingElem<C>> C positivePower(C a, java.math.BigInteger n) { 082 if (n.signum() <= 0) { 083 throw new IllegalArgumentException("only positive n allowed"); 084 } 085 if (a.isZERO() || a.isONE()) { 086 return a; 087 } 088 C b = a; 089 if (n.compareTo(java.math.BigInteger.ONE) == 0) { 090 return b; 091 } 092 C p = a; 093 java.math.BigInteger i = n.subtract(java.math.BigInteger.ONE); 094 do { 095 if (i.testBit(0)) { 096 p = p.multiply(b); 097 } 098 i = i.shiftRight(1); 099 if (i.signum() > 0) { 100 b = b.multiply(b); 101 } 102 } while (i.signum() > 0); 103 return p; 104 } 105 106 107 /** 108 * power of a to the n-th, n positive, modulo m. 109 * @param a element. 110 * @param n integer exponent > 0. 111 * @param m modulus. 112 * @return a^n mod m. 113 */ 114 public static <C extends RingElem<C>> C modPositivePower(C a, long n, C m) { 115 if (n <= 0) { 116 throw new IllegalArgumentException("only positive n allowed"); 117 } 118 if (a.isZERO() || a.isONE()) { 119 return a; 120 } 121 122 C b = a.remainder(m); 123 long i = n - 1; 124 C p = b; 125 do { 126 if (i % 2 == 1) { 127 p = p.multiply(b).remainder(m); 128 } 129 i = i / 2; 130 if (i > 0) { 131 b = b.multiply(b).remainder(m); 132 } 133 } while (i > 0); 134 return p; 135 } 136 137 138 /** 139 * power of a to the n-th. 140 * @param a element. 141 * @param n integer exponent. 142 * @param fac ring factory. 143 * @return a^n, with 0^0 = 0 and a^{-n} = {1/a}^n. 144 */ 145 @SuppressWarnings("unchecked") 146 public static <C extends RingElem<C>> C power(RingFactory<C> fac, C a, long n) { 147 if (a == null || a.isZERO()) { 148 return a; 149 } 150 //return a; 151 return (C) Power.<MonoidElem> power((MonoidFactory) fac, a, n); 152 } 153 154 155 /** 156 * power of a to the n-th. 157 * @param a element. 158 * @param n integer exponent. 159 * @param fac monoid factory. 160 * @return a^n, with a^{-n} = {1/a}^n. 161 */ 162 public static <C extends MonoidElem<C>> C power(MonoidFactory<C> fac, C a, long n) { 163 if (n == 0) { 164 if (fac == null) { 165 throw new IllegalArgumentException("fac may not be null for a^0"); 166 } 167 return fac.getONE(); 168 } 169 if (a.isONE()) { 170 return a; 171 } 172 C b = a; 173 if (n < 0) { 174 b = a.inverse(); 175 n = -n; 176 } 177 if (n == 1) { 178 return b; 179 } 180 C p = fac.getONE(); 181 long i = n; 182 do { 183 if (i % 2 == 1) { 184 p = p.multiply(b); 185 } 186 i = i / 2; 187 if (i > 0) { 188 b = b.multiply(b); 189 } 190 } while (i > 0); 191 if (n > 11 && debug) { 192 logger.info("n = " + n + ", p = " + p); 193 } 194 return p; 195 } 196 197 198 /** 199 * power of a to the n-th modulo m. 200 * @param a element. 201 * @param n integer exponent. 202 * @param m modulus. 203 * @param fac monoid factory. 204 * @return a^n mod m, with a^{-n} = {1/a}^n. 205 */ 206 public static <C extends MonoidElem<C>> C modPower(MonoidFactory<C> fac, C a, long n, C m) { 207 if (n == 0) { 208 if (fac == null) { 209 throw new IllegalArgumentException("fac may not be null for a^0"); 210 } 211 return fac.getONE(); 212 } 213 if (a.isONE()) { 214 return a; 215 } 216 C b = a.remainder(m); 217 if (n < 0) { 218 b = a.inverse().remainder(m); 219 n = -n; 220 } 221 if (n == 1) { 222 return b; 223 } 224 C p = fac.getONE(); 225 long i = n; 226 do { 227 if (i % 2 == 1) { 228 p = p.multiply(b).remainder(m); 229 } 230 i = i / 2; 231 if (i > 0) { 232 b = b.multiply(b).remainder(m); 233 } 234 } while (i > 0); 235 if (n > 11 && debug) { 236 logger.info("n = " + n + ", p = " + p); 237 } 238 return p; 239 } 240 241 242 /** 243 * power of a to the n-th modulo m. 244 * @param a element. 245 * @param n integer exponent. 246 * @param m modulus. 247 * @param fac monoid factory. 248 * @return a^n mod m, with a^{-n} = {1/a}^n. 249 */ 250 public static <C extends MonoidElem<C>> C modPower(MonoidFactory<C> fac, C a, java.math.BigInteger n, C m) { 251 if (n.signum() == 0) { 252 if (fac == null) { 253 throw new IllegalArgumentException("fac may not be null for a^0"); 254 } 255 return fac.getONE(); 256 } 257 if (a.isONE()) { 258 return a; 259 } 260 C b = a.remainder(m); 261 if (n.signum() < 0) { 262 b = a.inverse().remainder(m); 263 n = n.negate(); 264 } 265 if (n.compareTo(java.math.BigInteger.ONE) == 0) { 266 return b; 267 } 268 C p = fac.getONE(); 269 java.math.BigInteger i = n; 270 do { 271 if (i.testBit(0)) { 272 p = p.multiply(b).remainder(m); 273 } 274 i = i.shiftRight(1); 275 if (i.signum() > 0) { 276 b = b.multiply(b).remainder(m); 277 } 278 } while (i.signum() > 0); 279 if (debug) { 280 logger.info("n = " + n + ", p = " + p); 281 } 282 return p; 283 } 284 285 286 /** 287 * power of a to the n-th. 288 * @param a element. 289 * @param n integer exponent. 290 * @return a^n, with 0^0 = 0. 291 */ 292 public C power(C a, long n) { 293 return power(fac, a, n); 294 } 295 296 297 /** 298 * power of a to the n-th mod m. 299 * @param a element. 300 * @param n integer exponent. 301 * @param m modulus. 302 * @return a^n mod m, with 0^0 = 0. 303 */ 304 public C modPower(C a, long n, C m) { 305 return modPower(fac, a, n, m); 306 } 307 308 309 /** 310 * power of a to the n-th mod m. 311 * @param a element. 312 * @param n integer exponent. 313 * @param m modulus. 314 * @return a^n mod m, with 0^0 = 0. 315 */ 316 public C modPower(C a, java.math.BigInteger n, C m) { 317 return modPower(fac, a, n, m); 318 } 319 320 321 /** 322 * Logarithm. 323 * @param p logarithm base. 324 * @param a element. 325 * @return k ≥ 1 minimal with p^k ≥ b. 326 */ 327 public static <C extends RingElem<C>> long logarithm(C p, C a) { 328 //if ( p.compareTo(a) < 0 ) { 329 // return 0L; 330 //} 331 long k = 1L; 332 C m = p; 333 while (m.compareTo(a) < 0) { 334 m = m.multiply(p); 335 k++; 336 } 337 return k; 338 } 339 340 341 /** 342 * Multiply elements in list. 343 * @param A list of elements (a_0,...,a_k). 344 * @param fac ring factory. 345 * @return prod(i=0,...k) a_i. 346 */ 347 public static <C extends RingElem<C>> C multiply(RingFactory<C> fac, List<C> A) { 348 return multiply((MonoidFactory<C>) fac, A); 349 } 350 351 352 /** 353 * Multiply elements in list. 354 * @param A list of elements (a_0,...,a_k). 355 * @param fac monoid factory. 356 * @return prod(i=0,...k) a_i. 357 */ 358 public static <C extends MonoidElem<C>> C multiply(MonoidFactory<C> fac, List<C> A) { 359 if (fac == null) { 360 throw new IllegalArgumentException("fac may not be null for empty list"); 361 } 362 C res = fac.getONE(); 363 if (A == null || A.isEmpty()) { 364 return res; 365 } 366 for (C a : A) { 367 res = res.multiply(a); 368 } 369 return res; 370 } 371 372 373 /** 374 * Sum elements in list. 375 * @param A list of elements (a_0,...,a_k). 376 * @param fac ring factory. 377 * @return sum(i=0,...k) a_i. 378 */ 379 public static <C extends RingElem<C>> C sum(RingFactory<C> fac, List<C> A) { 380 return sum((AbelianGroupFactory<C>) fac, A); 381 } 382 383 384 /** 385 * Sum elements in list. 386 * @param A list of elements (a_0,...,a_k). 387 * @param fac monoid factory. 388 * @return sum(i=0,...k) a_i. 389 */ 390 public static <C extends AbelianGroupElem<C>> C sum(AbelianGroupFactory<C> fac, List<C> A) { 391 if (fac == null) { 392 throw new IllegalArgumentException("fac may not be null for empty list"); 393 } 394 C res = fac.getZERO(); 395 if (A == null || A.isEmpty()) { 396 return res; 397 } 398 for (C a : A) { 399 res = res.sum(a); 400 } 401 return res; 402 } 403 404}