your insights are exactly what I needed. I spotted the type casting of int but I have not thought it constrained all the operations too.. what a complicated world they have with C..

Now I ported to a more perlish versions, but speaking frankly, I'm quite struggling with it's efficiency. Infact the inner for loop for a precision of 1000 cause each of it's line to be called something like 3 million of times if I read correctly the Devel::NYTProf output.

UPDATE some output from NYTProf Performance Profile

Line    Statements    Time on line        Code

 9    1002               49.4ms        for $i(reverse 1..$l){
10    3347682            441ms                $x=10*$a[$i-1]+$q*$i;
11    3347682            474ms                $a[$i-1]=$x%(2*$i-1);
12    3347682            882ms                $q=int($x/(2*$i-1))
[download]

This inner for loop if I read correctly it's not influenced by the outer $j and only set a final (?) $q and the array element $a[$i-1] so i'm trying to cut the loop from there and prebuild an array of q linkable with $j indexes and prefilling the @a accordingly. No big luck until now.

In reality I'm working blindly not having well understood what the code do. I'll try a reverse eng. based on print statements if i do not desist sooner. Another ugly think I've done is the last line where I merely susbtitute the leading 03 with 3, any attempt to do this within the loop failed.

Anyway thank you again!

use strict;
use warnings;

my $n=1002;

my $len = 1 + int (10 * $n / 3);

my $pi;

my @a= (2) x $len;

my $nines = 0;

my $predigit = 0;

foreach my $j(1..$n){
    my $q = 0;
    foreach my $i( reverse 1..$len){
        my $x = 10 * $a[$i-1] + $q * $i;
        $a[$i-1] = $x % (2 * $i - 1);
        $q = int($x / (2 * $i - 1));
    }
    $a[0]=$q%10;
    $q=int($q/10);
    if (9 == $q){ ++$nines;   }
    elsif(10 == $q){
          $pi.=$predigit + 1;
          for (my $k = 0; $k < $nines; $k++){$pi.=0}
          $predigit = $nines = 0;
    }
    else{
         $pi.= int $predigit;
         $predigit = $q;
         if(0 != $nines){
              for (my $k = 0; $k < $nines; $k++) {
                  $pi.=9;
              }
              $nines = 0;
        }
    }
}
print $pi=~s/^03/3./r;
[download]

PS and yes these are the Pi digits and the C source is what you spotted!

L*

I spotted the type casting of int but I have not thought it constrained all the operations too

In C, when you say int q;, that variable is fixed to, depending on how your compiler defines it, a 32 (or 16 or 64) bit signed integer value, no more, no less - simplifying a bit, no matter what you try to assign to it, it will be cast back to an int.

Now I ported to a more perlish versions, but speaking frankly, I'm quite struggling with it's efficiency.

Since functionally the two programs are practically identical, that'll simply be the difference between a complied and interpreted language. I don't have much time for optimization right now, but you might try to compare the performance of the program with and without use integer; - I'm not sure if it'll make a significant difference but it's worth a try.

In reality I'm working blindly not have well understood wht the code do.

A bit of googling on the algorithm brings me to this page, while it's a bit difficult to read visually, it seems to give an example-based explanation of the "spigot algorithm" that this appears to be an implementation of.

Hello again,

you guessed rigth! use integer; boosts performance (if I have build my benchmarks correctly..)

Read more... (3 kB)

Benchmark: running no_integer_module  , with_integer_module for at lea
+st 20 CPU seconds...

no_integer_module  : 21 wallclock secs (20.64 usr +  0.00 sys = 20.64 
+CPU) @  0.92/s (n=19)
with_integer_module: 21 wallclock secs (20.50 usr +  0.00 sys = 20.50 
+CPU) @  1.37/s (n=28)

                    s/iter no_integer_module   with_integer_module
no_integer_module     1.09                  --                -33%
with_integer_module  0.732                 48%                  --
[download]

I read in the docs of the integer module:

> On many machines, this doesn't matter a great deal for most computations, but on those without floating point hardware, it can make a big difference in performance.

The above results show that my machine has not floating point hardware?

Thanks also for the link to the spigot explication; I must admit that yesterday night I've understood almost nothing.. I'll try under sun beans.

L*

There are no rules, there are no thumbs..
Reinvent the wheel, then learn The Wheel; may be one day you reinvent one of THE WHEELS.

Update: Implemented the divisor suggestion by soonix.

Hi Discipulus,

To have Perl match the C output (regarding the number of characters), a missing append is needed at the end of the Perl script. The C code is found here and at stackoverflow. Regarding C, a fix is necessary described here (under Update 2) and here.

$pi .= $predigit;    # <-- missing line

print $pi =~ s/^03/3./r;
[download]

I validated using the following code, based on yours and replies by fellow monks. Notice the Perlish for my $k (0..$nines - 1) { ... } near the end of the script. In your demonstration, calling int on $predigit isn't necessary because $q contains an integer value; e.g. $q = int( ... ).

# The spigot algorithm for calculating the digits of Pi.
# http://www.cut-the-knot.org/Curriculum/Algorithms/SpigotForPi.shtml

use strict;
use warnings;

my $n   = 100;
my $len = int(10 * $n / 3) + 1;
my $pi;

my @a = (2) x $len;

my $nines    = 0;
my $predigit = 0;

for my $j (1..$n) {
    my $q = 0;

    for my $i (reverse 0..$len - 1) {
        my $x = 10 * $a[$i] + $q * ($i + 1);
        my $divisor = 2 * $i + 1;
        $a[$i] = $x % $divisor;
        $q = int($x / $divisor);
    }

    $a[0] = $q % 10;
    $q    = int($q / 10);

    if (9 == $q) {
        ++$nines;
    }
    elsif (10 == $q) {
        $pi .= $predigit + 1;
        for my $k (0..$nines - 1) {
            $pi .= 0;
        }
        $predigit = $nines = 0;
    }
    else {
        $pi .= $predigit;
        $predigit = $q;
        if (0 != $nines) {
            for my $k (0..$nines - 1) {
                $pi .= 9;
            }
            $nines = 0;
        }
    }
}

$pi .= $predigit;

print $pi, "\n";
[download]

Pi computed to 10,000 digits is found here.

Update: The above runs 1.4 times faster with small changes. Basically, use integer. Thanks, haukex.

2a3
> use integer;
5c6
< my $len = int(10 * $n / 3) + 1;
---
> my $len = 10 * $n / 3 + 1;
20c21
<         $q = int($x / $divisor);
---
>         $q = $x / $divisor;
24c25
<     $q    = int($q / 10);
---
>     $q    = $q / 10;
[download]

Regards, Mario

    foreach my $i( reverse 1..$len){
        my $x = 10 * $a[$i-1] + $q * $i;
        $a[$i-1] = $x % (2 * $i - 1);
        $q = int($x / (2 * $i - 1));
    }
[download]

not sure if it's better or worse, but I'd change that to

    foreach my $i( reverse 0 .. $len-1){
        my $x = 10 * $a[$i] + $q * ($i+1);
        my $divisor = 2 * $i + 1;
        $a[$i] = $x % $divisor;
        $q = int($x / $divisor);
    }
[download]

not for efficiency, but for (perhaps) easier understanding
• $i one less, so the array index is a simple variable
• the common expression of the last two lines as a variable of its own

Hi soonix,

your version sounds much perlish! infact I translated the code line by line.

I totally agree that your version is more readable and .. explicit. It also avoid the divisor repetition.

L*

There are no rules, there are no thumbs..
Reinvent the wheel, then learn The Wheel; may be one day you reinvent one of THE WHEELS.

but I have not thought it constrained all the operations too.. what a complicated world they have with C

In Perl a variable is a concept - you can put whatever you want into it and Perl will try to do something suitable. In C a variable is a contract - you (and the compiler) must honor it and that includes forced conversions if necessary (and allowed). In a 'do what I mean' sense C is more complicated, in a 'what states do I need to consider' sense it is less complicated.

If I write a library function in C then I do not have to worry if my input variables may contain an integer, a float, an array, a hash, a reference, an object or whatever. Each variable can contain exactly one of these (unless I specifically do not want to care about it). This may be a boon or a burden. It depends.




(Actually you do not have to honor the contract. You can throw a tantrum, stomp with your feet and break it. But you should.)