mersenneforum.org Factorial modulo a prime
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

2011-08-23, 07:33   #45
axn

Jun 2003

136A16 Posts

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

 2011-08-23, 07:33 #46 Gammatester     Mar 2009 3810 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 = 11*31*149113, the result is zero after reaching 149113.
 2011-08-23, 08:05 #47 axn     Jun 2003 2×5×7×71 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, 08:23   #48
JohnFullspeed

May 2011
France

16110 Posts

Quote:
 Originally Posted by CRGreathouse 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

2011-08-23, 08:34   #49
JohnFullspeed

May 2011
France

101000012 Posts
Error

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

2011-08-23, 08:55   #50
Gammatester

Mar 2009

2×19 Posts

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?

 2011-08-23, 10:25 #51 JohnFullspeed   May 2011 France A116 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, 11:02   #52
axn

Jun 2003

136A16 Posts

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!

2011-08-23, 12:19   #53
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

838410 Posts

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.

 2011-08-23, 16:08 #54 JohnFullspeed   May 2011 France 7×23 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:=(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
2011-08-29, 14:32   #55
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

22×367 Posts

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.

 Thread Tools

 Similar Threads Thread Thread Starter Forum Replies Last Post rogue Lounge 8 2012-03-02 16:41 Raman Math 1 2010-02-16 21:25 T.Rex Math 7 2009-03-13 10:46 T.Rex Math 7 2007-06-04 21:30 T.Rex Math 9 2007-03-26 17:35

All times are UTC. The time now is 18:02.

Tue May 18 18:02:17 UTC 2021 up 40 days, 12:43, 0 users, load averages: 1.75, 2.00, 2.02

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.