0votos

La sucesión de Golomb en Haskell

por josejuan hace 5 años

La constante de ésta en Haskell sigue siendo mucho mayor que la versión en C, pero tiene la ventaja de calcular la sucesión infinita. Usa la misma estrategia que la última versión en C y calcula hasta g(4.5e10) en 1 segundo. No requiere predimensionar la memoria (incluso con buffer cíclico haría falta) porque usa un Data.Seq que desecha por la izquierda y crece por la derecha.

Cálculo eficiente de los términos de la sucesión de Golomb: 1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 8, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 11, 11, 11, 11, 11, 12, 12, 12, 12, 12, 12, 13, 13, 13, 13, 13, 13, 14, 14, 14, 14, 14, 14, 15, 15, 15, 15, 15, 15, ...

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
import System.Environment 
import Data.Int 
import Data.List 
import Data.Sequence ((|>)) 
import qualified Data.Sequence as S 
 
 
-- Es la sucesión infinita de Golomb pero comprimida, de forma que se entrega 
-- la cota superior de `n` para el que es g(n)=x. 
 
sucGolomb :: [(Int64, Int64)] 
sucGolomb = g (S.fromList [3]) 3 3 2 2 
  where g is iz igzz z gzz = (iz, z) : g is'' iz' igzz' zz gzz' 
          where zz = z + 1 
                iz' = iz + gzz' 
                (is', gzz', igzz') = if zz > is `S.index` 0 
                                       then (S.drop 1 is, gzz + 1, S.index is 1) 
                                       else (is, gzz, igzz) 
                is'' = is' |> iz' 
 
 
 
 
-- Entonces, obtener para un nº concreto es 
golomb n = snd $ head $ dropWhile ((<n).fst) sucGolomb 
 
 
 
main = getArgs >>= print . golomb . read . head 
 
{- 
 
Por ejemplo, en un AMD Phenom(tm) II X6 1045T 2.7GHz 
 
$ time -f "%E, %M" ./gs4 45000000000 
4612113 
0:01.51, 279972 
 
 
-- la misma versión sin lista infinita (devolviendo directamente `z`) toma los 1.091 segs prometidos. 
 
 
-} 

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.