XP is just a number PerlMonks

### Re: Algorithm for cancelling common factors between two lists of multiplicands

by tlm (Prior)
 on Aug 09, 2005 at 13:53 UTC ( #482213=note: print w/replies, xml ) Need Help??

Here's a another solution. It takes two array refs, makes copies of them, and cancels out common terms, removing all 1's.

```sub list_reduce {
my ( \$top, \$bot ) = map [ grep \$_ != 1, @\$_ ], @_;
die "Bad data\n" if ( grep \$_ < 1, @\$top, @\$bot );
OUTER:
for my \$i ( reverse 0 .. \$#\$top ) {
for my \$j ( reverse 0 .. \$#\$bot ) {
( \$top->[ \$i ], \$bot->[ \$j ] ) = reduce( \$top->[ \$i ], \$bot->[ \$
+j ] );
splice @\$bot, \$j, 1 if \$bot->[ \$j ] == 1;
if ( \$top->[ \$i ] == 1 ) {
splice @\$top, \$i, 1;
next OUTER;
}
}
}
return ( \$top, \$bot );
}

sub reduce {
my ( \$top, \$bottom ) = @_;
my \$gcd = Math::BigInt::bgcd( \$top, \$bottom );
return ( \$top/\$gcd, \$bottom/\$gcd );
}

the lowliest monk

Create A New User
Node Status?
node history
Node Type: note [id://482213]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others avoiding work at the Monastery: (5)
As of 2019-10-19 22:07 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
In 2019 the site I miss most is:

Results (48 votes). Check out past polls.

Notices?