I was able to construct a nonrecursive 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 lockstepping the threadingeither through complex locking or queuingand with the minimal effort required for each step of each iteration versus the cost of locking and context switching, again make that a nonstarter.
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 algorithmthat is not tail recursiveto 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 specialcased. 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 inplace, 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.
