Re: JSH: Surrogate factoring, periodic behavior

On Sep 2, 4:08 am, rossum <rossu...@xxxxxxxxxxxx> wrote:
On Sun, 02 Sep 2007 00:03:28 -0000, JSH <jst...@xxxxxxxxx> wrote:
Here is output from my program and a run I just did testing out some
new theory.

Here for various reasons I won't explain I'm using k=30, starting with
n=1, and there is a lot wrong with this example from my standpoint as
by my theory I don't think it should have factored at this point.

java Factor 34587541

I wrote an instrumented version of my program and tried it with your
inputs. It factored the target with 160 probes:

target = 34587541
k = 30

trying n = 1, surrogate = 34589341
trying factor pair: (1, 34589341)
1 failed. -1 failed. 34589341 failed. -34589341 failed.
trying factor pair: (463, 74707)
463 failed. -463 failed. 74707 failed. -74707 failed.

trying n = 2, surrogate = 69176882
trying factor pair: (1, 69176882)
1 failed. -1 failed. 69176882 failed. -69176882 failed.
trying factor pair: (2, 34588441)
2 failed. -2 failed. 34588441 failed. -34588441 failed.

trying n = 3, surrogate = 103764423
trying factor pair: (1, 103764423)
1 failed. -1 failed. 103764423 failed. -103764423 failed.
trying factor pair: (3, 34588141)
3 failed. -3 failed. 34588141 failed. -34588141 failed.
trying factor pair: (7, 14823489)
7 failed. -7 failed. 14823489 failed. -14823489 failed.
trying factor pair: (21, 4941163)
21 failed. -21 failed. 4941163 failed. -4941163 failed.

trying n = 4, surrogate = 138351964
trying factor pair: (1, 138351964)
1 failed. -1 failed. 138351964 failed. -138351964 failed.
trying factor pair: (2, 69175982)
2 failed. -2 failed. 69175982 failed. -69175982 failed.
trying factor pair: (4, 34587991)
4 failed. -4 failed. 34587991 failed. -34587991 failed.
trying factor pair: (179, 772916)
179 failed. -179 failed. 772916 failed. -772916 failed.
trying factor pair: (199, 695236)
199 failed. -199 failed. 695236 failed. -695236 failed.
trying factor pair: (358, 386458)
358 failed. -358 failed. 386458 failed. -386458 failed.
trying factor pair: (398, 347618)
398 failed. -398 failed. 347618 failed. -347618 failed.
trying factor pair: (716, 193229)
716 failed. -716 failed. 193229 failed. -193229 failed.
trying factor pair: (796, 173809)
796 failed. -796 failed. 173809 failed. -173809 failed.
trying factor pair: (971, 142484)
971 failed. -971 failed. 142484 failed. -142484 failed.
trying factor pair: (1942, 71242)
1942 failed. -1942 failed. 71242 failed. -71242 failed.
trying factor pair: (3884, 35621)
3884 failed. -3884 failed. 35621 failed. -35621 failed.

trying n = 5, surrogate = 172939505
trying factor pair: (1, 172939505)
1 failed. -1 failed. 172939505 failed. -172939505 failed.
trying factor pair: (5, 34587901)
5 failed. -5 failed. 34587901 failed. -34587901 failed.
trying factor pair: (4583, 37735)
4583 failed. -4583 failed. 37735 failed. -37735 failed.
trying factor pair: (7547, 22915)
7547 failed. -7547 failed. 22915 failed. -22915 failed.

trying n = 6, surrogate = 207527046
trying factor pair: (1, 207527046)
1 failed. -1 failed. 207527046 failed. -207527046 failed.
trying factor pair: (2, 103763523)
2 failed. -2 failed. 103763523 failed. -103763523 failed.
trying factor pair: (3, 69175682)
3 failed. -3 failed. 69175682 failed. -69175682 failed.
trying factor pair: (6, 34587841)
6 failed. -6 failed. 34587841 failed. -34587841 failed.
trying factor pair: (239, 868314)
239 failed. -239 failed. 868314 failed. -868314 failed.
trying factor pair: (478, 434157)
478 failed. -478 failed. 434157 failed. -434157 failed.
trying factor pair: (717, 289438)
717 failed. -717 failed. 289438 failed. -289438 failed.
trying factor pair: (1434, 144719)
1434 failed. -1434 failed. 144719 failed. -144719 failed.

trying n = 7, surrogate = 242114587
trying factor pair: (1, 242114587)
1 failed. -1 failed. 242114587 failed. -242114587 failed.
trying factor pair: (11, 22010417)
11 failed. -11 failed. 22010417 failed. -22010417 failed.
trying factor pair: (13, 18624199)
13 failed. -13 failed. 18624199 failed. -18624199 failed.
trying factor pair: (19, 12742873)
19 failed. -19 failed. 12742873 failed. -12742873 failed.
trying factor pair: (121, 2000947)
121 failed. -121 failed. 2000947 failed. -2000947 failed.
trying factor pair: (143, 1693109)
143 failed. -143 failed. 1693109 failed. -1693109 failed.
trying factor pair: (209, 1158443)
209 failed. -209 failed. 1158443 failed. -1158443 failed.
trying factor pair: (247, 980221)
247 failed. -247 failed. 980221 failed. BINGO! -980221 succeeded

factor = 307
34587541 = 307 * 112663
160 probes total.

Looking at things this way you can see that your method is repeatedly
trying 1, -1, 2 and -2 when they only need to be tried once each. For
example you could try all possible small factors of S from, say -10 to
10, at the start and then ignore them whenever they occur later. That
would remove repeats of those small factors - which is where repeats
are a problem.

Your current work on determining the best choices of k and n for a
given T is good. The more you can narrow down the allowed ranges of k
and n the fewer failed probes your method will have and the faster it
will run.

rossum

The values for k and n that work are bounded by various relations
determinable by theory.

Now that has been my point.

This thread was supposed to be about two decision relations that tell
what conditions MUST be met for surrogate factoring to work, but
posters waylaid it in various ways including your claims that my
surrogate factoring implementation was worse than random.

But that's like some primitives playing with nuclear materials unable
to make an atomic bomb declaring ideas to be a trash idea because they
can't be bothered with the theory.

I repeat, you are like primitives who unable to get the big boom
declare it impossible, when you refuse to be bothered with theory.

First comes theory, then experimentation.

You people fiddle with the materials a bit, can't get a boom and then
declare it to be nothing.

And the world, God help it, depends on you.


James Harris

.

Relevant Pages

  • Re: JSH: Surrogate factoring, periodic behavior
    ... It factored the target with 160 probes: ... would remove repeats of those small factors - which is where repeats ... surrogate factoring implementation was worse than random. ... declare it impossible, when you refuse to be bothered with theory. ...
    (sci.math)
  • Re: JSH: Surrogate factoring, periodic behavior
    ... would remove repeats of those small factors - which is where repeats ... surrogate factoring implementation was worse than random. ... But that's like some primitives playing with nuclear materials unable ... declare it impossible, when you refuse to be bothered with theory. ...
    (sci.math)
  • Re: JSH: Contradictory behavior, issue of math fraud
    ... but accept the FACT that surrogate factoring is twice as slow as ... For example, random-gcd kicks out candidates just as fast as random (or pseudo-random) numbers can be generated, while James usually has you /in addition/ putzing around with systematically generating all two-integer factorizations of some other number too. ... Reverse average = 12.70 probes. ...
    (sci.math)
  • Re: JSH: Contradictory behavior, issue of math fraud
    ... [JSH] ... but accept the FACT that surrogate factoring is twice as slow as ... James usually has you /in addition/ putzing around with systematically ... Reverse average = 12.70 probes. ...
    (sci.math)
  • Re: JSH: Contradictory behavior, issue of math fraud
    ... but accept the FACT that surrogate factoring is twice as slow as ... James gets the factorisation of S "for free" - I ... Also it is worth mentioning that your count of "probes" potentially ... distort the success of surrogate factoring in the negative, ...
    (sci.math)
Quantcast