### Comment on

 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

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!
• Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
• Read Where should I post X? if you're not absolutely sure you're posting in the right place.
• 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
• You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
 For: Use: & & < < > > [ [ ] ]
• Link using PerlMonks shortcuts! What shortcuts can I use for linking?

Create A New User
Chatterbox?
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others chilling in the Monastery: (4)
As of 2018-02-24 07:06 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
When it is dark outside I am happiest to see ...

Results (310 votes). Check out past polls.

Notices?