Chris, this blows up the memory on my Macbook Air and fills up all the
swap space (clearly there isn't much) and i had to restart the system to
recover it.
The pure perl version is more efficient due to possible perl optimizations.
So the culprit is the "$possible = where $possible, $possible % $p; "
line. There are way too many PDL objects being created and none of them
being freed.
Here is a more efficient C-based solution that I thought of:
I was thinking of a way to store the integers in a bitmap stream of
bytes where the integer value is just an index into a bitmap of 0's and 1's.
When the integer is composite or divisible by anything other than
itself, it's bit can be flipped to 0. So in the end all the primes will
be all the bits that are 1, whose indexes can then be collected.
I am not sure if I can do this in PDL.
It isn't necessary to.
Thanks for your program.
--Vikas
On 02/14/2015 05:27 PM, Chris Marshall wrote:
> Here is a PDL implementation but it runs in about 5mins
> on my cygwin/win7 system and uses a lot of memory. The
> real performance killer for PDL is the allocation and
> creation of new PDLs. The computations are much faster
> then the plain perl ones. How does this run on your Mac?
>
> #!/usr/bin/env perl
> use strict;
> use warnings;
>
> use PDL;
> use PDL::NiceSlice;
>
> # use POSIX qw(floor);
> # Problem 3:
> # The prime factors of 13195 are 5, 7, 13, 29.
> # What is the largest prime factor of 600851475143 ?
>
> my $num = 600851475143;
> #my $num = 13195;
>
> my $m = floor(sqrt($num));
> print "max factor limit: $m\n";
>
> # solve using sieve of erastothenes
> my @primes = ();
> my $possible = indx(2 .. $m);
>
> my $cnt = 0;
> while (any $possible) {
> my $p = $possible((0));
> $possible = where $possible, $possible % $p;
> push @primes, $p;
> #print "Remaining: ", $possible->nelem, "\n";
> #print "Found possible prime factor: $p\n";
> }
>
> my $factors = indx(@primes);
> $factors = where $factors, $num%$factors==0;
> if (any $factors) {
> print "Prime Factors of $num: $factors\n";
> } else {
> print "$num is prime\n";
> }
>
> Cheers,
> Chris
>
> On 2/14/2015 13:27, Vikas N Kumar wrote:
>> Hi
>>
>> I am just casually solving some Project Euler problems using Perl.
>>
>> For problem 3 (https://projecteuler.net/problem=3) I solved it using
>> the code below. The problem is stated in the code comments.
>>
>> The code is single threaded and takes about 5-10 minutes on a
>> standard Intel i5 CPU on a 3 year old Macbook Air.
>>
>> Can PDL make this faster ? No bignums are being used.
>>
>> #!/usr/bin/env perl
>> use strict;
>> use warnings;
>> use POSIX qw(floor);
>> # Problem 3:
>> # The prime factors of 13195 are 5, 7, 13, 29.
>> # What is the largest prime factor of 600851475143 ?
>> my $num = 600851475143;
>>
>> my $m = floor(sqrt($num));
>> print "max factor limit: $m\n";
>> # solve using sieve of erastothenes
>> #
>> my @primes = ();
>> my @possible = (2 .. $m);
>> while (@possible) {
>> my $p = shift @possible;
>> @possible = grep { $_ % $p != 0 } @possible;
>> push @primes, $p;
>> print "Remaining: ", scalar(@possible), "\n";
>> print "Found possible prime factor: $p\n";
>> }
>> my @factors = grep { $num % $_ == 0 } @primes;
>> if (@factors) {
>> print "Prime Factors of $num: ", join(",", @factors), "\n";
>> } else {
>> print "$num is prime\n";
>> }
>>
_______________________________________________
Perldl mailing list
Perldl@jach.hawaii.edu
http://mailman.jach.hawaii.edu/mailman/listinfo/perldl
