
View Poll Results: What about This app you like it?  
Yes  4  36.36%  
No  3  27.27%  
Regular  1  9.09%  
Very bad  3  27.27%  
Voters: 11. You may not vote on this poll 

Thread Tools 
20190104, 02:41  #34 
Jun 2003
2^{6}×73 Posts 
How difficult will it be to compile MLucas for android ?
I would love to see the performance of an actual stateoftheart code running on one of these. 
20190104, 06:53  #35 
Romulan Interpreter
Jun 2011
Thailand
2^{2}×17×127 Posts 
@OP: can you give us some info about the multiplication algorithm used? Is it school grade, is it karatsuba? FFT?
As per firejuggler's suggestion, we tried to run this toy in an android emulator  our kingdom is Cortex M, but we have some android emus laying around, as we have colleagues who develop applications with them, for our customers. We wanted to see how the tests scale in time  if the application is bogus, like reading exponents from a list and saying prime/composite, and doing other things meantime, then the timescaling would be also odd. We have some idea and could guess the multiplication algorithm used, if any tuning was done or it is just blind schoolgrade highlevel stuff. And we consider this to be a good test, because it would not be easy for the guy to fake the process (which involves exponentiations and multiplications related not only to the size of the exponents, but also to the number of bits which are 1 involved). And our toys can also debug/disassemble code. But unluckily, we can not run it. Our emulator does not like it, and our colleagues who could help didn't come back from their NY holidays yet... Our advice for now: avoid it. P.S. Carlos, you seem to be the only one liking it? Can you detail why? Or was that a voting mistake? Last fiddled with by LaurV on 20190104 at 06:58 
20190104, 07:11  #36 
"Carlos Pinho"
Oct 2011
Milton Keynes, UK
2^{2}×3^{3}×43 Posts 
Being Portuguese I’m being supportive with our Spanish brother but also I’m affected by flu since new year on my leave. Call me crazy: am I tired of fights with Spanish or is flu damaging my brain?!??? Or both?!

20190104, 07:22  #37 
Romulan Interpreter
Jun 2011
Thailand
21BC_{16} Posts 
Ok, that makes sense! (being supportive).

20190104, 09:29  #38 
Sep 2003
2579_{10} Posts 
Here is a Mersenne prime test. I didn't write it. It uses the GMP library.
It prints a 64bit hexadecimal residue: "0" for a Mersenne prime, nonzero otherwise. I compiled on Linux and ran on a single Skylake core on AWS. For 86243 it takes 11 seconds; for 216091 it takes 1 minute 38.5 seconds. And yet this is much slower than mprime/Prime95. Code:
/* Adapted from http://rosettacode.org/wiki/LucasLehmer_test#GMP */ #include <stdio.h> #include <stdlib.h> #include <gmp.h> void lucas_lehmer(unsigned long p, mpz_t *V) { mpz_t mp, t; unsigned long k; mpz_init_set_ui(t, p); mpz_init(mp); mpz_setbit(mp, p); mpz_sub_ui(mp, mp, 1); mpz_init_set_ui(*V, 4); for (k = 3; k <= p; k++) { mpz_mul(*V, *V, *V); mpz_sub_ui(*V, *V, 2); /* mpz_mod(*V, *V, mp) but more efficiently done given mod 2^p1 */ if (mpz_sgn(*V) < 0) mpz_add(*V, *V, mp); /* while (n > mp) { n = (n >> p) + (n & mp) } if (n==mp) n=0 */ /* but in this case we can have at most one loop plus a carry */ mpz_tdiv_r_2exp(t, *V, p); mpz_tdiv_q_2exp(*V, *V, p); mpz_add(*V, *V, t); while (mpz_cmp(*V, mp) >= 0) mpz_sub(*V, *V, mp); } mpz_clear(t); mpz_clear(mp); /* Residue is returned in V */ } int main(int argc, char* argv[]) { mpz_t m64, V; /* We want to print a 64bit residue */ mpz_init(m64); mpz_setbit(m64, 64); mpz_sub_ui(m64, m64, 1); unsigned long p; if (argc >= 2) { p = strtoul(argv[1], 0, 10); } else { fprintf(stderr, "Provide one argument, a Mersenne exponent, for instance: 11213\n"); return 1; } lucas_lehmer(p, &V); mpz_and(V, V, m64); mpz_out_str(stdout, 16, V); fprintf(stdout, "\n"); mpz_clear(m64); mpz_clear(V); return 0; } Last fiddled with by GP2 on 20190104 at 09:38 
20190104, 09:48  #39 
Romulan Interpreter
Jun 2011
Thailand
2^{2}·17·127 Posts 

20190104, 15:53  #40  
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
2^{7}×71 Posts 
Quote:
Quote:


20190104, 16:28  #41 
Jun 2003
2^{6}×73 Posts 
3 min 7 sec / 11 sec = 17x
23min 7 sec / 1 min 38.5 sec = 14x OP's code has better scaling than GMPbased one ! 
20190104, 17:25  #42 
Sep 2016
7×47 Posts 

20190104, 17:34  #43 
"Forget I exist"
Jul 2009
Dumbassville
8384_{10} Posts 

20190104, 19:21  #44 
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest
2^{3}·3^{2}·59 Posts 
Fixed overhead can give lower order empirical timing scaling from low p measurements and make an implementation look like it's using a better algorithm than it is. In other words, the order bends upward to higher power of p at higher exponent, as setup overhead gets diluted by longer runtimes for higher exponent. This can be seen in runtime scaling measurements and plots I made for cllucas, CUDALucas and gpuowl. The more setup overhead, the lower the apparent order at low p. OpenCL's compile on the fly guaranteed around 2 seconds of setup overhead at each fft length. CUDALucas scaling: https://www.mersenneforum.org/showpo...3&postcount=2; gpuowl V5 scaling: https://www.mersenneforum.org/showpo...&postcount=10; prime95 scaling: https://www.mersenneforum.org/showpo...78&postcount=2 The periteration time scaling of gpulucas, cllucas, CUDALucas, and gpuowl v1.9 are compared at https://www.mersenneforum.org/showpo...76&postcount=8
I'd expect grammarschool multiplication based primality testing to scale as ~p^{3}. With sufficient overhead, it may scale as p^{2.43} at the low end, as in my ancient inefficient primitive algorithm code from the late 80s and early 90s does at low p. (There, inefficient TF is part of the run time, as is printout of every iteration's res64 and very frequent state saves for resumption as insurance against the vagaries of MSDOS and no UPS.) Thorken's timings indicate scaling of p^{2.42}, very close to that. It could be grammar school, or something better. 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Fastest software for Mersenne primality test?  JonathanM  Information & Answers  25  20200616 02:47 
Another way to PRP test Mersenne numbers  paulunderwood  Miscellaneous Math  18  20170126 20:33 
Conjectured Primality Test for Specific Class of Mersenne Numbers  primus  Miscellaneous Math  1  20141012 09:25 
New test for Mersenne prime  allasc  Math  33  20110520 22:48 
another mersenne prime test  jocelynl  Math  8  20061020 19:36 