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.

Your benchmark looks ok, thanks, although the difference is a little smaller on my machine (-21% / +27%). I did surround your three divisions with int() in the no_integer version.

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

I doubt it, rather I guess that Perl can simply use more efficient implementations of the mathematical opcodes, that don't need to worry about all the floating-point stuff that Perl hides in its numerical types.

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]

    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]

• $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.

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.

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