We don't bite newbies here... much PerlMonks

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

by sk (Curate)
 on Aug 11, 2005 at 08:50 UTC ( #482867=note: print w/replies, xml ) Need Help??

Update:Added output and updated the list entries based on BrowserUk's final code example

Thanks for the detailed explanation!

Sometimes i get very sloppy when I write. My apologies, i should not have used the word factorize instead i should have used the word 'cancel' out.. Actually I was thinking more in terms removing'like' elements. This is in reference to your code.

In the code that I had, I was removing further cancelable terms

```{ multiply and divide remaining terms }

5 * 6 * 7
---------
2 * 3

The program I had would have done this before multiplying

5 * 7
-----
1
{result}
35

Here is a simple implementation of canceling out factorial terms without having to expand the factorials because of the fact

```n!/k! = PI(x) where x goes from (k+1) to (n) assuming n > k; PI(x) sta
+nds for product of<p>

```#!/usr/bin/perl

use strict;
use warnings;

# Numerator and Denominator specified as factorials [BrowserUk]'s exam
+ple numbers

my @snum = (44_289, 11_800, 10_389, 4570);
my @sden = (56_089, 989, 9_400, 43_300, 2_400);

# old list from previous node
# my @snum = (44_289, 11_800, 10_389, 45_700);
# my @sden = (56_089, 989, 9_400, 43_300, 11_800, 2_400);
#
@snum = sort {\$b<=>\$a} @snum;
@sden = sort {\$b<=>\$a} @sden;

my \$i = 0;

# Make the arrays equal size
if (@snum < @sden) {
foreach \$i (@snum..\$#sden) { \$snum[\$i] = 0;}
} else {
foreach \$i (@sden..\$#snum) { \$sden[\$i] = 0;}
}

print +(\$_,\$/) for (@snum);
print \$/;
print +(\$_,\$/) for (@sden);
print \$/;

my @nexp = ();
my @dexp = ();

# n!/k! = (k+1)..(n) [assuming n > k]
for \$i (0..\$#snum) {
if (\$snum[\$i] > \$sden[\$i]) {
print ("Numerator: Going to push from ", \$sden[\$i]+1, " to ",
+\$snum[\$i],\$/);
push (@nexp, ((\$sden[\$i]+1)..\$snum[\$i]));
} elsif (\$sden[\$i] > \$snum[\$i]) {
print ("Denominator: Going to push from ", \$snum[\$i]+1, " to "
+, \$sden[\$i],\$/);
push (@dexp, ((\$snum[\$i]+1)..\$sden[\$i]));
}
}

print ("Length of expanded numerator   = ", scalar @nexp, \$/);
print ("Length of expanded denominator = ", scalar @dexp, \$/);
print ("Total Number of elements = ", scalar @nexp + scalar @dexp, \$/)
+;
```__END__
Denominator: Going to push from 44290 to 56089
Denominator: Going to push from 11801 to 43300
Numerator: Going to push from 9401 to 10389
Numerator: Going to push from 2401 to 4570
Denominator: Going to push from 1 to 989
Length of expanded numerator   = 3159
Length of expanded denominator = 44289
Total Number of elements = 47448

Now with the expanded list I would run the GCD program which cancels out even more terms like for example the number 11 cancels 56089 in the numerator and cancels 2398 in the denominator

I hope it is clear now.

The reason I was trying to factor down even further is to avoid computing at very high precision for numbers that are going to be canceled out anyways

Has been a very interesting exercise so far!!! I will keep thinking about this problem as I am sure there should be a way to factor these numbers down further without going GCD route given they have such a nice pattern..after all they are just sequential products!

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

How do I use this? | Other CB clients
Other Users?
Others surveying the Monastery: (8)
As of 2019-10-22 02:12 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
In 2019 the site I miss most is:

Results (55 votes). Check out past polls.

Notices?