Mega Code Archive

 

Categories / Java / Data Type

 

BigInteger bitwise Gcd

/*  * @(#)MathUtil.java  1.0 Apr 26, 2008  *  *  The MIT License  *  *  Copyright (c) 2008 Malachi de AElfweald <malachid@gmail.com>  *  *  Permission is hereby granted, free of charge, to any person obtaining a copy  *  of this software and associated documentation files (the "Software"), to deal  *  in the Software without restriction, including without limitation the rights  *  to use, copy, modify, merge, publish, distribute, sublicense, and/or sell  *  copies of the Software, and to permit persons to whom the Software is  *  furnished to do so, subject to the following conditions:  *  *  The above copyright notice and this permission notice shall be included in  *  all copies or substantial portions of the Software.  *  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR  *  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,  *  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE  *  AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER  *  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,  *  OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN  *  THE SOFTWARE.  */     import java.math.BigDecimal; import java.math.BigInteger; import java.math.RoundingMode; public class Util{   protected static BigInteger BigIntegerZERO = BigInteger.ZERO;   protected static BigInteger BigIntegerONE = BigInteger.ONE;   protected static BigInteger BigIntegerTWO = BigInteger.valueOf(2);   protected static BigInteger BigIntegerTHREE=BigInteger.valueOf(3);   protected static BigInteger FactorialBreakpoint = BigInteger.valueOf(96);   protected static BigDecimal BigDecimalZERO = BigDecimal.ZERO;   protected static BigDecimal BigDecimalONE = BigDecimal.ONE;   protected static BigDecimal BigDecimalTWO = new BigDecimal(2);   protected static BigDecimal BigDecimalFOUR = new BigDecimal(4);      public static BigInteger bitwiseGcd(BigInteger u, BigInteger v)   {     if(u.equals(BigInteger.ZERO)) return v;     if(v.equals(BigInteger.ZERO)) return u; //    System.out.format("u=%s=%s\nu.getLowestSetBit()=%s\n%s>>%s=%s = %s\n", u, u.toString(2), u.getLowestSetBit(), u, u.getLowestSetBit(), u.shiftRight(u.getLowestSetBit()), u.shiftRight(u.getLowestSetBit()).toString(2));     int uBit = u.getLowestSetBit();     int vBit = v.getLowestSetBit();     int k = (uBit <= vBit ? uBit : vBit);     while(u.signum() > 0)     {       // first ensure that both are odd       u = u.shiftRight(u.getLowestSetBit());       v = v.shiftRight(v.getLowestSetBit());       if(u.subtract(v).signum() >= 0)       {         u = (u.subtract(v)).shiftRight(1);       }else{         v = (v.subtract(u)).shiftRight(1);       }     }     return v.shiftLeft(k);   } }