Beefy Boxes and Bandwidth Generously Provided by pair Networks
go ahead... be a heretic
 
PerlMonks  

Re: Finding divisors from factors (avoid dups)

by tye (Sage)
on Oct 09, 2014 at 05:25 UTC ( [id://1103254]=note: print w/replies, xml ) Need Help??


in reply to Finding divisors from factors

I make no claim that this is the fastest approach. It is likely slower because rather than an optimized call to sort, it does merge sorts as it goes (which might be faster if I were doing those merge sorts in C more like sort works). It also likely uses more memory than many solutions.

Though it appears to run in an instant on the size of problems I've thrown at it.

I only post it because I liked that I was able to avoid having to detect duplicates. I don't bother to do the multiplication to compute a divisor if it would end up being a duplicate.

#!/usr/bin/perl -w use strict; my %f = ( 2 => 2, 3 => 1, 5 => 1, 11 => 1, 277412413 => 1 ); my @f = sort { $a <=> $b } keys %f; my @d = @f; my( %d, %x ); for my $i ( 0..$#f ) { my $f = $f[$i]; ( $d{$f} = [(0)x@f] )->[$i]++; $x{$f} = $i; } for my $i ( 0..$#f ) { my $f = $f[$i]; my $p = $f{$f}; my @t = @d; for my $e ( 1..$f{$f} ) { my( @t2, @m, @n ); while( @t ) { my $t = shift @t; merge( \@n, $t, \@m, 1 < $e ? \@d : () ); push @n, $t if 1 == $e; if( $d{$t}[$i] < $p && $x{$t} <= $i # Avoid duplicates ) { my $m = $t*$f; push @m, $m; push @t2, $m; ( $d{$m} = [@{ $d{$t} }] )->[$i]++; $x{$m} = $i if ! $x{$m} || $x{$m} < $i; } } @t = @t2; merge( \@n, 0, \@m, 1 < $e ? \@d : () ); @d = @n; } } print "Factors:"; for my $f ( @f ) { if( 1 < $f{$f} ) { print " $f^$f{$f}"; } else { print " $f"; } } print "\nDivisors: 1 @d\n"; exit; sub merge { my( $to_av, $max, $from_av, @rest ) = @_; if( $max ) { while( @$from_av && $from_av->[0] < $max ) { my $next = shift @$from_av; merge( $to_av, $next, @rest ) if @rest; push @$to_av, $next; } merge( $to_av, $max, @rest ) if @rest; } elsif( @rest ) { while( @$from_av ) { my $next = shift @$from_av; merge( $to_av, $next, @rest ); push @$to_av, $next; } merge( $to_av, 0, @rest ); } else { push @$to_av, @$from_av; @$from_av = (); } }
Factors: 2^2 3 5 11 277412413 Divisors: 1 2 3 4 5 6 10 11 12 15 20 22 30 33 44 55 60 66 110 132 165 +220 330 660 277412413 554824826 832237239 1109649652 1387062065 16644 +74478 2774124130 3051536543 3328948956 4161186195 5548248260 61030730 +86 8322372390 9154609629 12206146172 15257682715 16644744780 18309219 +258 30515365430 36618438516 45773048145 61030730860 91546096290 18309 +2192580

- tye        

Replies are listed 'Best First'.
Re^2: Finding divisors from factors (avoid dups)
by danaj (Friar) on Oct 09, 2014 at 06:46 UTC

    > Though it appears to run in an instant on the size of problems I've thrown at it.

    For more complication, we can use a pathological case:

    #!/usr/bin/env perl use warnings; use strict; use bigint; my @f = (2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59); my @d = divisors(1922760350154212639070,@f); print "$_\n" for @d;

    Generating the 131,072 divisors is taking my machine anywhere from 5 seconds to 50 seconds for the various solutions. The performance ordering is a little different for bigints than for native ints. Roboticus's simple loop is the fastest, with my non-sqrt hash solution just behind. The least memory is my sqrt hash solution but not by a lot.

Log In?
Username:
Password:

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

How do I use this?Last hourOther CB clients
Other Users?
Others chanting in the Monastery: (5)
As of 2024-03-29 13:53 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found