baxy77bax has asked for the wisdom of the Perl Monks concerning the following question:

hi,

today i have a question about the multiplication process. ok , so the situation is that a have an array of numbers spanning from 230000..900000. oh, i have a dual core proc. my question is how to multiply the array of numbers but as fast as possible. i prefer not to use log function or gamma function due to some later errors i get(i'm referring to those that see the similarity with factorial function). so what i got for now is to do something like this:

my $k=1;
for (230000..900000){
  $k*=$_
}
print $k;
# typical alg. for factorial calculation

[download]
but this is too slow. then i thought ok let paralyze the whole bloody thing... but how should i paralyze it so that it get the procedure going as fastest as it can. should i :

thread1 : for (230000..565000){
             #multiply
          }
thread2: for (565001..900000){
             #multiply
          }

[download]
or maybe 

thread1 : for (230000..397500,732500..900000){
             #multiply
          }
thread2: for (397500..732500){
             #multiply
          }
# it will run faster

[download]
or maybe someone has a shortcut on how to reduce the multiplication step

does anyone has an alternative idea. i would like to hear an 'outside the box' opinion :). all comments are welcomed !

cheers

baxy

UPDATE:

First sorry for the misspell, i mistype the word and then just choose the first suggestion the spellchecker gives me without seeing what i have picked. Sorry!

Why do i need this precision. this number is then used in a recursive calculation that reduces the number up to a 1e-300. this is then used for a weighting and the difference in this case is huge, up to a 1e50 , that is 50 orders of magnitude if i use log or Stirling. and this is a problem for me, because depending on the later entropy that i'm calculating this means difference between the some biological signal that is important to me and case where there is no signal.... so ....

Why do i use Perl?

the difference that i'm getting for the brute force alg. that i mentioned between c and Perl is more or less big but not big enough. which means it is not the language that is the problem but the method.

and yes the bignum is used. i was assuming that was clear from the example i gave

the cancellation for such a big array of numbers i haven't considered since this is the canceled form , kind of ...

cheers

Replies are listed 'Best First'.
Re: how to multiply an array of number as fast as posible
by BrowserUk (Patriarch) on Sep 02, 2010 at 15:16 UTC

    The answer to your stated problem is (approximately): 

    1.62675140326585151695359576572305028615189801780017874401138747953366
+6153159557
7231689168104895638321577104465527647015203626362603998098979186946926
+8832653563
9876783696445088873548169461692031716658344408349608575969073401085646
+9974613384
9405956337321357208524215023135129502713155156225709454163291397424581
+6205784347
5431740808707270038873430922419306290943341499184229388612632870411538
+6624697621
1861673434551121694807279905899572891343788110628871316393375609771228
+8741592371
0603410526214509643406584397169902292984256457451844313620574254135229
+8152022680
9667066503022068942686945186662371921322607350580802347649425019123435
+6116588173
3499576581595447507264764340471182267254547886431989042026739164206635
+2222527744
3185422437032044145067492037856780857407031186997008368115810653126418
+5732353764
8593952946070043338085483314164347241434879451637334242547144110143792
+0986573147
31499871814441453762083542077883230646... × 10^3834649

    [download]

    As you can see, for full accuracy, however you calculate it, it's gonna take a while. So, rather than eschewing the use of approximations, you're going to have to decide how much accuracy you actually need?

    Also, it's often the case for calculations that generate these silly numbers, that they are only intermediate terms, with the final results being numbers much more in the realms of reality. And often, it is possible (and very desirable) to avoid the silly-sized intermediate terms by cancelling like terms earlier in the calculation. Describing your actual purpose may lead to better solutions.

    Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
    "Science is about questioning the status quo. Questioning authority".
    In the absence of evidence, opinion is indistinguishable from prejudice.
[reply]
[d/l]
Re: how to multiply an array of number as fast as posible
by kennethk (Abbot) on Sep 02, 2010 at 14:44 UTC
    What application could you have that needs a precise value of this product? I would be very surprised if you could not get the accuracy you require using the Stirling_approximation. In any case, if your question is optimization, then you need to test. Specifically, you need to use benchmarking (see Benchmark) and profiling (see Devel::NYTProf) to determine where exactly your bottlenecks are.

    For this operation, one very simple optimization would be swapping from a for to a while loop since Foreach Loops need to construct the list before beginning iteration. threads is also a fairly simple way to improve performance. Here is a simple benchmark, showing a 38% speedup using a while loop and two threads. Note the speedup is not higher because creating threads involves overhead.

    Threading in this case does not make sense - the overhead in starting a thread exceeds the performance boost. For loops with range operators are automatically transformed into efficient C-style loops internally by Perl. But you should really be using the Stirling_approximation and only storing the log of your value to avoid overflow. 

    #!/usr/bin/perl
use strict;
use warnings;
use Benchmark qw':all :hireswallclock';
use threads;

cmpthese(10, {
    'while' => sub {
        my $i = 230000;
        my $k = 1;
        while ($i <= 900000) {
            $k *= $i++;
        }
        },
    'for' => sub {
        my $k = 1;
        for (230000 .. 900000) {
            $k *= $_;
        }
        },
    'threads' => sub {
        my $k = 1;
        my $thr2 = async {
            my $k = 1;
            my $i = 565001;
            while ($i <= 900000) {
                $k *= $i++;
            }

            };
        my $i = 230000;
        while ($i <= 565000) {
            $k *= $i++;
        }
        $k *= $thr2->join();
    }
});

    [download]

    outputs 

              Rate threads   while     for
threads 3.09/s      --    -29%    -38%
while   4.33/s     40%      --    -13%
for     4.96/s     60%     15%      --

    [download]

    And if you look at the results from these multiplications, you have likely exceeded the maximum value representable by floating point on your machine.

    Update: Need caffeine, read my Benchmark results backwards, fixed above.

[reply]
[d/l]
[select]

      The problem with your benchmark is the calculation moves into floating point exception handling very early on.

      If you avoid that by adding logs, using threads improve performance by 65%: 

      #! perl -slw
use strict;
use threads;
use Time::HiRes qw[ time ];

{
    my $start = time;
    my $t = 0;
    $t += log( $_ ) for 230000..900000;
    printf "%.15f\n", $t;;

    printf "Took %.6f\n", time() - $start;
}

{
    my $start = time;

    my $thr = async {
        my $t = 0;
        $t += log( $_ ) for 230000..565000;
        return $t;
    };
    my $t = 0;
    $t += log( $_ ) for 565001..900000;

    $t += $thr->join;

    printf "%.15f\n", $t;;

    printf "Took %.6f\n", time() - $start;
}


__END__
C:\test>junk32
8829606.110849546300000
Took 0.132204
8829606.110849652400000
Took 0.080650

      [download]
      Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
      "Science is about questioning the status quo. Questioning authority".
      In the absence of evidence, opinion is indistinguishable from prejudice.
[reply]
[d/l]
        But at the same time, you've just added a transcendental function to every loop iteration, which is a much more expensive operation than a multiplication. As I pointed out in Re^3: how to multiply an array of number as fast as posible. A more fair comparison would be scaling the operations so that we avoid INFs in the first place: 

        #!/usr/bin/perl
use strict;
use warnings;
use Benchmark qw':all :hireswallclock';
use threads;

cmpthese(10, {
    'for' => sub {
        my $k = 1;
        for (230000 .. 900000) {
            $k *= 1 + $_* 0.0000000001;
        }
        #print "for: $k\n";
        },
    'threads' => sub {
        my $thr2 = async {
            my $k = 1;
            for (565001 .. 900000) {
                $k *= 1 + $_* 0.0000000001;
            }
            return $k;
        };
        my $k = 1;
        for (230000 .. 565000) {
            $k *= 1 + $_* 0.0000000001;
        }
        $k *= $thr2->join();
        #print "threads: $k\n";
    }
});

        [download]

        I've replaced one multiplication per iteration with 2 multiplications and an addition (plus the store), which should shift the balance toward threads. And yet, the benchmark comes out in favor of single-threaded operation: 

                  Rate threads     for
threads 2.92/s      --    -35%
for     4.48/s     53%      --

        [download]
[reply]
[d/l]
[select]

      the overhead in starting a thread exceeds the performance boost.

      What performance boost could you possibly get? The CPU is already working at 100% calculating the number. That's why threads makes no sense in this case.

[reply]
        The CPU is already working at 100% calculating the number.

        Yes, one core is working at 100% to calculate the product. By splitting the list in half, two cores are working at 100% - the OP cites having a dual core. It just so happens that in this case:

        loop_overhead + n*multiplication < thread_overhead + loop_overhead + (n/2)*multiplication

        as I would expect for this kind of simple operation. But throw in transcendental functions and maybe the balance shifts.

[reply]
        What performance boost could you possibly get? The CPU is already working at 100% calculating the number. That's why threads makes no sense in this case.

        Ahem! From the OP.

        i have a dual core proc

        If he decided to calculate this in arbitrary precision, using both his CPU's would make a huge difference.

[reply]
Re: how to multiply an array of number as fast as posible
by talexb (Chancellor) on Sep 02, 2010 at 15:16 UTC

    For a totally off the wall suggestion, you could factor each of the multiplicands into a series of prime numbers, then increment the count of each prime number. At the end of the process, calculate the products of all of the powers.

    So 30*22*45 would break down to (2*3*5) * (2*11) * (3*3*5), giving 2^2, 3^3, 5^2 and 11^1, or 4 * 9 * 25 * 11.

    The advantage of this approach is that you're not doing multiplications over and over again, you're just factoring and saving counts of prime numbers. The only multiplication is done at the very end.

    Alex / talexb / Toronto

    "Groklaw is the open-source mentality applied to legal research" ~ Linus Torvalds

[reply]
Re: how to multiply an array of number as fast as posible
by JavaFan (Canon) on Sep 02, 2010 at 17:24 UTC
    [Multiplying numbers]

    but this is too slow.

    My first reaction to anyone saying that basic arithmetic is too slow in Perl is: are you sure Perl is the right language to solve your problem in?.
    i would like to hear an 'outside the box' opinion :)
    Here's an outside the box opinion: 
        use autodie;

    my @a = (230000 .. 900000);

    $ENV{BC_LINE_LENGTH} = 1 << 31;

    open my $cld, "|-", "bc";
    local $" = "*";
    print $cld "@a\n";
    close $cld;

    [download]
    Now, that gets you an exact answer. And is certainly "out of the (Perl) box". It may not be the fastest. If you need the fastest solution, I'd look into PDL. It's made for stuff like that. Alternatively, I'd port FORTRAN to Parrot, write a FORTRAN routine to calculate the product, then call the FORTRAN routine from a more familiar language that also runs on Parrot. But the PDL way may be easier.

[reply]
[d/l]
Re: how to multiply an array of number as fast as posible
by SuicideJunkie (Vicar) on Sep 02, 2010 at 14:45 UTC

    If you want it really fast, and have 60+Gb free on your disk, you could cache the factorials up to 90k in a fixed record length file, then seek it and add/subtract to get the ranges you want.

    PS: Why in the world do you need so much precision that you can't use a pretty good approximation function? Surely you're not using all of the half-million digits in the answer.

[reply]
Re: how to multiply an array of number as fast as posible
by Anonymous Monk on Sep 02, 2010 at 14:29 UTC

    Would you be using BigInts, or does that just overflow after a few iterations?

    PS: Parallelize vs Paralyse

[reply]

Back to Seekers of Perl Wisdom