Java Dixon Factoring

// FILE: DixonMain.java
import java.math.BigInteger;
import java.util.Random;
import java.util.Scanner;

class DixonMain implements BigFactorTool
{
  private static final Random random = new Random();
  private static final Scanner scanner = new Scanner(System.in);
  public static final boolean debug = false;

  public static void main(String[] args)
  {
    if (args.length == 1)
    {
      BigInteger input = new BigInteger(args[0]);
      final DixonCommander commander = new DixonCommander();
      commander.setup(input);
      long start = System.nanoTime(), total;
      commander.start();
      total = System.nanoTime() - start;
      BigInteger[] factors = commander.result();
      if (debug)
      {
        System.out.println("Factored in " + (total / 1000000000.0) + " seconds");
        System.out.println("Factors: " + factors[0] + ", " + factors[1]);
      }
    } else if (args.length == 2)
    {
      BigInteger input = new BigInteger(args[0]);
      final DixonCommander commander = new DixonCommander();
      try
      {
        commander.setup(input, Integer.parseInt(args[1]));
      } catch (NumberFormatException e)
      {
        commander.setup(input);
      }
      long start = System.nanoTime(), total;
      commander.start();
      total = System.nanoTime() - start;
      BigInteger[] factors = commander.result();
      if (debug)
      {
        System.out.println("Factored in " + (total / 1000000000.0) + " seconds");
        System.out.println("Factors: " + factors[0] + ", " + factors[1]);
      }
    } else
    {
      String input, exit = "x";
      BigInteger[] factors;
      long start, total;
      do
      {
        System.out.print("Bits to Factor: ");
        input = scanner.next();
        try
        {
          start = System.nanoTime();
          factors = factor(Integer.parseInt(input));
          total = System.nanoTime() - start;
          System.out.println("Factored in " + (total / 1000000000.0) + " seconds");
          System.out.println("Factors: " + factors[0] + ", " + factors[1]);
        } catch (NumberFormatException e) {}
      } while (!input.equals(exit));
    }
  }

  public static BigInteger[] factor(final int bits)
  {
    return (new DixonMain()).factor(generateFactor(bits));
  }

  public static BigInteger generateFactor(final int bits)
  {
    final int hbits = bits / 2;
    final BigInteger a = BigInteger.probablePrime(hbits, random);
    final BigInteger b = BigInteger.probablePrime(bits - hbits, random)
    final BigInteger r = a.multiply(b);
    if (debug)
    {
      System.out.println("Input: " + r);
      System.out.println("Factor 1: " + a.toString());
      System.out.println("Factor 2: " + b.toString());
    }
    return r;
  }

  public BigInteger[] factor(final BigInteger n)
  {
    final DixonCommander commander = new DixonCommander();
    commander.setup(n);
    commander.start();
    return commander.result();
  }
}

// FILE: DixonCommander.java
import java.math.BigInteger;
import java.util.List;
import java.util.LinkedList;

class DixonCommander extends Thread
{
  // maximum 256 cores-->byte
  private static final byte cores = (byte) Runtime.getRuntime().availableProcessors();

  private final Object rowsLock = new Object();
  private final List<DixonRow> rows;
  private boolean ready = false;
  private DixonMonkey[] monkies;
  private DixonBanana banana;

  DixonCommander()
  {
    synchronized (rowsLock)
    {
      rows = new LinkedList<DixonRow>();
    }
    monkies = new DixonMonkey[cores - 1];
    if (DixonMain.debug)
      System.out.println("Constructed");
  }

  public void setup(final BigInteger n)
  {
    setup(n, (int) (30 * Math.exp(0.08 * n.bitLength())));
  }

  public void setup(final BigInteger n, int factorBase)
  {
    if (DixonMain.debug)
      System.out.println("Setting up...");
    final BigInteger[] base = DixonUtils.bigBase(factorBase);
    if (DixonMain.debug)
    {
      System.out.println("Base Size: " + base.length);
      for (BigInteger b : base)
        System.out.print(b + " ");
      System.out.print("\n");
    }
    banana = new DixonBanana(n, base, rows, (byte) monkies.length);
    for (byte monkey = 0; monkey < monkies.length; monkey++)
      monkies[monkey] = new DixonMonkey(banana);
    ready = true;
    if (DixonMain.debug)
      System.out.println("Complete");
  }

  public void run()
  {
    if (DixonMain.debug)
      System.out.println("Running...");
    if (!ready)
    {
      System.out.println("Not ready");
      return;
    }
    for (DixonMonkey monkey : monkies)
      monkey.start();
    banana.clear();
    for (DixonMonkey monkey : monkies)
      monkey.done();
  }

  public BigInteger[] result()
  {
    return banana.result();
  }
}

// FILE: DixonBanana.java
import java.math.BigInteger;
import java.util.concurrent.ConcurrentLinkedQueue;
import java.util.BitSet;
import java.util.List;
import java.util.LinkedList;

class DixonBanana
{
  private static final BigInteger ONE = BigInteger.ONE;

  public static final int chunkSize = 10000;
  private static final BigInteger bigChunkSize = BigInteger.valueOf(chunkSize);

  public final BigInteger n;
  public final byte monkies;
  public final BigInteger[] base;
  private BigInteger activeRow;
  private final ConcurrentLinkedQueue<DixonRow> incomingRows;
  private int waitingRows = 0;
  private final List<DixonRow> rows;
  private final BitSet columns;
  private List<DixonRow> xColumns;

  // for results
  private int resulting = 0;
  private final Object resultLock = new Object();
  private BigInteger result = null;

  DixonBanana(final BigInteger n, final BigInteger[] base, final List<DixonRow> rows, final byte monkies)
  {
    this.n = n;
    this.base = base;
    activeRow = DixonUtils.sqrt(n);
    this.rows = rows;
    incomingRows = new ConcurrentLinkedQueue<DixonRow>();
    columns = new BitSet(base.length);
    columns.set(0, base.length);
    xColumns = new LinkedList<DixonRow>();
    this.monkies = monkies;
  }

  public BigInteger next()
  {
    synchronized (activeRow)
    {
      BigInteger start = activeRow;
      activeRow = activeRow.add(bigChunkSize);
      return start;
    }
  }

  public void addRow(final DixonRow incomingRow)
  {
    incomingRows.offer(incomingRow);
    synchronized (rows)
    {
      if (waitingRows > 0)
      {
        rows.notifyAll();
        waitingRows = 0;
      }
    }
  }

  public void addRows(List<DixonRow> r)
  {
    incomingRows.addAll(r);
    synchronized (rows)
    {
      if (waitingRows > 0)
      {
        rows.notifyAll();
        waitingRows = 0;
      }
    }
  }

  private void waitRow()
  {
    try
    {
      synchronized (rows)
      {
        if (incomingRows.isEmpty())
        {
          waitingRows++;
          rows.wait();
        }
      }
    } catch (InterruptedException e) {}
  }

  public void clear()
  {
    long start = System.nanoTime();
    int rowIndex = 0;
    for (DixonRow currentRow;;)
    {
      waitRow();
      currentRow = incomingRows.poll();
      if (currentRow == null)
        continue;
      currentRow.setRow(rowIndex++);
      if (!columns.isEmpty())
      {
        for (int bit = columns.nextSetBit(0); bit >= 0; bit = columns.nextSetBit(bit + 1))
        {
          if (currentRow.bits.get(bit))
          {
            for (DixonRow col : xColumns)
            {
              if (currentRow.bits.get(bit))
              {
                currentRow.bits.xor(col.bits);
                currentRow.augmented.xor(col.augmented);
              }
            }
            for (DixonRow row : rows)
            {
              if (!row.flag && row.bits.get(bit))
              {
                row.bits.xor(currentRow.bits);
                row.augmented.xor(currentRow.augmented);
                if (checkRow(row))
                  return;
              }
            }
            currentRow.setFlag(bit);
            columns.clear(bit);
            xColumns.add(currentRow);
            if (columns.isEmpty() && DixonMain.debug)
              System.out.println("Cleared all columns");
            break;
          }
        }
      }
      if (!currentRow.flag)
      {
        for (DixonRow col : xColumns)
        {
          if (currentRow.bits.get(col.flagIndex))
          {
            currentRow.bits.xor(col.bits);
            currentRow.augmented.xor(col.augmented);
          }
        }
        if (checkRow(currentRow))
          return;
      }
      rows.add(currentRow);
    }
  }

  private boolean checkRow(DixonRow row)
  {
    if (!row.bits.isEmpty())
      return false;
    BigInteger r = row.r, fin, fr = row.fr;
    for (DixonRow col : xColumns)
    {
      if (row.augmented.get(col.row))
      {
        r = r.multiply(col.r);
        fr = fr.multiply(col.fr);
      }
    }
    fr = DixonUtils.sqrt(fr);
    fin = r;
    r = r.add(fr).gcd(n);
    if (!r.equals(ONE) && !r.equals(n))
    {
      if (DixonMain.debug)
      {
        System.out.println("Worked Row[" + row.r + ", " + row.fr + "]: " + row.bits);
        System.out.println("Final r: " + fin + ", Final f(r): " + fr);
      }
      notifyResult(r);
      return true;
    }
    return false;
  }

  private void notifyResult(BigInteger result)
  {
    synchronized (resultLock)
    {
      this.result = result;
      if (resulting > 0)
      {
        resultLock.notifyAll();
        resulting = 0;
      }
    }
    if (DixonMain.debug)
      System.out.println("Computation Complete.");
  }

  public BigInteger[] result()
  {
    try
    {
      synchronized (resultLock)
      {
        if (result == null)
        {
          resulting++;
          resultLock.wait();
        }
      }
    } catch (InterruptedException e)
    {
      return null;
    }
    return new BigInteger[] {result, n.divide(result)};
  }
}

// FILE: DixonMonkey.java
import java.math.BigInteger;
import java.util.BitSet;
import java.util.List;
import java.util.ArrayList;

class DixonMonkey extends Thread
{
  private static final BigInteger ZERO = BigInteger.ZERO;
  private static final BigInteger ONE = BigInteger.ONE;
  private static final BigInteger TWO = BigInteger.valueOf(2);

  private final DixonBanana banana;
  private boolean running;

  DixonMonkey(final DixonBanana banana)
  {
    this.banana = banana;
  }

  public void run()
  {
    if (DixonMain.debug)
      System.out.println("Monkey away!");
    running = true;
    BitSet set = new BitSet(banana.base.length);
    BigInteger[] checkMap;
    BigInteger ofr, fr, check;
    for (BigInteger r = banana.next(); running; r = banana.next())
    {
      for (int i = 0; i < banana.chunkSize && running; i++)
      {
        ofr = fr = r.multiply(r).mod(banana.n);
        for (int b = 0; b < banana.base.length; b++)
        {
          check = banana.base[b];
          while ((checkMap = fr.divideAndRemainder(check))[1].equals(ZERO))
          {
            fr = checkMap[0];
            set.flip(b);
          }
          if (fr.equals(ONE))
          {
            banana.addRow(new DixonRow(r, ofr, set));
            set = new BitSet(banana.base.length);
            break;
          } else
            set.clear();
        }
        r = r.add(ONE);
      }
    }
    if (DixonMain.debug)
      System.out.println("Monkey down!");
  }

  public void done()
  {
    running = false;
  }
}

// FILE: DixonRow.java
import java.math.BigInteger;
import java.util.BitSet;

class DixonRow
{
  public int row;
  public boolean flag = false;
  public int flagIndex = -1;
  public BigInteger r;
  public BigInteger fr;
  public BitSet bits;
  public BitSet augmented;

  DixonRow(final BigInteger r, final BigInteger fr, final BitSet bits)
  {
    this.r = r;
    this.fr = fr;
    this.bits = bits;
    augmented = new BitSet();
  }

  public void setRow(int row)
  {
    this.row = row;
    augmented.set(row);
  }

  public void setFlag(int fl)
  {
    flag = true;
    flagIndex = fl;
  }
}

// FILE: DixonUtils.java
import java.util.List;
import java.util.LinkedList;
import java.math.BigInteger;

final class DixonUtils
{
  private static final BigInteger ONE = BigInteger.ONE;
  private static final BigInteger TWO = BigInteger.valueOf(2);

  private DixonUtils() {}

  public static BigInteger[] bigBase(int limit)
  {
    // TODO: ignore 2, and make it only contain odd numbers?  2x improvement?
    limit--;
    boolean[] stream = makePrecacheBase(limit);
    final List<BigInteger> base = new LinkedList<BigInteger>();
    for (int i = 0, incr; i < limit; i++)
    {
      if (stream[i])
      {
        base.add(BigInteger.valueOf(incr = i + 2));
        for (int j = i + incr; j < limit; j += incr)
          stream[j] = false;
      }
    }
    return base.toArray(new BigInteger[base.size()]);
  }

  public static BigInteger sqrt(final BigInteger n)
  {
    BigInteger guess = ONE, antiguess = n.divide(guess), error;
    do
    {
      guess = guess.add(antiguess).divide(TWO);
      antiguess = n.divide(guess);
      error = guess.subtract(antiguess).abs();
    } while (error.compareTo(ONE) > 0);
    return guess;
  }

  private static boolean[] makePrecacheBase(int limit)
  {
    boolean[] base = new boolean[limit];
    while (limit-- > 0)
      base[limit] = true;
    return base;
  }
}

// FILE: BigFactorTool.java
import java.math.BigInteger;

interface BigFactorTool
{
  public BigInteger[] factor(BigInteger n);
}