title: Implementing efficient 512 bit integer type
body: <p>I was asked to create 512 bit integer type to my RSA encryption algorithm. I started from the simplest bitwise operations <code>OR, AND, XOR, NOT</code>, afterwards using mentioned operations I implemented addition, subtraction etc.
  Unfortunately after many tests, it's very slow on more than 128 bits. </p>
  
  <p>I was surprised when I found site with RSA generation where it generated key using apparently javascript in several miliseconds. How I can improve my algorithm to get better efficiency ? Or better question would be: how proffesionals implement so big types with
  such performance.</p>
  
  <p>Here is my code:</p>
  
  <pre><code>    public class BigInt {
  
        public static final int    BYTE = 8;
        public static final int    DEFAULT_SIZE = 128;
        public final static BigInt ZERO = new BigInt(0);
        public final static BigInt ONE = new BigInt(1);
        public final static BigInt TEN = new BigInt(10);
        private boolean[] number;
        private Endianness endianness = Endianness.BIG_ENDIAN;
  
      public BigInt() {
          number = new boolean[DEFAULT_SIZE];
      }
  
      public BigInt(boolean[] number) {
          this.number = number;
      }
  
      public BigInt(int integerNumber) {
          this();
          boolean isNegative = false;
          if (integerNumber &lt; 0) {
              isNegative = true;
              integerNumber = Math.abs(integerNumber);
          }
          for (int i = number.length - 1; i &gt;= 1 &amp;&amp; integerNumber &gt;= 1; i--) {
              number[i] = integerNumber % 2 == 1;
              integerNumber &gt;&gt;= 1;
          }
          if (isNegative) {
              number = new BigInt(number).not().add(ONE).number;
          }
      }
  
      public BigInt(String binaryString) throws InvalidBinaryStringException {
          this();
          for (int i = binaryString.length() - 1, j = number.length - 1;
               i &gt;= 0 &amp;&amp; j &gt;= 0; i--, j--) {
              if (binaryString.charAt(i) != '1' &amp;&amp; binaryString.charAt(i) != '0') {
                  throw new InvalidBinaryStringException(binaryString);
              }
              number[j] = (binaryString.charAt(i) - '0') == 1;
          }
      }
  
      public BigInt(BigInt copy) {
          this();
          System.arraycopy(copy.number, 0, number, 0, copy.number.length);
      }
  
      public BigInt add(BigInt component) {
          BigInt a, b;
          BigInt x = new BigInt(this);
          BigInt y = new BigInt(component);
          do {
              a = x.and(y);
              b = x.xor(y);
              x = a.shiftLeft(1);
              y = b;
          } while (!a.equals(ZERO));
          return b;
      }
  
      public BigInt sub(BigInt subtrahend) {
          return add(subtrahend.not().add(new BigInt(ONE)));
      }
  
      public BigInt mul(BigInt multiplier) {
          BigInt m = new BigInt(ONE), z = new BigInt(ZERO);
          BigInt x = new BigInt(this), y = new BigInt(multiplier);
  
          if (x.lessThen(ZERO)) {
              x = x.not().add(ONE);
              y = y.not().add(ONE);
          }
  
          while (x.greaterThenEqual(m) &amp;&amp; !y.equals(ZERO)) {
              if (!x.and(m).equals(ZERO)) {
                  z = y.add(z);
              }
              y = y.shiftLeft(1);
              m = m.shiftLeft(1);
          }
          return z;
      }
  
      public BigInt div(BigInt divisor) {
          BigInt mask = new BigInt(ONE);
          BigInt quotient = new BigInt(ZERO);
  
          BigInt numerator = new BigInt(this), denominator = new BigInt(divisor);
  
          if (numerator.lessThen(ZERO)) {
              numerator = numerator.not().add(ONE);
          }
  
          if (denominator.lessThen(ZERO)) {
              denominator = denominator.not().add(ONE);
          }
  
          while (denominator.lessThenEqual(numerator)) { // PROBLEM
              denominator = denominator.shiftLeft(1);
              mask = mask.shiftLeft(1);
          }
  
          while (mask.greaterThen(ONE)) {
              denominator = denominator.shiftRight(1);
              mask = mask.shiftRight(1);
              if (numerator.greaterThenEqual(denominator)) {
                  numerator = numerator.sub(denominator);
                  quotient = quotient.or(mask);
              }
          }
  
          if (number[0] != divisor.number[0]) {
              return quotient.not().add(ONE);
          }
          return quotient;
      }
  
  
      public BigInt mod(BigInt y) {
          // (x - y*(x/y))
          BigInt x = new BigInt(this);
          BigInt right = x.div(y);
          BigInt mid = y.mul(right);
          return x.sub(mid);
      }
  
      //completly inefficient for numbers larger than 32 bit
      @Deprecated
      public BigInt div2(BigInt divisor) {
          BigInt c = new BigInt(ZERO), sign = new BigInt(ZERO);
          BigInt x = new BigInt(this), y = new BigInt(divisor);
          if (x.lessThen(ZERO)) {
              x = x.not().add(ONE);
              sign = sign.xor(ONE);
          }
  
          if (y.lessThen(ZERO)) {
              y = y.not().add(ONE);
              sign = sign.xor(ONE);
          }
  
          if (!y.equals(ZERO)) {
              while (x.greaterThenEqual(y)) {
                  x = x.sub(y);
                  c = c.add(ONE);
              }
          }
  
          if (!sign.equals(ZERO)) {
              c = c.not().add(ONE);
          }
          return c;
      }
  
      //doesn't work for big numbers close to maximum bit
      @Deprecated
      public BigInt mod2(BigInt mod) {
          BigInt y = new BigInt(this);
          BigInt x = new BigInt(mod);
  
          BigInt p = new BigInt(x);
  
          if (y.lessThen(ZERO)) {
              y = y.not().add(ONE);
          }
  
          if (p.lessThen(ZERO)) {
              p = p.not().add(ONE);
              x = x.not().add(ONE);
          }
  
          while (p.lessThen(y)) {         //forever loop
              p = p.shiftLeft(1);
          }
  
          while (p.greaterThenEqual(x)) {
              if (y.greaterThenEqual(p)) {
                  y = y.sub(p);
              }
              p = p.shiftRight(1);
          }
  
          if (number[0]) {
              y = y.not().add(ONE);
          }
          return y;
      }
  
      @Override
      public boolean equals(Object obj) {
          if (obj == null)
              return false;
          if (obj == this)
              return true;
          if (!(obj instanceof BigInt))
              return false;
  
          BigInt bigInt = (BigInt) obj;
          for (int i = 0; i &lt; bigInt.number.length; i++) {
              if (number[i] != bigInt.number[i]) {
                  return false;
              }
          }
          if (!endianness.equals(bigInt.endianness)) {
              return false;
          }
          return true;
      }
  
      public boolean lessThen(BigInt num) {
          if (equals(num)) {
              return false;
          }
          if (number[0] &amp;&amp; !num.number[0]) {
              return true;
          } else if (!number[0] &amp;&amp; num.number[0]) {
              return false;
          }
          BigInt left = null, right = null;
          if (number[0]) {
              left = not().add(ONE);
              right = num.not().add(ONE);
          } else {
              left = this;
              right = num;
          }
          for (int i = 1; i &lt; number.length; i++) {
              if (left.number[i] != right.number[i]) {
                  if (number[0]) {
                      return !(!left.number[i] &amp;&amp; right.number[i]);
                  } else {
                      return !left.number[i] &amp;&amp; right.number[i];
                  }
              }
          }
          return false;
      }
  
      public boolean lessThenEqual(BigInt num) {
          if (equals(num)) {
              return true;
          }
          return lessThen(num);
      }
  
      public boolean greaterThen(BigInt num) {
          return !lessThen(num);
      }
  
      public boolean greaterThenEqual(BigInt num) {
          if (equals(num)) {
              return true;
          }
          return greaterThen(num);
      }
  
      /**
       * BITWISE OPERATORS*
       */
      //logical bitwise shift lefts
      public BigInt shiftLeft(int n) {
          //IT WORKS BECAUSE NEW OBJECT IS SET TO 0;
          BigInt shifted = new BigInt();
          for (int i = 0; i &lt; number.length - n; i++) {
              shifted.number[i] = number[i + n];
          }
          return shifted;
      }
  
      //logical bitwise shift right
      public BigInt shiftRight(int n) {
          BigInt shifted = new BigInt();
          for (int i = number.length - 1; i &gt;= n; i--) {
              shifted.number[i] = number[i - n];
          }
          boolean sign = number[0];
  
          for (int i = 0; i &lt; n; i++) {
              shifted.number[i] = sign;
          }
          return shifted;
      }
  
      //bitwise or |
      public BigInt or(BigInt num) {
          BigInt newInt = new BigInt();
          for (int i = 0; i &lt; number.length; i++) {
              newInt.number[i] = number[i] | num.number[i];
          }
          return newInt;
      }
  
      //bitwise and &amp;
      public BigInt and(BigInt num) {
          BigInt newInt = new BigInt();
          for (int i = 0; i &lt; number.length; i++) {
              newInt.number[i] = number[i] &amp; num.number[i];
          }
          return newInt;
      }
  
      //bitwise exclusive or ^
      public BigInt xor(BigInt num) {
          BigInt newInt = new BigInt();
          for (int i = 0; i &lt; number.length; i++) {
              newInt.number[i] = number[i] ^ num.number[i];
          }
          return newInt;
      }
  
      public BigInt not() {
          BigInt negate = new BigInt();
          for (int i = 0; i &lt; number.length; i++) {
             negate.number[i] = !number[i];
          }
          return negate;
      }
  
      @Override
      public String toString() {
        /* StringBuilder binaryRepr = new StringBuilder();
          for (byte b : number) {
              binaryRepr.append(b);
          }*/
  
         String decRepr = "";
          BigInt copy = new BigInt(this);
  
          if (copy.lessThen(ZERO)) {
              copy = copy.not().add(ONE);
          }
  
          while (copy.greaterThenEqual(ONE)) {
              BigInt rem = copy.mod(TEN);
              copy = copy.div(TEN);
              decRepr = String.valueOf(Integer.parseInt(getDecimalRemainder(rem), 2)) + decRepr;
          }
  
          if (number[0]) {
              return "-" + decRepr;// + binaryRepr.toString();
          }
          return decRepr;// + binaryRepr.toString();
          //return binaryRepr.toString();
      }
  
      private String getDecimalRemainder(BigInt copy) {
          String decimalString = "";
  
          for (int i = copy.number.length - 1; i &gt;= copy.number.length - 4; i--) {
              decimalString = (copy.number[i] ? "1" : "0") + decimalString;
          }
          return decimalString;
      }
  
      public String toBinaryString() {
          StringBuilder binaryString = new StringBuilder();
          boolean isFirstBit = false;
          for (boolean b: number) {
              if (b) {
                  isFirstBit = true;
              }
              if (isFirstBit) {
                  binaryString.append(b);
              }
          }
          return binaryString.toString();
      }
  
      public static BigInt nextBigInt(BigInt min, BigInt max) {
          BigInt pseudo = new BigInt();
          Random rnd = new Random();
          for (int i = 2; i &lt; pseudo.number.length; i++) {
              pseudo.number[i] = rnd.nextBoolean();
          }
          return pseudo.mod(max).add(min);
      }
  
  
      public static void main(String[] args) {
          String big = "";
          for(int i = 0; i &lt; 126; i++) {
              big += "1";
          }
          StopWatch stopWatch = new StopWatch();
          System.out.println(new BigInt(big));
          System.out.println(stopWatch.elapsedTime());
      }
  }
  </code></pre>