[php] Razbijanje giantskih števil na prafaktorja

Živjo, delam program za razbijanje zmnoška dveh izjemno velikih praštevil.
Na primer vhodni podatek je:
7228174241881

Izhodni podatek:
181081
39916801


Do nekega števila moja skripta deluje, potem pa dobil čuden izhodni podatek:
2
9.5601057529824E+15

ta eksponent na koncu mi zmede aplikacijo. Kako bi skripto še bolj optimiziral ?

<?php
$n = 19120211505964799;


$a = 2;
while ($a < $n)
{
	if(bcmod($n,$a)==0)
	{
		break;
	}
	$a++;
}

$p = $a;
$q = $n / $a;

echo $p.'<br>'.$q;

Namesto, da praštevila sam generiraš, jih morda lahko sparsaš iz kakšne strani, npr. Big Primes

Najenostavnejša optimizacija pa bi bila, da $a namesto za 1 povečuješ za 2 kot je omenjeno zgoraj.

Bolj kot hitrost je problem ta eksponent. To je tako kot pri kalkulatorju ko hočeš nekemu velikemu številu odšteti majhno število, sploh nemoreš ker ti zaokoži.

Namesto, da inkrementiraš praštevilske kandidate za 2, lahko stvar še malenkost bolj optimiziraš. Enostavno se da namreč dokazati, da za vsa praštevila večja od 3 velja: p=6*k+1 ali 6*k-1 (seveda ne velja obratno), ali drugače, kandidate izmenično povečuješ za 2 in 4. Sicer pa praštevilski razcep velja za računsko zahtevnega, na čemer konec koncev tudi temelji kriptografija. Celo kripto knjižnice pri res velikih številih samo ocenijo, če je dovolj velika verjetnost, da gre za praštevilo.

Sicer pa preveri, koliko bitna so cela števila pri PHP (po mojem 32 ali 64, kaj lahko je tudi odvisno od OS in HW arhitekture). Ko presežeš to območje, ti najverjetneje stvar pretvori v float z vsemi posledicami omejene natančnosti. Ena rešitev je, da napišeš razred (npr. BigInt) in v njem hraniš velika števila kot polja celih števil. Ali pa greš na jezik, kjer int pravzaprav nima omejitev (z izjemo razpoložljivega pomnilnika), npr. Python.

$q = $n / $a;

Tudi tu moraš uporabit bc* funkcije, npr:

$q = bcdiv($n, $a);

Koda ti bo potem delala, seveda pa si poglej še vse, kar so napisali ostali.

Evo, sedaj mi deluje, a sedaj je problem, ker se mi prej izteče 30 sekund: Fatal error: Maximum execution time of 30 seconds exceeded in C:\wamp\www\BigInteger.php on line 1354

Kako ta čas prestavim dalj. npr. 10 min ali več...oz rabim boljše generiranje praštevil

skripta:

<?php
include('BigInteger.php');

//stevilo za zlomit
$n = new Math_BigInteger ('19120211505964799');

//začetek zanke na praštevilo 3
$a = new Math_bigInteger('3');

//prvo praštevilo 2
$prvoPrastevilo = new Math_bigInteger('2');

//ker so praštevila liha (razen 2) prištevamo 2
$pristej = new Math_bigInteger('2');

//pogledamo ali je prvo praštevilo 2 
list($quotient,$remainder) = $n->divide($prvoPrastevilo);

if($remainder == '0') //če je deljivo z dva
{
	$N1 = $prvoPrastevilo; //deljitel je N1
}
else //če ni deljivo z dva
{
	while( $a < $n) //začnemo zanko 
	{
		list($quotient,$remainder) = $n->divide($a); //začnemo z 3

		if($remainder=='0') //ko dobimo deljitelja
		{
			$N1 = $a; //deljitelja damo v $N1
			break;
			
		}
	
		$a = $a->add($pristej); //če ni ga povečamo za 2

	}
}

if(!(isset($N1)))
{
	echo $n->toString().' je prastevilo';
}
else
{
	list($N2,$remainder) = $n->divide($N1);
	echo 'Stevilo: '.$n->toString().'<br>Prastevili:<br>'.$N1.'<br>'.$N2;
}


?>

Še ena opazka :)

Dejansko rabiš furat zanko le do sqrt(n): namreč če imaš netrivialnega delitelja, je vsaj en manjši oz. enak sqrt(n).

V primeru, da veš, da imaš praštevilo (tj, AKS test ali kaj drugega) je itak vseeno do kam daš zanko, ker boš itak našel nekaj preden prideš do korena.

(še link) AKS primality test @ Wikipedia

SQRTja sploh ne računaš ampak ga inkrementiraš in kvadriraš in tako dobivaš mejo, do kam ti velja, predno ga moraš spet inkrementirat in skvadrirat.
Če se že gremo naivno implementacijo :)

Verjetnost da znajo pada od leve proti desni tako kot si jih naštel :)
Sicer pa to sam preveriš v par minutah.

Ni tle standarda, so le enostavnejše in bol zahtevne optimizacije. Eni stvar terajo dlje,drugi odnehajo prej.

No, če je število vedno sestavljeno, potem res ne rabiš ustavitvenega pogoja, tako kot si napisal.

Za faktorizacijo drugače obstajajo boljši algoritmi.

darkkk je 2. apr 2013 ob 20:48 izjavil:

O loop unwrapping optimizaciji c++ se je govorilo že 10 let nazaj ampak ...

Ampak? GCC in Intelovi compilerji za C/C++ vem da to podpirajo že lep čas(-03 switch), za ostale pa nevem.

50!+1 v trenutku ?
You kidding me ?

Pa saj je napisal, da je 149 najmanjši prafaktor števila 50! + 1.

Nekdo je hotel bit preveč pameten.

technolog je 3. apr 2013 ob 09:49 izjavil:

Pa saj je napisal, da je 149 najmanjši prafaktor števila 50! + 1.

Nekdo je hotel bit preveč pameten.

In naslednje številke ?

Sprašujem prvotno op-a, ne tebe.
S čim si to počel (sw, hw) ?

Kateri distro imaš ? Meni v MS VPC in distro damn small linux 4.4 faktorira samo do 19 mestne številke, potem javi da številka ni "valid positive integer".