[php] rekenen met grote priemgetallen

[RSD]

Als ik met grote priemgetallen wil rekenen, dan gaat php op een gegevens moment ze omzetten naar floats. Dit wil ik niet, nu weet ik wel dat het mogelijk is om die getallen in arrays te zetten en er dan mee te rekenen, maar hoe doe ik dat? Heb al gezocht op google en op de php site, op deze site staat wel iets over array's etc.. maar dat is mij niet helemaal duidelijk, bestaan er geen classes die al met grote getallen rekenen.. dus alleen +,*,- en / . Heb overal gezocht, maar nix gevonden helaas. In principe is delen niet nodig. Wie kan mij helpen of heeft er tips, hoe dit op te lossen.

[ACM]

Je zou naar de bcmath extentie kunnen kijken, als het goed is kan je dan (pagina's vullend) lange getallen gebruiken

Anders zul je even moeten denken wat er gebeurt bij een optelling etc. Echt moeilijk is het niet. (wat gebeurt er met de overflow als je 10 + 99 optelt en dat is je maximum lengte? Precies, dan krijg je 1 en 9 als getallen in je array )

[kvdveer]

Hmmm. Dit is niet bepaald het soort zaken waar PHP voor bedoeld is. Ik vrees dat je zelf een bigint-class zult moeten schrijven...

code:

class bigint {
  var $storage;
  function bigint() {
    $storage = array();
    $storage[0] = 0;
  }

  function multiply($by) {
    $result = new $bigint;
    // doe berekening
    return $bigint;
  }
  
}

[kvdveer]

ACM schreef op 27 september 2002 @ 11:15:
Anders zul je even moeten denken wat er gebeurt bij een optelling etc. Echt moeilijk is het niet. (wat gebeurt er met de overflow als je 10 + 99 optelt en dat is je maximum lengte? Precies, dan krijg je 1 en 9 als getallen in je array )

Pardon? getallen van 0 tot 9 in een array? Ik neem aan dat je dan toch wel met een BASE 2^15 gaat werken... BASE 10 lijkt me enigsinds inefficient.

[Zoijar]

Optellen enzo valt wel mee, maar je zal toch ook efficient modulo machten willen berekenen, iets wat volgens mij niet geheel triviaal is. Maar ik kan me vergissen... BCMath lijkt me dus het beste

edit:
of mcrypt hehe

[kvdveer]

PHP:

// ik neem aan dat lsB vooraanstaat (Least significant Bytes)
// per integer sla ik even 14 bits op. Dit kan efficienter.
define("BASE",1<<15);

function addBigNumber($array1, $array2) {
   
   $result = array();
   $result[0] = 0;
   $overflow = 0;                         

   $maxlength = max(count($array1),count($array2)) + 1;                        

   for($i=0; $i<$maxlength; $i++) {
      if(isset($array1[$i]))$val1 = $array1[$i]; 
      else                  $val1 = 0;
      
      if(isset($array2[$i]))$val2 = $array2[$i]; 
      else                  $val2 = 0;
      
      $temp =  ($val1 + $val2 + $overflow)
      $result[$i] = $temp % BASE;
      if($temp >= BASE) $overflow=1;
      else              $overflow=0;
   }
   
   $return $result;
}

[ACM]

kvdveer schreef op 27 september 2002 @ 11:18:
Pardon? getallen van 0 tot 9 in een array? Ik neem aan dat je dan toch wel met een BASE 2^15 gaat werken... BASE 10 lijkt me enigsinds inefficient.

Je denkt toch serieus niet dat ik een voorbeeld ga tikken met 2^15-getallen
Voor het voorbeeld boeit de lengte of de base werkelijk helemaal niets, dezelfde rekenregels zijn van toepassing...

Trouwens, BASE 2^15 is nogal ERG groot als getal-basis... Over het algemeen werken we met decimale getallen en ondanks dat die misschien 100 cijfers kunnen bevatten blijft dat base 10

[Zoijar]

Kan best hoor, gewoon 2 bytes als base. In java bv is dat precies je char grootte. In een array heb je voor elk plekje 8 bitjes ter beschikking, dan ga je er daar toch niet maar 4 van gebruiken? Waste van 50% van je geheugen. Waarschijnlijk is 2^31 nog beter, iha fijner voor je memory bus enzo die haalt toch 32bits op, of je er nou 16 of 8 of 32 vraagt.

[ACM]

* ACM mist even waar het om gaat

Magoed, zullen we er voor het gemak dan maar vanuit gaan dat de delen ofwel uit hele integers ofwel uit hele longs zullen gaan bestaan?
Boeit verder niet namelijk, de rekenregels die gelden voor 10+99 zijn hetzelfde als die voor 12124132423543253534543 + 32431543523534 of whatever

[Zoijar]

Ik dacht dat je het decimale getal 1234 zo wilde opslaan:

0000 0001 | 0000 0010 | 0000 0011 | 0000 0100

ipv van zo:
0000 0100 | 1101 0010

Anyway, ik lees net dat BCMath standaard is. Dat is dus we het makkelijkste.
http://uk.php.net/manual/en/ref.bc.php

[kvdveer]

--edit--
Ik had niet alle reacties gelezen...

[ACM]

In php is het niet standaard _aan_ Wel standaard aanwezig om te kunnen compileren.

[RSD]

Heeft niemand een class die het simpel uitrekenen van grote getallen doet.... want ik kan geen extra modules compileren... dus heb zelf zo'n class nodig, hij hoeft maar 4 dingetjes te doen, ik kan het niet vinden en zelf maken lukt me ook niet denk ik... het lukt wel, maar het wordt dan een zooitje.. omdat ik niet de juiste algorithmes heb... op informatica opleiding krijg je ook zoiets, dat weet ik.

[Verwijderd]

RSD schreef op 29 september 2002 @ 11:26:
Heeft niemand een class die het simpel uitrekenen van grote getallen doet.... want ik kan geen extra modules compileren... dus heb zelf zo'n class nodig, hij hoeft maar 4 dingetjes te doen, ik kan het niet vinden en zelf maken lukt me ook niet denk ik... het lukt wel, maar het wordt dan een zooitje.. omdat ik niet de juiste algorithmes heb... op informatica opleiding krijg je ook zoiets, dat weet ik.

Misschien heb je hier wat aan, het gaat over een C# implementatie maar dat moet op zich goed in PHP te doen zijn.

[kvdveer]

Even een traktatie:

PHP:

define("BASE",1<<15);

class bignum {
   var $value; // array, LSB first. Bigendian dus...
   
   function bignum() {
      $value = array();
   }
   
   function add($num) {
      $result = array();
      $result[0] = 0;
      $overflow = 0;                         
      
      $maxlength = max(count($this->value),count($num)) + 1;                        
   
      for($i=0; $i<$maxlength; $i++) {
         if(isset($this->value[$i]))$val1 = $this->value[$i]; 
         else                  $val1 = 0;
         
         if(isset($num[$i]))$val2 = $num[$i]; 
         else                  $val2 = 0;
         
         $temp =  ($val1 + $val2 + $overflow)
         $result[$i] = $temp % BASE;
         if($temp >= BASE) $overflow=1;
         else              $overflow=0;
      }
      
      // even trimmen.
      if($result[count($result)-1] == 0) 
         unset($result[count($result)-1]);
      
      //alles netjes in een object verpakken.
      $return = new bignum();
      $return->value = $result;
         
      return $return;
   }

   function subtract($num) {
      $com = compareTo($num);
      if($com ==0) {
         //getallen zijn gelijk  
         return new bignum();
      }

      if($com == 1) {
         die "Result would be negative...";
      }
      
      $result = array();
      $result[0] = 0;
      $underflow = 0;                         
      
      $maxlength = max(count($this->value),count($num)) + 1;                        
   
      for($i=0; $i<$maxlength; $i++) {
         if(isset($this->value[$i]))$val1 = $this->value[$i]; 
         else $val1 = 0;
         
         if(isset($num[$i]))$val2 = $num[$i]; 
         else $val2 = 0;
         
         if($val1 - $underflow < $val2) {
            $underflow = 1;
            // deze construnctie is nodig om overflow te voorkomen.
            $temp = $val2 - $val1 + $underflow;
            $temp = BASE - $temp;
         } else {
            $underflow = 0;
            $temp = $val1 - $val2;  
         }
         $result[$i] = $temp;
      }
      
      // even netjes trimmen.
      $i = count($result);
      while(--$i >= 0) {
         if($result[$i] == 0) unset($result[$i]);
         else $i=0;
      }
      //alles netjes in een object verpakken.
      $return = new bignum();
      $return->value = $result;
         
      return $return;
      
   }
   
   
   // return 1 als $num groter is
   // return -1 als $num kleiner is
   // return 0 als $num gelijk is
   function compareTo($num) {
      if(count($this->value) == count($num->value)) {
         // als de getallen uit ongeveer hetzelde aantal bytes bestaan
         for($i=count($this->value) - 1; $i >= 0; $i--) {
            if($this->value[$i] == $num->value[$i]) continue;
            
            if($this->value[$i] > $num->value[$i]) return 1;
            return -1;
         }
         // alle getallen zijn gelijk...
         return 0;
      }
      // hier komen we alleen als de getallen niet even lang zijn.
      // Het langste getal wint :-)
      
      if(count($this->value) > count($num->value)) 
         return 1;
      return -1;
   }
}

100% untested, ondersteunt geen negatieve of gebroken getallen.
Vermenigvuldigen schrijf ik vanavond of vanmiddag nog, als ik weer zin heb.
Delen weet ik niet hoe dat moet, Modulus overweeg ik nog.

edit:

indenting wat opgeschoond. Dit forum snapt de werking van tab niet helemaal....

[ Voor 0% gewijzigd door kvdveer op 29-09-2002 12:35 . Reden: ubb ]

[RSD]

Heel erg bedankt, maar waarom define je die BASE??? Waa is dat eigenlijk voor? Dat eerste script snap ik nog hoe dat werkt, maar die laatste class?? het ziet er veelbelovend uit, maar hoe gaat het in zijn werk, want bij ADD hoef je geen 2 array's in te geven, maar bij die eerste wel

[ACM]

Om de getallen in stukken te hakken natuurlijk
Elk getal groter dan 2^15 wordt in tweeen gehakt zodat ie wel past

[RSD]

Maaruhm, hoe werkt deze class, dat eerste stukje code begrijp iknog, daar moet je 2 array's invoeren in die class hierboven niet...

[Apollo_Futurae]

kvdveer schreef op 29 september 2002 @ 12:33:
Delen weet ik niet hoe dat moet

een algoritme om twee zeer grote getallen door elkaar te delen staat in TAOCP (ik geloof deel 2, weet ik niet zeker).
als je wilt kan ik het voor je overtikken; beter is natuurlijk om meteen maar alle drie de delen te kopen