I did some tests with the modulus operator, which seemed to act
strangely for my proposed solution to the EUler problem:
pdl> p 10%5
0
pdl> p long(10)%long(5)
0
pdl> p longlong(10)%longlong(5)
36044800
So modulus fails when using the longlong data type.
The 'Euler' problem involves a large number 600851475143 and unfortunately
pdl> p longlong(600851475143)
600851475143
pdl> p long(600851475143)
-2147483648
it seems to require more bits than a long.
I'm using PDL 2.007 (005), perl 5.18.1. I attach the output of pdl -V.
Best regards,
Luis
On Sun, Feb 15, 2015 at 11:11:49PM -0600, Luis Mochan wrote:
> 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]
>
> real 0m6.148s
> user 0m6.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:
>
> DB<9> p $primes->slice('(19)') #get the suspect prime position
> 71
> DB<10> p $num%71 #71 divides $num, 600851475143
> 0
> DB<11> 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 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
> > [email protected]
> > http://mailman.jach.hawaii.edu/mailman/listinfo/perldl
>
>
> --
>
> o
> W. Luis Mochán, | tel:(52)(777)329-1734 /<(*)
> Instituto de Ciencias Físicas, UNAM | fax:(52)(777)317-5388 `>/ /\
> Apdo. Postal 48-3, 62251 | (*)/\/ \
> Cuernavaca, Morelos, México | [email protected] /\_/\__/
> Consider using GnuPrivacyGuard https://www.gnupg.org/
> My key: 791EB9EB, C949 3F81 6D9B 1191 9A16 C2DF 5F0A C52B 791E B9EB, yours?
>
>
>
>
> _______________________________________________
> Perldl mailing list
> [email protected]
> http://mailman.jach.hawaii.edu/mailman/listinfo/perldl
>
--
o
W. Luis Mochán, | tel:(52)(777)329-1734 /<(*)
Instituto de Ciencias Físicas, UNAM | fax:(52)(777)317-5388 `>/ /\
Apdo. Postal 48-3, 62251 | (*)/\/ \
Cuernavaca, Morelos, México | [email protected] /\_/\__/
Consider using GnuPrivacyGuard https://www.gnupg.org/
My key: 791EB9EB, C949 3F81 6D9B 1191 9A16 C2DF 5F0A C52B 791E B9EB, yours?
perlDL shell v1.357
PDL comes with ABSOLUTELY NO WARRANTY. For details, see the file
'COPYING' in the PDL distribution. This is free software and you
are welcome to redistribute it under certain conditions, see
the same file for details.
Summary of my PDL configuration
VERSION: PDL v2.007 (supports bad values)
$%PDL::Config = {
'PDL_CONFIG_VERSION' => '0.005',
'WHERE_PLPLOT_INCLUDE' => undef,
'MINUIT_LIB' => undef,
'WITH_3D' => '1',
'GD_LIBS' => undef,
'HDF_INC' => undef,
'FFTW_LIBS' => undef,
'HTML_DOCS' => '1',
'POGL_WINDOW_TYPE' => 'glut',
'PROJ_INC' => undef,
'TEMPDIR' => '/tmp',
'WITH_BADVAL' => '1',
'PDLDOC_IGNORE_AUTOLOADER' => '0',
'MALLOCDBG' => {},
'POGL_VERSION' => '0.6702',
'WITH_GSL' => '1',
'WITH_PROJ' => '1',
'WITH_DEVEL_REPL' => '1',
'BADVAL_USENAN' => '0',
'POSIX_THREADS_INC' => undef,
'FFTW_TYPE' => 'double',
'WITH_FFTW' => '0',
'WITH_IO_BROWSER' => '0',
'SKIP_KNOWN_PROBLEMS' => '0',
'HIDE_TRYLINK' => '1',
'USE_POGL' => '1',
'PROJ_LIBS' => undef,
'WHERE_PLPLOT_LIBS' => undef,
'FITS_LEGACY' => '1',
'HDF_LIBS' => undef,
'WITH_PLPLOT' => '0',
'BADVAL_PER_PDL' => '0',
'PDL_BUILD_DIR' =>
'/home/mochan/.cpanm/work/1388021404.19929/PDL-2.007',
'WITH_HDF' => '1',
'PDL_BUILD_VERSION' => '2.007',
'OPTIMIZE' => undef,
'GSL_LIBS' => undef,
'GL_BUILD' => '1',
'GD_INC' => undef,
'FFTW_INC' => undef,
'WITH_SLATEC' => '1',
'WITH_POSIX_THREADS' => '1',
'POSIX_THREADS_LIBS' => undef,
'WITH_MINUIT' => '1',
'WITH_GD' => '1',
'GSL_INC' => undef
};
Summary of my perl5 (revision 5 version 18 subversion 1) configuration:
Platform:
osname=linux, osvers=3.11-2-amd64, archname=x86_64-linux
uname='linux yapaque 3.11-2-amd64 #1 smp debian 3.11.10-1 (2013-12-04)
x86_64 gnulinux '
config_args='-de -Dprefix=/home/mochan/perl5/perlbrew/perls/5.18.1-amd
-Aeval:scriptdir=/home/mochan/perl5/perlbrew/perls/5.18.1-amd/bin'
hint=recommended, useposix=true, d_sigaction=define
useithreads=undef, usemultiplicity=undef
useperlio=define, d_sfio=undef, uselargefiles=define, usesocks=undef
use64bitint=define, use64bitall=define, uselongdouble=undef
usemymalloc=n, bincompat5005=undef
Compiler:
cc='cc', ccflags ='-fno-strict-aliasing -pipe -fstack-protector
-I/usr/local/include -D_LARGEFILE_SOURCE -D_FILE_OFFSET_BITS=64',
optimize='-O2',
cppflags='-fno-strict-aliasing -pipe -fstack-protector -I/usr/local/include'
ccversion='', gccversion='4.8.2', gccosandvers=''
intsize=4, longsize=8, ptrsize=8, doublesize=8, byteorder=12345678
d_longlong=define, longlongsize=8, d_longdbl=define, longdblsize=16
ivtype='long', ivsize=8, nvtype='double', nvsize=8, Off_t='off_t',
lseeksize=8
alignbytes=8, prototype=define
Linker and Libraries:
ld='cc', ldflags =' -fstack-protector -L/usr/local/lib'
libpth=/usr/local/lib /lib/x86_64-linux-gnu /lib/../lib
/usr/lib/x86_64-linux-gnu /usr/lib/../lib /lib /usr/lib
libs=-lnsl -ldl -lm -lcrypt -lutil -lc
perllibs=-lnsl -ldl -lm -lcrypt -lutil -lc
libc=, so=so, useshrplib=false, libperl=libperl.a
gnulibc_version='2.17'
Dynamic Linking:
dlsrc=dl_dlopen.xs, dlext=so, d_dlsymun=undef, ccdlflags='-Wl,-E'
cccdlflags='-fPIC', lddlflags='-shared -O2 -L/usr/local/lib
-fstack-protector'
_______________________________________________
Perldl mailing list
[email protected]
http://mailman.jach.hawaii.edu/mailman/listinfo/perldl
