metode til beregning af kubikrod

tænk binært.
1  ^3  =  1        //
10 ^3  =  1000    // jo større tal, jo tættere på
11 ^3  = 11011    //      "3 gange så mange binære cifre"
100^3  =  1000000  //
111^3  =101010111

det bruger du ti at få et godt første gæt

(x+1)*(x+1)*(x+1)  =  x^3 +3x^2 +3x + 1

den formel bruger du til at 'justere tallet list' indtil det er korrekt.

mvh JakobA

Kan du ikke bare gøre sådan:

public class Main
{
    public static int qroot(int n)
    {
        double q_root = Math.pow(n, 0.3333333d);
        return (int)q_root;
    }
   
    public static void main(String[] args)
    {
        for(int i=1;i<=20;i++)
        {
            int temp = i * i * i;
            System.out.println("Kubikroden af " + temp + "\t" + qroot(temp));
        }
    }
}

Output:
Kubikroden af 1    1
Kubikroden af 8    1
Kubikroden af 27    2
Kubikroden af 64    3
Kubikroden af 125    4
Kubikroden af 216    5
Kubikroden af 343    6
Kubikroden af 512    7
Kubikroden af 729    8
Kubikroden af 1000    9
Kubikroden af 1331    10
Kubikroden af 1728    11
Kubikroden af 2197    12
Kubikroden af 2744    13
Kubikroden af 3375    14
Kubikroden af 4096    15
Kubikroden af 4913    16
Kubikroden af 5832    17
Kubikroden af 6859    18
Kubikroden af 8000    19

Sådan:
    public static int qroot(int n)
    {
        double q_root = Math.pow(n, 0.3333333d);
        return (int)Math.ceil(q_root);
    }

Øh.

Du mener:

    public static int qroot(int n) {
        double q_root = Math.pow(n, 1/3.0D);
        return (int) Math.floor(q_root);
    }

ikke ?

soreno > Metoden virker vist ikke helt korrekt. hvis n=28 retunerer den 4, men det mest korrekte er vel 3. Desuden skal jeg være sikker på at invarianten er overholdt: r^3 <= n < (r+1)^3

Nej.

Det giver følgende output:
Kubikroden af 1    1
Kubikroden af 8    2
Kubikroden af 27    3
Kubikroden af 64    3
Kubikroden af 125    5
Kubikroden af 216    6
Kubikroden af 343    6
Kubikroden af 512    7
Kubikroden af 729    8
Kubikroden af 1000    9
Kubikroden af 1331    10
Kubikroden af 1728    11
Kubikroden af 2197    12
Kubikroden af 2744    13
Kubikroden af 3375    14
Kubikroden af 4096    15
Kubikroden af 4913    16
Kubikroden af 5832    17
Kubikroden af 6859    18
Kubikroden af 8000    19

keet>

Erstat ceil med floor som jeg foreslår, så virker det !

hov, så ikke ovenstående det virker..

søren>

Ceil virker perfekt med alle n^3 værdier !

Problemet er alle værdier midt imellem !

Så test med den her i.s.f.:

    public static void main(String[] args) {
        for (int i = 1; i <= 30; i++) {
            int j = qroot(i);
            System.out.println((j*j*j) + " <= " + i + " < " + (j+1)*(j+1)*(j+1));
        }
    }

ahh, ja.

Nu forstår jeg.

arne_v > hvis n er 64 retunerer den 3... det er vel 4

kan det være opgaven angler efter en assert

    public static int qroot(int n) {
        double q_root = Math.pow(n, 1/3.0D);
        int 1_q_root = (int) Math.floor(q_root);
        assert  ( Math.pow(i_q_root,3) <= n  && n < Math.pow(i_q_root+1,3) );
        return i_q_root;
    }

mvh JakobA

Det har du ret.

God gammeldags FP unøjagtighed.

Måske:

    public static int qroot(int n) {
        double q_root = Math.pow(n, 1/3.0D);
        return (int) Math.floor(q_root + 0.000000001);
    }

når jeg bruger assert-sætningen er jeg så sikker på at invarianten er overholdt?

kan problemet egentlig løses med while?

Følgende ser faktisk ud til at virke:

    public static int qroot(int n) {
        int guess = n;
        do {
            int newguess = guess - (guess*guess*guess - n) / (3*guess*guess);
            guess = (newguess != guess) ? newguess : newguess - 1;
            if(guess <= 0) guess = 1;
        } while((n < guess*guess*guess) || (n >= (guess+1)*(guess+1)*(guess+1)));
        return guess;
    }

Jeg har dog kun checket 1..75

ok, tak for hjælpen alle... :) Vil I alle svare, for jeg har brugt alles ideer :)

svar

Jeg tør ikke garantere at din sidste vil terminere (holde op med at køre rundt i while løkken). Kunne den evt begynde at oscillere?

Måske. Men så kunne den forbedres lidt mere.

hvordan kunne den forbedres?

Så man sikrede sig mod at den gik i uendelig løkke.

er det en nem måde at gøre dette på?

Jeg brygger lige på noget.

Det skulle nok gøres med et matematisk bevis.

hvis du kalder
    int kubikrodAf0 = qroot( 0 );

går det galt 2 steder
    division med 0 i første linie i din while
og
    if (guess <= 0) guess = 1;
        // forhindrer at den kan komme til at overholde din invariant

public static int qroot(int n) {
        int guess = 1;
        do {
            int newguess = guess - ((guess*guess*guess - n) / (3*guess*guess));
            guess = (newguess != guess) ? newguess : newguess + (Math.random() > 0.5 ? 1 : -1);
            if(guess > 1290) guess = 1290;
            if(guess <= 0) guess = 1;
        } while((n < guess*guess*guess) || (n >= (guess+1)*(guess+1)*(guess+1)));
        return guess;
    }

monoton funktion

resulateter boxet 1..1029 hvilket er hvad der kan være i en positiv int

random element til at forhindre at den kører fast

den tror jeg på !

Nul og negative tal skal selvfølgelig lige håndteres, men det bør ikke
være noget problem.

Jeg har testet med 1 .. 1000000 uden at den hænger

den behøver ikke at håndtere negative tal...

Jeg tror jeg klarer mig nu :) Hvad betyder iøvrigt "D" i pow() metoden?

Det er bare for at angive double fremfor float.

Hej keet!

Jeg kan næsten forstå på dit spm at du går på datalogi i århus? Hvis det er tilfældet skal du ligge mærke til at du ikke må benytte math klassen, du skal bruge en løkke.

/Kim

hehe :) ja, dette er jeg klar over :)

Har du så fået den lavet eller skal du have lidt hjælp?
:)

Jeg har følgende metode:
public static int CubeRoot2(int n)
    {
        int r = n;
        do {
            int a = r - ( (r*r*r - n) / (3*r*r));
            r = (a != r) ? a : a + (Math.random() > 0.5 ? 1 : -1);
            if( r > 1290) r = 1290;
            if(r <= 0) r = 1;
        } while( (n < r*r*r) || (n >= (r+1)*(r+1)*(r+1)) );
        return r;
    }
While-løkken tager ikke højde n=0 men det kan selvfølgelig gøres med en IF og så retunerer 0, ellers ved jeg ikke lige hvordan jeg gør det. Hvad kan jeg erstatte Math-delen med?

og hvorfor er det at r skal være > 1290... Er den del nødvendig?

Hvis r er større end 1290 så vil r*r*r overflow en int og så går der
kuk i beregningen.

Hvis du skal forklare logikken, så er det en ganske almindelig
Newtons metode.

Kan jeg så ikke bare lave r til en Integer?

Integer kan ikke klare mere end int.

En long kunne klare mere.

Men hvofor skulle vi ?

Hvis r*r*r overflower en int, så ved vi jo at kubikroden af n er
mindre end r !

men du bør nok ændre udregninging i while betingelsen til at give resultater af type long, for at undgå at (r+1)*(r+1)*(r+1) giver overflow.

Det er nok fornuftigt hvis n kan gå op til Integer.MAX_VALUE

Er det ikke lidt riski at bruge math.random... det er vel ikke lige meget om der bliver lagt 1 til eller trukket 1 fra?

Nej - algoritmen bør konvergere og netop muligheden for både +1 og -1 bør
mindske muligheden for at den "hænger fast" et forkert sted.