mersenneforum.org  

Go Back   mersenneforum.org > Math Stuff > Computer Science & Computational Number Theory

Reply
 
Thread Tools
Old 2011-08-23, 07:33   #45
axn
 
axn's Avatar
 
Jun 2003

12F216 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
*Bad* mistype, I meant 0.45 seconds = 450 ms.
FWIW, he's calculating 10^8# since
Code:
? default(primelimit, 10^8)
? primepi(10^8)
%1 = 5761455
? primepi(10^7)
%2 = 664579
axn is online now   Reply With Quote
Old 2011-08-23, 07:33   #46
Gammatester
 
Gammatester's Avatar
 
Mar 2009

2·19 Posts
Default

Any time for the original problem of JohnFullspeed for 10000000# mod 50847533 that is greater than say 1 ms, shows that used implementation is bad: Since 50847533 = 11*31*149113, the result is zero after reaching 149113.
Gammatester is offline   Reply With Quote
Old 2011-08-23, 08:05   #47
axn
 
axn's Avatar
 
Jun 2003

113628 Posts
Default

Some actual data:

Code:
  for i:=1 to 5761455 do
    m := (m * prime[i]) mod r;
takes 219 ms. "m" is a QWord.


Code:
  for i:=1 to 5761455 do
  begin
    x := prime[i];
    asm
    	movl m, %eax
    	mull x
    	divl r
    	movl %edx, m
    end;
  end;
takes 156 ms. "m" is a DWord.

All timings on a 2 GHz core2 in 32-bit mode. With little bit more optimization (mainly, keeping the variables in register, LOL), we can come closer to the theoretical prediction.

Last fiddled with by axn on 2011-08-23 at 08:11
axn is online now   Reply With Quote
Old 2011-08-23, 08:23   #48
JohnFullspeed
 
May 2011
France

7·23 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
I was asking for you to compute 10^7 primorial mod that number rather than 50847533, since 50847533 < 232 but 232 < 23832998845573 < 264.
you are rigth with the size of mod but

If your value is smaller that the size of the register then the processor is ALWAYS the speeder

Wit actual the lib are used when the ize is more 64 bits
before the difference is a hardware difference:

I change S to := 45089156699671; and I need LESS time!!!
The processor is speeder doing a mod 64 thant a 32. In fact it's normal
more the medulo is big more it's speed: it's trivial else change your lib...

inn fact I remove mod ,after th mul and and emppty bS BCL

The times are
Full version : 200 600=1 second
Remove mod : 182
Remove mul : 172
empty : 150

Mod and Div are well neer 1 cycle

The problem arrives after 64 bits you fave to write a mul,a div,a root
with numbers in a vector You have big diferennnces but the user believe that a mod 1000 digits is slover than a 2 digits and that is normal to wait day

John
JohnFullspeed is offline   Reply With Quote
Old 2011-08-23, 08:34   #49
JohnFullspeed
 
May 2011
France

7·23 Posts
Default Error

Quote:
Originally Posted by Gammatester View Post
Any time for the original problem of JohnFullspeed for 10000000# mod 50847533 that is greater than say 1 ms, shows that used implementation is bad: Since 50847533 = 11*31*149113, the result is zero after reaching 149113.
Exact but it was a sample you juust have to test the value =1 and begin a new cycle you are in modlar arithmetique (no infini)
implementation is not bad: it needs 'reglages'

John
JohnFullspeed is offline   Reply With Quote
Old 2011-08-23, 08:55   #50
Gammatester
 
Gammatester's Avatar
 
Mar 2009

2·19 Posts
Default

Quote:
Originally Posted by JohnFullspeed View Post
I change S to := 45089156699671; and I need LESS time!!!
...
Mod and Div are well neer 1 cycle
Perhaps your processor is clever and does an optimization you obviously refuse! Why do you choose this S? The largest factor is 11969 (much smaller than your first), and thus it is no surprise that the time goes down. Most of the time you calculate 0*p mod S = 0!

Please repeat your test with S=45089156699693!

Are there any references that multiply with 0 and dividing a zero is optimized on recent processors?
Gammatester is offline   Reply With Quote
Old 2011-08-23, 10:25   #51
JohnFullspeed
 
May 2011
France

7·23 Posts
Default S?

S was a copy and paste...
I change s with your value : same time

In the actual processor a divide by zero always make a crash and for the mul is the same:
mul by 0 or mul by 1234568 need the same time : no specific code

John

The dif beetwen CISC and RISC are somtimes funy



if you use factoring by divwe try to remove div to a dd
the code is speeder

But if you make it on a CVisc the result is slover
The same optimization make the inverse!

John
JohnFullspeed is offline   Reply With Quote
Old 2011-08-23, 11:02   #52
axn
 
axn's Avatar
 
Jun 2003

2×52×97 Posts
Default

Quote:
Originally Posted by JohnFullspeed View Post
The processor is speeder doing a mod 64 thant a 32. In fact it's normal
more the medulo is big more it's speed: it's trivial else change your lib...
Do you know anything at all about algorithmic complexity?

Quote:
Originally Posted by JohnFullspeed View Post
The times are
Full version : 200 600=1 second
Remove mod : 182
Remove mul : 172
empty : 150
What are the details of the processor -- type, clock speed, cache size -- that you're using? I am trying to figure out which brain dead processor takes 150ms to execute a 500,000 iteration empty loop!
axn is online now   Reply With Quote
Old 2011-08-23, 12:19   #53
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts
Default

Quote:
Originally Posted by axn View Post
Do you know anything at all about algorithmic complexity?


What are the details of the processor -- type, clock speed, cache size -- that you're using? I am trying to figure out which brain dead processor takes 150ms to execute a 500,000 iteration empty loop!
in pari mine take 94 ms in one test.
science_man_88 is offline   Reply With Quote
Old 2011-08-23, 16:08   #54
JohnFullspeed
 
May 2011
France

2418 Posts
Default processor

I cjhange my core 2for a G5
I ndide you havre a power 4 : two ptocdrsoo G5or at 1,7 giga heertz
3 giga DDR SDRAM

Version du système : Mac OS X 10.4.11 (8S165)
Version Kernel : Darwin 8.11.0
Volume de démarrage : Mac
Nom de l’ordinateur : Power Mac G5 de PM G5
Nom de l’utilisateur : PM G5 (pmg5)

I use the nehendertal FREE PASCAAL ffor MIPS,ARM800 and asmall constructor (IIBM , uou knox)
You seems to be meticulos
Beffore to laungth give the real time noit tha trhrotiy

I give the code for a CIDC
So givve the time to
[CODE]
a1 := GetTickCount;
S:= 45089156699671;
G1:= 1 ;
i1:=1;
Repeat
G1:=(G1*Primes[i1]) mod s;
i1:= I1+1;
until i1=5761456;
a1 := GetTickCount-a1;

Not difficult for you juste the ptimorial 10^7 (You prefere 2^32)

AFter if it's possible for you change the mod by a mul
a1 := GetTickCount;
S:= 45089156699671;
G1:= 1 ;
i1:=1;
Repeat
G1:=(G1*Primes[i1]) 0* s; perhaps to big for you
i1:= I1+1;
until i1=5761456;
a1 := GetTickCount-a1;

and last change for a ADD
a1 := GetTickCount;
S:= 45089156699671;
G1:= 1 ;
i1:=1;
Repeat
G1:=(G1*Primes[i1]) + s;
i1:= I1+1;
until i1=5761456;
a1 := GetTickCount-a1;

ande if ou have a scientifique spirir try empèye repeat


a1 := GetTickCount;
S:= 45089156699671;
G1:= 1 ;
i1:=1;
Repeat
G1:=(G1*Primes[i1]) + s;
i1:= I1+1;
until i1=5761456;
a1 := GetTickCount-a1;
If you don't understand the repeat do a for (you have it?)

It's strange I giove the time but I never have yoour
Of courde I bneleive yoou I don't restartmy core 2 to verify your time

0.128 0182 .0130 0.024 second And you


Core 2.4 Gisa 4 GO of ram Wndows,Linux FreeePascal or C

But the time is not mine it' the time of the processor

I work 10 years on CISC and now I search the speeder...
I baughth my Mac in JUNE: 250 euros
JohnFullspeed is offline   Reply With Quote
Old 2011-08-29, 14:32   #55
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

1,429 Posts
Default

Quote:
Originally Posted by MrRepunit View Post

Wilson-fast

p = range(50000000,50010000) (534 primes)
init: 2m38.122s
total: 11m48.556s
average time per prime without initialization: 1,03s
max memory usage: ~600MB

WilsonPrimeSearch
<br />
\begin{tabular}{ l l l }<br />
p=1 (\text{mod} 3) & \text{normal} & \text{reduced} \\<br />
50000017 & 0m1.457s & 0m0.244s\\<br />
3037000453 & 1m33.972s & 0m15.199s\\<br />
\end{tabular}<br />

<br />
\begin{tabular}{ l l l }<br />
p=5 (mod 12) & \text{normal} & \text{reduced} \\<br />
50000021& 0m1.462s &0m0.363s\\<br />
3037000493 &1m34.500s& 0m22.950s\\<br />
\end{tabular}<br />

<br />
\begin{tabular}{ l l l }<br />
p=11(mod 12) & \text{normal} & \text{reduced} \\<br />
50000063 &0m1.459s& 0m0.731s\\<br />
3037000427& 1m33.408s& 0m46.422s\\<br />
\end{tabular}<br />

normal means the normal factorial calculation, reduced is the scheme from the paper.

For comparison here are the timings of the Ibercivis program:
p = 50000017
0m4.553s (compiled from makefile)
0m2.526s (compiled with -O3)
Quote:
Originally Posted by rogue View Post
With the algorithm I mentioned, you can evaluate 3000000000 mod p in about 1 second and undoubtedly one could get it a bit faster than that. Yes, that is 3e9.
I have some really new ideas in my latest code, with it I can test all primes for the Wilson problem up to 5*10^7 in 671 seconds. I will release my code in about 4 days. Now I am at 4billions and I will reach 10billions in less than 4 days, not much chances for a Wilson prime (and indeed so far I have not found a new one).
So interestingly with a single computer it was possible to beat a boinc project, their goal was to test all primes up to 4billions, and as I can see they are at ~2.3billions.
R. Gerbicz is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
World Record Factorial Prime Found rogue Lounge 8 2012-03-02 16:41
square root modulo prime Raman Math 1 2010-02-16 21:25
Order of 3 modulo a Mersenne prime T.Rex Math 7 2009-03-13 10:46
Period of Lucas Sequence modulo a prime T.Rex Math 7 2007-06-04 21:30
Conjecture about multiplicative order of 3 modulo a Mersenne prime T.Rex Math 9 2007-03-26 17:35

All times are UTC. The time now is 16:12.

Thu Jan 28 16:12:30 UTC 2021 up 56 days, 12:23, 1 user, load averages: 4.36, 4.42, 4.55

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.