prime

Do you have a question? Post it now! No Registration Necessary.  Now with pictures!

•  Subject
• Author
• Posted on
•  prime
• George Mpouras
• 10-15-2014
# can this be any faster ;

use strict; use warnings; use feature qw/say/;
use Time::HiRes; my \$time_start = [ Time::HiRes::time ];

say "Found primes : ", Find_the_prime_numbers_upto(20_000);
say "Seconds      : ", Time::HiRes::tv_interval(\$time_start, [
Time::HiRes::time ]);

sub Find_the_prime_numbers_upto
{
return if \$_[0] < 2;
my (\$found, \$ok, \$number)=(1,1,1); #say 2;

for (1 .. int (\$_[0]-1)/2)
{
\$number = 2*\$_ + 1;
\$ok=1;
for (2 .. \$number-1)
{
if (0 == \$number % \$_)
{
\$ok=0;
last
}
}

\$found++ if \$ok; # say \$number if \$ok
}
\$found
}

Re: prime

[...]

[simple-minded implementation of prime search algorithm snipped]

Yes. The Sieve of Eratosthenes is significantly faster.

jue

Re: prime

On 15/10/2014 9:56 μμ, jurgenex@hotmail.com wrote:

4.4 seconds upto 10_000_000 , impressive !

Re: prime

El 15/10/14 a las 21:32, George Mpouras escribió:

In C, you will end with gigabytes of primes in little time.

This only probes Perl is fast _enough_ to do common calculus.
That's right because many stats and non high iterative computations
take no human significative time over a well optimized compiled
language as could be C or fortran.

--
http://www.telecable.es/personales/gamo/

Re: prime

On 16.10.14 11:57, gamo wrote:

No, you won't because, for large primes, C's data types today
likely do not support numbers that large. You need a library
for large numbers, which is typically written with the help
of assembly language, even while the assembly instructions are
sometimes thinly wrapped in compiler-specific language extensions
to C and relatives.

These libraries would also be used with Perl (or Python, etc.)

There is evidence that just having an optimizing compiler and
simply running it at the highest (nominal) level of optimization
is not usually enough to produce the fastest programs:

Even when the compiler is Intel Fortran, programs' performance
tends to be inferior in comparison to programs' performance that
are being optimized while they are running. There are at least
two ways to achieve this level of performance:

(a) profiling is fed back to compilation, or
(b) JIT compilers are doing that and observe the "hot spots".

So, in theory, and sometimes in practice, anything that runs on
top of an optimizing VM may actually produce faster program
execution---after some loops have run.

Re: prime

C's long long data type is at least 64 bits. Assuming you use the same
data type to store your primes, you just need 2**30 / 8 == 2**27 ==
134'217'728 primes to get one gigabyte of primes. Let's call it twice
that to get to "gigabytes" (plural).

According to the prime number theorem there are about 2**64 / ln (2**64)
== 4.16E17 prime numbers between 0 and 2**64. So C's native data types
are more than sufficient to compute "gigabytes of primes".

hp

--
_  | Peter J. Holzer    | Fluch der elektronischen Textverarbeitung:
|_|_) |                    | Man feilt solange an seinen Text um, bis
| |   | hjp@hjp.at         | die Satzbestandteile des Satzes nicht mehr
__/   | http://www.hjp.at/ | zusammenpaßt. -- Ralph Babel

Re: prime

El 16/10/14 a las 17:16, Peter J. Holzer escribió:

Right, but I was refering to decimal store of the primes, plus a new
line between them. In this format, the first 100 million primes occupy
a little more than 1 GB.

\$ tail primes.100M
2038074523
2038074547
2038074559
2038074593
2038074641
2038074659
2038074707
2038074713
2038074739
2038074743

View the numbers, there is no need to long long types, a unsigned long
(typically 64 bit number) is faster and could do the job.

Cheers

--
http://www.telecable.es/personales/gamo/

fast math? (Was: prime)

On 16.10.14 19:52, gamo wrote:

Yes, native int, compiled on a 64 bit platform, easily outperforms
a equivalent program written in Perl. More reason for me to ask:
Is there a package in use with Perl that would speed up int
computations in Perl?  Math::GMP does not seem to be it (not too
surprising). I imagine a test program like this one, in C and Perl:

# -8<-

/* pointless */
#include <stdint.h>
#include <inttypes.h>
#include <stdio.h>

typedef uint64_t num;

num f(const unsigned short divisor, const num init, const num stop)
{
num result = init;

for (num m = divisor; m > 0; ++m) {
while (1) {
result += m % 2 ? (2*m) : m;
result /= divisor;
if (result >= stop) {
m = -1;
break;
}
result *= divisor;
}
}
return result;
}

int main()
{
for (unsigned short runs = 3; runs; --runs) {
printf("result=%" PRIu64 "\n", f(300, 1000, 1<<28));
}
return 0;
}

# -8<-

# pointless
use integer;

sub f
{
my (\$divisor, \$init, \$stop) = @_;
my \$result = \$init;

for (my \$m = \$divisor; \$m > 0; ++\$m) {
while (1) {
\$result += \$m % 2 ? (2*\$m) : \$m;
\$result /= \$divisor;
if (\$result >= \$stop) {
\$m = -1;
last;
}
\$result *= \$divisor;
}
}
return \$result;
}

for (my \$runs = 3; \$runs; --\$runs) {
printf("result=%lu\n", f(300, 1000, 2**28));
}

Re: fast math? (Was: prime)

El 16/10/14 a las 21:28, G.B. escribió:

Clearly the response is no. You can't speed up native types.
A module for the various incarnations of GMP in Perl exists
under the directory /demos of GMP library, but this only
applies to big numbers, which are of ocassional use. And for
big numbers I understand numbers ahead of 2**49, wich is
big enough to store common currency numbers (e.g. national
accounting numbers). To store US debt numbers you need GMP ;-)

--
http://www.telecable.es/personales/gamo/

Re: fast math? (Was: prime)

Inline::C ;-)

I agree with the conclusion, but not the reason.

The "native type" in Perl (there really is only one relevant here) is a
rather complex thing (a scalar can be a signed int, an unsigned int, a
floating point number, a string, or several of these things at once)
and if you look at the perl source code you will probably be shocked to
see how many lines of C code even simple operations need.

So if a module could replace say "add" with a specialized routine which
really just adds two ints, that would be faster than perl's "add two
arbitrary scalars" op.

But I think that this wouldn't improve overall performance much.  You
still have all the interpreter overhead, you still have to provide valid
scalars (with reference counters and stuff), etc.

Of course, if you care about computational performance, you often don't
deal with individual scalars, but with arrays (vectors, matrices, ...)
and then PDL might be your friend.

hp

--
_  | Peter J. Holzer    | Fluch der elektronischen Textverarbeitung:
|_|_) |                    | Man feilt solange an seinen Text um, bis
| |   | hjp@hjp.at         | die Satzbestandteile des Satzes nicht mehr
__/   | http://www.hjp.at/ | zusammenpaßt. -- Ralph Babel

Re: fast math? (Was: prime)

El 17/10/14 a las 13:41, Peter J. Holzer escribió:

I try Inline::C

no better performance at all for alternatives PRNGs

--
http://www.telecable.es/personales/gamo/

Re: fast math? (Was: prime)

On 10/16/14 12:28, G.B. wrote:

I use Inline::C to do that.  It works like a charm.

Xho

Re: prime

Yeah, but only 1 GB, not "gigabytes" (plural). And in binary it's only
100E6 * 4 = 0.4 GB. So G.B. would have quibbled with that.

You are very close to 2**31 here which is the largest prime you can
compute with a naive implementation of the sieve of Eratosthenes with 32
bit numbers (You have to compute 2*n which would overflow with an
unsigned 32 bit int). I guess you could get to about twice that with a
less naive version, but you're still at the same order of magnitude.

But with 64 bit numbers you are many orders of magnitude beyond that.
There is no quibbling whether 100 million primes are "gigabytes" or not,
since we are clearly talking about many, many gigabytes here (actually a
few exabytes).

long is only guaranteed to be 32 bit. long long is guaranteed to be at
least 64 bit. On Linux 64 bit machines, long and long long are typically
both 64 bit.

My point was to show that C provides native types which can be used to
compute "gigabytes" of prime numbers with a (naive) sieve of
eratosthenes and that there is no need to resort to multi-precision
libraries. So naturally I'll use the biggest hammer that C promises to
provide.

hp

--
_  | Peter J. Holzer    | Fluch der elektronischen Textverarbeitung:
|_|_) |                    | Man feilt solange an seinen Text um, bis
| |   | hjp@hjp.at         | die Satzbestandteile des Satzes nicht mehr
__/   | http://www.hjp.at/ | zusammenpaßt. -- Ralph Babel

Re: prime

El 17/10/14 a las 12:59, Peter J. Holzer escribió:

No problem, as I said is quick to generate. Here:

2142636916 oct 17 20:06 primes.200M

are the first 200 million primes. A file to play
with xz compressor.

Of course no problem regarding integer type, I think
the problem could rise before in the line

z = sqrt((double) i);

for lack of precision in

if (p[j] > z) break;

But this is hypothesizing the limits. Maybe RAM be first.

Cheers

--
http://www.telecable.es/personales/gamo/

Re: prime

Sigh.

hp

--
_  | Peter J. Holzer    | Fluch der elektronischen Textverarbeitung:
|_|_) |                    | Man feilt solange an seinen Text um, bis
| |   | hjp@hjp.at         | die Satzbestandteile des Satzes nicht mehr
__/   | http://www.hjp.at/ | zusammenpaßt. -- Ralph Babel

Re: prime

On 16.10.14 17:16, Peter J. Holzer wrote:

I guess, then, that computability in plain C depends on
"plural" typically meaning less than 45?  ;-)

Re: prime

No, "plural" means "more than 1". As soon as you can compute more that 1
GB of primes with native C types, the statement "you can compute
gigabytes of primes with native C types" is proven. There is no upper
limit in the statement.

Also I have no idea where you get the number 45 here. 4.16E17 prime
numbers are about 3 billion gigabytes! (of course you couldn't possibly
have enough RAM for such a large sieve).

hp

--
_  | Peter J. Holzer    | Fluch der elektronischen Textverarbeitung:
|_|_) |                    | Man feilt solange an seinen Text um, bis
| |   | hjp@hjp.at         | die Satzbestandteile des Satzes nicht mehr
__/   | http://www.hjp.at/ | zusammenpaßt. -- Ralph Babel

Re: prime

On 17.10.14 13:06, Peter J. Holzer wrote:

Just another rhetorical twist of not sticking to the literal
"gigabytes of" as meaning more than 1GB.  (This is lacking
context/bound, facilitating an argument about native int in
the first place.) So push for the unbounded quantification,
in one way or other addressing long long's size in bits:

(4.16*10^17 * 44) / 2^64
.99226182825873365800

(4.16*10^17 * 45) / 2^64
1.01481323344643215023

prime numbers one can compute "quickly", using machine int
algorithms. With that in mind, also 32 bit machines (which you
have mentioned in another reply, I'll add lack of / slowness of
long long) and imagining "gigabytes of" not standing for
literally gigabytes, but literally gazillions, then
"for large primes, C's data types today likely do not support
numbers that large."

Of course, resorting to the literal, I'd agree that it cannot be
3 billion gigabytes, as, by the size of it, this is a different
order of magnitude, which does not go by the name "gigabytes".

Re: prime

What do think you are computing here?

hp

--
_  | Peter J. Holzer    | Fluch der elektronischen Textverarbeitung:
|_|_) |                    | Man feilt solange an seinen Text um, bis
| |   | hjp@hjp.at         | die Satzbestandteile des Satzes nicht mehr
__/   | http://www.hjp.at/ | zusammenpaßt. -- Ralph Babel

Re: prime

On 17.10.14 14:09, Peter J. Holzer wrote:

An approximation of 45 times as much as 4.16E17 that fits in
a machine int.