Optimierungspotential bei Primzahlsuche

[mrhappiness]

schaut's euch einfach mal an und sagt mir, was ihr besser machen würdet

danke

$numbers = array();

function bitmask($bit) {
  return -1 ^ (int)pow(2, $bit);
}

function add_number(&$target, $number) {
  $index = floor($number / 32);
  $number -= $index * 32;
  if (!isset($target[$index]))
    $target[$index] = 0;
  $target[$index] |= (int)pow(2, $number);
}

function make_array(&$target, $min, $max) {
  $full_entries = floor($max / 32);
  for ($i = 0; $i < $full_entries; $i++)
    $target[$i] = -1;
  for ($i = $full_entries * 32; $i <= $max; $i++)
    add_number($target, $i);
  $min = max($min, 2);
  for ($i = 0; $i < $min; $i++)
    remove_number($target, $i);
}

function remove_number(&$target, $number)  {
  $index = floor($number / 32);
  $number -= $index * 32;
  $target[$index] &= bitmask($number);
}

function find_prime(&$numbers, $step = 2) {
  if ($step > ceil(sqrt($_POST['max'])))
    return;
  for ($i = 2 * $step; $i <= $_POST['max']; $i += $step)
    remove_number($numbers, $i);
  find_prime($numbers, $step + 1);
}

function output_prime(&$numbers, $cols = 20) {
  $primes = array();
  for ($i = 0; $i < count($numbers); $i++)
    for ($j = 0; $j < 32; $j++)
      if ($numbers[$i] & (int)pow(2,$j))
        $primes[] = $i * 32 + $j;
  if (count($primes) == 0)
    return '<p>Keine</p> :-(';
  $primes = '<td>'.implode('</td><td>', $primes).'</td>';
  $cols = str_repeat('\<td\>\d+\</td\>', $cols);
  $primes = preg_replace('%('.$cols.')%', '<tr>$1</tr>', $primes);
  return '<table border="1">'.$primes.'</table>';
}

if (isset($_POST['min'])) {
  $_POST['min'] = max(0, (int)$_POST['min']);
  $_POST['max'] = max((int)$_POST['max'], $_POST['min']);
  if ($_POST['max'] > 1)
    make_array($numbers, $_POST['min'], $_POST['max']);
  find_prime($numbers);
  echo '<h1>Primzahlen im Bereich '.
    number_format($_POST['min'], 0, ',', '.').' - '.
    number_format($_POST['max'], 0, ',', '.').'</h1>'; 
  $_POST['cols'] = isset($_POST['cols']) ? max((int)$_POST['cols'], 20) : 20;
  echo output_prime($numbers, $_POST['cols']);
}

$_POST['min'] = isset($_POST['min']) ? (int)$_POST['min'] : 0;
$_POST['max'] = isset($_POST['max']) ? (int)$_POST['max'] : 64;
$_POST['cols'] = isset($_POST['cols']) ? max((int)$_POST['cols'], 20) : 20;

echo '<h1>Intervall für Suche nach Primzahlen</h1>
<form action="'.$_SERVER['PHP_SELF'].'"method="post">
Untergrenze: <input type="text" name="min" value="'.$_POST['min'].'" /><br />
Obergrenze: <input type="text" name="max" value="'.$_POST['max'].'"/><br />
Spaltenzahl: <input type="text" name="cols" value="'.$_POST['cols'].'"/><br />
<input type="submit" name="" value="Abschicken" />
</form>'; 

[derHund]

Re: Optimierungspotential bei Primzahlsuche

schaut's euch einfach mal an und sagt mir, was ihr besser machen würdet

so wies aussieht, benutzt du das sieb des eratosthenes?

imho wärs besser, wenn du in der funktion find_prime anstatt $step + 1 den wirklich nächsten punkt übergeben würdest.

ob es schneller geht, weiß ich nicht, zumindest kann ich dann auch den bereich zwischen 0 und 100.000 berechnen, wobei es mir mit deiner holzhammer-methode den apache wegbrutzelt ...

[mrhappiness]

Re: Re: Optimierungspotential bei Primzahlsuche

Original geschrieben von derHund
so wies aussieht, benutzt du das sieb des eratosthenes?

sagen wir mal so: ich bemühe mich *g*

imho wärs besser, wenn du in der funktion find_prime anstatt $step + 1 den wirklich nächsten punkt übergeben würdest.

imho auch, aber da brauche ich noch eine tolle idee, wie ich nach dem nächsten gesetzten bit suchen kann

ob es schneller geht, weiß ich nicht

mit sicherheit, weil ich dann nicht für z. B. 2^x (1 < x < sqrt($_POST['max'])) alles durchackere

zumindest kann ich dann auch den bereich zwischen 0 und 100.000 berechnen, wobei es mir mit deiner holzhammer-methode den apache wegbrutzelt ...

:-(

hab find_prime jetzt so:

function find_prime(&$numbers, $step = 2) {
  if ($step > ceil(sqrt($_POST['max'])))
    return;
  $index = floor($step / 32);
  $bit = $step - $index * 32;
  if ($numbers[$index] and (int)pow(2, $bit))
      for ($i = 2 * $step; $i <= $_POST['max']; $i += $step)
        remove_number($numbers, $i);
  find_prime($numbers, $step + 1);
} 

sonst fällt mir nur ein, das array durchzugehen und das erste gesetzte bit zu suchen, aber mit zwei verschachtelten for-schleifen in find_prime() und break 2, wenn ich was gefunden habe, klappts trotzdem nicht besser

[derHund]

Re: Re: Re: Optimierungspotential bei Primzahlsuche

sonst fällt mir nur ein, das array durchzugehen und das erste gesetzte bit zu suchen, aber mit zwei verschachtelten for-schleifen in find_prime() und break 2, wenn ich was gefunden habe, klappts trotzdem nicht besser

ungefähr so hab ich das auch gemacht ... abgesehen davon, daß du step erst ab der stelle suchen mußt, die größer step ist ...

die rechenzeit steigt zwar ins unendliche, aber wenigstens bleibt der apache am leben ...

ich werde noch mal schauen ...

dich stört sicher, daß es so lange dauert?

[mrhappiness]

Re: Re: Re: Re: Optimierungspotential bei Primzahlsuche

Original geschrieben von derHund
dich stört sicher, daß es so lange dauert?

nein, überhaupt nicht, ich habe alle zeit der welt

aber ich versuch mich mal an den schleifen

ist dir der apache abgeschmiert? ich hab nur nen timeout bekommen, weil ich max_execution_time überschritten hatte

[derHund]

Re: Re: Re: Re: Re: Optimierungspotential bei Primzahlsuche

nein, überhaupt nicht, ich habe alle zeit der welt

*g - viel schneller wirds imho nicht werden ...

ist dir der apache abgeschmiert? ich hab nur nen timeout bekommen, weil ich max_execution_time überschritten hatte

mit der 'finde den nächsten passenden step' kriege ich auch nur

Primzahlen im Bereich 0 - 1.000.000
Fatal error: Maximum execution time of 3000 seconds exceeded in

mit der step+1 methode erhalte ich

unknown software exception ...

ich werde auch mal ein wenig basteln, tunen und messen ...

[mrhappiness]

wenn ich max_execution_time abschalte, dauert's etwas, aber es funktioniert

hab jetzt mal den ganzen (int)pow... kram durch 1 << $bit ersetzt und die obergrenze (wurzel des maximums) einmal berechnet und nicht bei jedem rekursionsaufruf

und den nächsten wert für $step so berechnet

function find_prime(&$numbers, $step = 2) {
  if ($step > $_POST['max_sqrt'])
    return;
  for ($i = 2 * $step; $i <= $_POST['max']; $i += $step)
    remove_number($numbers, $i);
  $step++;
  $bin = decbin($numbers[floor($step / 32)]);
  $step = strpos($bin, '1', $step + 1);
  if ($step !== false)
      find_prime($numbers, $step - 1);
} 

aber mehr fällt mir jetzt beim besten willen nicht ein

[TBT]

wie schnell muß es denn sein?

<?php

$s = explode(' ', microtime());
$start = $s[1] + $s[0];

function remove( &$data, $zahl ) {
    reset( $data );
    foreach( $data as $key => $value ) {
        if( $value != $zahl && $value%$zahl == 0 ) {
            unset( $data[$key] );
        }
    }
}

$data = array();
for( $i=2; $i<10000; ++$i )
    $data[] = $i;

$max = ceil(count( $data )/2);
for( $i=2; $i<=$max; ++$i )
    if( isset( $data[$i]))
        remove( $data, $i );

echo implode(', ',$data)."<br><br>";

$e = explode(" ", microtime());
$ende = $e[1] + $e[0];

echo number_format(($ende-$start)*1000, 1, ',', '.').' ms';

?>

=> 5 sek für die Primzahlen bis 10.000

[asp2php]

OffTopic:

---

ich habe eine JAVA-Class, die die Primzahlen zwischen 1 bis 100 Mio. ausrechnet und in Array ablegt; dauert nur ca. 13-15 sek.

---

[mrhappiness]

@tbt

ich bin schneller: 0 - 10.000 in ca 1 Sekunde

übrigens: bei dir bekomme ich auch 9997, aber 9997 / 13 = 769 => keine primzahl

[penizillin]

TBT - naja, auf meinem rechner ca 15 s, bei 20.000 gibts schon n timeout.
ich denke, man darf das füllen des arrays $data ruhig außerhalb der gemessenen zeit geschehen lassen, schließlich ist die menge "gegeben". außerdem kann man das array von anfang an nur mit ungeraden zahlen füllen, die geraden sind ja allesamt nicht-primzahlen (gibts dafür ein wort?).

hab gerade auch die 91 gesehen - ist ja auch keine...

[mrhappiness]

Original geschrieben von penizillin
ich denke, man darf das füllen des arrays $data ruhig außerhalb der gemessenen zeit geschehen lassen, schließlich ist die menge "gegeben".

nicht unbedingt, ich messe bei mir ja auch die zeit zum füllen

außerdem kann man das array von anfang an nur mit ungeraden zahlen füllen

du kannst auch gleich alle vielfachen von 3 und 5 weglassen, aber das ist nicht der sinn des siebes...

wenn es aber was schnelleres gibt, dann immer her damit

[TBT]

Fehler mit deb "nicht"-Primzahlen behoben, und beschleunigt

$s = explode(' ', microtime());
$start = $s[1] + $s[0];

function remove( &$data, $zahl ) {
    foreach( $data as $key => $value )
        if( $value > $zahl && $value%$zahl == 0 )
            unset( $data[$key] );
}

$data = array();
$data[] = 2;
for( $i=3; $i<10000; $i+=2 )
    $data[] = $i;

$max = ceil(count( $data )/2);
for( $i=2; $i<=$max; ++$i )
    if( isset( $data[$i]) )
        remove( $data, $data[$i] );

$e = explode(" ", microtime());
$ende = $e[1] + $e[0];

echo implode(', ',$data)."<br><br>";
echo number_format(($ende-$start)*1000, 1, ',', '.').' ms'; 

2,4 Sek

[penizillin]

gehe ich recht in der annahme, dass bei linear steigender anzahl der zahlen N die benötigte zeit exponentiell wächst? dann wäre diese lösung dafür ungeeignet, in millionenbereiche zu gehen.

[derHund]

hmm,

kann mal jemand schnell nen script coden, welches bei wikipedia die primes ausliest und die mit dem errechneten ergebnis vergleicht? per hand (^^) ist das recht aufwendig.

ich brauche für

• 0 - 10.000: 0.063178062438965s
• 0 - 100.000: 1.4796030521393s
• 0 - 200.000: 11.224133968353s
• 0 - 500.000: 81.147593021393s

und das erscheint mir angesichts eure zahlen (außer denen von asp) doch recht ... fix. dabei ist der algo nicht mal optimiert ^^.

stichproben ergeben bisher immer korrektheit, aber ...