relacion online matematica funcion ejemplos ackerman haskell ghc ackermann

haskell - online - funcion de ackerman en python



MemorizaciĆ³n de la funciĆ³n de Ackermann. (3)

En caso de que tenga suficiente memoria, intente aumentar el tamaño de la pila :

$ ghc -O2 -rtsopts source.hs $ ./source +RTS -K128M

Me gustaría calcular el valor A(3, 20) de la función Ackermann (ver Wikipedia) que debería ser 2^23 - 3 = 8388605 usando Data.MemoCombinators . Mi código es:

{-# LANGUAGE BangPatterns #-} import Data.MemoCombinators as Memo ack = Memo.memo2 Memo.integral Memo.integral ack'' where ack'' 0 !n = n+1 ack'' !m 0 = ack (m-1) 1 ack'' !m !n = ack (m-1) $! (ack m (n-1)) main = print $ ack 3 20

Pero termina en un error de desbordamiento de pila ;-) ¿Se puede ajustar o la cadena de cómputo es realmente tan larga e incluso la memoria no puede ayudar?


La función es recursiva, y la implementaste correctamente. Creo que simplemente golpeas la parte superior de la pila. Eso no es sorprendente, porque el recuento de recursiones aumenta exponencialmente cuando m=3 . Es inevitable que te quedes sin pila. Aumentar la memoria total no ayudará, a menos que haga una implementación diferente que use algún otro método que no sea recursivo.

Entonces, para responder a tu pregunta, necesitarás alguna otra forma de memoria para continuar. O al menos necesitarás utilizar RAM de manera muy diferente.


Uno de los puntos de la función de Ackermann es que el cálculo recursivo conduce a una recursión muy profunda.

La profundidad de la recursión es aproximadamente igual al resultado (dependiendo de cómo cuentes, es de unos pocos niveles más o menos) sin meoisation. Desafortunadamente, la memoria no le compra mucho si llena la tabla de notas de acuerdo con el call-tree.

Sigamos el cálculo de ack 3 2 :

ack 3 2 ack 2 $ ack 3 1 ack 2 $ ack 2 $ ack 3 0 ack 2 $ ack 2 $ ack 2 1 ack 2 $ ack 2 $ ack 1 $ ack 2 0 ack 2 $ ack 2 $ ack 1 $ ack 1 1 ack 2 $ ack 2 $ ack 1 $ ack 0 $ ack 1 0 ack 2 $ ack 2 $ ack 1 $ ack 0 $ ack 0 1 -- here''s the first value we can compute and put in the map ack 2 $ ack 2 $ ack 1 $ ack 0 2 -- next three, (0,2) -> 3, (1,1)->3 and (2,0)->3 ack 2 $ ack 2 $ ack 1 3 -- need to unfold that ack 2 $ ack 2 $ ack 0 $ ack 1 2 ack 2 $ ack 2 $ ack 0 $ ack 0 $ ack 1 1 -- we know that, it''s 3 ack 2 $ ack 2 $ ack 0 $ ack 0 3 -- okay, easy (0,3)->4, (1,2)->4 ack 2 $ ack 2 $ ack 0 4 -- (0,4)->5, (1,3)->5, (2,1)->5 ack 2 $ ack 2 5 -- unfold ack 2 $ ack 1 $ ack 2 4 ack 2 $ ack 1 $ ack 1 $ ack 2 3 ack 2 $ ack 1 $ ack 1 $ ack 1 $ ack 2 2 ack 2 $ ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 2 1 ack 2 $ ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 2 0 -- we know that one, 3 ack 2 $ ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 1 3 -- that one too, it''s 5 ack 2 $ ack 1 $ ack 1 $ ack 1 $ ack 1 5 -- but not that ack 2 $ ack 1 $ ack 1 $ ack 1 $ ack 0 $ ack 1 4 ack 2 $ ack 1 $ ack 1 $ ack 1 $ ack 0 $ ack 0 $ ack 1 3 -- look up ack 2 $ ack 1 $ ack 1 $ ack 1 $ ack 0 $ ack 0 5 -- easy (0,5)->6 ack 2 $ ack 1 $ ack 1 $ ack 1 $ ack 0 6 -- now (1,5)->7 is known too, and (2,2)->7 ack 2 $ ack 1 $ ack 1 $ ack 1 7 ack 2 $ ack 1 $ ack 1 $ ack 0 $ ack 1 6 ack 2 $ ack 1 $ ack 1 $ ack 0 $ ack 0 $ ack 1 5 ack 2 $ ack 1 $ ack 1 $ ack 0 $ ack 0 7 -- here (1,6)->8 becomes known ack 2 $ ack 1 $ ack 1 $ ack 0 8 -- and here (1,7)->9, (2,3)->9 ack 2 $ ack 1 $ ack 1 9 ack 2 $ ack 1 $ ack 0 $ ack 1 8 ack 2 $ ack 1 $ ack 0 $ ack 0 $ ack 1 7 -- known ack 2 $ ack 1 $ ack 0 $ ack 0 9 -- here we can add (1,8)->10 ack 2 $ ack 1 $ ack 0 10 -- and (1,9)->11, (2,4)->11 ack 2 $ ack 1 11 ack 2 $ ack 0 $ ack 1 10 ack 2 $ ack 0 $ ack 0 $ ack 1 9 -- known ack 2 $ ack 0 $ ack 0 11 -- (1,10)->12 ack 2 $ ack 0 12 -- (1,11)->13, (2,5)->13 ack 2 13 ack 1 $ ack 2 12 ack 1 $ ack 1 $ ack 2 11 ack 1 $ ack 1 $ ack 1 $ ack 2 10 ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 2 9 ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 2 8 ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 2 7 ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 2 6 ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 2 5 -- uff ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 1 13 ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 0 $ ack 1 12 ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 0 $ ack 0 $ ack 1 11 -- uff ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 0 $ ack 0 13 -- (1,12)->14 ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 0 14 -- (1,13)->15, (2,6)->15 ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 1 15 ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 0 $ ack 1 14 ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 0 $ ack 0 $ ack 1 13 ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 0 $ ack 0 15 -- (1,14)->16 ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 0 16 -- (1,15)->17, (2,7)->17 ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 1 17 ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 0 $ ack 1 16 ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 0 $ ack 0 $ ack 1 15 ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 0 $ ack 0 17 -- (1,16)->18 ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 0 18 -- (1,17)->19, (2,8)->19 ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 1 19 ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 0 $ ack 1 18 ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 0 $ ack 0 $ ack 1 17 ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 0 $ ack 0 19 -- (1,18)->20 ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 0 20 -- (1,19)->21, (2,9)->21 ack 1 $ ack 1 $ ack 1 $ ack 1 21 ack 1 $ ack 1 $ ack 1 $ ack 0 $ ack 1 20 ack 1 $ ack 1 $ ack 1 $ ack 0 $ ack 0 $ ack 1 19 -- known ack 1 $ ack 1 $ ack 1 $ ack 0 $ ack 0 21 -- (1,20)->22 ack 1 $ ack 1 $ ack 1 $ ack 0 22 -- (1,21)->23, (2,10)->23 ack 1 $ ack 1 $ ack 1 23 ack 1 $ ack 1 $ ack 0 $ ack 1 22 ack 1 $ ack 1 $ ack 0 $ ack 0 $ ack 1 21 -- known ack 1 $ ack 1 $ ack 0 $ ack 0 23 -- (1,22)->24 ack 1 $ ack 1 $ ack 0 24 -- (1,23)->25, (2,11)->25 ack 1 $ ack 1 25 ack 1 $ ack 0 $ ack 1 24 ack 1 $ ack 0 $ ack 0 $ ack 1 23 -- known ack 1 $ ack 0 $ ack 0 25 -- (1,24)->26 ack 1 $ ack 0 26 -- (1,25)->27, (2,12)-> 27 ack 1 27 ack 0 $ ack 1 26 ack 0 $ ack 0 $ ack 1 25 ack 0 $ ack 0 27 ack 0 28 29

Entonces, cuando necesita calcular un ack 1 n nuevo (aún no conocido), debe calcular dos ack 0 n nuevos, y cuando necesita un ack 2 n , necesita dos ack 1 n nuevos y, por lo tanto, 4 nuevo ack 0 n , eso no es demasiado dramático.

Pero cuando necesita un nuevo ack 3 n , necesita ack 3 (n-1) - ack 3 (n-2) nuevo ack 2 k . Dicho todo, después de calcular ack 3 k , debe calcular 2^(k+2) nuevos valores de ack 2 n , y por la estructura de llamadas, estas son llamadas anidadas, por lo que obtiene una pila de 2^(k+2) Thunks anidados.

Para evitar ese anidamiento, necesita reestructurar el cálculo, por ejemplo, forzando el nuevo ack (m-1) k necesario ack (m-1) k en orden creciente de k ,

ack'' m 1 = ack (m-1) $! ack (m-1) 1 ack'' m n = foldl1'' max [ack (m-1) k | k <- [ack m (n-2) .. ack m (n-1)]]

lo que permite que la computación se ejecute (lentamente) con una pila pequeña (pero aún necesita una gran cantidad de pilas, parece que se requiere una estrategia de memoria a medida).

Almacenar solo ack mn para m >= 2 , y evaluar ack 1 n como si estuviera memorizado reduce la memoria necesaria lo suficiente como para que el cómputo ack 3 20 termine con menos de 1 GB de pila (usar Int lugar de Integer hace que se ejecute aproximadamente el doble) rápido):

{-# LANGUAGE BangPatterns #-} module Main (main) where import qualified Data.Map as M import Control.Monad.State.Strict import Control.Monad type Table = M.Map (Integer,Integer) Integer ack :: Integer -> Integer -> State Table Integer ack 0 n = return (n+1) ack 1 n = return (n+2) ack m 0 = ack (m-1) 1 ack m 1 = do !n <- ack (m-1) 1 ack (m-1) n ack m n = do mb <- gets (M.lookup (m,n)) case mb of Just v -> return v Nothing -> do !s <- ack m (n-2) !t <- ack m (n-1) let foo a b = do c <- ack (m-1) b let d = max a c return $! d !v <- foldM foo 0 [s .. t] mp <- get put $! M.insert (m,n) v mp return v main :: IO () main = print $ evalState (ack 3 20) M.empty