Beefy Boxes and Bandwidth Generously Provided by pair Networks
Just another Perl shrine
 
PerlMonks  

Re: ulam's spiral too slow

by graff (Chancellor)
on Apr 16, 2007 at 03:16 UTC ( #610253=note: print w/ replies, xml ) Need Help??


in reply to ulam's spiral too slow

After seeing the difference in outputs between the OP code and liverpole's version, and then actually looking up the references at wikipedia, I realized that there were other problems besides execution speed: way too many spots were being drawn in black, which meant way too many numbers were being categorized as primes I felt compelled to figure out who was wrong; I have updated my earlier reply accordingly.

I also noticed that the OP code actually draws all the points (from 1 to $max), both the supposed primes and the supposed non-primes. But you really only need to draw one set, and just leave the other set as "background color".

Then, I thought it would be helpful to get a sense of what took longest -- computing or drawing -- so I decided to refactor the code as follows:

  • run through all the desired numeric range before doing any drawning, keeping track of the x/y coords as we go;

  • each time we find a prime number, store that as both a hash key and as an item in an ascending array; use the hash value to store the x/y coords where the dot should be drawn for that prime;

  • once all the primes have been found, set up the Tk::Canvas, then run through the sorted list of prime values (which are hash keys), and draw a dot for each one.

As it turns out, the computing takes about twice as long as the drawing (4 sec vs. 2 sec for a max number of 150,000, which pretty well fills the given grid); but bear in mind the compute step loops over all integers in the given range, while the drawing step only loops over the primes.

And luckily, the resulting canvas looks a lot more like the pictures I saw over at wikipedia (it still might not be entirely correct -- but you could try dumping a portion of the %primecoord hash structure to make sure the values are as intended).

#!/usr/local/bin/perl use strict; use Tk; die "Usage: $0 max_number\n" # use the command-line, Luke! if ( @ARGV != 1 or $ARGV[0] !~ /^\d+/ ); my $lastnumber = shift; my ( $mincoord, $midcoord, $maxcoord ) = ( 50, 250, 450 ); plot_grid( compute_primes( $lastnumber )); MainLoop; { # closure for building prime number hash structure my @sorted_primes = ( 1 ); # primes in ascending order my %primecoord = ( 1 => [$midcoord, $midcoord] ); # HoA: keys are primes, values are x/y coords in grid sub ck_prime { my ( $num, $x, $y ) = @_; my $end = int( sqrt( $num )); my $keep = 1; for my $prime ( @sorted_primes ) { if ( 0 == $num % $prime ) { $keep = 0; last; } elsif ( $prime > $end ) { last; } } if ( $keep ) { $primecoord{$num} = [ $x, $y ]; push @sorted_primes, $num; } } sub compute_primes { # list of directions for incrementing x, y coordinates: my %vector = ( 0 => [ 1, 0 ], # rightward 1 => [ 0, 1 ], # downward 2 => [ -1, 0 ], # leftward 3 => [ 0, -1 ], # upward ); my $x = my $y = 250; # starting position my $direction = 0; # changes when we've gone $pathlen steps my $traveled = 0; # no. of points drawn in current direction my $pathlen = 1; # increments on every second direction chang +e my $changes = 0; # no. of dir. changes since last $pathlen in +crement my $number = 1; my $bgn = time; while ( ++$number <= $lastnumber ) { $x += $vector{$direction}[0]; $y += $vector{$direction}[1]; last if ( $x < $mincoord or $x > $maxcoord ); if ( ++$traveled == $pathlen ) { $direction = ++$direction % 4; $traveled = 0; if ( ++$changes % 2 == 0 ) { $changes = 0; $pathlen++; } } ck_prime( $number, $x, $y ); } my $end = time; warn "Checked $lastnumber integers in ", $end - $bgn, " sec\n" +; return( \@sorted_primes, \%primecoord ); } } sub plot_grid { my ( $primes, $coords ) = @_; my $mw = MainWindow->new; my $c = $mw->Canvas(-width => $maxcoord+50, -height => $maxcoord+5 +0, -background => 'white' )->pack; $c->createLine( $mincoord, $midcoord, $maxcoord, $midcoord ); $c->createText( $mincoord-30, $midcoord, -fill => 'blue', -text => + 'X'); $c->createLine( $midcoord, $mincoord, $midcoord, $maxcoord ); $c->createText( $midcoord, $mincoord-30, -fill => 'blue', -text => + 'Y'); my $bgn = time; for my $prime ( @$primes ) { my ( $x, $y ) = @{$$coords{$prime}}; $c->createText( $x, $y, -fill => 'black', -text => "\xb7" ); } my $end = time; warn "Plotted ", scalar @$primes, " primes in ", $end - $bgn, " se +c\n"; }
Note that I used "\xb7" (centered dot) as the character -- seemed like "." (period) was off-center.

(updated to correct the comments about the "%vector" hash, to reflect the fact that coords in Tk::Canvas put 0,0 at the upper left corner)


Comment on Re: ulam's spiral too slow
Download Code

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others about the Monastery: (3)
As of 2014-09-24 04:17 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    How do you remember the number of days in each month?











    Results (245 votes), past polls