[33020] in Perl-Users-Digest
Perl-Users Digest, Issue: 4296 Volume: 11
daemon@ATHENA.MIT.EDU (Perl-Users Digest)
Fri Oct 17 09:14:17 2014
Date: Fri, 17 Oct 2014 06:14:07 -0700 (PDT)
From: Perl-Users Digest <Perl-Users-Request@ruby.OCE.ORST.EDU>
To: Perl-Users@ruby.OCE.ORST.EDU (Perl-Users Digest)
Perl-Users Digest Fri, 17 Oct 2014 Volume: 11 Number: 4296
Today's topics:
Re: prime <justin.1410@purestblue.com>
Re: prime <gamo@telecable.es>
Re: prime <bauhaus@futureapps.invalid>
Re: prime (hymie!)
Re: prime <hjp-usenet3@hjp.at>
Re: prime <gamo@telecable.es>
Re: prime <bauhaus@futureapps.invalid>
Re: prime <gamo@telecable.es>
Re: prime <gamo@telecable.es>
Re: prime <bauhaus@futureapps.invalid>
Re: prime <kaz@kylheku.com>
Re: prime <gravitalsun@hotmail.foo>
Re: prime <gravitalsun@hotmail.foo>
Re: prime <lionslair@consolidated.net>
Re: prime <gamo@telecable.es>
Re: prime <hjp-usenet3@hjp.at>
Re: prime <hjp-usenet3@hjp.at>
Re: prime <hjp-usenet3@hjp.at>
Re: prime <bauhaus@futureapps.invalid>
Re: prime <hjp-usenet3@hjp.at>
Digest Administrivia (Last modified: 6 Apr 01) (Perl-Users-Digest Admin)
----------------------------------------------------------------------
Date: Thu, 16 Oct 2014 09:53:28 +0100
From: Justin C <justin.1410@purestblue.com>
Subject: Re: prime
Message-Id: <8ld4hb-t79.ln1@zem.masonsmusic.co.uk>
On 2014-10-15, George Mpouras <gravitalsun@hotmail.foo> wrote:
> # 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;
You're assigning the value '1' to $found and $ok...
>
> for (1 .. int ($_[0]-1)/2)
> {
> $number = 2*$_ + 1;
> $ok=1;
... then immediately assigning them again. For a program that's going
to iterate a very large number of times you might want to save every
clock cycle you can.
my $found = 1;
my ($number, $ok);
or
my ($found, $number, $ok) = (1);
I have no idea how these will compare over a significant number of
iterations, but searches for primes tend to iterate a very large
number of times, I'm sure there must be some saving. Not to mention
how it looks.
Justin.
--
Justin C, by the sea.
------------------------------
Date: Thu, 16 Oct 2014 11:57:02 +0200
From: gamo <gamo@telecable.es>
Subject: Re: prime
Message-Id: <m1o4pf$egf$1@speranza.aioe.org>
El 15/10/14 a las 21:32, George Mpouras escribió:
>> [simple-minded implementation of prime search algorithm snipped]
>>
>> Yes. The Sieve of Eratosthenes is significantly faster.
>>
>> jue
>>
>
>
> 4.4 seconds upto 10_000_000 , impressive !
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/
------------------------------
Date: Thu, 16 Oct 2014 13:40:10 +0200
From: "G.B." <bauhaus@futureapps.invalid>
Subject: Re: prime
Message-Id: <m1oaqo$3nu$1@dont-email.me>
On 16.10.14 11:57, gamo wrote:
> El 15/10/14 a las 21:32, George Mpouras escribió:
>>> [simple-minded implementation of prime search algorithm snipped]
>>>
>>> Yes. The Sieve of Eratosthenes is significantly faster.
>>>
>>> jue
>>>
>>
>>
>> 4.4 seconds upto 10_000_000 , impressive !
>
>
> In C, you will end with gigabytes of primes in little time.
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.)
> 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.
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.
------------------------------
Date: 16 Oct 2014 12:38:12 GMT
From: hymie@lactose.homelinux.net (hymie!)
Subject: Re: prime
Message-Id: <543fbc34$0$29948$882e7ee2@usenet-news.net>
In our last episode, the evil Dr. Lacto had captured our hero,
George Mpouras <gravitalsun@hotmail.foo>, who said:
>sub Find_the_prime_numbers_upto
>{
> for (2 .. $number-1)
> {
> if (0 == $number % $_)
> {
> $ok=0;
> last
> }
> }
I'm pretty sure that you can stop checking at int(sqrt(x)), rather than x-1 .
I'm also pretty sure there's a proof, but I can't find it right now.
--hymie! http://lactose.homelinux.net/~hymie hymie@lactose.homelinux.net
-------------------------------------------------------------------------------
------------------------------
Date: Thu, 16 Oct 2014 17:16:25 +0200
From: "Peter J. Holzer" <hjp-usenet3@hjp.at>
Subject: Re: prime
Message-Id: <slrnm3voa9.shh.hjp-usenet3@hrunkner.hjp.at>
On 2014-10-16 11:40, G.B. <bauhaus@futureapps.invalid> wrote:
> On 16.10.14 11:57, gamo wrote:
>> El 15/10/14 a las 21:32, George Mpouras escribió:
>>>> [simple-minded implementation of prime search algorithm snipped]
>>>>
>>>> Yes. The Sieve of Eratosthenes is significantly faster.
>>>
>>> 4.4 seconds upto 10_000_000 , impressive !
>>
>>
>> In C, you will end with gigabytes of primes in little time.
>
> No, you won't because, for large primes, C's data types today likely
> do not support numbers that large.
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
------------------------------
Date: Thu, 16 Oct 2014 19:52:27 +0200
From: gamo <gamo@telecable.es>
Subject: Re: prime
Message-Id: <m1p0ks$td0$1@speranza.aioe.org>
El 16/10/14 a las 17:16, Peter J. Holzer escribió:
> On 2014-10-16 11:40, G.B. <bauhaus@futureapps.invalid> wrote:
>> On 16.10.14 11:57, gamo wrote:
>>> El 15/10/14 a las 21:32, George Mpouras escribió:
>>>>> [simple-minded implementation of prime search algorithm snipped]
>>>>>
>>>>> Yes. The Sieve of Eratosthenes is significantly faster.
>>>>
>>>> 4.4 seconds upto 10_000_000 , impressive !
>>>
>>>
>>> In C, you will end with gigabytes of primes in little time.
>>
>> No, you won't because, for large primes, C's data types today likely
>> do not support numbers that large.
>
> 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
>
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/
------------------------------
Date: Thu, 16 Oct 2014 20:14:24 +0200
From: "G.B." <bauhaus@futureapps.invalid>
Subject: Re: prime
Message-Id: <m1p1tu$j3k$1@dont-email.me>
On 16.10.14 17:16, Peter J. Holzer wrote:
> 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".
I guess, then, that computability in plain C depends on
"plural" typically meaning less than 45? ;-)
------------------------------
Date: Thu, 16 Oct 2014 20:28:15 +0200
From: gamo <gamo@telecable.es>
Subject: Re: prime
Message-Id: <m1p2nv$3jg$1@speranza.aioe.org>
El 16/10/14 a las 14:38, hymie! escribió:
> In our last episode, the evil Dr. Lacto had captured our hero,
> George Mpouras <gravitalsun@hotmail.foo>, who said:
>> sub Find_the_prime_numbers_upto
...
> I'm pretty sure that you can stop checking at int(sqrt(x)), rather than x-1 .
>
> I'm also pretty sure there's a proof, but I can't find it right now.
>
Here
http://stackoverflow.com/questions/5811151/why-do-we-check-upto-the-square-root-of-a-prime-number-to-determine-if-it-is-pri
> --hymie! http://lactose.homelinux.net/~hymie hymie@lactose.homelinux.net
> -------------------------------------------------------------------------------
>
--
http://www.telecable.es/personales/gamo/
------------------------------
Date: Thu, 16 Oct 2014 21:28:50 +0200
From: gamo <gamo@telecable.es>
Subject: Re: prime
Message-Id: <m1p69j$ddt$1@speranza.aioe.org>
El 16/10/14 a las 13:40, G.B. escribió:
> 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.
I really want that you were right, but it's a clever no, no,
in practical test, and in both VM that runs perl6... it's
a lot slower than perl5.
--
http://www.telecable.es/personales/gamo/
------------------------------
Date: Thu, 16 Oct 2014 21:31:56 +0200
From: "G.B." <bauhaus@futureapps.invalid>
Subject: Re: prime
Message-Id: <m1p6f9$l00$2@dont-email.me>
On 16.10.14 21:28, gamo wrote:
> El 16/10/14 a las 13:40, G.B. escribió:
>> 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.
>
> I really want that you were right, but it's a clever no, no,
> in practical test, and in both VM that runs perl6... it's
> a lot slower than perl5.
Yes, I should have clarified I was thinking about VMs that
have received substantial ... work.
------------------------------
Date: Thu, 16 Oct 2014 19:36:27 +0000 (UTC)
From: Kaz Kylheku <kaz@kylheku.com>
Subject: Re: prime
Message-Id: <20141016120223.841@kylheku.com>
On 2014-10-16, hymie! <hymie@lactose.homelinux.net> wrote:
> In our last episode, the evil Dr. Lacto had captured our hero,
> George Mpouras <gravitalsun@hotmail.foo>, who said:
>>sub Find_the_prime_numbers_upto
>>{
>> for (2 .. $number-1)
>> {
>> if (0 == $number % $_)
>> {
>> $ok=0;
>> last
>> }
>> }
>
> I'm pretty sure that you can stop checking at int(sqrt(x)), rather than x-1 .
>
> I'm also pretty sure there's a proof, but I can't find it right now.
Each factor f of a number x, such that f <= sqrt(x), pairs
pairs with another number g, also a factor of x, such that
f * g = x and g > sqrt(x).
We know that g exists such that f * g = x because that's the definition
of what it means for f to be a factor of x. This other number g
is also a factor, by the symmetric definition of the product.
We know that g >= sqrt(x) because if we suppose the opposite, namely
that g < sqrt(x), then since f <= sqrt(x), then f * g < sqrt(x) * sqrt(x).
But sqrt(x) * sqrt(x) = x, and so f * g < x, which contradicts f * g = x.
This works in reverse also. Using a similar argument, we can show that each
factor g > sqrt(x) pairs with some f <= sqrt(x).
In other words, given two positive integers f and g (or real numbers, for
that matter) such that f * g = x: we have only these three possibilities:
f = sqrt(x) and g = sqrt(x)
f > sqrt(x) and g < sqrt(x)
f < sqrt(x) and g > sqrt(x)
Thus:
* If we look for factors of x, and do not find any up to sqrt(x),
we are done: there are no factors above sqrt(x) either: the number
is prime.
* If we are looking to discover and list all the factors of a composite number
x, we just need to discover the ones up to sqrt(x). Then for each factor f
thus discovered, we calculate x / f, to obtain the remaining factors.
We do not have to search the space above sqrt(x) which is much
larger than the space below, and asymptotically slower to search.
------------------------------
Date: Fri, 17 Oct 2014 00:54:11 +0300
From: George Mpouras <gravitalsun@hotmail.foo>
Subject: Re: prime
Message-Id: <m1peq3$cf$1@news.ntua.gr>
> In other words, given two positive integers f and g (or real numbers, for
> that matter) such that f * g = x: we have only these three possibilities:
>
> f = sqrt(x) and g = sqrt(x)
> f > sqrt(x) and g < sqrt(x)
> f < sqrt(x) and g > sqrt(x)
>
> Thus:
>
> * If we look for factors of x, and do not find any up to sqrt(x),
> we are done: there are no factors above sqrt(x) either: the number
> is prime.
>
> * If we are looking to discover and list all the factors of a composite number
> x, we just need to discover the ones up to sqrt(x). Then for each factor f
> thus discovered, we calculate x / f, to obtain the remaining factors.
>
> We do not have to search the space above sqrt(x) which is much
> larger than the space below, and asymptotically slower to search.
>
clever !
------------------------------
Date: Fri, 17 Oct 2014 01:39:57 +0300
From: George Mpouras <gravitalsun@hotmail.foo>
Subject: Re: prime
Message-Id: <m1phft$7ol$1@news.ntua.gr>
> We do not have to search the space above sqrt(x) which is much
# the simple approach with sqrt is much faster.
sub Find_the_prime_numbers_upto
{
return if $_[0]<2;
my ($found,$N)=1; # say 2;
for (1 .. int ($_[0]-1)/2)
{
$N = 2*$_ + 1;
for (3 .. sqrt $N)
{
$N=0, last unless $N % $_
}
$found++ if $N # ;say $N if $N
}
$found
}
------------------------------
Date: Thu, 16 Oct 2014 23:13:33 -0500
From: Martin Eastburn <lionslair@consolidated.net>
Subject: Re: prime
Message-Id: <WH00w.416111$412.34468@fx30.iad>
I've written Factoral 1000 in Basic and in Assembly and Perl.
Basic converted on the fly took 11.5 hours for full precision integer
with all zeros and all digits. It printed on a 132 sheet paper in 10
pitch. Full sheet.
Assembly in 3 hours. I based the assembly loosely on the method I used
in Basic.
Both of those were with an 8080 processor. 2 MHz. Not bad for '76.
I did factorial 1000 in three seconds with my i7
â—¦CPU_Name: Intel(R) Core(TM) i7-4960X CPU @ 3.60GHz
32 GB of memory.
The process I did back in '76 was to use an array. Each digit of the
number is an array cell. Each cell had a value of 0 to 9. If greater,
one simple works it down the array.
The trick was to generate the array of a size needed. During
development, it took several tries until I remembered I had a
exponential version in a table book from the Government Printing office.
Sizing it was easy enough once the magnitude of the number was determined.
Martin
On 10/16/2014 6:40 AM, G.B. wrote:
> On 16.10.14 11:57, gamo wrote:
>> El 15/10/14 a las 21:32, George Mpouras escribió:
>>>> [simple-minded implementation of prime search algorithm snipped]
>>>>
>>>> Yes. The Sieve of Eratosthenes is significantly faster.
>>>>
>>>> jue
>>>>
>>>
>>>
>>> 4.4 seconds upto 10_000_000 , impressive !
>>
>>
>> In C, you will end with gigabytes of primes in little time.
>
> 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.)
>
>> 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.
>
> 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.
>
------------------------------
Date: Fri, 17 Oct 2014 11:03:50 +0200
From: gamo <gamo@telecable.es>
Subject: Re: prime
Message-Id: <m1qm1o$qsr$1@speranza.aioe.org>
El 17/10/14 a las 06:13, Martin Eastburn escribió:
> I did factorial 1000 in three seconds with my i7
> â—¦CPU_Name: Intel(R) Core(TM) i7-4960X CPU @ 3.60GHz
> 32 GB of memory.
You must be refering to factorial of 10000 or higher.
--
http://www.telecable.es/personales/gamo/
------------------------------
Date: Fri, 17 Oct 2014 12:59:36 +0200
From: "Peter J. Holzer" <hjp-usenet3@hjp.at>
Subject: Re: prime
Message-Id: <slrnm41tko.j7p.hjp-usenet3@hrunkner.hjp.at>
On 2014-10-16 17:52, gamo <gamo@telecable.es> wrote:
> El 16/10/14 a las 17:16, Peter J. Holzer escribió:
>> On 2014-10-16 11:40, G.B. <bauhaus@futureapps.invalid> wrote:
>>> On 16.10.14 11:57, gamo wrote:
>>>> El 15/10/14 a las 21:32, George Mpouras escribió:
>>>>>> [simple-minded implementation of prime search algorithm snipped]
>>>>>>
>>>>>> Yes. The Sieve of Eratosthenes is significantly faster.
>>>>>
>>>>> 4.4 seconds upto 10_000_000 , impressive !
>>>>
>>>>
>>>> In C, you will end with gigabytes of primes in little time.
>>>
>>> No, you won't because, for large primes, C's data types today likely
>>> do not support numbers that large.
>>
>> 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".
>
> 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.
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.
> $ tail primes.100M
> 2038074523
> 2038074547
> 2038074559
> 2038074593
> 2038074641
> 2038074659
> 2038074707
> 2038074713
> 2038074739
> 2038074743
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).
> 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.
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
------------------------------
Date: Fri, 17 Oct 2014 13:06:17 +0200
From: "Peter J. Holzer" <hjp-usenet3@hjp.at>
Subject: Re: prime
Message-Id: <slrnm41u19.j7p.hjp-usenet3@hrunkner.hjp.at>
On 2014-10-16 18:14, G.B. <bauhaus@futureapps.invalid> wrote:
> On 16.10.14 17:16, Peter J. Holzer wrote:
>> 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".
>
> I guess, then, that computability in plain C depends on
> "plural" typically meaning less than 45? ;-)
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
------------------------------
Date: Fri, 17 Oct 2014 13:21:25 +0200
From: "Peter J. Holzer" <hjp-usenet3@hjp.at>
Subject: Re: prime
Message-Id: <slrnm41utl.j7p.hjp-usenet3@hrunkner.hjp.at>
On 2014-10-17 09:03, gamo <gamo@telecable.es> wrote:
> El 17/10/14 a las 06:13, Martin Eastburn escribió:
>> I did factorial 1000 in three seconds with my i7
>> â—¦CPU_Name: Intel(R) Core(TM) i7-4960X CPU @ 3.60GHz
>> 32 GB of memory.
#!/usr/bin/perl
use warnings;
use strict;
use bigint;
use v5.10;
my $f = 1;
for (2 .. 1000) {
$f *= $_;
}
say $f;
0.15 seconds on a 1.85 GHz Core2 Duo.
> You must be refering to factorial of 10000 or higher.
That sounds about right for the run time, but it's more than "1 full
sheet" of paper (but then factorial 1000 is less than that).
My guess is that Martin's multiprecision routines are a lot slower than
those in modern libraries (for example he mentioned decimal arithetic,
while GMP uses 32 or even 64 bit chunks).
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
------------------------------
Date: Fri, 17 Oct 2014 13:44:51 +0200
From: "G.B." <bauhaus@futureapps.invalid>
Subject: Re: prime
Message-Id: <m1qvfh$4tt$1@dont-email.me>
On 17.10.14 13:06, Peter J. Holzer wrote:
> Also I have no idea where you get the number 45 here. 4.16E17 prime
> numbers are about 3 billion gigabytes!
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
Without context, any plural invites (me) asking about how many
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".
------------------------------
Date: Fri, 17 Oct 2014 14:09:45 +0200
From: "Peter J. Holzer" <hjp-usenet3@hjp.at>
Subject: Re: prime
Message-Id: <slrnm421o9.bj7.hjp-usenet3@hrunkner.hjp.at>
On 2014-10-17 11:44, G.B. <bauhaus@futureapps.invalid> wrote:
> (4.16*10^17 * 44) / 2^64
> .99226182825873365800
>
> (4.16*10^17 * 45) / 2^64
> 1.01481323344643215023
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
------------------------------
Date: 6 Apr 2001 21:33:47 GMT (Last modified)
From: Perl-Users-Request@ruby.oce.orst.edu (Perl-Users-Digest Admin)
Subject: Digest Administrivia (Last modified: 6 Apr 01)
Message-Id: <null>
Administrivia:
To submit articles to comp.lang.perl.announce, send your article to
clpa@perl.com.
Back issues are available via anonymous ftp from
ftp://cil-www.oce.orst.edu/pub/perl/old-digests.
#For other requests pertaining to the digest, send mail to
#perl-users-request@ruby.oce.orst.edu. Do not waste your time or mine
#sending perl questions to the -request address, I don't have time to
#answer them even if I did know the answer.
------------------------------
End of Perl-Users Digest V11 Issue 4296
***************************************
