The Math Help Topic

[Matyuv]

My course is focusing on analysis mainly so far, yours seems more interesting... it's gonna change next year though (if I make it to the Higher Maths department of my faculty)

[DesLife]

Unfortunately, there's more analysis than algebra, we're done with algebra for this year, whis is really disappointing. However, I'm bothered by the fact that I might not do pure maths anymore next year in engineering school... I really want to go further into it though. I'll buy books if there's nothing else to do, but we'll see how this will go, it'll depend on which school I'm in I guess.

[Matyuv]

Yay! There are 50 847 534 prime numbers from 1 to billion.
Time taken: 8564.61s

[DesLife]

Fuck you, it's been 13500 seconds here already. xD
50 847 534... That's 5% ! That's really a lot.

[Matyuv]

Fuck you, it's been 13500 seconds here already. xD

Hahahahah, p0wned
And yeah that's a lot... I expected it to be like 2-3%.

Got any other orsum problems to do? Or should do some ProjectEuler? ;P

[DesLife]

Use the Gram-Schmidt process to create an orthonomal base of Rn[X] with the following dot product : <P,Q>=int(P*Q,t=0..1) ! It should keep you busy !

[Matyuv]

Sweet. I'll do it tomorrow probably, I have to try and concentrate on revising for my programming exam now... damn it.

[DesLife]

It's a shame there's only three of us on this forum that have taken advanced maths. It's so much fun.

[SanteriEdelweiss]

No more maths for me!

BTW... what's 1 / 1?

[DesLife]

Get the fuck out my maths thread.

[Tenderz]

Argh, I wish I already got some more advanced math at my school, the stuff I get is way too simple :S

[Haruka]

I think I forgot almost everything I gave in Math and the 2 years that I had Math B.

[DesLife]

Ah ! It took 69252.1s !
Now from 1 to gogolplex ?

[Matyuv]

Haha wow that's a lot of time...
On this page someone presents his C source code for the Sieve of Eratosthenes and claims to gets some ridiculously fast results (primes under 1 billion in 1.16sec on a 2GHz proc with 3GB RAM)

The code's not very readable though.

[DesLife]

Fuck, that's fast. But his code is not readable at all ahahah. But it's 69000 times faster than mine so that's worth it.

It seems that this is isprime()'s code :

Code: Select all

proc (n)
local btor, nr, p, r;
options remember, system,
‘Copyright 1993 by Waterloo Maple Software‘;
if not type(n,integer) then
if type(n,numeric) then
ERROR(‘argument must be an integer‘)
else
RETURN(’isprime(n)’)
;
if n
<
2 then
false
elif has(‘isprime/w‘,n) then
true
elif igcd(2305567963945518424753102147331756070,n)
<>
1 then
false
elif n
<
10201 then
true
elif igcd(84969694892334181105323399091873499659260625866489327366
1154542634220389327076939090906947730950913750978691711866802886149933382
5097682386722983737962963066757674131126736578936440788157186969893730633
1130664786204486249492573240226273954373636390387526081667586612559568346
3069722044751229884822222855006268378634251996022599630131594564447006472
0696621750477244528915927867113,n)
<>
1 then
false
elif n
<
1018081 then
true
else nr := igcd(408410100000,n-1);
nr := igcd(nr^ 5,n-1);
r := iquo(n-1,nr);
btor := modp(power(2,r),n);
if ‘isprime/cyclotest‘(n,btor,2,r) = false
or irem(nr,3) = 0 and ‘isprime/cyclotest‘(n,btor,3,r) = false
or irem(nr,5) = 0 and ‘isprime/cyclotest‘(n,btor,5,r) = false
or irem(nr,7) = 0 and ‘isprime/cyclotest‘(n,btor,7,r) = false then
RETURN(false)
;
for p from 3 while (numtheory[jacobi])(p^ 2-4,n)
<>
-1 do od;
evalb(‘isprime/TraceModQF‘(p,n+1,n) = [2, p])
fi
end

Enjoy.

[Tenderz]

Fuck, that's fast. But his code is not readable at all ahahah. But it's 69000 times faster than mine so that's worth it.

It seems that this is isprime()'s code :

Code: Select all

proc (n)
local btor, nr, p, r;
options remember, system,
‘Copyright 1993 by Waterloo Maple Software‘;
if not type(n,integer) then
if type(n,numeric) then
ERROR(‘argument must be an integer‘)
else
RETURN(’isprime(n)’)
;
if n
<
2 then
false
elif has(‘isprime/w‘,n) then
true
elif igcd(2305567963945518424753102147331756070,n)
<>
1 then
false
elif n
<
10201 then
true
elif igcd(84969694892334181105323399091873499659260625866489327366
1154542634220389327076939090906947730950913750978691711866802886149933382
5097682386722983737962963066757674131126736578936440788157186969893730633
1130664786204486249492573240226273954373636390387526081667586612559568346
3069722044751229884822222855006268378634251996022599630131594564447006472
0696621750477244528915927867113,n)
<>
1 then
false
elif n
<
1018081 then
true
else nr := igcd(408410100000,n-1);
nr := igcd(nr^ 5,n-1);
r := iquo(n-1,nr);
btor := modp(power(2,r),n);
if ‘isprime/cyclotest‘(n,btor,2,r) = false
or irem(nr,3) = 0 and ‘isprime/cyclotest‘(n,btor,3,r) = false
or irem(nr,5) = 0 and ‘isprime/cyclotest‘(n,btor,5,r) = false
or irem(nr,7) = 0 and ‘isprime/cyclotest‘(n,btor,7,r) = false then
RETURN(false)
;
for p from 3 while (numtheory[jacobi])(p^ 2-4,n)
<>
-1 do od;
evalb(‘isprime/TraceModQF‘(p,n+1,n) = [2, p])
fi
end

Enjoy.

Would look way better with tabs and beter use of new lines, now it's just unreadable

[PluMGMK]

Plum : soon.

Ah, but how soon is soon?

6 months.

That's not soon. You have disappointed me...


... and bad things happen to those who disappoint me.

[DesLife]

Bad things happen to those who threaten me. Like getting banned.

[Matyuv]

I coded another program for the same purpose yet again, but now it finished counting primes under 1 billion in 67.357 seconds ^^

Code: Select all

int main()
{
	double diff;
	clock_t start = clock();

	bool* IsPrime = new bool[SIZE];
	for (unsigned long i=0; i<SIZE; i++) IsPrime[i] = true;

	IsPrime[0] = false; IsPrime[1] = false; IsPrime[2] = true;

        //Sieve of Eratosthenes
	for (unsigned long i = 2; i < sqrt((double)SIZE); i++)
	{
		if (IsPrime[i]) 
		{
			unsigned long j = 2;
			while (i*j < SIZE)
			{
				IsPrime[i*j] = false;
				++j;
			}
		}
	}

	long count = 0;
	for (unsigned long i = 0; i < SIZE; i++)
		if(IsPrime[i]) ++count;
	diff = ( clock() - start ) / (double)CLOCKS_PER_SEC;

	cout << count << "\nTime taken: " << diff << " seconds.\n" << endl;

	delete[] IsPrime;
	return 0;
}

The idea is to create a boolean vector IsPrimei where the index corresponds to the number and the value is 1 for primes and 0 for non-primes.
edit: it uses up 1gb of memory though :/

[Tenderz]

>< I just tried various stuff in c++ to calculate prime numbers, and it worked good for detecting numbers between 2 and maybe 1000, I tried 1000000 (^^) and that didn't really go fast . and then I tried doing it in a different way, and then it allocated a shit load of memory and all my applications running and graphics driver crashed, but then my pc recovered in about 5 minutes throwing all kinds of error's in my face.

So I guess that doesn't work