Not near a real computer now - but a more efficient sieve implementation would
use affine slices...
Sent from my iPad
> On Feb 15, 2015, at 6:32 AM, Vikas N Kumar <vi...@cpan.org> wrote:
>
> 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
_______________________________________________
Perldl mailing list
Perldl@jach.hawaii.edu
http://mailman.jach.hawaii.edu/mailman/listinfo/perldl
