Beefy Boxes and Bandwidth Generously Provided by pair Networks
XP is just a number
 
PerlMonks  

Re: porting C code to Perl (updated!)

by haukex (Abbot)
on Oct 22, 2017 at 19:57 UTC ( #1201854=note: print w/replies, xml ) Need Help??


in reply to porting C code to Perl

All of your C variables are ints, so you need to change the two divisions in your program like so:

$q = int( $x / (2 * $i - 1) ); ... $q = int( $q / 10 );

And then the two programs produce the same output (Update: "03141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342117067"*, in case anyone was wondering). Alternatively, you can stick a use integer; at the top of the Perl file (of course this only applies when all the variables in the program are integers).

Also, although this doesn't seem to affect your program, note that there are differences between C's modulo % and Perl's % (use integer; also affects this).

* Update 2: The C compiler (gcc -std=c99 -Wall -Wextra -Wpedantic 1201848.c) complained about the line predigit, nines = 0;: "warning: left-hand operand of comma expression has no effect", so initially I adjusted it to your interpretation, predigit=0; nines=0;, but actually that causes a slight variation in the output (first one doesn't change predigit, second one does set it to zero):

0314159265358979323846264338327954288419716939937510582097494459230781 +6406286208998628734825342117067 0314159265358979323846264338327950288419716939937510582097494459230781 +6406286208998628034825342117067 here ^ + and here ^

In either case, making the equivalent change to the Perl program produces the same output. Since these are the digits of π, obviously the second one is the correct one. BTW, I guess you took the C code from here?

Update 3: Minor ninja edits to the above. I'm done for now :-)

Replies are listed 'Best First'.
Re^2: porting C code to Perl -- solved
by Discipulus (Monsignor) on Oct 23, 2017 at 16:12 UTC
    thanks a lot haukex!

    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))

    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;

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

    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.
      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..)

        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% --

        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;

      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";

      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;

      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)); }
      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); }
      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.)

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://1201854]
help
Chatterbox?
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others browsing the Monastery: (7)
As of 2017-12-17 23:43 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    What programming language do you hate the most?




















    Results (466 votes). Check out past polls.

    Notices?