## Other

drummers-lowrise

Message boards : Generalized Fermat Prime Search : Z-transform?

 Subscribe SortOldest firstNewest firstHighest rated posts first
Author Message
Christopher Siegert

Joined: 5 Jul 09
Posts: 233
ID: 42986
Credit: 121,873,589
RAC: 0

Message 77210 - Posted: 14 Jun 2014 | 0:53:44 UTC

"all new genefer using a faster 'Z-transform'"

So what's the deal with this new Z-transform?

Is this new math or just a new programming algorithm?

What are the ramifications of this new Z-transform? Will it have an effect on the search for GFPs of higher N/B values? How much faster is it?

My curiosity is raging...

rroonnaalldd
Volunteer developer
Volunteer tester

Joined: 3 Jul 09
Posts: 1213
ID: 42893
Credit: 34,634,263
RAC: 0

Message 77217 - Posted: 14 Jun 2014 | 2:26:15 UTC - in response to Message 77210.

Please have a look in the thread Minimum CUDA requirement for GFN. Iain explained the "z-transform".
____________
Best wishes. Knowledge is power. by jjwhalen

Yves Gallot
Volunteer developer
Project scientist

Joined: 19 Aug 12
Posts: 843
ID: 164101
Credit: 306,521,622
RAC: 5,385

Message 77229 - Posted: 14 Jun 2014 | 10:23:47 UTC - in response to Message 77210.

I called this new algorithm the "z-Transform" because of Georg Bruun paper:
z-Transform DFT Filters and FFT's, IEEE Trans. ASSP, ASSP-26, No. 1, February 1978.
http://orbit.dtu.dk/fedora/objects/orbit:20643/datastreams/file_4658740/content

If you have a look at Figure 4, you see that we can use half a FFT to "filter" with the z-transfer function z^-N/2 - 1. Because (z^-N - 1) / (z^-N/2 - 1) = z^-N/2 + 1, we compute modulo a GF polynomial.

That is faster than the DWT that was used in the previous versions of genefer:
http://www.ams.org/journals/mcom/1994-62-205/S0025-5718-1994-1185244-1/S0025-5718-1994-1185244-1.pdf
http://www.ams.org/journals/mcom/2002-71-238/S0025-5718-01-01350-3/S0025-5718-01-01350-3.pdf

This is not really "new math" but it is a new algorithm.

Note that the chapter VI of Bruun's paper is known as Bruun's FFT
http://en.wikipedia.org/wiki/Bruun's_FFT_algorithm
It is twice as fast as the complex z-Transform (for real data) but rouding error increases quickly with FFT size. Because of this inaccurate numerical precision, it cannot be used with 64-bit floating point type for GF test.

Yves

Yves Gallot
Volunteer developer
Project scientist

Joined: 19 Aug 12
Posts: 843
ID: 164101
Credit: 306,521,622
RAC: 5,385

Message 77230 - Posted: 14 Jun 2014 | 11:19:22 UTC - in response to Message 77210.

Will it have an effect on the search for GFPs of higher N/B values? How much faster is it?

The rouding error is smaller then higher B can be tested.

How mush faster? It depends on hardware and on the number of instances:
10%-30% faster on GPU, 10%-60% faster on CPU.
The algorithm was completely rewritten on CPU with a different data ordering.
It was tuned on Ivy Bridge and Haswell processors and then is very fast on them.
On GPU, the "structure" is identical but the number of operations is smaller.

On Mike's Core i5-4670K, he measured:
N=20
3.2.0, AVX, 1 core: 8.77 ms
3.2.0, AVX, 4 cores: 14.6 ms.
3.2.1, FMA, 1 core: 5.27 ms
3.2.1, FMA, 4 cores: 6.46 ms

Yves

Message boards : Generalized Fermat Prime Search : Z-transform?