James,

You appear to abhor the notion of backing up your claims
with solid evidence, much less proof. You'd rather simply
accuse others of lying about your work.

Here's another, more objective approach to comparing claims
about factoring. I took a list of numbers which you recently
posted with your results. Your program failed to factor
about half of them and there was no elapsed time data
provided by you.

Below is the list with results from a quick program I threw
together *with* elapsed times.

Program to factor integers with benchmark timer
(COMPAQ Presario Laptop, 2GHz Pentium 4)
-----------------------------------------------

Input a positive integer: 1996465633
Prime Factor: 35141
Prime Factor: 56813
Elapsed time: 0.090738 msec

Input a positive integer: 2348221831
Prime Factor: 48073
Prime Factor: 48847
Elapsed time: 0.012504 msec

Input a positive integer: 3574886741
Prime Factor: 57679
Prime Factor: 61979
Elapsed time: 0.028172 msec

Input a positive integer: 3172590413
Prime Factor: 54949
Prime Factor: 57737
Elapsed time: 0.020424 msec

Input a positive integer: 2514657533
Prime Factor: 43991
Prime Factor: 57163
Elapsed time: 0.062648 msec

Input a positive integer: 1388161393
Prime Factor: 36217
Prime Factor: 38329
Elapsed time: 0.017706 msec

Input a positive integer: 2335689907
Prime Factor: 44281
Prime Factor: 52747
Elapsed time: 0.044006 msec

Input a positive integer: 2493433781
Prime Factor: 41879
Prime Factor: 59539
Elapsed time: 0.07928 msec

Input a positive integer: 1840902013
Prime Factor: 39451
Prime Factor: 46663
Elapsed time: 0.039426 msec

Input a positive integer: 2095611269
Prime Factor: 42751
Prime Factor: 49019
Elapsed time: 0.03484 msec

Notice that (1) *all* given numbers were factored in less
than 100 microseconds and, (2) I have made no claims
whatsoever about the value, quality or correctness of your
work. I have simply posted the results of a simple,
inelegant program with benchmark data against which you can
compare your own work.

Please post your results with benchmarks so we can compare
hard facts instead of unsupported blustering.

--
There are two things you must never attempt to prove: the
unprovable -- and the obvious.
--
Democracy: The triumph of popularity over principle.
--
http://www.crbond.com

From:	Chip Eastham
Subject:	Re: JSH: Benchmark challenge
Date:	23 Jan 2005 20:04:51 -0800

Christian Bau wrote:

> At which point do the more complicated methods overtake
> the simpler, slower ones in real life implementations?

In D. Bressoud's Factorization and Primality Testing (S-V,1989)
introducing Chapt. 8 on Quadratic Sieve methods, he suggests
that elliptic curve methods can fill the breach between "where
trial division becomes impossible until well into the range where
QS can be implemented, at least 25-30 digits."

I'd guess that most benchmarks are done with numbers that can
be assumed to have no small divisors, and maybe trial division
is not well modelled in some of these timings. Certainly you can
whip through the first 10,000 primes (the 10,000th = 104,729),
which exhausts the composites up to 10 digits or so.

regards, chip

From:	Christian Bau
Subject:	Re: JSH: Benchmark challenge
Date:	Mon, 24 Jan 2005 09:10:31 +0000

In article <1106537255.316447.25750@f14g2000cwb.googlegroups.com>,
"Chip Eastham" wrote:

> Christian Bau wrote:
>
> > At which point do the more complicated methods overtake
> > the simpler, slower ones in real life implementations?
>
> In D. Bressoud's Factorization and Primality Testing (S-V,1989)
> introducing Chapt. 8 on Quadratic Sieve methods, he suggests
> that elliptic curve methods can fill the breach between "where
> trial division becomes impossible until well into the range where
> QS can be implemented, at least 25-30 digits."
>
> I'd guess that most benchmarks are done with numbers that can
> be assumed to have no small divisors, and maybe trial division
> is not well modelled in some of these timings. Certainly you can
> whip through the first 10,000 primes (the 10,000th = 104,729),
> which exhausts the composites up to 10 digits or so.

I might just for fun try to implement Pollard's method. If I read Knuth
right, it is supposed to run in roughly the square root of the second
largest prime factor if you include a primality test to avoid trying to
factor large primes. It should be faster than trial division for
relatively small numbers.

Then I re-read Knuth's description of Fermat's method and figured out
again what was wrong again (I had forgotten about it): If the largest
factor of N less than sqrt (N) is t * sqrt (N), 0 < t <= 1, then
Fermat's method takes time sqrt (N) * (1/t - t), which is excellent if t
is close to 1 but bad news if t is lets say 1/100.

From:	Jesse F. Hughes
Subject:	Re: JSH: Benchmark challenge
Date:	Sun, 23 Jan 2005 18:00:04 +0100

"C. Bond" writes:

> Program to factor integers with benchmark timer
> (COMPAQ Presario Laptop, 2GHz Pentium 4)
> -----------------------------------------------
>
> Input a positive integer: 1996465633
> Prime Factor: 35141
> Prime Factor: 56813
> Elapsed time: 0.090738 msec
>
> Input a positive integer: 2348221831
> Prime Factor: 48073
> Prime Factor: 48847
> Elapsed time: 0.012504 msec
>
> Input a positive integer: 3574886741
> Prime Factor: 57679
> Prime Factor: 61979
> Elapsed time: 0.028172 msec
>
> Input a positive integer: 3172590413
> Prime Factor: 54949
> Prime Factor: 57737
> Elapsed time: 0.020424 msec
>
> Input a positive integer: 2514657533
> Prime Factor: 43991
> Prime Factor: 57163
> Elapsed time: 0.062648 msec
>
> Input a positive integer: 1388161393
> Prime Factor: 36217
> Prime Factor: 38329
> Elapsed time: 0.017706 msec
>
> Input a positive integer: 2335689907
> Prime Factor: 44281
> Prime Factor: 52747
> Elapsed time: 0.044006 msec
>
> Input a positive integer: 2493433781
> Prime Factor: 41879
> Prime Factor: 59539
> Elapsed time: 0.07928 msec
>
> Input a positive integer: 1840902013
> Prime Factor: 39451
> Prime Factor: 46663
> Elapsed time: 0.039426 msec
>
> Input a positive integer: 2095611269
> Prime Factor: 42751
> Prime Factor: 49019
> Elapsed time: 0.03484 msec
>
> Notice that (1) *all* given numbers were factored in less
> than 100 microseconds and, (2) I have made no claims
> whatsoever about the value, quality or correctness of your
> work. I have simply posted the results of a simple,
> inelegant program with benchmark data against which you can
> compare your own work.
>
> Please post your results with benchmarks so we can compare
> hard facts instead of unsupported blustering.

Just for comparison, here's the output from a Linux box (2G AMD
Athlon) using the stock factor program (and the time program for
measuring time).

Strangely, my laptop (Intel 1.4G) gave considerably better times. No
idea why.

jesse@phiwumbda:~$ sh /tmp/f.sh
1996465633: 35141 56813

real 0m0.070s
user 0m0.000s
sys 0m0.010s
2348221831: 48073 48847

real 0m0.014s
user 0m0.000s
sys 0m0.010s
3574886741: 57679 61979

real 0m0.082s
user 0m0.000s
sys 0m0.010s
3172590413: 54949 57737

real 0m0.014s
user 0m0.000s
sys 0m0.010s
2514657533: 43991 57163

real 0m0.099s
user 0m0.000s
sys 0m0.010s
1388161393: 36217 38329

real 0m0.040s
user 0m0.000s
sys 0m0.010s
2335689907: 44281 52747

real 0m0.015s
user 0m0.000s
sys 0m0.010s
2493433781: 41879 59539

real 0m0.052s
user 0m0.000s
sys 0m0.010s
1840902013: 39451 46663

real 0m0.036s
user 0m0.010s
sys 0m0.000s
2095611269: 42751 49019

real 0m0.021s
user 0m0.010s
sys 0m0.000s

--
Jesse F. Hughes

"But you do talk a lot in posts on Usenet where you probably live out
some fantasy." -- James S. Harris

From:	David Kastrup
Subject:	Re: JSH: Benchmark challenge
Date:	Sun, 23 Jan 2005 21:03:21 +0100

"Jesse F. Hughes" writes:

> But maybe there was something funny about the load at the time. I
> just tried it again and *every* number was factored in 0m0.000s of
> user time and considerably less real time, too.

Considerably less real time than 0m0.000s is impressive. The factors
are returned before you even start the factorization? Just do some
heavy recursion on it, and you should be able to get the factorization
of 1024-bit numbers _years_ before you even start factoring.

--
David Kastrup, Kriemhildstr. 15, 44793 Bochum

From:	David C. Ullrich
Subject:	Re: JSH: Benchmark challenge
Date:	Sun, 23 Jan 2005 12:11:34 -0600

On Sun, 23 Jan 2005 18:00:04 +0100, "Jesse F. Hughes"
wrote:

>[...]
>
>Just for comparison, here's the output from a Linux box (2G AMD
>Athlon) using the stock factor program (and the time program for
>measuring time).
>
>Strangely, my laptop (Intel 1.4G) gave considerably better times. No
>idea why.

How much RAM do the two machines have?

************************

David C. Ullrich

From:	Jesse F. Hughes
Subject:	Re: JSH: Benchmark challenge
Date:	Sun, 23 Jan 2005 20:36:02 +0100

David C. Ullrich writes:

> On Sun, 23 Jan 2005 18:00:04 +0100, "Jesse F. Hughes"
> wrote:
>
>>[...]
>>
>>Just for comparison, here's the output from a Linux box (2G AMD
>>Athlon) using the stock factor program (and the time program for
>>measuring time).
>>
>>Strangely, my laptop (Intel 1.4G) gave considerably better times. No
>>idea why.
>
> How much RAM do the two machines have?

Roughly the same, 500M.

The desktop shows 515484K and the laptop 506316K and neither of them
should have been particularly busy at the moment.

I had run the command remotely on the desktop, which might increase
real time, but not user time (I think).

But maybe there was something funny about the load at the time. I
just tried it again and *every* number was factored in 0m0.000s of
user time and considerably less real time, too.

--
"Now I'm informing all of you that the people arguing against me are EVIL,
yes they are real, live EVIL people as mathematics is that important, so
it's important enough for Evil itself to send minions like them."
-- James Harris on Evil's interest in Algebraic Number Theory

From:	Mark Nudelman
Subject:	Re: Benchmark challenge
Date:	Sun, 23 Jan 2005 09:52:46 -0800

C. Bond wrote:
> James,
>
> You appear to abhor the notion of backing up your claims
> with solid evidence, much less proof. You'd rather simply
> accuse others of lying about your work.
>
> Here's another, more objective approach to comparing claims
> about factoring. I took a list of numbers which you recently
> posted with your results. Your program failed to factor
> about half of them and there was no elapsed time data
> provided by you.
>
> Below is the list with results from a quick program I threw
> together *with* elapsed times.

.... snip ...

> Notice that (1) *all* given numbers were factored in less
> than 100 microseconds and, (2) I have made no claims
> whatsoever about the value, quality or correctness of your
> work. I have simply posted the results of a simple,
> inelegant program with benchmark data against which you can
> compare your own work.
>
> Please post your results with benchmarks so we can compare
> hard facts instead of unsupported blustering.

James is claiming that his current program is just a prototype to test his
algorithm, and (implicitly) that there is therefore room for substantial
performance improvement. This is not an unreasonable argument. What would
be interesting is to see the performance of his (or your) algorithm on a
range of different sized numbers. This would give a rough idea of the
asymptotic behavior of the algorithm, showing whether it's exponential or
polynomial. If, for example, his algorithm factored a 30 digit number in
twice the time it takes to factor a 15 digit number, this would be
significant. Unfortunately, your numbers are all roughly the same size, so
this sample set isn't useful in determining this crucial piece of
information.

--Mark

From:	C. Bond
Subject:	Re: Benchmark challenge
Date:	Sun, 23 Jan 2005 23:29:30 GMT

Mark Nudelman wrote:

> C. Bond wrote:
> > James,
> >
> > You appear to abhor the notion of backing up your claims
> > with solid evidence, much less proof. You'd rather simply
> > accuse others of lying about your work.
> >
> > Here's another, more objective approach to comparing claims
> > about factoring. I took a list of numbers which you recently
> > posted with your results. Your program failed to factor
> > about half of them and there was no elapsed time data
> > provided by you.
> >
> > Below is the list with results from a quick program I threw
> > together *with* elapsed times.
>
> ... snip ...
>
> > Notice that (1) *all* given numbers were factored in less
> > than 100 microseconds and, (2) I have made no claims
> > whatsoever about the value, quality or correctness of your
> > work. I have simply posted the results of a simple,
> > inelegant program with benchmark data against which you can
> > compare your own work.
> >
> > Please post your results with benchmarks so we can compare
> > hard facts instead of unsupported blustering.
>
> James is claiming that his current program is just a prototype to test his
> algorithm, and (implicitly) that there is therefore room for substantial
> performance improvement. This is not an unreasonable argument.

James claimes that he has a "solution" to the factoring problem. A solution
consists of a theory and a supporting implementation. He has provided neither.

> What would be interesting is to see the performance of his (or your)
> algorithm on a
> range of different sized numbers. This would give a rough idea of the
> asymptotic behavior of the algorithm, showing whether it's exponential or
> polynomial. If, for example, his algorithm factored a 30 digit number in
> twice the time it takes to factor a 15 digit number, this would be
> significant. Unfortunately, your numbers are all roughly the same size, so
> this sample set isn't useful in determining this crucial piece of
> information.

My numbers were taken from a list of numbers to which James had already applied
his algorithm. I make no claimes about about exponential vs. polynomial times.
Only that he had posted his results on these numbers and I post mine -- with
benchmark timing.

--
There are two things you must never attempt to prove: the unprovable -- and the
obvious.
--
Democracy: The triumph of popularity over principle.
--
http://www.crbond.com

From:	Mark Nudelman
Subject:	Re: Benchmark challenge
Date:	Sun, 23 Jan 2005 18:34:31 -0800

C. Bond wrote:
> Mark Nudelman wrote:
>> What would be interesting is to see the performance of his (or your)
>> algorithm on a
>> range of different sized numbers. This would give a rough idea of
>> the asymptotic behavior of the algorithm, showing whether it's
>> exponential or polynomial. If, for example, his algorithm factored
>> a 30 digit number in twice the time it takes to factor a 15 digit
>> number, this would be significant. Unfortunately, your numbers are
>> all roughly the same size, so this sample set isn't useful in
>> determining this crucial piece of information.
>
> My numbers were taken from a list of numbers to which James had
> already applied his algorithm. I make no claimes about about
> exponential vs. polynomial times. Only that he had posted his results
> on these numbers and I post mine -- with benchmark timing.

Of course I know that it's essentially impossible that James has "solved"
factoring (that is, produced a polynomial-time algorithm) using the
high-school algebra methods that he's using. I'm just pointing out that
what you propose isn't a fair test of a factoring algorithm. It's logically
possible that a real polynomial-time algorithm, if one existed, would
perform poorly on small numbers, but overtake conventional methods on large
numbers. Based on James' statements about some of his factorizations of
small numbers taking "minutes", we know already that his program will not
beat your program. And the fact that he's using Java is a big handicap
right off the bat. (You didn't state -- what language is yours written in?)
As I said, a more interesting set of data would be the performance on a
range of numbers of different sizes. Unfortunately, if he's not using some
kind of BigNum package for math, we won't be able to get that kind of data.

--Mark

From:	Christian Bau
Subject:	Re: JSH: Benchmark challenge
Date:	Sun, 23 Jan 2005 22:14:43 +0000

In article <41F3CDEC.85DE24D9@ix.netcom.com>,
"C. Bond" wrote:

> Program to factor integers with benchmark timer
> (COMPAQ Presario Laptop, 2GHz Pentium 4)
> -----------------------------------------------
>
> Input a positive integer: 1996465633
> Prime Factor: 35141
> Prime Factor: 56813
> Elapsed time: 0.090738 msec

< similar times snipped >

Your program isn't by any chance using Fermat's method? It seems to be a
bit too fast for trial division.

From:	C. Bond
Subject:	Re: JSH: Benchmark challenge
Date:	Sun, 23 Jan 2005 23:31:10 GMT

Christian Bau wrote:

> In article <41F3CDEC.85DE24D9@ix.netcom.com>,
> "C. Bond" wrote:
>
> > Program to factor integers with benchmark timer
> > (COMPAQ Presario Laptop, 2GHz Pentium 4)
> > -----------------------------------------------
> >
> > Input a positive integer: 1996465633
> > Prime Factor: 35141
> > Prime Factor: 56813
> > Elapsed time: 0.090738 msec
>
> < similar times snipped >
>
> Your program isn't by any chance using Fermat's method? It seems to be a
> bit too fast for trial division.

Hi Christian,

If there is some interest in comparing factoring methods with benchmark
timings, I'll post the source code.

--
There are two things you must never attempt to prove: the unprovable -- and
the obvious.
--
Democracy: The triumph of popularity over principle.
--
http://www.crbond.com

From:	Christian Bau
Subject:	Re: JSH: Benchmark challenge
Date:	Mon, 24 Jan 2005 00:00:20 +0000

In article <41F43394.9DED9C3E@ix.netcom.com>,
"C. Bond" wrote:

> Christian Bau wrote:
>
> > In article <41F3CDEC.85DE24D9@ix.netcom.com>,
> > "C. Bond" wrote:
> >
> > > Program to factor integers with benchmark timer
> > > (COMPAQ Presario Laptop, 2GHz Pentium 4)
> > > -----------------------------------------------
> > >
> > > Input a positive integer: 1996465633
> > > Prime Factor: 35141
> > > Prime Factor: 56813
> > > Elapsed time: 0.090738 msec
> >
> > < similar times snipped >
> >
> > Your program isn't by any chance using Fermat's method? It seems to be a
> > bit too fast for trial division.
>
> Hi Christian,
>
> If there is some interest in comparing factoring methods with benchmark
> timings, I'll post the source code.

Yes, that would be welcome.

What I would be curious about: There are simple methods that anyone
without much mathematical background should easily understand (trial
division and Fermat's method), and then there are more complicated
methods (Pollard's method is still relatively simple, but what I would
call "real" mathematics). At which point do the more complicated methods
overtake the simpler, slower ones in real life implementations?