No such thing as a small change 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
Domain Nodelet?
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 surveying the Monastery: (10)
As of 2023-03-20 13:22 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
Which type of climate do you prefer to live in?

Results (59 votes). Check out past polls.

Notices?