in reply to Re: Algorithm for cancelling common factors between two lists of multiplicands

in thread Algorithm for cancelling common factors between two lists of multiplicands

If the solution in my earlier node doesn't return what you want, this surely will:

or this messier but potentially faster alternative:use Math::BigInt (); *gcd = \&Math::BigInt::bgcd; sub embiggen { local $_ = @_ ? $_[0] : $_; return Math::BigInt->new($_); } my @a = ( 10, 20, 33, 45, 60 ); my @b = ( 2, 5, 10, 12, 16, 23, 45 ); # my %a = map { $_ => 1 } @a; # my %b = map { $_ => 1 } @b; # # my @c = map embiggen, # grep { !$b{$_} } # @a; # # my @d = map embiggen, # map { Math::BigInt->new($_) } # grep { !$a{$_} } # @b; my @c = @a; my @d = @b; foreach my $c (@c) { foreach my $d (@d) { my $gcd = gcd($c, $d); $c /= $gcd; $d /= $gcd; } } @c = grep { $_ != 1 } @c; @d = grep { $_ != 1 } @d;

Both untested.use Math::BigInt (); use Math::Big::Factors (); *gcd = \&Math::BigInt::bgcd; *factor = \&Math::Big::Factors::factors_wheel; sub embiggen { local $_ = @_ ? $_[0] : $_; return Math::BigInt->new($_); } my @a = ( 10, 20, 33, 45, 60 ); my @b = ( 2, 5, 10, 12, 16, 23, 45 ); # my %a = map { $_ => 1 } @a; # my %b = map { $_ => 1 } @b; # # my @c = map embiggen, # grep { !$b{$_} } # @a; # # my @d = map embiggen, # grep { !$a{$_} } # @b; my @c = @a; my @d = @b; my %c_factors; foreach my $c_idx (0..$#c) { my @c_factors = factor($c[$c_idx]); foreach my $c_factor (@c_factors) { push(@{$c_factors{$c_factor}}, $c_idx); } } foreach my $d (@d) { my @d_factors = factor($d); foreach my $d_factor (@d_factors) { next unless $c_factors{$d}; next unless @{$c_factors{$d}}; my $c_idx = shift(@{$c_factors{$d}}); $c[$c_idx] /= $d_factor; $d /= $d_factor; } } @c = grep { $_ != 1 } @c; @d = grep { $_ != 1 } @d;

In Section
Seekers of Perl Wisdom