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


in reply to Re^6: Algorithm for cancelling common factors between two lists of multiplicands (192.5 ms)
in thread Algorithm for cancelling common factors between two lists of multiplicands

Here is my implementation and results with benchmark. It is 45-50% faster. I am not sure what it the exact digit at which the result becomes unreliable so it could be slightly off

My perl skills are not that great so my implementation is very simple and straightforward

tmoertel's haskell implementation amazes me on the precision! I wonder if that is specific to Haskell or the way it was coded

My implementation

#!/usr/bin/perl use strict; use warnings; use Benchmark::Timer; my $timer= new Benchmark::Timer; my $tag = "fet inputs: " . join (',',@ARGV); $timer->start($tag); my (@snum,@sden,@nmul,@dmul) = (); my ($i,$p,$power) = (0,0,0); construct (@ARGV); @snum = sort {$b<=>$a} @snum; @sden = sort {$b<=>$a} @sden; # Make the arrays equal size if (@snum < @sden) { foreach $i (@snum..$#sden) { $snum[$i] = 0;} } else { foreach $i (@sden..$#snum) { $sden[$i] = 0;} } for $i (0..$#snum) { my @elements; if ($snum[$i] > $sden[$i]) { @elements = (($sden[$i]+1)..$snum[$i]); my ($num,$np) = multiply(\@elements); push(@nmul,$num); $power += $np; } elsif ($sden[$i] > $snum[$i]) { @elements = (($snum[$i]+1)..$sden[$i]); my ($den,$dp) = multiply(\@elements); push(@dmul,$den); $power -= $dp; } } my ($num,$den) = (1,1); $num *= $_ for (@nmul); $den *= $_ for (@dmul); printf ("Ratio = %.17fe%d\n", $num/$den,$power); $timer->stop($tag); print $timer->report; sub multiply { my $p = 0; my $x = shift; my $product = 1; for (@$x) { $product *= $_; while ($product > 1) { $product /= 10; $p++; } while ($product < 0.1) { $product *= 10; $p--; } } return ($product,$p); } sub construct { my @data = @_; my $R1 = $data[0]+$data[1]; my $R2 = $data[2]+$data[3]; my $C1 = $data[0]+$data[2]; my $C2 = $data[1]+$data[3]; my $N = $R1 + $R2; @snum = ($R1,$R2,$C1,$C2); @sden = ($N,$data[0],$data[1],$data[2],$data[3]); }
Output

I gave enough time between each run to avoid any CPU heating/fan issues

program BUK = your implementation to avoid machine speed variation.

C:\>perl fet 989 9400 43300 2400 Ratio = 0.08070604647867725e-7028 1 trial of fet inputs: 989,9400,43300,2400 (80.804ms total) C:\>perl fet 1e5 2e5 2e5 1e5 Ratio = 0.13249945964968005e-14759 1 trial of fet inputs: 1e5,2e5,2e5,1e5 (3.289s total) C:\>perl fet 1e6 2e6 2e6 1e6 Ratio = 0.02733537591856761e-147574 1 trial of fet inputs: 1e6,2e6,2e6,1e6 (38.062s total) C:\>perl buk 989 9400 43300 240 0.80706046478677251e-7029 1 trial of [989 9400 43300 2400] (163.696ms total) C:\>perl buk 1e5 2e5 2e5 1e5 1.32499459649680040e-14760 1 trial of [1e5 2e5 2e5 1e5] (6.552s total) C:\>perl buk 1e6 2e6 2e6 1e6 2.73353759185676100e-147576 1 trial of [1e6 2e6 2e6 1e6] (70.739s total)