[QUOTE=Batalov](Ironically enough, in this thread it only gets a #2 award, i.e. Generalized Proth, since there isn't a category for Generalized Fermat.)[/QUOTE]

How long did it take you to find this?

Also: I did not include Generalized Fermat because they were all previously discovered to any practical size and range.

But, you indeed get a top 5-k spot for number 2. In fact, you have found the largest prime for that particular category.

Trial-dividing competition!
 

An applet I have can currently use trial division to prove the primality of any 15-digit number in around 11-14 seconds.

Vs. A program I made in PARI for trial-dividing:

For the prime 5038546397:

Program: 17.8 seconds
Applet: < 1 second. (My best guess is between 0.6 and 0.9 seconds)

PFGW's trial-factoring option:
For the prime 880249016263951:
Applet: 39 seconds.
PFGW: ≈ 0.25 seconds. (My estimate)

The closer you get to the metal, the more efficient your code can be. Pari's quite high up; the numbers you deal with are not just multi-precision but dynamically typed, and every operation you do with them requires type checking and extra bignum hassle. So Pari isn't well-suited for low-level manipulations like sieving.

The applet is presumably a Java applet. Java has a just-in-time compiler: 'ordinarily' there's quite a bit of indirection like in Pari, but as things run the hot spots become reasonably efficient.

A directly compiled program like PFGW will be written in a traditional language like C, possibly with bits of inline assembly for the important parts. This lets you wring every last bit of performance out of the machine.


So you'd expect that Pari is the slowest, followed by the applet, followed by the compiled program... and that's just what you see.

[QUOTE=Charles]The closer you get to the metal, the more efficient your code can be.[/QUOTE]

Agreed.

[QUOTE=Charles]The applet is presumably a Java applet. Java has a just-in-time compiler: 'ordinarily' there's quite a bit of indirection like in Pari, but as things run the hot spots become reasonably efficient.
[/QUOTE]

Actually, you can download it yourself and try it [URL="http://www.naturalnumbers.org/"]here.[/URL] I doubt that it is written in Java, or else I could not access it.

[QUOTE=Charles]A directly compiled program like PFGW will be written in a traditional language like C, possibly with bits of inline assembly for the important parts. This lets you wring every last bit of performance out of the machine.
[/QUOTE]

I see.

[QUOTE=Charles]So you'd expect that Pari is the slowest, followed by the applet, followed by the compiled program... and that's just what you see.
[/QUOTE]

Also: About my PFGW estimate: It is actually closer to 1/6 of a second for the prime I showed.

[QUOTE=3.14159;228452]Actually, you can download it yourself and try it [URL="http://www.naturalnumbers.org/"]here.[/URL] I doubt that it is written in Java, or else I could not access it.[/QUOTE]

Generally speaking, being an "applet" implies that the program is in Java. (Further, I don't know why you think you wouldn't be able to run Java programs...?)

But OK, maybe it's not an applet but a different kind of program. Either it's another JIT language (say, C#), in which case the same explanation applies, or there's some other reason. These may include:
1. It uses a slow algorithm.
2. It's poorly written.
3. It's written in a low-performance language.
4. It's optimized for a different CPU.


I'm not sure of your example, now that I look. I just wrote out the straightforward Pari script for checking primality by trial division, and on this slow (Pentium D) machine it took only 1.5 milliseconds to prove that 5038546397 is prime, vs. your 17.8 seconds.

It took about three seconds to prove the primality of an 18-digit number.

[QUOTE=Charles]I'm not sure of your example, now that I look. I just wrote out the straightforward Pari script for checking primality by trial division, and on this slow (Pentium D) machine it took only 1.5 milliseconds to prove that 5038546397 is prime, vs. your 17.8 seconds.
[/QUOTE]

Are you sure? I'm going to make sure I didn't make an error there. Ah, shit! I remember. I tested the p15!

[QUOTE=Charles]Generally speaking, being an "applet" implies that the program is in Java. (Further, I don't know why you think you wouldn't be able to run Java programs...?)
[/QUOTE]

Only executables can be run as apps outside of the Internet. If it's Internet-based, JavaScript rules.

[QUOTE=Charles]1. It uses a slow algorithm.[/QUOTE]

I would hardly call trial division to 10[sup]6[/sup] in about 2.5 seconds slow.

[QUOTE=3.14159;228459]Only executables can be run as apps outside of the Internet. If it's Internet-based, JavaScript rules.[/QUOTE]

I'm a computer programmer; I have an excellent understanding of just what can be run on computers and how.

Javascript (or properly ECMAScript) is quite popular, but javascripts aren't called applets -- they're called scripts. Applets are (a subset of) Java programs. In particular, applets are Java programs designed to run in a sandbox from a browser (on a website).

From your general link I can't tell what you're referring to on that naturslnumbers site, so I can't tell you what it is. But please be careful with your terminology lest you confuse both those who understand [i]and[/i] those who don't!

[QUOTE=Charles]From your general link I can't tell what you're referring to on that naturslnumbers site, so I can't tell you what it is. But please be careful with your terminology lest you confuse both those who understand and those who don't!
[/QUOTE]

I'm practically a comp. illiterate. I can't help it!

[QUOTE=Charles]I'm a computer programmer; I have an excellent understanding of just what can be run on computers and how.
[/QUOTE]

[B]Prove it.[/B]

[QUOTE=3.14159;228459]I would hardly call trial division to 10[sup]6[/sup] in about 2.5 seconds slow.[/QUOTE]

Why? That's 30,000 to 100,000 processor cycles per prime, much too slow by my standards. Pari takes 300 Pentium D cycles (probably less than 200 Core 2 cycles) to do that.

[QUOTE=3.14159;228461][B]Prove it.[/B][/QUOTE]

No thanks.

[QUOTE=Charles]Why? That's 30,000 to 100,000 processor cycles per prime, much too slow by my standards. Pari takes 300 Pentium D cycles (probably less than 200 Core 2 cycles) to do that.
[/QUOTE]

The app time for the p10 was <1 second.

[QUOTE=Charles]No thanks.
[/QUOTE]

Caught, red-handed! :missingteeth: Next!