20191129, 05:01  #12 
Jun 2003
19×271 Posts 
My adventures in understanding DWT
Using Pari/GP for prototyping:
The functions. Note, pari vectors start with index 1. Code:
weight(v,w,N)=vector( N, i, v[i]*w[i] ); \\ apply a weight w to signal v unweight(v,w,N)=vector( N, i, v[i]/w[i] ); \\ remove the weight w from signal v halve( v, N )=vector(N/2, i, v[i] + I*v[i+N/2]); \\ combine k and k+N/2 real elements into a single complex unhalve( v, N )=vector(N*2, i, if(i <= N, real(v[i]), imag(v[iN]))); \\ reverse the complex elements back into real elements forward(v,N)=vector( N, k, sum(n=1,N, v[n]*exp(I*2*Pi*(k1)*(n1)/N)) ); \\ simple O(N^2) DFT inverse(v,N)=vector( N, k, sum(n=1,N, v[n]*exp(+I*2*Pi*(k1)*(n1)/N))/N );\\ inverse DFT forward_weight(v,N,w)=forward( weight(v,w,N), N ); \\ DWT inverse_weight(v,N,w)=unweight( inverse(v, N), w, N ); \\ inverse DWT square(v,N)=vector( N, i, v[i]^2 ); \\ pointwise squaring Code:
N=8; v=[1592, 4744, 2670, 4702, 5898, 1185, 513, 1678]; \\ a random number 1038670476017199579990351480376 w=[1, 2^.375, 2^.75, 2^.125, 2^.5, 2^.875, 2^.25, 2^.625]; \\ irrational base weight for p=101, N=8 w2=vector(N, i, exp(I*Pi*(i1)/N)); \\ weight for negacyclic w3=vector(N, i, w[i]*w2[i]); \\ combined weight for IB + negacyclic Code:
u=forward_weight(v, N, w); u=square(u, N); u=inverse_weight(u, N, w); round(u) = [131715320, 65806708, 55646526, 107656084, 85866497, 86563572, 114850764, 78330688] \\ results Mod(131715320 + 65806708*2^13+ 55646526* 2^26+ 107656084*2^38+ 85866497*2^51+ 86563572*2^64+ 114850764*2^76+ 78330688*2^89, 2^1011) = Mod(320904239316807117549353868207, 2535301200456458802993406410751) Mod(1038670476017199579990351480376, 2^1011)^2 = Mod(320904239316807117549353868207, 2535301200456458802993406410751) Wagstaff mod 2^101+1 Code:
u=forward_weight(v, N, w3); u=square(u, N); u=inverse_weight(u, N, w3); round(u) = [126646392, 35596916, 6367106, 23618092, 69432719, 83120316, 103588028, 78330688] \\ results Mod(126646392 + 35596916*2^13 + 6367106* 2^26 + 23618092*2^38 + 69432719*2^51+ 83120316*2^64+ 103588028*2^76+ 78330688*2^89, 2^101+1) = Mod(2005153614013422538592239271122, 2535301200456458802993406410753) Mod(1038670476017199579990351480376, 2^101+1)^2 = Mod(2005153614013422538592239271122, 2535301200456458802993406410753) complex>complex rightangle convolution for wagstaff Code:
vw=weight(v, w, N); \\ apply irrational base weights h=halve(vw, N); \\ combine into complex u=forward_weight(h, N/2, w2); \\ DWT with negacyclic weights sq=square(u, N/2); u=inverse_weight(sq, N/2, w2); \\ inverse DWT uh=unhalve(u, N/2); \\ back to reals u=unweight(uh, w, N); \\ undo IB weights round(u) = [7430296, 9893668, 37926930, 23618092, 31874255, 36346212, 70633156, 78330688] Mod(7430296 + 9893668*2^13 + 37926930* 2^26 + 23618092*2^38 + 31874255*2^51+ 36346212*2^64+ 70633156*2^76+ 78330688*2^89, 2^101+1) = Mod(2049592028740143596208787739827, 2535301200456458802993406410753) Mod(1038670476017199579990351480376, 2^101+1)^2 = Mod(2005153614013422538592239271122, 2535301200456458802993406410753) 
20191201, 02:10  #13 
Sep 2002
Database er0rr
3^{3}·11·13 Posts 
In your "data" section you should have:
Code:
w2=vector(N, i, exp(I*Pi*(i1)/N)); \\ weight for negacyclic Last fiddled with by paulunderwood on 20191201 at 02:42 
20191201, 03:06  #14 
Jun 2003
19×271 Posts 
Crandall & Fagin (http://www.faginfamily.net/barry/Pap...Transforms.pdf) says that you can use either, and they explicitly use the minus version (eg: 5.3).
Indeed it works for the naive wagstaff version. Nonetheless, let me try the right angle convolution with the other one... Code:
? weight(v,w,N)=vector( N, i, v[i]*w[i] ); \\ apply a weight w to signal v ? unweight(v,w,N)=vector( N, i, v[i]/w[i] ); \\ remove the weight w from signal v ? halve( v, N )=vector(N/2, i, v[i] + I*v[i+N/2]); \\ combine k and k+N/2 real elements into a single complex ? unhalve( v, N )=vector(N*2, i, if(i <= N, real(v[i]), imag(v[iN]))); \\ reverse the complex elements back into real elements ? ? forward(v,N)=vector( N, k, sum(n=1,N, v[n]*exp(I*2*Pi*(k1)*(n1)/N)) ); \\ simple O(N^2) DFT ? inverse(v,N)=vector( N, k, sum(n=1,N, v[n]*exp(+I*2*Pi*(k1)*(n1)/N))/N );\\ inverse DFT ? forward_weight(v,N,w)=forward( weight(v,w,N), N ); \\ DWT ? inverse_weight(v,N,w)=unweight( inverse(v, N), w, N ); \\ inverse DWT ? ? square(v,N)=vector( N, i, v[i]^2 ); \\ pointwise squaring ? N=8; ? v=[1592, 4744, 2670, 4702, 5898, 1185, 513, 1678]; \\ a random number 1038670476017199579990351480376 ? w=[1, 2^.375, 2^.75, 2^.125, 2^.5, 2^.875, 2^.25, 2^.625]; \\ irrational base weight for p=101, N=8 ? w2=vector(N, i, exp(I*Pi*(i1)/N)); \\ weight for negacyclic ? w3=vector(N, i, w[i]*w2[i]); \\ combined weight for IB + negacyclic ? vw=weight(v, w, N); \\ apply irrational base weights ? h=halve(vw, N); \\ combine into complex ? u=forward_weight(h, N/2, w2); \\ DWT with negacyclic weights ? sq=square(u, N/2); ? u=inverse_weight(sq, N/2, w2); \\ inverse DWT ? uh=unhalve(u, N/2); \\ back to reals ? u=unweight(uh, w, N); \\ undo IB weights ? round(u) %22 = [126646392, 35596916, 6367106, 23618092, 69432719, 83120316, 103588028, 78330688] Now, to see if I can fork cudaLucas to make it do wagstaff. 
20191211, 01:55  #15 
Sep 2002
Database er0rr
3^{3}·11·13 Posts 
@George Woltman. How hard is to write a modulo for 2^p+1 as well as 2^p1? Is it something the average programmer can do with gpuowl.cl?

20191211, 04:47  #16  
P90 years forever!
Aug 2002
Yeehaw, FL
2^{4}×3^{2}×53 Posts 
Quote:
There is a learning curve playing gpuowl.cl. The rest of the code is C++ code with std library which I have not used over the last 2 decades. I do not know how to debug other than studying code and using printfs. Optimizations to working routines is much easier to code and debug than writing brand new code. 

20200105, 16:19  #17 
Jun 2003
19·271 Posts 
Here is cudaWagstaff v0.03 (adapted from cudalucas)
This is a cut down version with lot of the noncritical functionalities missing. For comparable FFT it is about 5% slower than CUDALucas (on my 1660Ti  YMMV). Assignment syntax is PRP=<exponent> or PRP=<exponent>,<fft> Implements GEC PRP. GEC failure / rollback logic is untested, but should work. Supports cufftbench functionality, but no threadbench. I have only built/tested in Linux; may or may not build/run under windows. Please give it a try. Let me know if you have any questions / issues / feedback. EDIT: Attachment updated with minor change Last fiddled with by axn on 20200105 at 16:29 
20200105, 18:12  #18  
Sep 2002
Database er0rr
3^{3}×11×13 Posts 
Quote:
Have you checked Ryan's two PRPs? If so how long did each take? How does that compared to a CPU? How does one select "fft"? Is there a coordinated search ongoing? If so, how does one get assignments? Last fiddled with by paulunderwood on 20200105 at 18:13 

20200105, 18:52  #19 
"Mr. Meeseeks"
Jan 2012
California, USA
3^{2}×241 Posts 
CUDA runs only on nvidia hardware, it would need to be ported to OpenCL.

20200105, 20:49  #20  
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest
1011010010100_{2} Posts 
No. CUDA is for NVIDIA. Radeon VII is AMD, OpenCL.
Quote:
Quote:
Quote:


20200106, 03:03  #21  
Jun 2003
19×271 Posts 
Quote:
fft is just the length. Once you run cufftbench option, the program will have benchmark for optimal fft selection (plus some heuristics for appropriate size ffts). But, if the fft length selected by program is somehow not optimal, you can override. Quote:
I am also currently TFing the 1415m range to 69 bits. This is first time territory (I think). If you're interested in first time tests, you can coordinate with GP2. 

20200110, 15:19  #22 
Jul 2003
1001100011_{2} Posts 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
gpuowl: runtime error  SELROC  GpuOwl  69  20210929 10:07 
Status of Wagstaff testing? and testing Mersenne primes for Wagstaffness  GP2  Wagstaff PRP Search  414  20201227 08:11 
gpuOwl Windows setup for Radeon VII  Prime95  GpuOwl  91  20191230 08:30 
gpuowl tuning  M344587487  GpuOwl  14  20181229 08:11 
How to interface gpuOwl with PrimeNet  preda  PrimeNet  2  20171007 21:32 