Gitt en brøk a/b...

[sEirik]

...hvordan kan man finne ut, uten å utføre den faktiske divisjonen, om brøken vil kunne utvides til et desimaltall med endelig antall desimaler eller ikke?

F.eks., hvis man får a = 1 og b = 3, som tilsvarer [tex]1 \over 3[/tex], da kan ikke brøken utvides til et desimaltall, fordi man vil få uendelig antall desimaler. Men hvis man derimot får a = 2 og b = 5, kan brøken utvides til et desimaltall med endelig antall desimaler, nemlig 0,4.

Er det mulig å finne ut dette uten å utføre selve divisjonen?

[Solar Plexsus]

Svaret på spørsmålet er ja. Anta at du har en brøk a/b der 0 < a < b, og at denne brøken er maksimalt forkortet, dvs. at største felles divisor (SFD) til a og b er 1. Dersom det desimaltallet som denne brøken tilsvarer, har et endelig antall desimaler n, så finnes det et naturlig tall m < 10[sup]n[/sup] slik at

[tex](1) \;\; \frac{a}{b} \;=\; \frac{m}{10^n} \, .[/tex]

Ved å multiplisere (1) med 10[sup]n[/sup], får vi at

[tex](2) \;\; \frac{a \cdot 10^n}{b} \;=\; m.[/tex]

I.o.m. at m er et naturlig tall og SFD(a,b) = 1, følger det av (2) at b er en faktor i 10[sup]n[/sup]. M.a.o. er 2 og 5 de eneste primtall som kan være delelig med b.

På grunnlag av dette resonnementet kan vi stille opp følgende regel:

En brøk a/b som er maksimalt forkortet, kan skrives som et endelig desimaltall hvis og bare hvis nevneren kan skrives på formen b = 2[sup]p [/sup] 5[sup]q[/sup], der p og q er ikke-negative heltall.

[sEirik]

Takk! Så genialt!
En grei algoritme for å få til dette i et dataprogram er vel noe sånt som:

Kode: Velg alt

bool Expandable(int a, int b)
{
    if (!(a > 0 && a < b)) return false;

    // quotient q
    int q = b;
    while(q % 2 == 0)
        q = q / 2;
    while(q % 5 == 0)
        q = q / 5;

    return q == 1;
}

Skal innrømme at jeg prøver å lage et dataprogram som bl.a. kan regne med brøker, og da er egentlig funksjonen til det her å bestemme om det er "lurt" å utvide brøken til et desimaltall eller beholde den som den er. Og det er jo absolutt ikke lurt å utvide en brøk til et desimaltall hvis det har uendelig mange desimaler...
Dette var bare et kjapt forsøk på en algoritme som fungerer. Den deler nevner på 2 til den ikke kan deles på 2 mer, så deler den nevner på 5 til den ikke kan deles på 5 mer. Så sjekker den om det er igjen flere faktorer.
Det sier vel seg selv at det tar lang tid å dele på 2 og 5 mange ganger etter hverandre for store tall, og worst-case-scenariet kan jo gå ut på at nevner er på formen 2^n, da programmet vil dele på 2 ganske, ganske lenge. Kan det finnes en raskere metode som involverer logaritmer, kanskje?