Take a look at one of my early questions: Algorithm for cancelling common factors between two lists of multiplicands

I guess an approach might be to convert each factor into its decomposition into primes and then to decompose factors on the other side until you can cancel out stuff there as well. That way you prevent multiplying up the numbers into products too large.

Good point.

Sorting and alternating the arrays to keep the temporary product near 1 should help minimizing the error.

Cheers Rolf
_{(addicted to the Perl Programming Language and ☆☆☆☆ :)
Je suis Charlie!}

It really depends on the purpose of the whole thing. For some uses, floating point arithmetic is probably just good enough, and may very well be the most efficient solution; for example, it would probably be just good enough is the final aim is to compute probabilities.

For some others purposes, you may need accurate integer arithmetic.

I am asking all these questions because the best strategy would probably depend on the answers to at least some of these questions. The "shape" of the data is especially important in such cases.

Update: fixed a typo ('numerator' instead of 'denominator' in one place).

Hi,

1. well the numbers are in range of 1-10 thousand (x).
2. well very large with O(x!) being some upper limit (for both numerator and denumerator) but final coefficient is ought to be small from 0.00001 to 10000 3. Yes absolute accuracy is a must have But I see that BrowserUK already had a similar problem when computing fisher's exact, so that mihgt be already solved problem.

Since Perl 6 has good handling of rational numbers, perhaps looking at its guts would help.

Using Perl 6 one could use the OP's arrays to do this:

#!/usr/bin/env perl6

my @a = <1 4 6 2 7 87 5 6 4 32>;
my @b = <86 50 62 41 32>;

my $a = [*] @a;
my $b = [*] @b;

say "Product of array \@a = $a";
say "Product of array \@b = $b";

# generate an arbitrary precision rational number:
my $c = FatRat.new($a, $b);
say "Real \$c: $c";
say "Rational \$c: { $c.numerator } / { $c.denominator }";
[download]

Output

Product of array @a = 112250880
Product of array @b = 349779200
Real $c: 0.3209193
Rational $c: 87696 / 273265
[download]

I'd use a hash of primes as keys, powers of those as the values. Decompose each element of each list into primes. For the numerator list, increase the primes power value. For the denominator list, decrease it:

my @a = qw(1 4 6 2 7 87 5 6 4 32);
my @b = qw(86 50 62 41 32);
my %primes;
map { $primes{$_}++ } map { primes($_) } @a;
map { $primes{$_}-- } map { primes($_) } @b;

sub primes {
   ... # left as an exercise for the reader
}
[download]

Then just compute the product of the powers:

$result *= $_ ** $primes{$_} for keys %primes;
[download]

And this last line is where the discussion in BrowserUk's early question kicks in, with regards to accuracy, overflow, timing etc. Should we sort the keys? is there a more efficient way to produce the division with partial powers of positive and negative exponents? Is there a way to keep the intermediate results close to zero?

My aim is to multiply integers within a given array and then divide two arrays

This is an XY Problem - for division/factorial you don't have to precompute each term.