Velocity Reviews > Perl > arithmetic persistence

# arithmetic persistence

Marc Girod
Guest
Posts: n/a

 02-20-2011
On Feb 20, 6:39*pm, Willem <(E-Mail Removed)> wrote:

> Like this, you're skipping a lot of calculations indeed,
> but at the cost of sorting the digits.

....which is a rising cost, and ends up being prohibitive...

> By the way, here's a simple version that's marginally faster
> even, and doesn't require lots of memory. *It uses a simple
> pruning trick to cut off calculation when it knows that a
> result isn't good enough.

Yes, a much simpler idea, indeed.
I have to get out of my first mindset of getting the value anyway.

> I also wrote this in C, using 64-bit ints, and it turns out that
> 3778888999 is the first of p(10), which my box found in 2m50.

And I am nowhere near this, of course.
Thanks,
Marc

Willem
Guest
Posts: n/a

 02-20-2011
Marc Girod wrote:
) On Feb 20, 6:39?pm, Willem <(E-Mail Removed)> wrote:
)
)> Like this, you're skipping a lot of calculations indeed,
)> but at the cost of sorting the digits.
)
) ...which is a rising cost, and ends up being prohibitive...

Nah. What's prohibitive is the memory footprint.

)> By the way, here's a simple version that's marginally faster
)> even, and doesn't require lots of memory. ?It uses a simple
)> pruning trick to cut off calculation when it knows that a
)> result isn't good enough.
)
) Yes, a much simpler idea, indeed.
) I have to get out of my first mindset of getting the value anyway.
)
)> I also wrote this in C, using 64-bit ints, and it turns out that
)> 3778888999 is the first of p(10), which my box found in 2m50.
)
) And I am nowhere near this, of course.

Well, this is almost all arithmetics, so Perl just doesn't compare.
0.8 seconds to find P(9) in C, versus 1m36 in Perl.

SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

Marc Girod
Guest
Posts: n/a

 02-20-2011
On Feb 20, 7:14*pm, Willem <(E-Mail Removed)> wrote:

> Nah. *What's prohibitive is the memory footprint.

But this rises quite slowly...

324 keys in the hash for 10 millions
459 for 100
596 for 1 billion...

I'd need to profile.

> Well, this is almost all arithmetics, so Perl just doesn't compare.
> 0.8 seconds to find P(9) in C, versus 1m36 in Perl.

Interesting. I was not aware of this ratio.
Thanks.

Marc

Ilya Zakharevich
Guest
Posts: n/a

 02-21-2011
On 2011-02-20, Willem <(E-Mail Removed)> wrote:
> Oh I see. Does that help ? I would imagine that looking up
> the results in an array would give a big speedup.

Me too. But it looks like there is little speedup or even slowdown; see below.

> use strict;
> use warnings;
> use List::Util qw(reduce);
>
> my \$found = 0;
> my \$fnum = 0;
>
> for (my \$i = 10; \$found < 8; \$i++) {
> my \$prod = reduce { \$a * \$b } split('', \$i);
> next if (\$prod < \$fnum);
> my \$cnt = 1;
> while (\$prod >= 10) {
> \$prod = reduce { \$a * \$b } split('', \$prod);
> \$cnt++;
> }
> if (\$cnt > \$found) {
> \$found = \$cnt;
> \$fnum = \$i;
> print "\$i is the first of p(\$cnt)\n";
> }
> }

On my machine what is below is almost an order of magnitude better.
It also allows tuning (first arg is the target for \$found [8 above]);
second arg gives size of cache in decimal digits (should be at least
half of the size of the answer). On machine arguments 8 4, 8 5, 8 6
finish in very similar time - this means that benefits of caching are
eaten by not being able to prune when caching...

Hope this helps,
Ilya

#!/usr/bin/perl -w
use strict;
use List::Util qw(reduce);

my \$found = 0;
my \$fnum = 0;
my \$lim = shift;
my \$cache_lim10 = shift;
my \$cache_lim = 10**\$cache_lim10;
my \$rex_lim = '.' x \$cache_lim10;

my (@prod, @perc, \$prod, \$p1, \$p2, \$cnt, \$i);

sub report_size (\$\$) {
my (\$i, \$cnt) = (shift, shift);
\$found = \$cnt;
\$fnum = \$i;
print "\$i is the first of p(\$cnt)\n";
}

\$prod[\$_] = \$_, \$perc[\$_] = 0 for 0..9;

\$#prod = \$#perc = \$cache_lim;

for my \$i (10..\$cache_lim-1) { # Round 1: cache, no pruning
if (\$i =~ /0/) {
\$prod = \$prod[\$i] = 0;
} else {
\$prod = \$prod[\$i] = (\$i%10) * \$prod[int(\$i/10)];
}
report_size(\$i, \$p1)
if (\$p1 = \$perc[\$i] = \$perc[\$prod] + 1) > \$found;
}

LOOP: # Round 2: non-hashing, pruning
for (my \$i = \$cache_lim; \$found < \$lim; \$i++) {
next if \$i =~ /0/;
\$prod = \$prod[\$i % \$cache_lim]*\$prod[int(\$i / \$cache_lim)];
next if \$prod < \$fnum; # Prune
\$cnt = 1;
while (\$prod >= \$cache_lim) {
next LOOP if \$prod =~ /0/;
\$prod = \$prod[\$prod % \$cache_lim]*\$prod[int(\$prod / \$cache_lim)];
++\$cnt;
}
\$cnt += \$perc[\$prod];
report_size(\$i, \$cnt) if \$cnt > \$found;
}

Marc Girod
Guest
Posts: n/a

 02-21-2011
On Feb 21, 12:48*am, Ilya Zakharevich <(E-Mail Removed)> wrote:

> On my machine what is below is almost an order of magnitude better.

Just want to acknowledge.
Thanks.
Marc

Martin Str|mberg
Guest
Posts: n/a

 02-24-2011
Thank you for an interesting problem and solutions. However nobody has
so far mentioned the Memoize perl module, which I guess would help
speed up the original solution. But perhaps not the pruning ones.

--
MartinS