pomoc s kvadratickou rovnici v C .. otazka spise pro matematiky

[SIGSEGV]

zdravim,

Myslim, ze komentar v kodu nepotrebuje dalsi vysvetleni ..

pripominam jen, ze se mi nechtelo delat bsearch(), proto to linearni vyhledavani stejne jako nedelani nejakeho map|table|hash ..
dale pripominam, ze pro L ocekavame korektni data, vzesla z predpokladaneho zpusobu inkrementu n .. (proto int a ne float|double)
pro matematiky ale neprogramatory: sqrt() == odmocnina, pow() == mocnina

otazka tedy zni: dokaze nekdo vyjadrit ciste aritmeticky n=?, pripadne ubastlit nejaky algoritmus pro bisection_method kterej to zefektivni ? (http://en.wikipedia.org/wiki/Bisection_method a http://en.wikipedia.org/wiki/Secant_method)

/* sample example: `gcc -o foo bar -lm`
*       having inane equation n(n+sqrt(n))=L where:
*       n increments as m=1; n=(++m)**2 .. so only integers are used
*       the highest value of sqrt(n) is FF (255) so n could be up to 255**2
*
*       you're getting L and need to determine n
*       in example below we increment n and break() until we reach equality with L
*
*       well, this code uses linear search which is NOT definitely very optimal
*       foo() also requires that only correct L will be passed ..
*/

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

long foo(long long L)
{
        long m, n, e;
        m = n = 1;
        e = pow(255, 2);

        for(n = 1; n <= e; n = pow(++m, 2)) {
                if(n * (n + sqrt(n)) == L)
                        break;
        };
        return(n);
}

int main(void)
{
        printf("%ld\n", foo(2439853704)); /* L value is hardcoded here .. */
        exit(0);
}

diky, 11

ps. overovat muzete napriklad takto:

Kód: [Vybrat]

# perl -Mbigint -e '$n=222**2; print $n*($n+sqrt($n)), " $n\n"'
2439853704 49284
pps. je to jenom priklad kodu, ktery resi opisem to, co by se melo resit aritmeticky .. samotny kod neni dulezity, stejne jako linearni|binarni vyhledavani ... to co je zajimave je bud prime vyjadreni n= a nebo bisection_metoda (a^4 + a^3 IMO)

[MacHala]

mno, analyticky to sice resit jde, ale asi te to moc nepotesi... http://www.wolframalpha.com/input/?i=x^2%2Bx^%283%2F2%29%3Dn


jinak inkrementovat to n od 0 je pro vyssi cisla docela hloupe, mnohem lepsi mas zacit dekrementovat od odmocniny z L


a v pripade, ze chces pocitat jen pro n z intervalu <0,255>, tak naprosto nechapu co resis, kdyz si muzes predem vsechny vysledky vyplivnout do souboru, ktery muzes nasledne grepovat temi svymi zadanymi L...


P.S.:
tvrzeni v komentari, ze se pouzivaji jen itegery je naprosto mimo, protoze pouzivas funkce sqrt a pow... (klidne si to zkus dissassemblovat)

[MacHala]

no, jestli nechces to analyticke reseni z wolframalpha, tak bude asi opravdu nejjednodussi pouzit to puleni intervalu, jako vychozi horni hranici muzes pouzit tu odmocninu z L a jako dolni hranici treba odmocninu z L/2 (to bude platne jen pro priblizne  n>=1)

reseni napr tady - nezkousel jsem ani zkompilovat ale na pohled to vypada dobre... (pozor bude fungovat jen pro L>2 a z vrchu to bude omezeno vlastnostmi double)

Kód: [Vybrat]

double bisect(double L) {
double horni, dolni , stred;
horni = pow(L,0.5);
dolni = pow(L/2,0.5);
stred= dolni;

#define POZADOVANAPRESNOST 0.01

while ( (horni-dolni)> POZADOVANAPRESNOST )
   stred = (horni-dolni)/2+dolni;
   if ((pow(stred,2)+pow(stred,1.5))>L) {
     horni=stred;
   }
   else {
      dolni=stred;
   }
}
return  stred;
}


[pacholik]

protože to tak není, jenom zaokrouhluješ na celý čísla

Kód: [Vybrat]

$ perl -Mbigint -E '$n=333**2; say $n*($n+sqrt($n))'
12333296358
$ , "sqrt(pow(12333296358,0.25)^2)"
333.2497189606259215505959496500707673843419867626453155931505670117
$ , 333^4
12296370321
$ , "sqrt(pow(12296370321,0.25)^2)"
332.9999999999999999999999999999999999999999999999999999999999999772
_{mám jednoduchou kalkulačku s bc}

[MacHala]

nechapu jak je to mozny ale mam to vyreseny:
prosim o vysvetleni proc u:

n(n+sqrt(n))=L === m4+m3=L

n=int(L**(1/4))

vcera jsem to tu necetl zrovna pozorne, takze k tomu, ze je to m^4+m^3=L (bral jsem to tak, ze n je obecne a tudiz je to celkove n^2+n^1.5=L )

vysvetleni proc oriznuti funguje je celkem jednoduche (ale na limity jsem si vcera ani nevzpomnel):

vliv m^3 je ve srovnani s m^4 cim dal tim zanedbatelnejsi (pri m jdoucim k nekonecnu se L limitne blizi hodonote m^4), takze se da rict m^4~=L => |m|~=L^(1/4)

to oriznuti na cela cisla by melo fungovat pro vsechna takova m, ze m^4+m^3<(m+1)^4 (no, pro zaporna m je to samozrejme blbost (L^(1/4)>0) a to orezavani se podela i na casti intervalu (0,1) (pro m<1 a zaroven m^4+m^3>1), tzn zajimaji-li te jen kladna cela cisla, tak to funguje vsude

EDIT: vyse uvedene je z vetsiny hloupost, nechavam to tu pro ilustraci toho, jake hlouposti muze nekdy napsat i inteligentni clovek a take toho, ze zaobalime-li spravne jadro ( tzn fakt, ze m^4 =< m^4+m^3 < (m+1)^4 ) do hromady hloupych kecu, tak ostatni nemusi to jadro ani najit...)

[daysleeper]

vliv m^3 je ve srovnani s m^4 cim dal tim zanedbatelnejsi (pri m jdoucim k nekonecnu se L limitne blizi hodonote m^4), takze se da rict m^4~=L => |m|~=L^(1/4)

IMO:
pri m jdoucim k nekonecnu se L limitne blizi nekonecnu taky, ne m^4

take napr. jiz pro rovnici m^4+100*m^3+299=L neplati, ze m=int(L^(1/4)), pro libovolne cele kladne m, takze se to neda takto zobecnit (ty parametry 100 a 299 tam mam jen pro zjednoduseni vypoctu, urcite by sly najit i nejake mensi)

dale technicka poznamka: nejedna se o kvadratickou, ale kvartickou rovnici

nakonec otazka: kde na takovato zadani chodite? 

[MacHala]

vliv m^3 je ve srovnani s m^4 cim dal tim zanedbatelnejsi (pri m jdoucim k nekonecnu se L limitne blizi hodonote m^4), takze se da rict m^4~=L => |m|~=L^(1/4)

IMO:
pri m jdoucim k nekonecnu se L limitne blizi nekonecnu taky, ne m^4

take napr. jiz pro rovnici m^4+100*m^3+299=L neplati, ze m=int(L^(1/4)), pro libovolne cele kladne m, takze se to neda takto zobecnit (ty parametry 100 a 299 tam mam jen pro zjednoduseni vypoctu, urcite by sly najit i nejake mensi)

1. ostavec:
to je to same

2. odstavec:
nevytrhavej to z kontextu, pro tebou uvedeny vyraz je jasne, ze to platit nebude, protoze neni pravda, ze m^4+100*m^3+299<(m+1)^4 (opet ma smysl bavit se jen o kladnych cislech)

EDIT: omlouvam se za lehce utocny ton, uznavam, ze citovany post byl napsan hloupe (viz jeho editace), takze proniknout k jadru pudla mohl byt nadlidsky vykon

[pacholik]

Výraz (x⁴+x³)^0,25 - (x⁴)^0,25 nikdy nedosáhne vysokých hodnot, limitně se blíží 1/4. Něco o limitě v každý středoškolský učebnici matematiky

[MacHala]

vzhledem k tomu, ze limity uz jsem prakticky zapomnel, tak jeste jednou (a lepe (a taky bez limit (a aby to pripadne pochopil i clovek s 3 promilemi v krvi* )))

m^4 = L <=> L^0.25 = m
(m+1)^4 = K <=>  K^0.25 = m+1

kdyz budu predpokladat, ze m je cele cislo a misto 1 prictu cokoliv mensiho (napr. 0.99), tak
(m+0.99)^4 = K <=>  K^0.25 = m+0.99

nic se samozrejme nezmenilo, ale vezmu-li rovnici

K^0.25 = m+0.99 a provedu pro obe strany oriznuti na celou cast, zjistim, ze

int(K^0.25) = m  a tedy int( ((m+0.99)^4)^0.25 ) = m
--------------------------------------------------------------------------------------------
z vyse uvedeneho by kazdemu melo byt alespon intuitivne jasne (intuitivne celkem staci, protoze jak se rika, "matematiku nepochopis, na tu si zvyknes") ze plati:
 int( ((m+z)^4)^0.25 ) = m  (pro z z intervalu <0,1) a cele m )

a tedy, vzhledem k tomu, ze m^4+m^3 je mensi nez (m+1)^4 (na prvni pohled mozna neni videt, ale po roznasobeni :
(m+1)^4=m^4+4m^3+6m^2+4m+1
je to zrejme) plati, ze pro cele m bude vzdy platit int( ((m^4+m^3)^0.25 ) = m

---------------------------------------------------------------------------------------------
* budu vdecny za experimetalni vyzkouseni...

[daysleeper]

uff... rozhodne jednodussi nez ta limita... pacholika bych poprosil, jestli by mi mohl naznacit, jak tuto limitu obecne vyresit pouze pomoci znalosti stredoskolske matematiky 

mne z podminky (viz MacHala)
m⁴+m³ < (m+1)⁴
po uprave vychazi
3m³+6m²+4m+1 > 0, coz je trivialne splneno pro vsechna prirozena m (tim je dukaz ukoncen (za strizliva tedy) )

pro zajimavost jiz pro vyraz m⁴+5m³ tato podminka obecne neplati, neni tedy mozne psat

Kód: [Vybrat]

pow(m, 4) + 5 * pow(m, 3) = L <=====> (int) pow(L, 0.25) = m