Re: [Perldl] Project Euler and Perl
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
Re: [Perldl] Project Euler and Perl
Yes, maybe some use of -sever to turn off data flow
might allow things to be freed. It is definitely
possible to tend the memory directly in the implementation
to work around the alloc/free issue.
--Chris
On 2/15/2015 08:32, Vikas N Kumar 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
Re: [Perldl] Project Euler and Perl
I made my own attempt at a solution (attached).
It runs in 6s in a Dell Inspiron N5110 and in 53s in an ASUS
Transformer tablet. So I guess it is fast. It seems correct but I have
some doubts (below)
-- Code:
#!/usr/bin/env perl
use strict;
use warnings;
use feature 'say';
use POSIX 'floor';
use PDL::Lite;
use PDL::NiceSlice;
my $num=$ARGV[0];
my $max=floor(sqrt($num));
my $possible=PDL-sequence($max+1);
$possible-((1)).=0;
foreach(2..$max/2) {
next unless $possible-(($_));
$possible-(2*$_:-1:$_).=0;
}
my $primes=$possible-where($possible);
my $factors;
my $allfactors=PDL-zeros(0);
my $n=$num;
do {
$factors=$primes-where($n%$primes==0);
$n/=$factors-prod;
$allfactors=$allfactors-append($factors);
} while $factors-nelem;
$allfactors=$allfactors-append($n) unless $n==1;
say $allfactors-qsort;
Output: -
mochan@yapaque:~/txt/cache/15/scratch$ time ./erastotenes.pl 600851475143
[71 839 1471 6857]
real0m6.148s
user0m6.132s
sys 0m0.012s
The do loop is to catch the multiplicity of the prime factors.
There is something strange though. I suspect my system has errors when
calculating moduli, as the factor 71 was the last found instead of
being the first. When I ran with the debugger I got this strange
result:
DB9 p $primes-slice('(19)') #get the suspect prime position
71
DB10 p $num%71 #71 divides $num, 600851475143
0
DB11 p $num%$primes-slice('(19)')
753322814151
I expected to obtain zero here, as $primes-slice('(19)')==71, but
instead I obtained 753322814151. So it seems that pdl and perl yield
different results! Could it be due to using default types?
Best regards,
Luis
On Sun, Feb 15, 2015 at 04:03:45PM -0500, Chris Marshall wrote:
Yes, maybe some use of -sever to turn off data flow
might allow things to be freed. It is definitely
possible to tend the memory directly in the implementation
to work around the alloc/free issue.
--Chris
On 2/15/2015 08:32, Vikas N Kumar 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
