[PHP] Modulo en Floats

[Koeniepoenie]

Heej hallo,

Ik ben met een stukje PHP aan de gang, en stuitte bij een berekening op een foutje.
Ik wilde namelijk 'enorme' getallen, die dus van type float zijn, een bepaalde modulo rekenen.
Om maar meteen met de deur in huis te vallen,
wil ik dit uitrekenen:

code:

x = a^b * c mod d

Maar a^b * c word een enorme float, bijv. 1.4196030194005E+37.
En als ik dan de modulo neem, krijg ik 0.
Na de search te hebben gebruikt, kwam ik op dit topic.
Maar die bied geloof ik geen verdere uitkomst..

Het lijkt me persoonlijk een beetje ranzig om het als een string te gaan behandelen, en zo die 37 eruit te filteren, en als 10^37 te schrijven oid. Tevens onnauwkeurig.

Ik heb ook al geprobeerd verschillende getallen te casten naar integer of naar float, om zo te gaan rekenen. Maar dit werkte niet.

Dus, weet iemand een oplossing, om toch de modulo te kunnen berkenen van zo'n float getal?

BVD

[.oisyn]

Een float heeft maar een precisie van 24 bits. Als je met restdelingen wilt werken zijn alle bits even belangrijk. Het is dus onmogelijk om modulo berekeningen te doen op een getal als dat getal niet in 24 bits past

Modulo op een niet geheel getal is sowieso een beetje zinnig, dus ik zou gewoon integral types gebruiken. Echter, een long, van 64 bits, is nog altijd niet genoeg om 10³⁷ te bevatten, dus je zult aan een één of andere huge number library moeten gebruiken.

.edit:
Oh, het lukt trouwens ook wel gewoon met ints, vooropgesteld dat de a, b, c en d in jouw berekening klein genoeg zijn

(x * y) % n = ((x % n) * (y % n)) % n
En laat er nou net een hele goede methode bestaan om x^y % n efficient uit te rekenen, even zoeken

ah hier: [rml].oisyn in "[ C++] klasse bigint met pow()"[/rml]

[ Voor 29% gewijzigd door .oisyn op 04-05-2004 20:41 ]

[.oisyn]

In php code:

PHP:

function modpow ($a, $m, $n)  // a^m % n
{
    $r = 1;
    $num = (int)(log (m) / log (2));
    for ($i = $num; $i >= 0; $i--)
    {
        $r = $r * $r % $n;
        if (($m & (1 << $i)) != 0)
            $r = ($r * $a) % $n;
    }
    return $r;
}


// ....
$x = (modpow ($a, $b, $d) * $c) % $d;

niet getest enzo

[ Voor 31% gewijzigd door .oisyn op 04-05-2004 20:48 ]

[Koeniepoenie]

Hmm ja,

code:

modpow (a,m,n)   // a^m % n
{
    res = 1;
    conta = int(2log(m)); // #bits - 1    
    for (i = conta; i >= 0; i--)
    {
        res = (res * res) % n; 
        if (bi = 1) res = (res * a) % n;
    }                
    return res;
}

Als ik dat omtover naar PHP,

PHP:

modpow ($a, $m, $n)   // a^m % n
{
    $res = 1;
    $conta = (int) 2log(m); // #bits - 1    
    for ($i = $conta; $i >= 0; $i--)
    {
        $res = ($res * $res) % $n; 
        if ($bi = 1) $res = ($res * $a) % $n;
    }                
    return $res;
}

Alleen weet ik geen vervangende functie voor 2log() in PHP?

En ik moet ook nog die vermenigvuldiging op een of andere manier ertussen proppen..

Maar iig bedankt

edit:
Je was me al voor

[ Voor 3% gewijzigd door Koeniepoenie op 04-05-2004 20:49 ]

[PrisonerOfPain]

fmod -> float modulo
log ($m, 2) -> 2log

[.oisyn]

PrisonerOfPain schreef op 04 mei 2004 @ 20:58:
fmod -> float modulo

[rml].oisyn in "[ PHP]Modulo en Floats"[/rml]
Heb je dus geen fluit aan

[ Voor 6% gewijzigd door .oisyn op 04-05-2004 21:01 ]

[Koeniepoenie]

* Koeniepoenie heeft teveel wiskunde gehad vandaag
Ik moest namelijk een kleine aanpassing maken in mn 'formule'
nu is hij namelijk zo:

code:

x = a * (b^c mod d) mod d
// of ookwel:
x = a * (b^c % d) % d

Ik probeerde het eerst alleen met fmod(), maar dat ging helaas niet.
Toen combineerde ik de functie van .oisyn en fmod()
En zowaar, het werkt..

code:

$x = fmod($a * modpow($b, $c, $d), $d)

Heren,

hartstikke bedankt

[.oisyn]

let wel dat modpow alleen op integers werkt he

[tech-no-logical]

KoenieMan schreef op 04 mei 2004 @ 20:32:

code:

x = a^b * c mod d

misschien overbodig, omdat er al een oplossing is, maar kan 't niet ook met de bcmath-extensie ?

code:

x = bcmod(bcmul(bcpow(a,b),c),d)

zoiets ? (de bcmath-extensie is tegenwoordig meegeleverd,, hoeft alleen geactiveerd te zijn).