' Optimized Ackermann Function with Memoization for MMBasic
' Minimizes recursion depth using iterative optimizations
' Author: Claude AI MMBasic Implementation
' Prompted and Debugged by Steve Johnson
' Date: September 12 2025

Option EXPLICIT
Option DEFAULT INTEGER

' Maximum values for memoization table
Const MAX_M = 5
Const MAX_N = 40

' Memoization table - using -1 to indicate uncomputed values
Dim memo(MAX_M, MAX_N)

' Statistics tracking
Dim cache_hits, cache_misses, max_recursion_depth, current_depth

' Initialize the program
Sub Initialize
 Local m, n

 ' Clear memoization table
 For m = 0 To MAX_M
   For n = 0 To MAX_N
     memo(m, n) = -1
   Next n
 Next m

 ' Reset statistics
 cache_hits = 0
 cache_misses = 0
 max_recursion_depth = 0
 current_depth = 0

 Print "Ackermann Function Calculator with Memoization"
 Print "=============================================="
 Print
End Sub

' Optimized Ackermann function with memoization
Function Ackermann(m, n)
 current_depth = current_depth + 1
 If current_depth > max_recursion_depth Then
   max_recursion_depth = current_depth
 EndIf

 ' Check if we can use memoization
 If m <= MAX_M And n <= MAX_N Then
   If memo(m, n) <> -1 Then
     cache_hits = cache_hits + 1
     current_depth = current_depth - 1
     Ackermann = memo(m, n)
     Exit Function
   EndIf
 EndIf

 cache_misses = cache_misses + 1

 ' Base cases and optimizations to reduce recursion depth
 If m = 0 Then
   ' A(0, n) = n + 1
   Ackermann = n + 1
 ElseIf n = 0 Then
   ' A(m, 0) = A(m-1, 1)
   Ackermann = Ackermann(m - 1, 1)
 ElseIf m = 1 Then
   ' A(1, n) = n + 2 (optimization to avoid recursion)
   Ackermann = n + 2
 ElseIf m = 2 Then
   ' A(2, n) = 2*n + 3 (optimization to avoid recursion)
   Ackermann = 2 * n + 3
 ElseIf m = 3 Then
   ' A(3, n) = 2^(n+3) - 3 (optimization to avoid recursion)
   Ackermann = Power2(n + 3) - 3
 Else
   ' General case: A(m, n) = A(m-1, A(m, n-1))
   Ackermann = Ackermann(m - 1, Ackermann(m, n - 1))
 EndIf

 ' Store in memo table if within bounds
 If m <= MAX_M And n <= MAX_N Then
   memo(m, n) = Ackermann
 EndIf

 current_depth = current_depth - 1
End Function

' Efficient power of 2 calculation
Function Power2(exp)
 If exp <= 0 Then
   Power2 = 1
 ElseIf exp <= 63 Then
   ' Use bit shifting for efficiency (2^exp = 1 << exp)
   Power2 = 1
   Power2 = Power2 << exp
 Else
   ' For very large exponents, return error indicator
   Power2 = -1
   Print "Error: Exponent too large for 2^" + Str$(exp)
 EndIf
End Function

' Display the memoization table
Sub ShowMemoTable
 Local m, n
 Print
 Print "Memoization Table Contents:"
 Print "=========================="
 Print "   n=";
 For n = 0 To Min(MAX_N, 10)
   Print n,
 Next n
 Print

 For m = 0 To MAX_M
   Print "m=" + Str$(m) + ":";
   For n = 0 To Min(MAX_N, 10)
     If memo(m, n) = -1 Then
       Print "   -";
     Else
       Print memo(m, n),
     EndIf
   Next n
   Print
 Next m
End Sub

' Display statistics
Sub ShowStats
 Print
 Print "Performance Statistics:"
 Print "======================"
 Print "Cache hits: " + Str$(cache_hits)
 Print "Cache misses: " + Str$(cache_misses)
 If cache_hits + cache_misses > 0 Then
   Print "Hit ratio: " + Format$((cache_hits * 100) / (cache_hits + cache_misses), "%.1f") + "%"
 EndIf
 Print "Maximum recursion depth: " + Str$(max_recursion_depth)
End Sub

' Test the Ackermann function with various inputs
Sub RunTests
 Local m, n, result, start_time, end_time, test_max_depth

 Print "Testing Ackermann Function:"
 Print "=========================="

 ' Test cases that demonstrate the optimization
 Dim test_cases(10, 2)
 test_cases( 0, 0) = 0: test_cases( 0, 1) = 0
 test_cases( 1, 0) = 0: test_cases( 1, 1) = 1
 test_cases( 2, 0) = 1: test_cases( 2, 1) = 0
 test_cases( 3, 0) = 1: test_cases( 3, 1) = 1
 test_cases( 4, 0) = 1: test_cases( 4, 1) = 2
 test_cases( 5, 0) = 2: test_cases( 5, 1) = 0
 test_cases( 6, 0) = 2: test_cases( 6, 1) = 1
 test_cases( 7, 0) = 2: test_cases( 7, 1) = 2
 test_cases( 8, 0) = 3: test_cases( 8, 1) = 0
 test_cases( 9, 0) = 3: test_cases( 9, 1) = 1
 test_cases(10, 0) = 3: test_cases(10, 1) = 2

 Local i
 For i = 0 To 10
   m = test_cases(i, 0)
   n = test_cases(i, 1)

   ' Reset depth counter for each test
   current_depth = 0
   test_max_depth = max_recursion_depth

   start_time = Timer
   result = Ackermann(m, n)
   end_time = Timer

   Print "A(" + Str$(m) + "," + Str$(n) + ") = " + Str$(result) ;
   Print " (depth: " + Str$(max_recursion_depth - test_max_depth) ;
   Print ", time: " + Format$((end_time - start_time) * 1000, "%.1f") + "ms)"
 Next i
End Sub

' Interactive mode for user input
Sub InteractiveMode
 Local m, n, result, continue_flag, old_hits, old_misses, start_time, end_time, old_max_depth, current_depth

 continue_flag = 1
 Do While continue_flag
   Print
   Print "Enter Ackermann function parameters (or -1 to quit):"
   Input "m = ", m
   If m = -1 Then Exit

   Input "n = ", n
   If n = -1 Then Exit

   If m < 0 Or n < 0 Then
     Print "Error: m and n must be non-negative integers"
     Continue DO
   EndIf

   If m > 4 Or (m = 4 And n > 2) Then
     Print "Warning: This computation may take a very long time or exceed memory limits"
     Local proceed$
     Input "Continue? (y/n): ", proceed$
     If UCase$(proceed$) <> "Y" Then Continue DO
   EndIf

   ' Reset statistics for this computation
   old_hits = cache_hits
   old_misses = cache_misses
   current_depth = 0
   old_max_depth = max_recursion_depth

   start_time = Timer
   result = Ackermann(m, n)
   end_time = Timer

   Print
   Print "A(" + Str$(m) + "," + Str$(n) + ") = " + Str$(result)
   Print "             Computation time: " + Format$((end_time - start_time) * 1000, "%.1f") + "ms"
   Print "  Cache hits this computation: " + Str$(cache_hits - old_hits)
   Print "Cache misses this computation: " + Str$(cache_misses - old_misses)
   Print "      Maximum recursion depth: " + Str$(max_recursion_depth - old_max_depth)
 Loop  
End Sub

' Main program
Initialize

' Run automated tests
RunTests

' Show performance statistics
ShowStats

' Show memoization table
ShowMemoTable

' Enter interactive mode
InteractiveMode

Print
Print "Program completed. Final statistics:"
ShowStats

End