http://qs1969.pair.com?node_id=482851


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

I cannot read Haskell so I was not sure how the factoring was done. Going through the example it seems like tmoertel was just factoring like terms.
My implementation doesn't actually do any factoring. Rather, it efficiently cancels all like terms before doing any multiplications or divisions. The idea is to replace expensive mathematical operations with inexpensive comparisons until I have picked all of the low-hanging fruit. If I pick enough fruit, there isn't enough left on the tree to make factoring worthwhile, and so I can just go ahead a multiply out the rest. (Although it might be interesting to emit the tree after my low-handing-fruit pass and process it with some of the other bits of code in this thread.)

The following shows how my code might compute 7!/(3!4!): 

7!
-----
3! 4!

{ expand fac into series of multiplications }

 P(2,3,4,5,6,7)
-----------------
P(2,3) * P(2,3,4)

{ merge multiplied products }

 P(2,3,4,5,6,7)
-----------------
  P(2,2,3,3,4)

{ cancel like terms across division boundary }

 P(/,/,/,5,6,7)
-----------------
  P(/,2,/,3,/)

{ multiply and divide remaining terms }

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

{ result }

35

[download]
In reality, the code does all of these steps in a parallel pipeline, which means I don't have to pay the price for large intermediate terms: bits of big terms are plucked off and used as they are produced lazily. This is an essentially free benefit of using Haskell.

Cheers,
Tom

Tom Moertel : Blog / Talks / CPAN / LectroTest / PXSL / Coffee / Movie Rating Decoder

  • Comment on Re^6: Algorithm for cancelling common factors between two lists of multiplicands
  • Download Code

Replies are listed 'Best First'.
Re^7: Algorithm for cancelling common factors between two lists of multiplicands
by sk (Curate) on Aug 11, 2005 at 08:50 UTC
    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

    Going back to your example 

    { 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

    [download]
    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>
<readmore>

    [download]
    #!/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, $/)
+;

    [download]
    __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

    [download]

    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!

[reply]
[d/l]
[select]

In Section Seekers of Perl Wisdom