Well Sup Forums

well Sup Forums

Can you solve it?

Other urls found in this thread:

mathworld.wolfram.com/AckermannFunction.html
en.wikipedia.org/wiki/Ackermann_function
twitter.com/AnonBabble

maximum call stack exceeded, shit. how do you solve it?

I'd say it's あ where あ = A(4, 2)

solved :^)

⊥

n keeps on adding one. The function does not terminate

no but she is my waifu.

Le this

>He did all this instead of just hiding the thread

Can't know that it won't terminate.

>superexponential time function
>you should be able to solve this

two bottom functions decrease m by one. When m=0 the only value that is modified is n. M's value cannot change, so n will be added by one infinitely.

it is 2^(65536) − 3

well Sup Forums

Can you solve it?

You are on Sup Forums. The question we need answered is: What is "sex"?

>How do two girls have sex?
Without me.

tripfaggot

...

The function can terminate because the top returns the value of N+1 without calling itself again, in other words, when m=0, you're done.

I hope you didn't just flunk your recursion test, user.

Does it not just return 1?

2^(65536) − 3

1?

Ah shit, I see now, I inverted one of the recursive calls like a fucking moron.

One girl puts her penis in the other!

2^65536-3

This is the number

great movie user

y tho

mathworld.wolfram.com/AckermannFunction.html

`/* stupid Sup Forums bullshit
* { n + 1 if m = 0
* A(m,n) = { A(m - 1, 1) if m > 0 and n = 0
* { A(m - 1, A(m, n - 1)) if m > 0 and n > 0
*/

#include

int func_a(int m, int n) {

if(m == 0) {

return (n + 1);
} else if(m > 0 && n == 0) {

return func_a(m - 1,1);
} else if(m > 0 && n > 0) {

return func_a((m - 1), func_a(m, n - 1));
}

return result;
}

int main() {

int m = 4;
int n = 2;

printf("%d\n", func_a(m, n));
return 0;
}`
did I do it right...?

Fuck me, I can't into formatting

Looks right
Try running it :^)

did you run the program? You get a stack overflow. The only way to do it is by hand, recognize the geometric series and find the value.

just because you stuck your homework behind an anime girl doesn't mean you don't have to do it anymore

It just gives me 2. Not anything near 2^(65536) - 3

see

well, firstly your func_a returns an integer, which has a range of -2^31 to 2^31, which of course couldn't fit 2^65536 - 3. try using double precision floating points instead.

>return result;
Variable not defined, just throw an error instead.

It doesn't give me 2 when I run your code.

AH, there's my problem. Thank you!

Completely spaced on that.

that and make wasn't cooperating.

Thanks guys.

additionally, I don't know how your code even compiled. It should cause a stack overflow, since it literally goes up to 2^65536-3 levels deep at least.

The magic of C maybe? C doesn't do any compile time checks, so it should fail at runtime. But yes, it gave me a SIGSEGV.

Calle Calle

What anime is she from? Pic related...

I did it in python and ruby, i also had errors.
SystemStackError in ruby after 8724 levels.
RecursionError in python.

do it iteratively if you can't math wtf

kek

It's the ackermann function, don't even bother it would take more time than the time the universe has existed to solve it for 4 and 2, it does have a solution but no one knows

Ackermann, is that you?

Why can n = A(m, n)?

should have used a language with tail call optimization

The answer is exactly (((2^65533)-1)*8)+5. If you want to know how I did it, leave a reply.

Stop pretending to be clever
en.wikipedia.org/wiki/Ackermann_function

Alright, so I've stumbled into this shit. Would someone explain to my retarded ass just what the fuck I'm looking at? Are we communicating with aliens, or writing down the physical formulae for casting fire-ball? (Keeping in mind math-models was the most advanced math class I was qualified for.)

I didn't know it was a thing. I just figured it out after running a program and making a couple of graphs :(

Does python really not allow recursion?

It is a recursive function. If the condition on the right is true then that is the version of the function that is used:

For A(4, 2), since 4 > 0 and 2 > 0, then = A(4 - 1, A(4, 2 - 1)) or A(3, A(4, 1))
For A(3, 0), since 3 > 0 and 0 = 0, then = A(2, 1)
For A(0, 1), since 0 = 0, then = 1 + 1 or 2

Let's try this again.

Using no numbers, and only a very basic outline of what the hell all of this is actually supposed to mean/accomplish, what in the actual fuck is all of this?

You should probably kys
n+1 is the termination return value

Okay, it's a special function that Wilhelm Ackermann found that is computable but is not a specific type of special function that contains itself called a primitive recursive function, showing that not all computable functions are primitive recursive functions.

Ok, so the 'function' is the entirety of the problem itself, 'computable' means 'solve-able', and 'recursive' I don't know, but get a vague feeling it means curving (Fuck if I know on a technical level how math 'curves', but I'm pretty sure it has something to do with geometry.)

The 'primitive' bit I've got nothing for.

So if I understand, this is basically a math problem a guy found that lists out numbers until it eventually goes back to the first number listed?

A recursive function is a function that has itself in its definition like f(x) = f(x-1) + 1 or something like that. A primitive recursive function is a specific type of recursive function that is made up of special axiom (an axiom is like a rule) functions.

This function doesn't list out numbers, each two numbers (m, n) give out one number. You might have to do some extra math like when you borrow in subtraction to get the result, but in the end you have one number.

Learned about it in three different places:
Algorithms course in college
SICP
and Day9's video with the worst yo-mama joke
Did it RIP your computer?

Goodness, for some reason understanding that (to what extent I have) made it unreasonably hilarious... I don't think I've ever laughed at a math problem before. Thanks for the explanation.

Why are there 2 commas?

Holy shit all this debate.

Can someone who knows Coq or something just come out and prove it?

OP here, if anyone didn't figure this out already, this function grows at a monstruous rate.

pic related

If you still have troubles with recursion, just check the fibonacci and factorial recursive algorithms.

I get the feeling this is a job for GMP. Or as I like to call it, the GNU plus MP library.

I recognized the function, but I didn't know the name so I made a program, but I used text replacement so I could analyze computation. This way I could see if it even was possible to compute and try to look for patterns. I could see some A(m, n) finish to some number p so I would add a case for A(m, n) to be p, and on the next run I would see another A(r, s) finish to q and would add another case, etc. After a couple of cases I could see The result for A(1, x) pretty easily and set A(1, x) = x + 2. Which led me to easily seeing the values for A(2, x) = x*2 + 3. Finally A(3, x) = 2^(x+3) - 3.

So the final program output was:
A(4, 2)
A(3, A(4, 1))
A(3, A(3, A(4, 0)))
A(3, A(3, A(3, 1)))
A(3, A(3, 13))
A(3, 65533)
Where it would fail because the number is too large, so I just plugged it in to the A(3, x) form above yielding 2^65536 + 3

The original program didn't crash because It was not recursive but it required more memory than probably ever has been in existence to keep the state of the answer in memory. That's why I used the Algebraz to make the final calculation. :)

The irony is that the fib sequence is taught in every single recursion tutorial, but fib(large) is noticably faster to calculate using an iterative solution.

Its not really ironic. The recursion tutorial is teaching recursion, not the most efficient way to calculate fib(n), so when iteration it's faster... well no shit; that was not the goal. However, in a tail-optimized language it should be equivalent.

I literally have no idea what you just said, but if I ever need math for anything more than casual shit, I'll be sure to try and remember that.

Nice one user

Solution for A(4,2):

A(4, 2)=A( 3, A(4,1) )

A(4, 1) = A( 3, A(4,0) )
A(4, 0) = A(3, 1)
A(3, 1) = A( 2, A(3, 0) )
A(3, 0) = A(2, 1)
A(2, 1) = A( 1, A(2, 0) )
A(2, 0) = A(1, 0) = A(0, 1) = 2

thus A(2, 1) = A(1, 2) = A( 0, A(1, 1) )
A(1, 1) = A( 0, A(1, 0) ) = A(0, 2) = 3

thus A(2, 1) = A(0, 3) = 4

hence A(3, 0) = 4
A(3, 1) = A(2, 4)
A(2, 4) = A( 1, A(2, 3) )
A(2, 3) = A( 1, A(2, 2) )
A(2, 2) = A( 1, A(2, 1) ) = A(1, 4) = A( 0, A(1, 3) )
A(1, 3) = A( 0, A(1, 2) ) = A(0, 4) = 5

thus A(2, 2) = A(0, 5) = 6
A(2, 3) = A(1, 6) = A( 0, A(1, 5) )
A(1, 5) = A( 0, A(1, 4) )
A(1, 4) = A( 0 , A(1, 3) ) = A(0, 5) = 6

thus A(1, 5) = A(0, 6) = 7
A(2, 3) = A(0, 7) = 8
A(2, 4) = A(1, 8) = A( 0, A(1, 7) )
A(1, 7) = A( 0 , A(1, 6) )
A(1, 6) = A( 0 , A(1, 5) ) = A(0, 7) = 8

thus A(1, 7) = A(0, 8) = 9

by induction A(1, y) = y + 2
hence A(2, 4) = 10
and again by induction A(2, y) = 2y + 2

furthermore by induction and more generally A(x, y) = xy + 2

thus A(4, 2) = 8 + 2 = 10

Fuck you OP, give me a prize for wasting my time while at work (i've done postgrad maths).

yuru yuri

You couldn't be more wrong though.

how?

That is not quite true. It's really the result of this
result=13
for(i = 2; i

>thus A(4, 2) = 8 + 2 = 10
>(I've done postgrad maths)

I believe where you went wrong when you tried using induction to get A(x, y). Your A(1, y) is correct. A(2, y) isn't (but is close), and A(x, y) is certainly not = xy + 2. See (SPOILER) for the correct answer.

Are you fucking retarded?

Yes

You are wrong. He is right. And your program will end when the last star dies.

good point
i should have stopped at 8 + 2

lmao, I'll allow you to interject.

I went wrong by saying A(2, 0) = A(1, 0). meant A(1, 1) fuck

>You are wrong. He is right.
No, he is absolutely wrong.

Consider the problem A(3, n)

A(3, 1) == 13
A(3, 2) == 29 which is A(3, 1) + 2^4
A(3, 3) == 61 which is A(3, 2) + 2^5
A(3, 4) == 125 which is A(3, 3) + 2^6
...
A(3, 13) == 65533

>your program will end when the last star dies
Okay retard, whatever you say. It finished running (pic related is the result)

3

>literally a hackerman function

>two non-negative integers

why not just fucking say 'two positive integers'? Why needlessly complicate the language with a double negative?

A couple of things.
First: I though it wouldn't end because of the scale, however, you are not counting by one, so it definitely is possibly to calculate. (As evidenced. In this regards I was a total tard).
Second: I misunderstood your answer because you said 2^65536 - 3 is wrong since...
Thirdly: You calculated 2^65536 - 3. Congrats.

>using anime to trick Sup Forums into doing your homework
nice, anime board confirmed

Because m or n may be zero.

non-negative includes zero (0)

fucking zeroes what a bullshit number making shit complicated

To elaborate more on my answer, it is very easy to demonstrate that the following function calls are equivalent:

A(4, 2) == A(3, A(4, 1)) == A(3, 65533)

The pattern for A(3, n) is quite a simple one. I explained it in my previous post. The following code produces the result of A(3, n):
result=13
for(i = 2; i

>Thirdly: You calculated 2^65536 - 3. Congrats.
Oh I see. Yeah, now I feel like the tard for not realizing that is the same thing. That calculation takes only a second and here I am making some dumbass loop that takes several minutes to calculate the same thing.

(2 -> 5 -> 2) - 3

This is the absolute state of Sup Forums:
If something is harder than fizzbuzz, it's unsolvable..


First we chose what language to use.
Obviously you want something like Ruby where you don't have buffer overflows.

You'll still get problems with your stack, so let's simplify first:
A(0,x) = x+1
A(1,x) = x+2
A(2,x) = 2*x + 3
A(3,x) = { 5 if x is 0; else 2*A(3,x-1) + 3 }


You can also calculate:
A(4,2)
= A(3, A(4,1))
= A(3, A(3, A(4,0)))
= A(3, A(3, A(3,1)))


To avoid problems with your stack, you need to make you own stack. In Ruby you can simply use an Array for that, it already provides stack methods for us. We now have approximately a stack call depth of about 500 million, which is more than enough.


my_stack = []


Now let's initialize it, notice the '+'-sign, you'll need it in a minute:
my_stack.push 'a(4,2)'
my_stack.push ' + 0'


The rest should be obvious:
1. If the stack has only one element, return the result
2. Get the last two stack elements
3. If they are both numbers, evaluate them (!) and put the result on the stack
4. If it's a String, evaluate it and calculate the (simplified) Ackermann function:
-Either you get a number ==> put it on the stack!
-Or you get "2*A(3, (n-1)) + 3"

You can also put this on the stack:
my_stack.push ' + 3'
my_stack.push ' * 2'
my_stack.push 'A(3, {n}-1)' [replace n with the number]


Here you go.
The programm is left as exercise for the reader.