Beefy Boxes and Bandwidth Generously Provided by pair Networks
Keep It Simple, Stupid
 
PerlMonks  

Comment on

( #3333=superdoc: print w/ replies, xml ) Need Help??
I was able to construct a non-recursive implementation of the Ackermann function.

Impressive work!

Maybe you'll have better luck with that.

I couldn't see much opportunity for parallisation in your first version.

Update: Cleaned up code a bit.

That's certainly easier to follow. (*)

The 'obvious' thing would be to async the inner for loop. Except that with maximum realistic values of m being 5, starting a thread for 5 iterations is nonsense.

So then my attention moves to the outer loop, with the thought that you can often split the range of a loop into subranges and run them in parallel.

But, firstly we don't know the range. Secondly, even iteratively, the dependency of each subsequent iteration upon the previous would require lock-stepping the threading--either through complex locking or queuing--and with the minimal effort required for each step of each iteration versus the cost of locking and context switching, again make that a non-starter.

Upshot: I think you called it earlier with your z = F(x); return F(z); comment that went over my head at the time. In the light of that, I've modified my first tentative rule from a post above to be:

For a recursive algorithm--that is not tail recursive--to be a suitable candidate for parallelisation, it requires that it has multiple, independant, recursive calls at each level.

The interesting thing now is: how many recursive algorithms fit that pattern?

m < 4 can be special-cased. Known formula exist for A(0,n), A(1,n), A(2,n) and A(3,n).

Indeed. The following returns all the tractable cases within the machine capability in a blink of an eye:

sub ackermann_c { use constant INF => exp(~0 >> 1); my( $m, $n ) = @_; --$m, $n=1 if $n == 0; return $n + 1 if $m == 0; return $n + 2 if $m == 1; return 2*( $n+3)-3 if $m == 2; return 2**($n+3)-3 if $m == 3; return INF unless $m == 4; my( $p, $r ) = ( $n+3, 2 ); $r = 2**$r while --$p; return $r - 3; }

But that now means I need to find a more suitable testcase for my experiments.

An in-place, parallised qsort maybe?

(*)Though wonder why you do a loop initialisation rather than my @n = (-1 ) x $m; my @A = ( 1 ) x $m; given that m will realistically max out at 5. And whilst I'm on unimportant, purely subjective matters, why for(;;) not while( 1 )?


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.

In reply to Re^2: Non-recursive Ackermann by BrowserUk
in thread [OT]: threading recursive subroutines. by BrowserUk

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":



  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • Outside of code tags, you may need to use entities for some characters:
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.
  • Log In?
    Username:
    Password:

    What's my password?
    Create A New User
    Chatterbox?
    and the web crawler heard nothing...

    How do I use this? | Other CB clients
    Other Users?
    Others examining the Monastery: (7)
    As of 2014-08-21 05:32 GMT
    Sections?
    Information?
    Find Nodes?
    Leftovers?
      Voting Booth?

      The best computer themed movie is:











      Results (127 votes), past polls