Calcular la superraíz de un número

10

En matemáticas, la tetración es el siguiente hiperoperador después de la exponenciación, y se define como exponenciación iterada.

Suma ( un éxito n veces)

Multiplicación ( un agregado a sí mismo, n veces)

Exponenciación ( un multiplicado por sí mismo, n veces)

Tetración ( un exponenciadas por sí mismo, n veces)

Las relaciones inversas de la tetración se denominan superraíz y superlogaritmo. Su tarea consiste en escribir un programa que, dada A y B, imprime el B nd -order súper raíz del A.

Por ejemplo:

  • si A = 65,536y B = 4se imprime2
  • si A = 7,625,597,484,987y B = 3se imprime3

A y B son enteros positivos y el resultado debe ser un número de coma flotante con una precisión de 5 dígitos después del punto decimal. El resultado pertenece al dominio real.

Tenga cuidado, las superraíces pueden tener muchas soluciones.

Andrea Ciceri
fuente
1
¿Hay límites mínimos / máximos en los números de entrada? ¿Debería una respuesta válida admitir respuestas de coma flotante o solo un entero?
Josh
3
Si hay varias soluciones, ¿el programa debe encontrar todas o solo una?
Johannes H.
55
Entonces, ¿cuál es su criterio ganador?
Mhmd
2
¿Puedes dar un ejemplo simple de una superraíz que tenga más de una solución para A y B ≥ 1?
Tobia
1
¿Puedes dar la representación matemática de una superraíz? Me temo que todavía no entiendo cómo se define.

Respuestas:

6

C - buscando claridad, no intenté exprimir el código

Considerando la entrada:

A: A ∈ ℝ, A ≥ 1.0
B: B ∈ ℕ, B ≥ 1

Entonces, por lo general, solo debe haber una solución en ℝ, lo que simplifica considerablemente el problema.

El código es:

#include <stdlib.h>
#include <stdio.h>
#include <math.h>

#define TOLERANCE    1.0e-09

double tetrate(double, int);

int main(int argc, char **argv)
{
    double target, max, min, mid, working;
    int levels;

    if (argc == 3)
    {
        target = atof(argv[1]); // A
        levels = atoi(argv[2]); // B

        // Shortcut if B == 1
        if (levels == 1)
        {
            printf("%f\n", target);
            return 0;
        }

        // Get a first approximation
        max = 2.0;
        while (tetrate(max, levels) < target)
            max *= 2.0;

        min = max / 2.0;

        // printf("Answer is between %g and %g\n", min, max);

        // Use bisection to get a closer approximation
        do
        {
            mid = (min + max) / 2.0;
            working = tetrate(mid, levels);
            if (working > target)
                max = mid;
            else if (working < target)
                min = mid;
            else
                break;
        }
        while (max - min > TOLERANCE);

        // printf("%g: %f = %f tetrate %d\n", target, tetrate(mid, levels), mid, levels);
        printf("%f\n", mid);
    }

    return 0;
}

double tetrate(double d, int i)
{
    double result = d;

    // If the result is already infinite, don't tetrate any more
    while (--i && isfinite(result))
        result = pow(d, result);

    return result;
}

Compilar:

gcc -o tet_root tet_root.c -lm

Correr:

./tet_root A B

P.ej:

4 2

$ ./tet_root 65536 4
2.000000

3 3

$ ./tet_root 7625597484987 3
3.000000

3 π

$ ./tet_root 1.340164183e18 3
3.141593

n (2 ½ ) ➙ 2 como n ➙ ∞? (límite bien conocido)

$ ./tet_root 2 10
1.416190

$ ./tet_root 2 100
1.414214

$ ./tet_root 2 1000
1.414214

¡Si!

n (e 1 / e ) ➙ ∞ como n ➙ ∞? (límites superiores)

$ ./tet_root 9.999999999e199 100
1.445700

$ ./tet_root 9.999999999e199 1000
1.444678

$ ./tet_root 9.999999999e199 10000
1.444668

$ ./tet_root 9.999999999e199 100000
1.444668

¡Frio! (e 1 / e ≅ 1.44466786101 ...)


fuente
Realmente sabes mucho sobre matemáticas que puedo decir :) (Esta respuesta) ∈ (cosas realmente impresionantes)
Albert Renshaw
@AlbertRenshaw Esto es solo una implementación de bisección. No es muy difícil en absoluto.
Simply Beautiful Art
5

Python, 87 caracteres

E=lambda x,n:x**E(x,n-1)if n else 1
def S(A,B):
 x=1.
 while E(x,B)<A:x+=1e-5
 return x

Una búsqueda lineal simple para la respuesta.

Fuera de tema, pero ¿qué pasa con el **operador de Python * # $ (@!

>>> 1e200*1e200
inf
>>> 1e200**2
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
OverflowError: (34, 'Numerical result out of range')
Keith Randall
fuente
Digno de un informe de error?
Josh
¿Se está interponiendo la asociatividad? Tal vez usted está comparando (1e200)**2a 1e(200**2)?
danmcardle
2
@Josh: informé de un error: bugs.python.org/issue20543 Básicamente, trabajando según lo previsto, no son mucho para el flotador IEEE. Si tuvieran que arreglar algo, sería generar un OverflowErroren el primer caso.
Keith Randall
3

Mathematica, 35 40

n /. Solve[Nest[#^(1/n) &, a, b] == n]~N~5

Genera una lista de todas las soluciones, con precisión de 5 dígitos.

n /. Last@Solve[Nest[#^(1/n) &, a, b] == n]~N~5

5 caracteres más para obtener solo la solución real, que exigen las reglas actualizadas.

shrx
fuente
2

Julia

julia> t(a,b)=(c=a;for j=1:b-1;c=a^c;end;c)
julia> s(c,b)=(i=1;while t(i,b)!=c;i+=1;end;i)
julia> s(65536,4)
2
julia> s(7625597484987,3)     
3

Se omitió la instrucción de coma flotante ya que la pregunta solo define el comportamiento de los enteros.

gggg
fuente
2

¿Cuándo se convirtió esto en un código de golf? ¡Pensé que era un desafío de código encontrar el mejor algoritmo!


APL, 33 caracteres

{r←⍵⋄⍺{1≥⍵⍟⍣⍺⊢r:⍵⋄⍺∇⍵+i}1+i←1e¯6}

Esta es una búsqueda lineal simple, comenzando desde C = 1 + 10 -6 e incrementándola en 10 -6 hasta
    log C log C log C ⋯ A ≤ 1
donde la función log C se aplica recursivamente B veces.

Ejemplos

      4 {r←⍵⋄⍺{1≥⍵⍟⍣⍺⊢r:⍵⋄⍺∇⍵+i}1+i←1e¯6} 65536
2.0000009999177335
      3 {r←⍵⋄⍺{1≥⍵⍟⍣⍺⊢r:⍵⋄⍺∇⍵+i}1+i←1e¯6} 7625597484987
3.0000000000575113

Este código es muy lento, pero para bases pequeñas como 2 o 3 se completa en unos segundos. Vea a continuación para algo mejor.


APL, complejidad logarítmica

Complejidad realmente lineal en el orden raíz, logarítmica en el tamaño del resultado y precisión:

    tiempo = O (B × log (C) + B × log (D))

donde B es el orden de la raíz, C es la base de la tetración que se solicita y D es el número de dígitos de precisión solicitados. Esta complejidad es mi comprensión intuitiva, no he presentado una prueba formal.

Este algoritmo no requiere números enteros grandes, solo usa la función de registro en números regulares de punto flotante, por lo tanto, es bastante eficiente en números muy grandes, hasta el límite de la implementación de punto flotante (ya sea doble precisión o números FP grandes arbitrarios en el Implementaciones de APL que las ofrecen.)

La precisión del resultado se puede controlar configurando ⎕CT(tolerancia de comparación) el error aceptable deseado (en mi sistema, el valor predeterminado es 1e¯14, aproximadamente 14 dígitos decimales)

sroot←{              ⍝ Compute the ⍺-th order super-root of ⍵:
  n←⍺ ⋄ r←⍵          ⍝ n is the order, r is the result of the tetration.
  u←{                ⍝ Compute u, the upper bound, a base ≥ the expected result:
    1≥⍵⍟⍣n⊢r:⍵       ⍝   apply ⍵⍟ (log base ⍵) n times; if ≤1 then upper bound found
    ∇2×⍵             ⍝   otherwise double the base and recurse
  }2                 ⍝ start the search with ⍵=2 as a first guess.
  (u÷2){             ⍝ Perform a binary search (bisection) to refine the base:
    b←(⍺+⍵)÷2        ⍝   b is the middle point between ⍺ and ⍵
    t←b⍟⍣n⊢r         ⍝   t is the result of applying b⍟ n times, starting with r;
    t=1:b            ⍝   if t=1 (under ⎕CT), then b is the super-root wanted;
    t<1:⍺∇b          ⍝   if t<1, recurse between ⍺ and b
    b∇⍵              ⍝   otherwise (t>1) returse between b and ⍵
  }u                 ⍝ begin the search between u as found earlier and its half.
}

No estoy seguro de si lo 1≥⍵⍟⍣nanterior podría fallar con un Error de dominio (porque el registro de un argumento negativo podría fallar de inmediato o dar un resultado complejo, que no estaría en el dominio de ), pero no he podido encontrar Un caso que falla.

Ejemplos

      4 sroot 65536
1.9999999999999964
      4 sroot 65537
2.000000185530773
      3 sroot 7625597484987
3
      3 sroot 7625597400000
2.999999999843567
      3 sroot 7625597500000
3.000000000027626

'3' sale como un valor exacto porque resulta ser uno de los valores directamente alcanzados por la búsqueda binaria (comenzando desde 2, doblado a 4, bisecado a 3). En el caso general de que eso no suceda, el resultado se aproximará al valor raíz con un error ⎕CT (más precisamente, la prueba logarítmica de cada base candidata se realiza con tolerancia ⎕CT).

Tobia
fuente
1

Ruby, 79 bytes

->a,b{x=y=1.0;z=a;eval"y=(x+z)/2;x,z=a<eval('y**'*~-b+?y)?[x,y]:[y,z];"*99;p y}

Esto es lo mismo que el siguiente programa, pero menos preciso ya que solo ejecuta 99 bucles.

Rubí, 87 bytes

->a,b{x=y=1.0;z=a;(y=(x+z)/2;x,z=a<eval("y**"*~-b+?y)?[x,y]:[y,z])while y!=(x+z)/2;p y}

Pruébalo en línea

Esto es simplemente bisección. Sin golf:

-> a, b {
    # y^^b by evaluating the string "y ** y ** ..."
    tetration =-> y {eval "y ** " * (b-1) + ?y}

    lower = middle = 1.0
    upper = a

    while middle != (lower + upper) / 2 do
        middle = (lower + upper) / 2

        if tetration[middle] > a
            upper = middle
        else
            lower = middle
        end
    end

    print middle
}
Simplemente hermoso arte
fuente
0

k [52 caracteres]

{{{((%x)*(z*x-1)+y%z xexp x-1)}[x;y]/[2]}[y]/[y<;x]}

Una versión modificada de mi propio puesto n º raíz

Ejemplo:

{{{((%x)*(z*x-1)+y%z xexp x-1)}[x;y]/[2]}[y]/[y<;x]}[7625597484987;3]
3f 

{{{((%x)*(z*x-1)+y%z xexp x-1)}[x;y]/[2]}[y]/[y<;x]}[65536;4]
2f
nyi
fuente
0

Haskell

Búsqueda lineal simple, devuelve primero, se encuentra la coincidencia más pequeña.

{-
    The value of a is the result of exponentiating b some number of times.
    This function computes that number.
-}
superRoot a b = head [x | x<-[2..a], tetrate x b == a]

{-
    compute b^b^...^b repeated n times
-}
tetrate b 1 = b
tetrate b n = b^(tetrate b (n-1))

Ejemplo

*Main> superRoot 65536 4
2
*Main> superRoot 7625597484987 3
3
danmcardle
fuente
0

Mathematica, 41 bytes sin optimización

Mathematica fue inventado básicamente para resolver problemas como este. Una solución fácil es construir el problema como una serie de potencia anidada y pasarlo a la Reducefunción incorporada, que busca soluciones analíticas para las ecuaciones. Como resultado, lo siguiente, además de ser un código inusualmente conciso, tampoco es fuerza bruta.

Reduce[Nest[Power[#, 1/x] &, a, b] == x, x, Reals]

Puede eliminar la restricción para proporcionar solo soluciones de números reales si es paciente y desea guardar seis bytes. También puede expresar algunas de las funciones anidadas en forma abreviada para guardar algunos bytes más. Según lo dado, vuelve así

ingrese la descripción de la imagen aquí

Michael Stern
fuente
0

05AB1E , 16 bytes

1[ÐU²FXm}¹@#5(°+

Puerto de la respuesta Python de @KeithRandall .

Pruébalo en línea.

Explicación:

1                 # Push a 1
 [                # Start an infinite loop:
  Ð               #  Triplicate the top value on the stack
   U              #  Pop and store one in variable `X`
    ²F            #  Inner loop the second input amount of times:
      Xm          #   And take the top value to the power `X`
        }         #  After the inner loop:
         ¹@       #  If the resulting value is larger than or equal to the first input:
           #      #   Stop the infinite loop
                  #   (after which the top of the stack is output implicitly as result)
            5(°+  #  If not: increase the top value by 10^-5

ÐU²FXm}también podría ser D²>и.»mpara el mismo número de bytes:

  D               #   Duplicate the top value on the stack
   ²>             #   Push the second input + 1
     и            #   Repeat the top value that many times as list
                #   Reduce it by:
        m         #    Taking the power
Kevin Cruijssen
fuente