What a difference 30 years makes!
 

Here's an interesting quote from "What Drives An Aliquot Sequence?", from Mathematics of Computation, 1975. This is regarding the 276 sequence, and the state-of-the-art knowledge back then:[quote]Lehmer has computed a further 200 terms which show an erratic upward tendency. The extent of our present knowledge is[indent]107100047962427456048833497403019424 = 276:433 = [tex]2^53*199*c[/tex][/indent]where [i][b]c[/b][/i] is a 31-digit composite with no small factors.[/quote]Kinda unbelievable when you think about it....

BTW, the c31 factors as 1171449981591251 * 4785657413964331.

[quote=schickel;167217]BTW, the c311 factors as 1171449981591251 * 4785657413964331.[/quote]

When was it a C311? (I wonder whether we'll be onto C311s in 30 years' time...)

BTW, how long did it take to factor the C31, and what method was used?

[SIZE=1]{Heh, no "beat you to the edit" this time!}[/SIZE]

I don't know what method schickle used, but it took me less than a tenth of a second, not counting the time it took to type in the command:

[code]echo 107100047962427456048833497403019424 | ecm -t 200 -c 10 7000
GMP-ECM 6.2 [powered by GMP 4.2.2] [ECM]
Input number is 107100047962427456048833497403019424 (36 digits)
********** Factor found trial div: 2
Found proven prime factor of 1 digits: 2^5
********** Factor found trial div: 3
Found proven prime factor of 1 digits: 3
********** Factor found trial div: 199
Found proven prime factor of 3 digits: 199
Using B1=7000, B2=754806, polynomial x^1, sigma=4282110816
Step 1 took 44ms
Step 2 took 40ms
********** Factor found in step 2: 1171449981591251
Found probable prime factor of 16 digits: 1171449981591251
Probable prime cofactor 4785657413964331 has 16 digits

real 0m0.098s
user 0m0.096s
sys 0m0.004s[/code]

[quote=Mr. P-1;167228]I don't know what method schickle used, but it took me less than a tenth of a second, not counting the time it took to type in the command:

[code]echo 107100047962427456048833497403019424 | ecm -t 200 -c 10 7000
GMP-ECM 6.2 [powered by GMP 4.2.2] [ECM]
Input number is 107100047962427456048833497403019424 (36 digits)
********** Factor found trial div: 2
Found proven prime factor of 1 digits: 2^5
********** Factor found trial div: 3
Found proven prime factor of 1 digits: 3
********** Factor found trial div: 199
Found proven prime factor of 3 digits: 199
Using B1=7000, B2=754806, polynomial x^1, sigma=4282110816
Step 1 took 44ms
Step 2 took 40ms
********** Factor found in step 2: 1171449981591251
Found probable prime factor of 16 digits: 1171449981591251
Probable prime cofactor 4785657413964331 has 16 digits

real 0m0.098s
user 0m0.096s
sys 0m0.004s[/code][/quote]

I mean, what method was originally used?

[QUOTE=Mr. P-1;167228]I don't know what method schickle used, but it took me less than a tenth of a second, not counting the time it took to type in the command:[/QUOTE]Read a little closer.....that was [b]quoted from an article from 1975[/b].

I was comparing "state of the art" then and now......

[QUOTE=10metreh;167229]I mean, what method was originally used?[/QUOTE]I don't know. It was factored some time after the original 1975 article.....I guess someone could contact Lehmer and see if he remembers factoring it way back then.

[quote=schickel;167231]I don't know. It was factored some time after the original 1975 article.....I guess someone could contact Lehmer and see if he remembers factoring it way back then.[/quote]

I thought he had died back in '91 or some time around then.

[QUOTE=10metreh;167232]I thought he had died back in '91 or some time around then.[/QUOTE]
OK, we could call Jennifer Love Hewitt, then.....:razz:

[QUOTE=schickel;167230]Read a little closer.....that was [b]quoted from an article from 1975[/b].

I was comparing "state of the art" then and now......[/QUOTE]

I understood the point of your post. I took 10metreh's question to mean how long did it take [i]you[/i] to factorize using today's technology. (I assumed that you had, since you posted the factors.)

The point being that what was infeasible in 1975 took less than a tenth of a second in 2009 on a commodity processor which was nowhere near the fastest available even when I bought it three years ago.

I wonder how much of the advance in 30 years has been due to faster hardware, and how much due to better algorithms.

[QUOTE=Mr. P-1;167249]I wonder how much of the advance in 30 years has been due to faster hardware, and how much due to better algorithms.[/QUOTE]

I doubt whether faster hardware could've contributed to more than a factor of 1e6 in performance gain in 30 years.

So, my vote is for the bulk of the improvement due to faster algos.

[quote=Mr. P-1;167249]I understood the point of your post. I took 10metreh's question to mean how long did it take [I]you[/I] to factorize using today's technology. (I assumed that you had, since you posted the factors.)

The point being that what was infeasible in 1975 took less than a tenth of a second in 2009 on a commodity processor which was nowhere near the fastest available even when I bought it three years ago.

I wonder how much of the advance in 30 years has been due to faster hardware, and how much due to better algorithms.[/quote]

Well, [url=http://en.wikipedia.org/wiki/Pollard's_rho_algorithm]Pollard's Rho[/url] algorithm was available at some point in 1975, and with a commodity processor I can factor the C31 in about 20 seconds using Rho with 10e6 iterations on the poly x^2 + 1. Admittedly this is using Brent's faster variation, which wasn't available until 1980. If "infeasible" is defined as 1 week, then this is at least 30 thousand times faster hardware.

With QS it factors in 3 hundredths of a second on the same processor, so algorithms contribute another ~700x speed improvement.

I programmed the original Pollard Rho in UBASIC and inserted a counter to find how many iterations are needed. The output was 38905704.

[QUOTE=bsquared;167262]Well, [url=http://en.wikipedia.org/wiki/Pollard's_rho_algorithm]Pollard's Rho[/url] algorithm was available at some point in 1975, and with a commodity processor I can factor the C31 in about 20 seconds using Rho with 10e6 iterations on the poly x^2 + 1. Admittedly this is using Brent's faster variation, which wasn't available until 1980. If "infeasible" is defined as 1 week, then this is at least 30 thousand times faster hardware.

With QS it factors in 3 hundredths of a second on the same processor, so algorithms contribute another ~700x speed improvement.[/QUOTE]

It occurs to me that "better algorithms" and "faster hardware" aren't the only two factors. A third perhaps is "availability". Even if the number could have been factored in a week using the hardware and algorithms of the time, it's possible that the researchers did not have a week's worth of processor time to spend on it.

[quote=Mr. P-1;167297]It occurs to me that "better algorithms" and "faster hardware" aren't the only two factors. A third perhaps is "availability". Even if the number could have been factored in a week using the hardware and algorithms of the time, it's possible that the researchers did not have a week's worth of processor time to spend on it.[/quote]

Very true, and certainly availablity of computing power has drastically increased as well since 1975 (another corollary to Moore's law?). I guess my original point is that unless they spent less than ~ 20sec*700 = 4 hrs on it with Rho, the majority of the speedup appears to be hardware, not algorithms, for this size number. Assuming, of course, that the relative speed ratio between my modern day Rho and QS would have been the same in 1975 if QS had existed then.

[QUOTE=Mr. P-1;167249]I understood the point of your post. I took 10metreh's question to mean how long did it take [i]you[/i] to factorize using today's technology. (I assumed that you had, since you posted the factors.)
[/QUOTE]I have to apologize, since when I first read your reply, the forum skipped over 10metreh's message entirely, and I didn't see his question until the second time reading replies, so I thought you were replying to my original message.. (I've seen that before, sometimes reading "new replies" starts at a later reply....the perils of live reading, I guess....)

I guess the real question is, does someone have some old hardware we could run this stuff on? I have a 10+ year old PC, unfortunately, it won't boot no more. :sad: (I keep thinking I should pull the HD and see if there's anything I need on there.)

[quote=schickel;167378]I guess the real question is, does someone have some old hardware we could run this stuff on? I have a 10+ year old PC, unfortunately, it won't boot no more. :sad: (I keep thinking I should pull the HD and see if there's anything I need on there.)[/quote]

I guess someone could write a REALLY SLOW implementation of Pollard's original rho method... :wink:

What a difference another three years make!
Greetings from 21-Dec-2012!

You will be pleased to know that in 2012, all your sequences are belong to us!

[QUOTE=schickel;167378]I guess the real question is, does someone have some old hardware we could run this stuff on? I have a 10+ year old PC, unfortunately, it won't boot no more. :sad: (I keep thinking I should pull the HD and see if there's anything I need on there.)[/QUOTE]Yup.

What do you want? The oldest machine I have powered up at the moment is relatively new but there's a fair chance I could get something running from the 1970s.

You might have to provide software on 8" floppies ...

Paul

According to wikipedia, CFRAC was translated into a computer-friendly algorithm around 1975, so that may have been the most advanced algorithm available. Without a lot of tweaks, even CFRAC would huff and puff trying to factor a C31.

[QUOTE=xilman;167937]Yup.

What do you want? The oldest machine I have powered up at the moment is relatively new but there's a fair chance I could get something running from the 1970s.

You might have to provide software on 8" floppies ...

Paul[/QUOTE]
Sorry, I lost my last 8" floppy after someone ironed it after trying to stuff it in a 3.5" drive....:sad:

is that some sort of april fool's joke? it's hard to believe that actually happened.

[QUOTE=Joshua2;167974]is that some sort of april fool's joke? it's hard to believe that actually happened.[/QUOTE]:innocent: :whistle:

You caught me.....that's an amalgamation of a couple of different tech support urban legends.

[QUOTE=jasonp;167940]According to wikipedia, CFRAC was translated into a computer-friendly algorithm around 1975, so that may have been the most advanced algorithm available. Without a lot of tweaks, even CFRAC would huff and puff trying to factor a C31.[/QUOTE]Resurrecting this old thread...

Just downloaded a copy of [B]The Aliquot Project: [I]An Application of Job Chaining to Number Theoretic Computing[/I][/B][SUP]1[/SUP] by M. C. Wunderlich.

This sheds a little light on what he was using back then. After some discussion of the properties of Aliquot Sequences, he talks about a framework that was being built to automate the production of sequences. Hardware is given as being an IBM 360/70[sup]2[/sup] computer running HASP. (A time of <12 seconds to generate an [TEX]N\pm1[/TEX] primality proof for numbers less than 40 digits on such a system is given.)

In the main program, trial division was used (looks like maybe 1M as an upper bound). If the trial division was unsuccessful, the composite was submitted to an external factoring utility. If a quick method (maybe Pollard's Monte Carlo method) could not factor it, another, longer, job was submitted to factor it.[quote=Wunderlich]We already have a very successful version of Brillhart's continued fraction program which submits a sequence of small jobs each of which generates a collection of factored quadratic residues. When a large enough collection of factored residues are generated, a 1 minute program is submitted which completes the factorization proces by doing a Gaussian elimination on a very large (360,000 bytes) 0-1 matrix.[/quote]One example is given in the article:[quote=Wunderlich]One of our 36 digit factorizations took from Wednesday afternoon to Saturday morning to complete its work, going trhough a chain of 10 twenty minute jobs.[/quote]So it looks like ~3 hours wall time to factor a 36 digit number, though it probably would have been impossible to wangle 3 consecutive hours of time on a heavily used computer. So the wait must have been almost unbearable: 3 hours to do 36 digits, but having it spread out over 3 days. Talk about suspense!

-----------

[SUP]1[/SUP][I]Proceedings of the 1976 ACM Symposium on Symbolic and Algrebraic Computing.[/I] Unfortunately, ACM has not opened up their article archives yet. Luckily I had $15 sitting unused on a gift card......might as well burn it on something interesting.

[sup]2[/sup]A nice description of a 360/70 is given [URL="http://www.bobseidel.com/columns/history4.html"]here[/URL].