0votos

Potencia de Un Numero en Haskell

por josejuan hace 4 años

Éste desafío ya lo propuse hace tiempo http://www.solveet.com/exercises/Potencia-en-microcontrolador-/77 Aquí resuelvo usando el binomio de Newton. Únicamente se usan sumas y desplazamiento de bits.

Hacer la elevacion de un numero n.

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
import Test.QuickCheck 
import Data.Bits 
import Prelude hiding ((>>)) 
 
{- 
 
        Sean A, B >= 0 enteros, entonces 
 
        Si B es par, es B = 2C 
 
                A * B = A * 2C = (A * C) << 1 
 
        Si B es impar, es B = 2C + 1 
 
                A * B = A * (2C + 1) = 
                      = A * 2C + A = (A * C) << 1 + A 
 
-} 
mul :: (Bits a, Integral a) => a -> a -> a 
mul a b | b == 0         = 0 
        | b == 1         = a 
        | a < b          = mul b a 
        | b `testBit` 0  = d + a 
        | otherwise      = d 
                           where d = (mul a (b >> 1)) << 1 
 
{- 
 
        El triángulo de pascal se contruye trivialmente usando sumas 
        (ver implementación abajo). 
 
        Sean A, B >= 0 enteros, entonces 
 
        Si A es par, es A = 2C 
 
                A^B = (2C)^B = C^B << B 
 
        Si A es impar, es A = 2C + 1 
 
                A^B = (2C + 1)^B 
 
        por el binomio de Newton es 
 
                A^B = (2C)^B + k1 (2C)^(B-1) + k2 (2C)^(B-2) + ... 
 
        donde k1, k2, ... son los coeficientes del triángulo de pascal 
        en la fila B-ésima. 
 
-} 
pow :: (Bits a, Integral a) => a -> Int -> a 
pow a b | a == 0           = 0 
        | a == 1 || b == 0 = 1 
        | a `testBit` 0    = let e = a `clearBit` 0 
                             in  sum [mul p (pow e z) | (z, p) <- zip [0..b] (pascal!!b)] 
        | otherwise        = (pow (a >> 1) b) << b 
 
-- Triángulo de pascal (infinitas filas) 
pascal :: Integral a => [[a]] 
pascal = let p a = a: p (1: zipWith (+) a (tail a) ++ [1]) in p [1] 
 
-- Un test para verificar multiplicaciones 
testMul n = quickCheckWith (stdArgs { maxSuccess = n }) f 
            where f :: Integer -> Integer -> Bool 
                  f u v = let (a, b) = (abs u, abs v) in a * b == mul a b 
 
-- Un test para verificar potencias 
testPow n = quickCheckWith (stdArgs { maxSuccess = n }) f 
            where f :: Integer -> Int -> Bool 
                  f u v = let (a, b) = (abs u, abs v `mod` 10) in (a==0 && b==0) || a^b == pow a b 
 
-- Unos alias para mejorar la lectura 
(>>), (<<) :: Bits a => a -> Int -> a 
(>>) = shiftR 
(<<) = shiftL 
 
 
{- 
 
        *Main> :l pow.hs 
        [1 of 1] Compiling Main             ( pow.hs, interpreted ) 
        Ok, modules loaded: Main. 
        *Main> testMul 100000 
        +++ OK, passed 100000 tests. 
        *Main> testPow 10000 
        +++ OK, passed 10000 tests. 
        *Main> pow 23213 15 
        306174537884136640863282419695585866329780785601025284773752262757 
        *Main> 23213^15 
        306174537884136640863282419695585866329780785601025284773752262757 
        *Main> 
 
-} 

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.