Beefy Boxes and Bandwidth Generously Provided by pair Networks
P is for Practical
 
PerlMonks  

Re^2: ulam's spiral too slow

by atcroft (Abbot)
on Apr 20, 2007 at 06:47 UTC ( #611092=note: print w/replies, xml ) Need Help??


in reply to Re: ulam's spiral too slow
in thread ulam's spiral too slow

Does the following code help any?

#!/usr/bin/perl -w use strict; use vars qw($image_w $image_h $image_w_2 $image_h_2); use Benchmark; use Getopt::Long; use Tk; $| = 1; my $max; # ( $image_w, $image_h ) = ( 1920, 1200 ); # ( $image_w, $image_h ) = ( 1920, 1080 ); # ( $image_w, $image_h ) = ( 1680, 1050 ); # ( $image_w, $image_h ) = ( 1600, 1200 ); # ( $image_w, $image_h ) = ( 1440, 900 ); # ( $image_w, $image_h ) = ( 1366, 768 ); # ( $image_w, $image_h ) = ( 1280, 1024 ); # ( $image_w, $image_h ) = ( 1280 800 ); # ( $image_w, $image_h ) = ( 1280, 720 ); # ( $image_w, $image_h ) = ( 1024, 768 ); # ( $image_w, $image_h ) = ( 800, 600 ); # ( $image_w, $image_h ) = ( 640, 480 ); # ( $image_w, $image_h ) = ( 640, 350 ); # ( $image_w, $image_h ) = ( 640, 200 ); # ( $image_w, $image_h ) = ( 320, 200 ); ( $image_w, $image_h ) = ( 160, 200 ); if ( scalar( grep( /^-/, @ARGV ) ) ) { GetOptions( 'width:i' => \$image_w, 'height:i' => \$image_h, 'help' => \&help, ); $image_w_2 = $image_w / 2; $image_h_2 = $image_h / 2; $max = ( ( $image_h < $image_w ? $image_h : $image_w ) - 10 ) **2; print qq{Creating $image_w x $image_h image, up to $max points\n}; } else { &help; } my %spinner_data = ( characters => [ q{|}, q{/}, q{-}, q{\\} ], bigscale => 100_000_000, scale => 10, count => 0, ); my $mw; my $f; my $can; my $img; my $rs; $mw = MainWindow->new; # Create outer containers $f = $mw->Frame->pack( -side => q{top}, -fill => q{both}, -expand => 1 ); $can = $mw->Canvas( -width => 320, -height => 240 )->pack(); # Create top frame container $rs = $f->Frame->pack( -side => q{left}, -fill => q{both}, -expand => 1 ); $f->Button( -text => q{Exit}, -command => sub { exit; } ) ->pack( -side => q{right}, -fill => q{both}, -expand => 1 ); # Reconfigure canvas size, and create image $can->configure( -width => $image_w, -height => $image_h ); $img = $mw->Photo( -width => $image_w, -height => $image_h, -palette => q{256/256/256} ); $img->blank(); $can->createImage( 0, 0, -image => $img, -anchor => q{nw} ); # Draw grid lines for image { foreach my $x ( 0 .. $image_w ) { $img->put( q{GREEN}, -to => ( $x, $image_h_2 ) ); } foreach my $y ( 0 .. $image_h ) { $img->put( q{GREEN}, -to => ( $image_w_2, $y ) ); } } # Generate pixels on image my @grid; my $time_took = timeit( 1, sub { get_grid( \$img, $max, \@grid ); } ); print qq{Generation took: }, timestr($time_took), qq{\n}; MainLoop; # # Subroutines # sub get_grid { my ( $img, $max, $found ) = @_; foreach my $g ( 0 .. $image_h ) { foreach my $i ( 0 .. $image_w ) { push @{ $found->[$g] }, 0; } } my $level = 0; my @numbers = get_primes_2($max); my $count = 0; my %d = ( x => 0, y => 0 ); my %p = ( x => 0, y => 0 ); foreach my $i ( 0 .. $#numbers ) { foreach my $s (qw(x y)) { $p{$s} += $d{$s}; } $count++; &spinner; if ( ( $level == 0 ) or ( ( $count == $level ) or ( $count == 2 * $level ) ) ) { if ( $count >= 2 * $level ) { $count = 0; $level++; } my $delta = 1; $delta *= -1 if ( $level % 2 ); %d = ( x => 0, y => 0 ); $d{x} -= $delta unless ($count); $d{y} += $delta if ($count); } ${$img}->put( q{BLUE}, -to => ( $image_w_2 + $p{x}, $image_h_2 + $p{y} ) ) if ( $numbers[$i] ); } } sub get_primes_2 { my ($max) = @_; my @found = ( 1 .. $max ); my $i = 0; $found[0] = 0; while ( $i <= int( sqrt($max) ) ) { $i++; next unless ( $found[$i] ); my $j = $found[$i]; my $k = $i + $j; while ( $k <= $#found ) { $found[$k] = 0; $k += $j; } } return @found; } sub help { printf <<HELPTEXT, $0; %s [-width n] [-height n] [-help] -width n - width in pixels to generate -height n - height in pixels to generate -help - display this help text Grid generated is (s - 10) on a side, where s is the smaller of the width and height. Some sizes to experiment with (dependent upon your monitor resolution) include: 1920x1200, 1920x1080, 1680x1050, 1600x1200, 1440x900, 1366x768, 1280x1024, 1280x800, 1280x720, 1024x768, 800x600, 640x480, 640x350, 640x200, 320x200, 160x200 HELPTEXT exit; } sub spinner { print $spinner_data{characters} [ ( $spinner_data{count}++ / $spinner_data{scale} ) % 4 ], "\b"; print '.' unless ( $spinner_data{count} % $spinner_data{bigscale} ); }

With it, I was able to generate (on an Athlon XP 2900+) 348_100 points (590**2 points) in 83 wallclock seconds, 220_900 (470**2) in 47 wallclock seconds, and 10_000 (100**2) in 2 wallclock seconds.

(As an aside, it would probably be much quicker if there were a formula for determining the position based on the value, but I couldn't wrap my mind around one that would work. Anyone?)

HTH.

Replies are listed 'Best First'.
Re^3: ulam's spiral too slow
by orange (Beadle) on Apr 21, 2007 at 07:14 UTC
    thanks very much atcroft , many ideas in your program, which will help. while searching in http://groups.google.com/group/comp.lang.perl.tk
    i have found that we can draw the screen gradually, ie dot by dot with animation by inserting the line
    $mw->update;
    after
    ${$img}->put( q{BLUE}, -to => ( $image_w_2 + $p{x}, $image_h_2 + $p{y} ) ) if ( $numbers$i );
    so we can enjoy watching the process of drawing.

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://611092]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others browsing the Monastery: (3)
As of 2021-07-29 18:36 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found

    Notices?