Raíz entera

PorJosé A. Alonso 8-abril-20161-mayo-2016

Definir la función

   raizEnt :: Integer -> Integer -> Integer

1	raizEnt :: Integer -> Integer -> Integer

tal que (raizEnt x n) es la raíz entera n-ésima de x; es decir, el mayor número entero y tal que y^n <= x. Por ejemplo,

   raizEnt  8 3      ==  2
   raizEnt  9 3      ==  2
   raizEnt 26 3      ==  2
   raizEnt 27 3      ==  3
   raizEnt (10^50) 2 ==  10000000000000000000000000

raizEnt 8 3 == 2

raizEnt 9 3 == 2

raizEnt 26 3 == 2

raizEnt 27 3 == 3

raizEnt (10^50) 2 == 10000000000000000000000000

Comprobar con QuickCheck que para todo número natural n,

    raizEnt (10^(2*n)) 2 == 10^n

1	raizEnt (10^(2*n)) 2 == 10^n

Soluciones

import Test.QuickCheck

-- 1ª definición
raizEnt1 :: Integer -> Integer -> Integer
raizEnt1 x n =
    last (takeWhile (\y -> y^n <= x) [0..])

-- 2ª definición         
raizEnt2 :: Integer -> Integer -> Integer
raizEnt2 x n =
    floor ((fromIntegral x)**(1 / fromIntegral n))

-- Nota. La definición anterior falla para números grandes. Por ejemplo,
--    λ> raizEnt2 (10^50) 2 == 10^25
--    False
          
-- 3ª definición          
raizEnt3 :: Integer -> Integer -> Integer
raizEnt3 x n = aux (1,x)
    where aux (a,b) | d == x    = c
                    | c == a    = c
                    | d < x     = aux (c,b)
                    | otherwise = aux (a,c) 
              where c = (a+b) `div` 2
                    d = c^n

-- Comparación de eficiencia
--    λ> raizEnt1 (10^14) 2
--    10000000
--    (6.15 secs, 6,539,367,976 bytes)
--    λ> raizEnt2 (10^14) 2
--    10000000
--    (0.00 secs, 0 bytes)
--    λ> raizEnt3 (10^14) 2
--    10000000
--    (0.00 secs, 25,871,944 bytes)
--    
--    λ> raizEnt2 (10^50) 2
--    9999999999999998758486016
--    (0.00 secs, 0 bytes)
--    λ> raizEnt3 (10^50) 2
--    10000000000000000000000000
--    (0.00 secs, 0 bytes)
                        
-- La propiedad es                        
prop_raizEnt :: Integer -> Bool
prop_raizEnt n =
    raizEnt3 (10^(2*m)) 2 == 10^m
    where m = abs n

-- La comprobación es              
--    λ> quickCheck prop_raizEnt
--    +++ OK, passed 100 tests.

import Test.QuickCheck

-- 1ª definición

raizEnt1 :: Integer -> Integer -> Integer

raizEnt1 x n =

last (takeWhile (\y -> y^n <= x) [0..])

-- 2ª definición

raizEnt2 :: Integer -> Integer -> Integer

raizEnt2 x n =

floor ((fromIntegral x)**(1 / fromIntegral n))

-- Nota. La definición anterior falla para números grandes. Por ejemplo,

-- λ> raizEnt2 (10^50) 2 == 10^25

-- False

-- 3ª definición

raizEnt3 :: Integer -> Integer -> Integer

raizEnt3 x n = aux (1,x)

where aux (a,b) | d == x = c

| c == a = c

| d < x = aux (c,b)

| otherwise = aux (a,c)

where c = (a+b) `div` 2

d = c^n

-- Comparación de eficiencia

-- λ> raizEnt1 (10^14) 2

-- 10000000

-- (6.15 secs, 6,539,367,976 bytes)

-- λ> raizEnt2 (10^14) 2

-- 10000000

-- (0.00 secs, 0 bytes)

-- λ> raizEnt3 (10^14) 2

-- 10000000

-- (0.00 secs, 25,871,944 bytes)

-- λ> raizEnt2 (10^50) 2

-- 9999999999999998758486016

-- (0.00 secs, 0 bytes)

-- λ> raizEnt3 (10^50) 2

-- 10000000000000000000000000

-- (0.00 secs, 0 bytes)

-- La propiedad es

prop_raizEnt :: Integer -> Bool

prop_raizEnt n =

raizEnt3 (10^(2*m)) 2 == 10^m

where m = abs n

-- La comprobación es

-- λ> quickCheck prop_raizEnt

-- +++ OK, passed 100 tests.

Soluciones en Maxima

raizEnt (x,n) := inrt (x,n)$

1	raizEnt (x,n) := inrt (x,n)$

7 Comentarios

fracruzam dice:

8-abril-2016 a las 08:31

Predefinida en Maxima:

Haskell

raizEnt (x,n) := inrt (x,n)$

1

raizEnt (x,n) := inrt (x,n)$

Responder
juamorrom1 dice:

8-abril-2016 a las 10:25

Haskell

-- Definición no muy eficiente. raizEnt :: Integer -> Integer -> Integer raizEnt x n = last $ filter (\y -> y^n <= x) [1..div x 2]

1
2
3

-- Definición no muy eficiente.
raizEnt :: Integer -> Integer -> Integer
raizEnt x n = last $ filter (\y -> y^n <= x) [1..div x 2]

Responder

raizEnt :: Integer -> Integer -> Integer
raizEnt x n = floor $ (fromIntegral x)**(1/fromIntegral n)

-- El último caso no lo calcula pero creo que es porque Haskell está redondeando.
-- Pd: Muchas gracias a Fran por ayudarme con los tipos

raizEnt :: Integer -> Integer -> Integer

raizEnt x n = floor $ (fromIntegral x)**(1/fromIntegral n)

-- El último caso no lo calcula pero creo que es porque Haskell está redondeando.

-- Pd: Muchas gracias a Fran por ayudarme con los tipos

Responder

-- Es poco eficiente

raizEnt':: Integer -> Integer -> [Integer]
raizEnt' x n = [ y | y <- [0..x], y^n <= x ]

raizEnt :: Integer -> Integer -> Integer
raizEnt x n = last (raizEnt' x n)

-- Es poco eficiente

raizEnt':: Integer -> Integer -> [Integer]

raizEnt' x n = [ y | y <- [0..x], y^n <= x ]

raizEnt :: Integer -> Integer -> Integer

raizEnt x n = last (raizEnt' x n)

Responder

Paola Cabrera Perza dice:

10-abril-2016 a las 09:44

Haskell

raizEnt :: Integer -> Integer -> Integer raizEnt x n = truncate ((fromIntegral x)**(1/fromIntegral n))

1
2

raizEnt :: Integer -> Integer -> Integer
raizEnt x n = truncate ((fromIntegral x)**(1/fromIntegral n))

Responder

raizEnt :: Integer -> Integer -> Integer
raizEnt x n = raizEntAux x n 1

raizEntAux x n y | y^n<=x = raizEntAux x n (y+1)
                 | otherwise = y-1 



raizEnt' :: Integer -> Integer -> Integer
raizEnt' x n = raizEntAux x n 
   (floor $ aplica sqrt (busca n potencias2) $ fromIntegral x)

potencias2 = (aux 2)
   where aux n = n:(aux (2*n))

busca n (x:xs) | n<=x = 1
               | otherwise = 1+(busca n xs)

-- La primera definicion es menos eficiente pero mas sencilla, 
-- utiliza como valor inicial 1. La segunda lo que intenta es 
-- buscar un valor inicial mayor a traves del uso sucesivo de 
-- la raiz cuadrada (ya definida en haskell). Aun asi sigue sin
-- hacer el ultimo caso, pero si hace (raizEnt' 10^45 2). Por
-- supuesto es mas eficiente si n es potencia de 2, o numeros
-- grandes

raizEnt :: Integer -> Integer -> Integer

raizEnt x n = raizEntAux x n 1

raizEntAux x n y | y^n<=x = raizEntAux x n (y+1)

| otherwise = y-1

raizEnt' :: Integer -> Integer -> Integer

raizEnt' x n = raizEntAux x n

(floor $ aplica sqrt (busca n potencias2) $ fromIntegral x)

potencias2 = (aux 2)

where aux n = n:(aux (2*n))

busca n (x:xs) | n<=x = 1

| otherwise = 1+(busca n xs)

-- La primera definicion es menos eficiente pero mas sencilla,

-- utiliza como valor inicial 1. La segunda lo que intenta es

-- buscar un valor inicial mayor a traves del uso sucesivo de

-- la raiz cuadrada (ya definida en haskell). Aun asi sigue sin

-- hacer el ultimo caso, pero si hace (raizEnt' 10^45 2). Por

-- supuesto es mas eficiente si n es potencia de 2, o numeros

-- grandes

Responder

-- Mediante búsqueda dicotómica:

raizEnt :: Integer -> Integer -> Integer
raizEnt x n = aux 0 x
    where aux a b | c^n > x     =  aux a c
                  | (c+1)^n > x = c
                  | otherwise   = aux c b
              where c = f a b

f a b | even x   = x `div` 2
      | otherwise = 1 + x `div` 2
      where x = a + b

-- La definición
raizEnt1 :: Integer -> Integer -> Integer
raizEnt1 x n = floor $ (fromIntegral x)**(1/fromIntegral n)

-- no da el resultado correcto cuando x es una potencia n-sima.

-- Mediante búsqueda dicotómica:

raizEnt :: Integer -> Integer -> Integer

raizEnt x n = aux 0 x

where aux a b | c^n > x = aux a c

| (c+1)^n > x = c

| otherwise = aux c b

where c = f a b

f a b | even x = x `div` 2

| otherwise = 1 + x `div` 2

where x = a + b

-- La definición

raizEnt1 :: Integer -> Integer -> Integer

raizEnt1 x n = floor $ (fromIntegral x)**(1/fromIntegral n)

-- no da el resultado correcto cuando x es una potencia n-sima.

Responder

Raíz entera

Soluciones

Soluciones en Maxima

7 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico

Soluciones

Soluciones en Maxima

Se puede imprimir o compartir con

7 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico