[php] getal -> teller en noemer herleiden

[Verwijderd]

Stel :

Ik heb getal : $x = 0.6666666667

Ik heb me suf zitten piekeren:
Hoe krijg ik de teller en noemer weer terug?

$x_teller = 2;
$x_noemer = 3;

Dus dat bovenstaande resultaten eruit komen?

Maar dit moet ook werken bij bijvoorbeeld: $x = 0.94

$x_teller = 47;
$x_noemer = 50;

Wie denkt mee?
(morgen ben ik pas weer online, dus ik ben benieuwd of jullie er al iets mee willen / kuennen)

[Verwijderd]

Verwijderd schreef op 09 oktober 2002 @ 17:17:
Stel :

Ik heb getal : $x = 0.6666666667

Ik heb me suf zitten piekeren:
Hoe krijg ik de teller en noemer weer terug?

$x_teller = 2;
$x_noemer = 3;

Dus dat bovenstaande resultaten eruit komen?

Maar dit moet ook werken bij bijvoorbeeld: $x = 0.94

$x_teller = 47;
$x_noemer = 50;

Wie denkt mee?
(morgen ben ik pas weer online, dus ik ben benieuwd of jullie er al iets mee willen / kuennen)

Ik stel voor om je $x steeds te vermenigvuldigen met een geheel getal (beginnende bij 2) en door te gaan tot er een ander geheelgetallig getal uitkomt

[Dash2in1]

Hmm lastig, sla ze op als je deelt, of probeer iets als volgt (wat je afrondt/als significant beschouwd mag je zelf uitvogelen):
begin op het gehele getal + 1/2 .. is het getal wat je zoekt groter, hoog de noemer van de breuk op, is het getal kleiner, hoog de teller van de breuk op. Vereenvoudig daarna.
Dus in dit geval:
0 + 1/2 -> hoger
0 + 2/2 -> lager
0 + 2/3 -> bingo
Je zou ook Q kunnen aftellen:

code:

----------------------------
| 1/2 2/3 3/4 
| 1/3 2/4
| 1/4
| etc

(1/2 -> 1/3 -> 2/3 -> 1/4 -> 2/4 -> 3/4)

Misschien dat er een makkelijkere manier is.

[edit]
lol, en net als ik klaar ben met tiepen komt IggY2 met iets veel makkelijkers

[Verwijderd]

Tja misschien is dit wel een beetje omslachtig, maar misschien zou je 'm kunnen laten beginnen met een noemer = 2, dan alle mogelijke tellers laten proberen (1 in dit geval, 2 levert een heel op), is de uitkomst fout, doe noemer + 1, en laat dit zo lang itereren totdat je het correcte antwoord hebt gevonden.

Dit is dus een brute force 'uitprobeer'-maniertje, er schiet me even niets netters te binnen.

[Verwijderd]

Heb ook nog ff zitten denken:

$x = 0.66666667

$x_teller = 1-$x;
$x_noemer = 1 + aantal decimalen; (8 decimalen -> $x_noemer = 100000000);

En dan de gemene deler zoeken

$x_teller = $x_teller / gemene deler;
$x_noemer = $x_noemer / gemene deler;

Of iets dergelijks .......

[_Squatt_]

2/3 wordt wat lastig, omdat 0.666666667 != 2/3. Maar voor je andere voorbeeld:

0.94 = 94/100

Dan pak je de grootste gemene deler van 94 en 100, dat is 2, en zo krijg je 47/50.

_{inmiddels wat meer replies..}

[jhksema]

Zoek 's op functie rat/rats in matlab documentatie.
http://www.mathworks.com/...help/techdoc/matlab.shtml

[Verwijderd]

Die gebroken grote / eindeloze getallen zijn ook het probleem

[SuperRembo]

Daar heb ik ooit eens college over gehad. Er bestaan mooie algoritmes om bij een reeel getal de beste benadering te vinden met |teller|, |noemer| < bepaalde waarde. Ik zal eens kijken of ik 't dictaat nog ergens kan vinden.

[Bosmonster]

eerst honderdsten (procenten) van maken en hierbij naar beneden afronden (floor()).

0.6666666 wordt dan 66/100
0.3333333 wordt ook 33/100

en dat herleiden tot zo klein mogelijke breuk?

Dus in recursieve functie kijken of beiden deelbaar zijn door 2, 3, 4, etc t/m de eigen waarde (eerst helen eruit halen uiteraard).. En als die deelbaar is weer terug beginnen bij 2.

Lijkt me wel te doen in een paar regels.

[SuperRembo]

Bij mathworks staat het uitgelegd. Eigenlijk best simpel (alleen bewijzen dat het de beste benaderingen zijn is lastiger).

Voorbeeld met pi:

1
x1 = 3.14159265
d1 = int(x1) = 3
f1 = frac(x1) = 0.14159265
1e benadering
a1 = 3
afwijking 1e benadering
e1 = a1-x = -0.14159265

2
x2 = 1/f1 = 7.06251330
d2 = fint(x2) = 7
f2 = frac(x2) = 0.06251330
a2 = 3+1/7 = 3.14285714
e2 = a2-x = 0.00126448

3
x3 = 1/f2 = 15.99659440
d3 = fint(x3) = 15
f3 = frac(x3) = 0.99659440
a3 = 3+1/(7+1/15) = 3.14150943
e3 = a3-x = 0.00008321

etc.

[stekkel]

Onmogelijk om dat te doen met 2/3.
0.666666 ... 666 is slechts een benadering van 2/3.

[Dash2in1]

Daarom werk je ook met significantie, je kapt op een bepaalde nauwkeurigheid af ..

[SuperRembo]

JavaScript:

// Rational fraction approximation

function RatFrac(x, tol) 
{
    var tol0 = 1e-10;
    var maxIt = 50;  
    
    var xi=x;
    var d=[];
    var n,ni,t;
    var i,j;
    
    if (typeof(tol)=='undefined')
    {
        tol = tol0;
    }
    
    for (i=0; i<maxIt; i++)
    {
        d[i] = Math.round(xi);
        xi = 1/(xi-d[i]);
        
        t = d[i];
        n = 1;
        for (j=i-1; j>=0; j--)
        {   
            ni = n;
            n = t;
            t = ni+t*d[j];
        }
        if (n<0) 
        {
            n = -n;
            t = -t;
        }

        if ((Math.abs(t/n-x)<tol)) 
        {
            break;
        }
    }
    return [n,t];
}        

x = Math.PI;
f = RatFrac(x,1e-10);
n = f[0];
t = f[1]; 

Werkt ok zolang je geen rare dingen invoert (zoals 0)

x = 3.141592653589793 ~ 355/113 = 3.1415929203539825 (2.667641894049666e-7)

x = 2.718281828459045 ~ 1457/536 = 2.718283582089552 (0.17536305070287028e-5)

x = 0.6666666666666666 ~ 2/3 = 0.6666666666666666 (0)

x = 0.66666667 ~ 2/3 = 0.6666666666666666 (-3.333333387089965e-9)

[Verwijderd]

mmmm, damned ... dan moet dat dus omgezet worden in PHP ... das balen

[stekkel]

Verwijderd schreef op 14 oktober 2002 @ 10:24:
mmmm, damned ... dan moet dat dus omgezet worden in PHP ... das balen

lijkt me een eitje

[Verwijderd]

Nou, ik probeer het te vertalen en had gedacht dat het zo had moeten lukken, maar de output klopt voor geen meter! Ik krijg 1 en 0 terug.
Als ik bovendien de @ in regel 12 verwijder krijg ik warnings voor het delen door 0;

PHP:

function RatFrac($x, $tol=false){
   $tol0  = 1e-10;
   $maxIt = 50;
   $xi    = $x;
   $d[]   = array();

   if(!$tol) $tol = $tol0;

    for ($i=0; $i<$maxIt; $i++){
    
        $d[$i] = round($xi,0);
        $xi    = @(1 / ($xi-$d[$i]));
        
        $t = $d[$i];
        $n = 1;
        
        for ($j=i-1; $j>=0; $j--){   
            $ni = $n;
            $n = $t;
            $t = $ni+$t*$d[$j];
        }
        
        if($n<0){
           $n = -$n;
           $t = -$t;
        }

        if ((abs($t/$n-$x)<$tol)) break;
    }
    
    $result[0] = $n;
    $result[1] = $t;
    return $result;   
}

$f = RatFrac(0.125,1e-10);

# Hier zou 8 en 1 uit moeten komen
print_r($f);

Iemand enig idee?

[ACM]

Dan zal die round wel niet helemaal lekker gaan he?
En/of xi == round(xi) dus.

[Verwijderd]

volgens mij klopt er in de php-versie geen hout van.
Wat ik ook voor round($xi) invul, de functie geeft als 2e item in de array altijd $xi terug!

Lijkt wel of er niets mee gebeurt of zo

[Verwijderd]

Ik heb het idee dat het probleem hem zit in regel 28:
if ((abs($t/$n-$x)<$tol)) break;

Dit voert ie HELEMAAL niet uit !
Volgens mij snapt PHP dat 1E-10 helemaal niet of wel?
HELP !

[Verwijderd]

Misschien weet iemand anders hoe het wel moet of kent iemand een ander script dat teller en noemer zo goed mogelijk bij benadering teruggeeft?!

[thomaske]

je kan je bericht ook editten hoor..

regel 5 ga je de fout in, je mag zelf zoeken wat je fout doet!

[Verwijderd]

STOM STOM STOM !!!!! nu doet ie het perfectooooo !!! Bedankt

[Verwijderd]

Toch vreemd,
als ik $x = 0.012605; gebruik dan zou de uitkomst : 2/328 moeten zijn
Maar hij geeft: 1259 / 99881
Hoe kan dat dan weer ?!

[Soultaker]

Verwijderd schreef op 14 oktober 2002 @ 14:14:
Toch vreemd,
als ik $x = 0.012605; gebruik dan zou de uitkomst : 2/328 moeten zijn
Maar hij geeft: 1259 / 99881
Hoe kan dat dan weer ?!

1259 / 99881 = 0,01260499994994042911064166357966
2 / 238 = 0,0060975609756097560975609756097561

Het lijkt me dat 1259 / 99881 heel wat dichter in de buurt komt. Als je afgerond hebt op 6 decimalen, zou je toch tenminste 0,00610 moeten invoeren. Dat scheelt nogal.