Przybliż moje kwadraty

10

Zainspirowany tym filmem autorstwa tecmath .

Przybliżenie pierwiastka kwadratowego dowolnej liczby xmożna znaleźć, biorąc całkowitą pierwiastek kwadratowy s(tj. Największą liczbę całkowitą taką s * s ≤ x), a następnie obliczając s + (x - s^2) / (2 * s). Nazwijmy to przybliżeniem S(x). (Uwaga: jest to równoważne z zastosowaniem jednego etapu metody Newtona-Raphsona).

Chociaż ma to dziwactwo, gdzie S (n ^ 2 - 1) zawsze będzie √ (n ^ 2), ale ogólnie będzie bardzo dokładne. W niektórych większych przypadkach może to mieć dokładność> 99,99%.

Wejście i wyjście

Weźmiesz jeden numer w dowolnym dogodnym formacie.

Przykłady

Format: Wejście -> Wyjście

2 -> 1.50
5 -> 2.25
15 -> 4.00
19 -> 4.37               // actually 4.37       + 1/200
27 -> 5.20
39 -> 6.25
47 -> 6.91               // actually 6.91       + 1/300
57 -> 7.57               // actually 7.57       + 1/700
2612 -> 51.10            // actually 51.10      + 2/255
643545345 -> 25368.19    // actually 25,368.19  + 250,000,000/45,113,102,859
35235234236 -> 187710.50 // actually 187,710.50 + 500,000,000/77,374,278,481

Dane techniczne

  • Twój wynik musi być zaokrąglony do co najmniej najbliższej setnej (tj. Jeśli odpowiedź to 47.2851, możesz otrzymać 47,29)

  • Dane wyjściowe nie muszą mieć następujących zer i dziesiętnych, jeśli odpowiedź jest liczbą całkowitą (tzn. 125.00 można również zapisać jako 125 i 125,0)

  • Nie musisz obsługiwać żadnych liczb poniżej 1.

  • Nie musisz obsługiwać danych wejściowych niecałkowitych. (tj. 1,52 itd.)

Zasady

Standardowe luki są zabronione.

To jest golf golfowy , więc wygrywa najkrótsza odpowiedź w bajtach.

code-golf math approximation Stan Strum
źródło
Piaskownica
Stan Strum
3
Uwaga:s + (x - s^2) / (2 * s) == (x + s^2) / (2 * s)
JungHwan Min
Moje rozwiązania: Pyth , 25 bajtów ; 14 bajtów
Stan Strum
Czy musi zawierać co najmniej 2 cyfry?
całkowicie ludzki,
@totallyhuman Yes. 47,2851 można przedstawić jako 47,28, ale nigdy więcej niedokładnych.
Stan Strum

Odpowiedzi:

2

Galaretka ,  8  7 bajtów

-1 bajt dzięki uproszczonej formule matematycznej Oliviera Grégoire'a - zobacz odpowiedź na Javę .

÷ƽ+ƽH

Wypróbuj online!

W jaki sposób?

÷ƽ+ƽH - Link: number, n
 ƽ     - integer square root of n  -> s
÷       - divide                    -> n / s
    ƽ  - integer square root of n  -> s
   +    - add                       -> n / s + s
      H - halve                     -> (n / s + s) / 2
Jonathan Allan
źródło
7 bajtów: ÷ƽ+ƽHpo raz pierwszy próbuję użyć Galaretki, więc mogę się mylić. Chciałbym jednak wiedzieć, jak przechowywać ƽ, żeby tego nie powtarzać. To może zaoszczędzić kolejny bajt.
Olivier Grégoire
Dzięki @ OlivierGrégoire! ƽɓ÷⁹+Hnie przeliczyłby korzenia całkowitoliczbowego, ale również 7. ɓrozpoczyna nowy łańcuch diadadowy z zamienionymi argumentami, a następnie ⁹odnosi się do właściwego argumentu tego łańcucha (tj. wyniku ƽ). ƽɓ÷+⁹Hteż tu by działał.
Jonathan Allan
4

Haskell , 34 bajty

f x=last[s+x/s|s<-[1..x],s*s<=x]/2

Wypróbuj online!

Objaśnienie w pseudokodzie imperatywnym:

results=[]
foreach s in [1..x]:
 if s*s<=x:
  results.append(s+x/s)
return results[end]/2
Lew
źródło
4

Java (OpenJDK 8) , 32 bajty

n->(n/(n=(int)Math.sqrt(n))+n)/2

Wypróbuj online!

Objaśnienia

Kod jest równoważny z tym:

double approx_sqrt(double x) {
  double s = (int)Math.sqrt(x);  // assign the root integer to s
  return (x / s + s) / 2
}

Matematyka za:

s + (x - s²) / (2 * s)  =  (2 * s² + x - s²) / (2 * s)
                        =  (x + s²) / (2 * s)
                        =  (x + s²) / s / 2
                        =  ((x + s²) / s) / 2
                        =  (x / s + s² / s) / 2
                        =  (x / s + s) / 2
Olivier Grégoire
źródło
Wydaje się, że to nie obsługuje specyfikacji: dane wyjściowe należy zaokrąglić do co najmniej setnej setki
Ayb4btu
2
Cóż, jest zaokrąglony do mniejszej niż najbliższa setna, więc jest całkowicie poprawny.
Olivier Grégoire
Ach, rozumiem, moje nieporozumienie.
Ayb4btu
4

Python 2 , 47 ... 36 bajtów

-3 bajty dzięki @JungHwanMin
-1 bajtów dzięki @HyperNeutrino
-2 bajty dzięki @JonathanFrech
-3 bajtów dzięki @ OlivierGrégoire

def f(x):s=int(x**.5);print(x/s+s)/2

Wypróbuj online!

ovs
źródło
-2 bajty: s+(x-s*s)/s/2do(x+s*s)/s/2
JungHwan Min
-2 bajty przy użyciu funkcji
HyperNeutrino,
@HyperNeutrino ja tylko dostać -1 bajt
OVS
Och przepraszam, przypadkowo
usunąłem
Nie można pominąć +.0i zastąpić /s/2z /2./s, oszczędzając dwa bajty?
Jonathan Frech
3

R, 43 bajty 29 bajtów

x=scan()
(x/(s=x^.5%/%1)+s)/2

Dzięki @Giuseppe za nowe równanie i pomoc w golfie 12 bajtów dzięki rozwiązaniu dzielenia liczb całkowitych. Wymieniając wywołanie funkcji do skanowania, grałem w golfa o kolejne kilka bajtów.

Wypróbuj online!

znak
źródło
1
35 bajtów ; bardziej ogólnie, możesz użyć pola „nagłówek” TIO i wstawić, f <- aby przypisać funkcję. Ale wciąż fajne rozwiązanie, pamiętaj, aby przeczytać Porady dotyczące gry w golfa w R, gdy masz szansę!
Giuseppe
1
31 bajtów przy użyciu formuły Olivera Gregoire'a
Giuseppe
2

JavaScript (ES7), 22 bajty

x=>(s=x**.5|0)/2+x/s/2

Tak naprawdę nie potrzebujemy zmiennej pośredniej, więc można ją przepisać jako:

x=>x/(x=x**.5|0)/2+x/2

Przypadki testowe

Pokaż fragment kodu

Arnauld
źródło
2

C, 34 bajty

Dzięki @Olivier Grégoire!

s;
#define f(x)(x/(s=sqrt(x))+s)/2

Działa tylko z floatwejściami.

Wypróbuj online!

C,  41   39  37 bajtów

s;
#define f(x).5/(s=sqrt(x))*(x+s*s)

Wypróbuj online!

C,  49   47   45  43 bajtów

s;float f(x){return.5/(s=sqrt(x))*(x+s*s);}

Wypróbuj online!

Dzięki @JungHwan Min za zapisanie dwóch bajtów!

Steadybox
źródło
1
47 bajtów ; edycja: Dziękuję, ale dziękuję @JungHwanMin za znalezienie tego.
Stan Strum,
34 bajty
Olivier Grégoire
2

Haskell , 40 bajtów

Kolejny bajtuje kurz dzięki H.PWiz.

f n|s<-realToFrac$floor$sqrt n=s/2+n/s/2

Wypróbuj online!

całkowicie ludzki
źródło
2

AWK , 47 44 38 bajtów

{s=int($1^.5);printf"%.2f",$1/2/s+s/2}

Wypróbuj online!

UWAGA: TIO like ma 2 dodatkowe bajty, \naby uczynić wydruk ładniejszym. :)

To trochę oszustwo, aby użyć sqrt do znalezienia pierwiastka kwadratowego, więc tutaj jest wersja z kilkoma dodatkowymi bajtami, która tego nie robi.

{for(;++s*s<=$1;);s--;printf("%.3f\n",s+($1-s*s)/(2*s))}

Wypróbuj online!

Robert Benson
źródło
1
cóż, można powiedzieć, że to jest AWKward. Pokażę się. edytuj: pierwotnie planowałem uniknąć pytania za pomocą sqrt, ale jest zbyt wiele odpowiedzi i dostanę tortury, jeśli je zmienię, aby mój oryginalny pomysł zadziałał.
Stan Strum
Kalambury „AWK” są fajne :)
Robert Benson
zamiast sqrt($1)ciebie możesz użyć$1^.5
Cabbie407
Dzięki @ Cabbie407 nie wiem, dlaczego o tym nie pomyślałem.
Robert Benson
1
Nie ma za co. Kilka innych rzeczy: nie potrzebujesz, \naby uzyskać wynik, printf w awk nie potrzebuje nawiasów, a formułę można skrócić s/2+$1/s/2, co powoduje {s=int($1^.5);printf"%.2f",s/2+$1/s/2}. Przepraszam, jeśli ten komentarz wydaje się niegrzeczny.
Cabbie407
1

Rakieta , 92 bajty

Dzięki @JungHwan Min za wskazówkę w sekcji komentarzy

(λ(x)(let([s(integer-sqrt x)])(~r(exact->inexact(/(+ x(* s s))(* 2 s)))#:precision'(= 2))))

Wypróbuj online!

Nie golfił

(define(fun x)
  (let ([square (integer-sqrt x)])
    (~r (exact->inexact (/ (+ x (* square square)) (* 2 square)))
        #:precision'(= 2))))
Rodrigo Ruiz Murguía
źródło
1

PowerShell , 54 bajty

param($x)($x+($s=(1..$x|?{$_*$_-le$x})[-1])*$s)/(2*$s)

Wypróbuj online! lub Zweryfikuj niektóre przypadki testowe

Pobiera dane wejściowe, $xa następnie robi dokładnie to, co jest wymagane. |?Część znajdzie maksymalnej liczby całkowitej, że gdy do kwadratu, jest -less niż lub- equal do wejścia $x, a następnie wykonujemy niezbędne obliczenia. Wynik jest niejawny.

AdmBorkBork
źródło
Łał. Nigdy nie byłem w stanie zrozumieć, jak ludzie grają w golfa w Windows Powershell
Stan Strum
@StanStrum Nie jesteś sam, lol. : D
AdmBorkBork
1

Łuska , 9 bajtów

½Ṡ§+K/(⌊√

Wypróbuj online!

W tej odpowiedzi wciąż jest coś brzydkiego, ale nie mogę znaleźć krótszego rozwiązania.

Wyjaśnienie

Wdrażam jeden krok algorytmu Newtona (który jest rzeczywiście równoważny z tym zaproponowanym w tym pytaniu)

½Ṡ§+K/(⌊√
  §+K/       A function which takes two numbers s and x, and returns s+x/s
 Ṡ           Call this function with the input as second argument and
      (⌊√    the floor of the square-root of the input as first argument
½            Halve the final result
Lew
źródło
Myślę, że chcesz rzeczywistego podziału, a nie÷
H.PWiz
@ H.PWiz ups, tak, dziękuję. To był pozostałość z eksperymentu mającego na celu znalezienie innych rozwiązań
Leo
1

Pyt , 11 10 bajtów

←Đ√⌊Đ↔⇹/+₂

Wyjaśnienie

code                explanation                        stack
←                   get input                          [input]
 Đ                  duplicate ToS                      [input,input]
  √⌊                calculate s                        [input,s]
    Đ               duplicate ToS                      [input,s,s]
     ↔              reverse stack                      [s,s,input]
      ⇹             swap ToS and SoS                   [s,input,s]
       /            divide                             [s,input/s]
        +           add                                [s+input/s]
         ₂          halve                              [(s+input/s)/2]
                    implicit print
mudkip201
źródło
Właśnie to zobaczyłem i minęła dobra chwila, zanim zdałam sobie sprawę, że to nie Pyth. Świetna odpowiedź.
Stan Strum,
Tak, to jest mały język, o którym myślałem przez jakiś czas i po prostu postanowiłem go stworzyć.
mudkip201,
Czy ToS jest na szczycie stosu ... a jeśli tak, to czym jest SoS?
Stan Strum,
ToS jest na szczycie stosu, a SoS jest na drugim miejscu
mudkip201,
Fajnie, zobaczę, czy mogę zagłębić się w ten język; Lubię to!
Stan Strum,
1

Droga Mleczna , 17 lat 14 bajtów

-3 bajty przy użyciu formuły Oliviera Grégoire'a

^^':2;g:>/+2/!

Wypróbuj online!

Wyjaśnienie

code              explanation                   stack layout

^^                clear preinitialized stack    []
  ':              push input and duplicate it   [input, input]
    2;            push 2 and swap ToS and SoS   [input, 2, input]
      g           nth root                      [input, s=floor(sqrt(input))]
       :          duplicate ToS                 [input, s, s]
        >         rotate stack right            [s, input, s]
         /        divide                        [s, input/s]
          +       add                           [s+input/s]
           2/     divide by 2                   [(s+input/s)/2]
             !    output                        => (s+input/s)/2
ovs
źródło
czy nie powinna to być podłoga zamiast sufitu?
mudkip201,
@ mudkip201 Zaktualizowano, dziękuję
dniu