Fórum: Valaki mondja meg!

[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] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128] [129] [130] [131] [132] [133] [134] [135] [136] [137] [138] [139] [140] [141] [142] [143] [144] [145] [146] [147] [148] [149] [150] [151] [152] [153] [154] [155] [156] [157] [158] [159] [160] [161] [162] [163] [164] [165] [166] [167] [168] [169] [170] [171] [172] [173] [174] [175] [176] [177] [178] [179] [180] [181] [182] [183] [184] [185] [186] [187] [188] [189] [190] [191] [192] [193] [194] [195] [196] [197] [198] [199] [200] [201] [202] [203] [204] [205] [206] [207] [208] [209] [210] [211] [212] [213] [214] [215] [216] [217] [218] [219] [220] [221] [222] [223] [224] [225] [226] [227] [228] [229] [230]

Szeretnél hozzászólni? Jelentkezz be.

[412] csewe

2008-04-04 15:13:47

mindenkinek kösz a segítséget a wikipédiás oldal angol,ugyhogy ez nálam kilőve

a gyökvonásból nemsokat értettem, mert éphogy hármas voltam matekból, és már az sem most volt

mivel ez az egyenlet amire itt megoldást kértem ,csupán a program gyorsítását szolgálta volna, így arra az elhatározásra jutottam, hogy más megoldást keresek

ti jók voltatok, csak ez már nekem magas

sziasztok

Előzmény: [411] Sirpi, 2008-04-04 14:19:18

[411] Sirpi	2008-04-04 14:19:18
Rákerestem a wikipédián, itt van egy csomó módszer gyökvonásra.
Előzmény: [410] Róbert Gida, 2008-04-04 13:58:23

[410] Róbert Gida	2008-04-04 13:58:23
Van egyébként osztásmentes verziója is a négyzetgyök kiszámolásának (ott szorozni kell). Továbbá a legjobb programok természetesen nem teljes pontossággal számolnak, mint te például 14 jeggyel, hanem mindig kb. megduplázzák az értékes jegyek számát az a_k-ban.
Előzmény: [409] Sirpi, 2008-04-04 12:42:14

[409] Sirpi

2008-04-04 12:42:14

Ha már felmerült a téma, és azt állítottam, hogy a pontos jegyek száma iterációs lépésenként duplázódik, akkor kicsit pontosítanék, meg bizonyítanám is az állításomat. Tehát a rekurzió $a_{k+1}= \frac{a_k+n/a_k}2$

A számtani-mértani közepek közti egyenlőtlenség szerint ez mindig legalább $\sqrt{n}$ , így tegyük fel, hogy $x=\sqrt{n}+c$ (tehát x-nek c( $\geq$ 0) a hibája), és nézzük meg, hogy x-re alkalmazva az iterációt, mekkora lesz a következő tag, azaz $\frac{x+n/x}2$ hibája.

$\frac{x+n/x}2 - \sqrt n = \frac{\sqrt n + c + \frac n{\sqrt n + c}}2 - \sqrt n = \frac{-\sqrt n + c + \frac n{n-c^2} \cdot (\sqrt n - c)}2=$

$=\frac{(\frac{n}{n-c^2}-1)\cdot (\sqrt n - c)}2=\frac{\frac{c^2}{n-c^2}\cdot (\sqrt n - c)}2=\frac{c^2}{2(\sqrt n + c)}$

Ebből már pár dolog kiolvasható. Ha x nagy $\sqrt n$ -hez viszonyítva, akkor a hiba nagyjából feleződik: x=tn, ekkor c is hasonló nagyságrendű, és $\frac{c^2}{2(\sqrt n + c)} \approx \frac {t^2n^2}{2tn} = x/2$

Viszont ha már c<1, akkor a következő hiba már kisebb, mint c², vagyis valóban igaz a lépésenkénti duplázódó pontosság.

* * *

Ha gyorsítani akarunk az eljáráson, akkor annyit még érdemes megtenni, hogy a $\sqrt n$ -re adunk egy körülbelüli becslést, hogy az algoritmusnak ne kelljen az n,n/2,n/4... lépéseken végigmennie. Ha d alapú számrendszert használunk, akkor keressük meg a legkisebb k-t, amire n $\leq$ d^2k, és ilyenkor indítsuk az algoritmust d^k-ból, ezzel az első jó pár lépést megspóroljuk.

Egy példa a $\sqrt 2$ kiszámolására, a₁=2 indulóértékkel:

2,00000000000000 --- 1,50000000000000 --- 1,41666666666667 --- 1,41421568627451 --- 1,41421356237469 --- 1,41421356237309 --- 1,41421356237309

Vagyis a 6. érték már 14 jegyre pontos.

Előzmény: [406] Sirpi, 2008-04-03 10:40:19

[408] Hajba Károly

2008-04-04 00:18:51

Hallgass Sirpire, meglásd megéri!

Mivel a Sirpi javasolta rekurziós gyökvonás pontossága hatványozottan nő, így nagy számok esetén is gyors eredményt adhat. Talán nagyobb problémád lesz a nagy számok kezelésével, mint ezzel az eljárással.

Előzmény: [407] csewe, 2008-04-03 14:48:10

[407] csewe

2008-04-03 14:48:10

tulajdonképpen a szummát (remélem jól fogalmazok" szeretném visszafejteni n = (1 + 2 + 3 + 4 + ...végtelen) az egyenlettel megkapom ,hogy hányadik lépésnél éri el az n -et az összedás.

ehhez tudnotok kell hogy az eredeti képletem n = x * (x + 1 ) / 2 volt ezzel a képlettel megkaptam hogy hány számot kell összeadnom ,hony n -hez jussak.

reményeim szerint egy prímszitához tudom majd felhasználni a képletet , amivel néhányszáz esetleg néhányezer digites számokrol mondanám meg hogy prím e

a gyökvonás hosszú időtrabló folyamat, és nekem gyors algoritmus kellene

de sajnos nem ez az egyetlen probléma , hanem a nagy számok programozása is úgyhogy egyenlőre csak akkora számokra írom meg a rutint amekkorát a programnyelv alapból kezelni tud ,és ha sikeres akkor rátérek a nagyobb feladatra

ez nekem csak kedvtelés , de nagyon megköszönném, ha segitenétek.

Előzmény: [406] Sirpi, 2008-04-03 10:40:19

[406] Sirpi

2008-04-03 10:40:19

Igazából mire és milyen környezetben kell Neked erre megoldást adni? Mert amit írtam (a másodfokú egyenlet megoldóképlete szerinti megoldást), az a megoldás, és más nincs, szóval nem lehet gyökjel nélkül felírni. Programmal akarod esetleg csinálni? (Mert ott elvileg van gyökvonás.) Meg milyen nagyságrendű az n? Ha ezekre választ adsz, akkor jobban segíteni tudunk talán abban, amire szükséged van.

* * *

A gyökvonást mi magunk is implementálhatjuk, alapműveletekkel, ha épp nem akarunk beépítettet használni. Legyen mondjuk a₁=1 (vagy a $\sqrt{n}$ bármilyen közelítése, ha tudunk jobbat), majd $a_{k+1}= \frac{a_k + n / a_k}2$ . Ez a rekurzió nagyon gyorsan tart a $\sqrt{n}$ -hez, a_k+1-nek kétszer annyi jegye pontos, mint a_k-nak. Csak be kell állítani valami leállási paramétert, hogy a program ne fusson a végtelenségig (pl. $\left|a_{k+1}-a_k\right| < 10^{-10}$ , vagy amilyen pontosság nekünk kell).

Előzmény: [405] csewe, 2008-04-03 08:42:26

[405] csewe	2008-04-03 08:42:26
nem kell az x-nek egésznek lenni
Előzmény: [404] BohnerGéza, 2008-04-02 19:31:13

[404] BohnerGéza	2008-04-02 19:31:13
Az x-nek is egésznek kell lennie?
Előzmény: [400] csewe, 2008-04-02 17:02:09

[403] csewe

2008-04-02 17:50:26

köszi a megoldást

még azt kérdezném,hogy nem menne ez gyökvonás nélkül

mert nagy számoknál ez elég problémás

Már regisztráltál?
Új vendég vagy?