Thread for posting tiny primes - Page 24

3.14159 · 2010-09-04, 22:42

Quote:

Originally Posted by 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.)

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.

3.14159 · 2010-09-04, 23:02

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)

CRGreathouse · 2010-09-05, 02:03

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.

3.14159 · 2010-09-05, 02:09

Quote:

Originally Posted by Charles

The closer you get to the metal, the more efficient your code can be.

Agreed.

Quote:

Originally Posted by 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.

Actually, you can download it yourself and try it here. I doubt that it is written in Java, or else I could not access it.

Quote:

Originally Posted by 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.

I see.

Quote:

Originally Posted by 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.

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

CRGreathouse · 2010-09-05, 02:28

Quote:

Originally Posted by 3.14159

Actually, you can download it yourself and try it here. I doubt that it is written in Java, or else I could not access it.

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.

3.14159 · 2010-09-05, 02:28

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

Quote:

Originally Posted by 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.

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:

Originally Posted by 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...?)

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

Quote:

Originally Posted by Charles

1. It uses a slow algorithm.

I would hardly call trial division to 10⁶ in about 2.5 seconds slow.

CRGreathouse · 2010-09-05, 02:37

Quote:

Originally Posted by 3.14159

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

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 and those who don't!

3.14159 · 2010-09-05, 02:38

Quote:

Originally Posted by 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!

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

Quote:

Originally Posted by Charles

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

Prove it.

CRGreathouse · 2010-09-05, 02:42

Quote:

Originally Posted by 3.14159

I would hardly call trial division to 10⁶ in about 2.5 seconds slow.

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.

CRGreathouse · 2010-09-05, 02:43

Quote:

Originally Posted by 3.14159

Prove it.

No thanks.

3.14159 · 2010-09-05, 02:44

Quote:

Originally Posted by 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.

The app time for the p10 was <1 second.

Quote:

Originally Posted by Charles

No thanks.

Caught, red-handed!

Next!

2010-09-04, 23:02	#255
3.14159 May 2010 Prime hunting commission. 2⁴·3·5·7 Posts	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) Last fiddled with by 3.14159 on 2010-09-04 at 23:06

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Prime posting thread, part 2. (With a catch.)	3.14159	Miscellaneous Math	55	2010-11-19 23:55
Tiny range request .... 555.1M	petrw1	LMH > 100M	1	2010-07-13 15:35
Other primes thread	nuggetprime	No Prime Left Behind	32	2009-10-21 21:48
Error: tiny factoring failed	10metreh	Msieve	26	2009-03-08 23:28
Tiny error on nfsnet pages.	antiroach	NFSNET Discussion	1	2003-07-08 00:27

2010-09-05, 02:03	#256
CRGreathouse Aug 2006 3×1,993 Posts	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.