Perkirakan Kuadratku

10

Terinspirasi oleh video ini oleh tecmath .

Perkiraan akar kuadrat dari angka apa pun xdapat ditemukan dengan mengambil akar kuadrat bilangan bulat s(yaitu bilangan bulat terbesar sehingga s * s ≤ x) dan kemudian menghitung s + (x - s^2) / (2 * s). Mari kita sebut perkiraan ini S(x). (Catatan: ini setara dengan menerapkan satu langkah metode Newton-Raphson).

Meskipun ini memiliki kekhasan, di mana S (n ^ 2 - 1) akan selalu menjadi √ (n ^ 2), tetapi umumnya akan sangat akurat. Dalam beberapa kasus yang lebih besar, ini dapat memiliki akurasi> 99,99%.

Masukan dan keluaran

Anda akan mengambil satu nomor dalam format apa pun.

Contohnya

Format: Input -> Output

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

Spesifikasi

  • Output Anda harus dibulatkan ke paling tidak seperseratus terdekat (mis. Jika jawabannya 47.2851, Anda dapat output 47.29)

  • Output Anda tidak harus memiliki nol dan titik desimal berikut jika jawabannya adalah bilangan bulat (mis. 125.00 dapat ditampilkan sebagai 125 dan 125.0, juga)

  • Anda tidak harus mendukung angka apa pun di bawah 1.

  • Anda tidak harus mendukung input non-integer. (mis. 1,52 dll ...)

Aturan

Celah Standar dilarang.

Ini adalah kode-golf , jadi jawaban tersingkat dalam byte menang.

code-golf math approximation Stan Strum
sumber
Sandbox
Stan Strum
3
Catatan:s + (x - s^2) / (2 * s) == (x + s^2) / (2 * s)
JungHwan Min
Solusi saya: Pyth , 25 byte ; 14 byte
Stan Strum
Apakah harus akurat setidaknya 2 digit?
totallyhuman
@ benar-benar manusia Ya. 47.2851 dapat direpresentasikan sebagai 47.28, tetapi tidak ada lagi yang tidak akurat.
Stan Strum

Jawaban:

2

Jelly ,  8  7 byte

-1 byte berkat rumus matematika sederhana Olivier Grégoire - lihat jawaban Java mereka .

÷ƽ+ƽH

Cobalah online!

Bagaimana?

÷ƽ+ƽ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
sumber
7 byte: ÷ƽ+ƽHPertama kali mencoba menggunakan Jelly jadi saya mungkin salah. Saya berharap saya tahu cara menyimpan ƽ, untuk tidak mengulanginya. Itu mungkin menghemat byte lain.
Olivier Grégoire
Terima kasih @ OlivierGrégoire! ƽɓ÷⁹+Htidak akan menghitung ulang akar integer, tetapi juga 7. ɓmemulai rantai diad baru dengan argumen bertukar dan kemudian ⁹merujuk ke argumen kanan rantai itu (yaitu hasil ƽ). ƽɓ÷+⁹Hakan bekerja di sini juga.
Jonathan Allan
4

Haskell , 34 byte

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

Cobalah online!

Penjelasan dalam pseudocode imperatif:

results=[]
foreach s in [1..x]:
 if s*s<=x:
  results.append(s+x/s)
return results[end]/2
Leo
sumber
4

Java (OpenJDK 8) , 32 byte

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

Cobalah online!

Penjelasan

Kode ini setara dengan ini:

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

Matematika di belakang:

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
sumber
Ini tampaknya tidak menangani spesifikasi: Output Anda harus dibulatkan ke setidaknya seratus terdekat
Ayb4btu
2
Yah, itu dibulatkan ke yang lebih rendah dari yang keseratus terdekat, jadi itu benar-benar valid.
Olivier Grégoire
Ah, begitu, kesalahpahaman saya.
Ayb4btu
4

Python 2 , 47 ... 36 byte

-3 byte berkat @JungHwanMin
-1 byte berkat @HyperNeutrino
-2 byte terima kasih kepada @JonathanFrech
-3 byte terima kasih kepada @ OlivierGrégoire

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

Cobalah online!

ovs
sumber
-2 byte: s+(x-s*s)/s/2ke(x+s*s)/s/2
JungHwan Min
-2 byte menggunakan fungsi
HyperNeutrino
@HyperNeutrino Saya hanya mendapatkan -1 byte
ovs
Oh maaf, saya tidak sengaja menghapus karakter setelah pengujian dan kemudian menghitung byte setelah: P yeah hanya -1
HyperNeutrino
Tidak bisakah Anda menghilangkan +.0dan mengganti /s/2dengan /2./s, menghemat dua byte?
Jonathan Frech
3

R, 43 byte, 29 byte

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

Terima kasih kepada @Giuseppe untuk persamaan baru dan bantuan dalam bermain golf sebesar 12 byte dengan solusi pembagian integer. Dengan menukar fungsi panggilan untuk memindai, saya bermain golf beberapa byte lagi.

Cobalah online!

Menandai
sumber
1
35 byte ; lebih umum, Anda dapat menggunakan bidang "header" dari TIO dan meletakkan f <- untuk menetapkan fungsi. Tapi tetap saja, solusi yang bagus, pastikan Anda membaca Tips untuk bermain golf di R saat Anda mendapat kesempatan!
Giuseppe
1
31 byte menggunakan rumus Oliver Gregoire
Giuseppe
2

JavaScript (ES7), 22 byte

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

Kami tidak benar-benar membutuhkan variabel perantara, jadi ini sebenarnya dapat ditulis ulang sebagai:

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

Uji kasus

Tampilkan cuplikan kode

Arnauld
sumber
2

C, 34 byte

Terima kasih kepada @Olivier Grégoire!

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

Hanya bekerja dengan floatinput.

Cobalah online!

C,  41   39  37 byte

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

Cobalah online!

C,  49   47   45  43 byte

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

Cobalah online!

Terima kasih kepada @JungHwan Min karena telah menghemat dua byte!

Steadybox
sumber
1
47 byte ; sunting: Terima kasih, tetapi kreditlah @JungHwanMin karena menemukan itu.
Stan Strum
34 byte
Olivier Grégoire
2

Haskell , 40 byte

Satu lagi bytes debu berkat H.PWiz.

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

Cobalah online!

benar-benar manusiawi
sumber
2

AWK , 47 44 38 byte

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

Cobalah online!

CATATAN: Seperti TIO memiliki 2 byte tambahan untuk \n membuat output lebih cantik. :)

Rasanya seperti curang sedikit untuk menggunakan sqrt untuk menemukan akar kuadrat, jadi di sini adalah versi dengan beberapa byte lagi yang tidak.

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

Cobalah online!

Robert Benson
sumber
1
baik Anda bisa mengatakan ini AWKward. Saya akan menunjukkan diri. sunting: awalnya saya berencana untuk menghindari menggunakan sqrt, tetapi ada terlalu banyak jawaban dan saya akan mendapatkan kesalahan jika saya mengubahnya sehingga ide asli saya berfungsi.
Stan Strum
Permainan kata-kata 'AWK' sangat menyenangkan :)
Robert Benson
alih-alih sqrt($1)Anda dapat menggunakan$1^.5
Cabbie407
Terima kasih @ Cabbie407 tidak tahu mengapa saya tidak memikirkan itu.
Robert Benson
1
Sama-sama. Beberapa hal lain: Anda tidak perlu \nmendapatkan output, printf dalam awk tidak perlu tanda kurung dan rumus dapat disingkat s/2+$1/s/2, yang menghasilkan {s=int($1^.5);printf"%.2f",s/2+$1/s/2}. Maaf jika komentar ini sepertinya tidak sopan.
Cabbie407
1

Raket , 92 byte

Terima kasih kepada @JungHwan Min atas tipnya di bagian komentar

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

Cobalah online!

Tidak disatukan

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

PowerShell , 54 byte

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

Cobalah online! atau Verifikasi beberapa kasus uji

Mengambil input $xdan kemudian melakukan apa yang diminta. Bagian |?menemukan bilangan bulat maksimal yang, ketika kuadrat, adalah -less-than-or- equal ke input $x, maka kami melakukan perhitungan yang diperlukan. Output tersirat.

AdmBorkBork
sumber
Wow. Saya tidak pernah bisa memahami bagaimana orang bermain golf di Windows Powershell
Stan Strum
@StanStrum Anda tidak sendirian, lol. : D
AdmBorkBork
1

Sekam , 9 byte

½Ṡ§+K/(⌊√

Cobalah online!

Masih ada sesuatu yang buruk dalam jawaban ini, tetapi sepertinya saya tidak dapat menemukan solusi yang lebih pendek.

Penjelasan

Saya menerapkan satu langkah algoritma Newton (yang memang setara dengan yang diusulkan dalam pertanyaan ini)

½Ṡ§+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
Leo
sumber
Saya pikir Anda ingin pembagian yang sebenarnya, bukan÷
H.PWiz
@ H.Peiz whoops, saya lakukan, terima kasih. Itu adalah sisa dari percobaan untuk menemukan solusi lain
Leo
1

Pyt , 11 10 byte

←Đ√⌊Đ↔⇹/+₂

Penjelasan

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
sumber
Baru saja melihat ini dan itu adalah menit yang baik sampai saya menyadari itu bukan Pyth. Jawaban yang bagus
Stan Strum
Ya, itu sedikit bahasa yang saya pikirkan untuk sementara waktu dan baru saja memutuskan untuk membuatnya.
mudkip201
Apakah ToS top-of-stack ... dan jika demikian, apa itu SoS?
Stan Strum
ToS berada di atas tumpukan, dan SoS adalah yang kedua di tumpukan
mudkip201
Bagus, saya akan melihat apakah saya bisa mempelajari bahasa ini; Saya suka itu!
Stan Strum
1

Bimasakti , 17 14 byte

-3 byte dengan menggunakan rumus Olivier Grégoire

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

Cobalah online!

Penjelasan

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
sumber
bukankah seharusnya itu lantai bukannya langit-langit?
mudkip201
@ mudkip201 Diperbarui, terima kasih
Ov