Re: Simple integer factorization algorithm

On Fri, 28 Nov 2008 19:59:58 -0800 (PST), JSH <jstevh@xxxxxxxxx>
wrote:

I'd like code to test the algorithm, please.
Since I have run some tests on James' algorithm in the past, here is
part of my test code. This does the timing of the factoring algorithm
over a range of bit sizes to get an impression of how the algorithm
scales with the size of the target number.

Standard Java imports are:

import java.math.BigInteger;
import java.util.Random;

There are also two of my own utility classes, Stopwatch and Tuple2.

Stopwatch is a simple timer, methods start(), stop(), elapsed() and
reset() do the obvious. elapsed() returns microseconds.

Tuple2 is a simple generic two member tuple. getM1() returns the
first member and getM2() returns the second member. The constructor
takes two parameters corresponding to the two members.

The method jshFactor() is just a stub as I have not looked in detail
at James' current version of his method. I only have code to hand for
some of the earlier versions of his method(s).

Careful with line wrap on some of the longer print statements.

//// Begin Code ////

private static Random mRand = new Random();

/** Times the factorisation algorithm over a range of bit sizes. */
static private void main(String[] args) {
final int loBits = 16;
final int hiBits = 24;
final int bitStep = 2;
final int numTests = 200;

int misfactors;
Tuple2<Integer, Integer> result;
Stopwatch sw = new Stopwatch();
System.out.printf("%n%nAverage timings over %d numbers:%n",
numTests);
for (int bits = loBits; bits <= hiBits; bits += bitStep) {
// Set up numbers to factor
int[] numbers = new int[numTests];
for (int i = 0; i < numTests; ++i) {
numbers[i] = makeComposite(bits);
}

// Time factoring
misfactors = 0;
sw.reset();
sw.start();
for (int num : numbers) {
result = jshFactor(num);
if (result.getM1() * result.getM2() != num) {
++misfactors; }
}
sw.stop();
System.out.printf(" %d bits: %9.3f mSec average per
number. " +
"%d misfactors.%n",
bits, (sw.elapsed() * 1000.0) / numTests, misfactors);
} // end for

System.out.println("Finished.");

} // end timerTest()

/** Creates random composite with two unequal prime factors */
private static int makeComposite(int bitSize) {
final int size1 = bitSize / 2;
final int size2 = bitSize - size1;
BigInteger factor1 = BigInteger.probablePrime(size1, mRand);
BigInteger factor2;
do {
factor2 = BigInteger.probablePrime(size2, mRand);
} while(factor1.equals(factor2));
return factor1.multiply(factor2).intValue();
} // end makeComposite()

/** Runs the JSH Factorisation algorithm. Currently a stub. */
static Tuple2<Integer, Integer> jshFactor(int num) {
// Dummy return
return new Tuple2(num, 1);
} // end jshFactor

//// End Code ////

//// Sample Output ////

Average timings over 200 numbers:
16 bits: 1157.902 mSec average per number. 0 misfactors.
18 bits: 7751.154 mSec average per number. 0 misfactors.
20 bits: 48874.328 mSec average per number. 0 misfactors.
22 bits: 331362.618 mSec average per number. 0 misfactors.
24 bits: 2202700.117 mSec average per number. 0 misfactors.
Finished.

//// End Sample Output ////
.

Relevant Pages

  • Re: JSH: One other option
    ... away any factoring of surrogates. ... JSH claims to be a programmer. ... int SF ... Because all that Java development was done on the company ...
    (sci.math)
  • Re: Local variables controversial?
    ... > amounts to pushing some items on a stack and offsetting a stack ... > As for your other comments about factoring in other languages, ... While Forth allows finer-grained factoring, ... inline int add ...
    (comp.lang.forth)
  • Re: JSH: One other option
    ... away any factoring of surrogates. ... JSH claims to be a programmer. ... int SF ...
    (sci.math)