Factorial modulo a prime - Page 5

axn · 2011-08-23, 07:33

Quote:

Originally Posted by CRGreathouse

*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

Gammatester · 2011-08-23, 07:33

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.

axn · 2011-08-23, 08:05

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.

JohnFullspeed · 2011-08-23, 08:23

Quote:

Originally Posted by CRGreathouse

I was asking for you to compute 10^7 primorial mod that number rather than 50847533, since 50847533 < 2³² but 2³² < 23832998845573 < 2⁶⁴.

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 · 2011-08-23, 08:34

Quote:

Originally Posted by Gammatester

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

Gammatester · 2011-08-23, 08:55

Quote:

Originally Posted by JohnFullspeed

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?

JohnFullspeed · 2011-08-23, 10:25

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

axn · 2011-08-23, 11:02

Quote:

Originally Posted by JohnFullspeed

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

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!

science_man_88 · 2011-08-23, 12:19

Quote:

Originally Posted by axn

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.

JohnFullspeed · 2011-08-23, 16:08

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

R. Gerbicz · 2011-08-29, 14:32

Quote:

Originally Posted by MrRepunit

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
$ \begin{tabular}{ l l l } p=1 (\text{mod} 3) & \text{normal} & \text{reduced} \\ 50000017 & 0m1.457s & 0m0.244s\\ 3037000453 & 1m33.972s & 0m15.199s\\ \end{tabular} $

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

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

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

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.

2011-08-23, 08:05	#47
axn Jun 2003 2·3²·269 Posts	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

2011-08-23, 10:25	#51
JohnFullspeed May 2011 France A1₁₆ Posts	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

2011-08-23, 16:08	#54
JohnFullspeed May 2011 France 10100001₂ Posts	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:=(G1Primes[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:=(G1Primes[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:=(G1Primes[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:=(G1Primes[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

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

2011-08-23, 07:33	#46
Gammatester Mar 2009 2·19 Posts	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 = 1131149113, the result is zero after reaching 149113.