private BigInteger exactDivideBy3(){
  int len=mag.length;
  int[] result=new int[len];
  long x, w, q, borrow;
  borrow=0L;
  for (int i=len - 1; i >= 0; i--) {
    x=(mag[i] & LONG_MASK);
    w=x - borrow;
    if (borrow > x) {
      borrow=1L;
    }
 else {
      borrow=0L;
    }
    q=(w * 0xAAAAAAABL) & LONG_MASK;
    result[i]=(int)q;
    if (q >= 0x55555556L) {
      borrow++;
      if (q >= 0xAAAAAAABL)       borrow++;
    }
  }
  result=trustedStripLeadingZeroInts(result);
  return new BigInteger(result,signum);
}

private BigInteger exactDivideBy3 ( ) { int len = mag . length ; int [ ] result = new int [ len ] ; long x , w , q , borrow ; borrow = 0L ; for ( int i = len - 1 ; i >= 0 ; i -- ) { x = ( mag [ i ] & LONG_MASK ) ; w = x - borrow ; if ( borrow > x ) { borrow = 1L ; } else { borrow = 0L ; } q = ( w * 0xAAAAAAABL ) & LONG_MASK ; result [ i ] = ( int ) q ; if ( q >= 0x55555556L ) { borrow ++ ; if ( q >= 0xAAAAAAABL ) borrow ++ ; } } result = trustedStripLeadingZeroInts ( result ) ; return new BigInteger ( result , signum ) ; }
does an exact division ( that is , the remainder is known to be zero ) of the specified number by 3 . this is used in toom - cook multiplication . this is an efficient algorithm that runs in linear time . if the argument is not exactly divisible by 3 , results are undefined . note that this is expected to be called with positive arguments only .
