mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Operazione Doppi Mersennes

Reply
 
Thread Tools
Old 2012-10-08, 06:52   #100
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

CB516 Posts
Default

Code:
LL: 43112609 (FFT 2240K)
PRP=2,2,43112610,-3 (FFT 2560K)
PRP=3,2,43112610,-5 (FFT 2688K)
PRP=4,2,43112610,-7 (FFT 2688K)
PRP=5,2,43112610,-9 (FFT 2880K)
PRP=6,2,43112610,-11 (FFT 2880K)
PRP=7,2,43112610,-13 (FFT 3000K)
PRP=8,2,43112610,-15 (FFT 2800K)
PRP=9,2,43112610,-17 (FFT 3200K)
PRP=10,2,43112610,-19 (FFT 3000K)
PRP=20,2,43112610,-39 (FFT 3360K)
PRP=30,2,43112610,-59 (FFT 3840K)
PRP=40,2,43112610,-79 (FFT 3584K)
PRP=50,2,43112610,-99 (FFT 4000K)
PRP=60,2,43112610,-119 (FFT 4000K)
PRP=70,2,43112610,-139 (FFT 4480K)
PRP=80,2,43112610,-159 (FFT 3840K)
PRP=90,2,43112610,-179 (FFT 4480K)
PRP=100,2,43112610,-199 (FFT 4480K)
PRP=110,2,43112610,-219 (FFT 4608K)
PRP=120,2,43112610,-239 (FFT 4480K)
PRP=130,2,43112610,-259 (FFT 4608K)
PRP=140,2,43112610,-279 (FFT 4608K)
PRP=150,2,43112610,-299 (FFT 4608K)
PRP=160,2,43112610,-319 (FFT 4000K)
PRP=170,2,43112610,-339 (FFT 4608K)
PRP=180,2,43112610,-359 (FFT 4608K)
PRP=190,2,43112610,-379 (FFT 4608K)
PRP=200,2,43112610,-399 (FFT 4608K)
ATH is offline   Reply With Quote
Old 2012-10-08, 08:43   #101
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

483810 Posts
Default

MM47 sieved up to 1T (except for 185).

Luigi
ET_ is offline   Reply With Quote
Old 2012-10-08, 18:33   #102
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

23×3×487 Posts
Default

Quote:
Originally Posted by ET_ View Post
MM47 sieved up to 1T (except for 185).

Luigi
No new factors found, then? My 10T run of k=185 finished last week, sans factor.
ewmayer is online now   Reply With Quote
Old 2012-10-08, 18:56   #103
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

12E616 Posts
Default

Quote:
Originally Posted by ewmayer View Post
No new factors found, then? My 10T run of k=185 finished last week, sans factor.
I don't remember which factors were known, so I will report all factors found for the exponent 43112609.

The columns read as follows:

id, exponent_id, k, sieve_level, factor.

Luigi
Attached Thumbnails
Click image for larger version

Name:	list.jpg
Views:	114
Size:	45.8 KB
ID:	8719  

Last fiddled with by ET_ on 2012-10-08 at 18:57
ET_ is offline   Reply With Quote
Old 2012-10-09, 01:37   #104
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

101101101010002 Posts
Default

Quote:
Originally Posted by Prime95 View Post
Number of big words is (n + log2 k)%N bits. Every FFT word has an integral number of bits except the most significant FFT word. This doesn't cause an increase in the FFT size, but during carry propagation FFT words must be multiplied by k before rounding. This gives us log2 k bit fewer bits of precision in the output. Also, wrapping the carry to the least significant FFT word is tricky but do-able.

The +/- c values causes us to use weights between 1 and log2 (abs (c)). This costs us precision on the FFT input words.

Zero-padding is not required. Really small k values often end up using the same FFT size as Mersenne LL tests.
OK, let's try a small example. Say I want to do multiplication with respect to the modulus m = k.2^n - 1. Specifically, let`s try k - 185 and n = 89, using transform length N = 4.

The wordsizes are as for DWT modulo 2^p-1, but with p replaced by (n + log2 k) = 89 + 7.53... = 96.53...

This translates to 24 bits per word for words 0-2, and with the high word (word 3) having as many as 24.53... bits?

And what are the 4 weight factors for this case? (For p = 96 and n = 4, the straight Mersenne-mod DWT weights are all unity).
ewmayer is online now   Reply With Quote
Old 2012-10-09, 02:17   #105
Prime95
P90 years forever!
 
Prime95's Avatar
 
Aug 2002
Yeehaw, FL

171368 Posts
Default

Quote:
Originally Posted by ewmayer View Post
This translates to 24 bits per word for words 0-2, and with the high word (word 3) having as many as 24.53... bits?
Yes, the top FFT word has 24.53 bits.

Quote:
And what are the 4 weight factors for this case? (For p = 96 and n = 4, the straight Mersenne-mod DWT weights are all unity).
Comments from the code:

// The FFT weight for the j-th FFT word doing a b^n+c weighted transform is
// b ^ (ceil (j*n/FFTLEN) - j*n/FFTLEN) * abs(c) ^ j/FFTLEN

In your case b = 2, n = 96.53...., c = -1, FFTLEN=4.
Prime95 is online now   Reply With Quote
Old 2012-10-09, 02:22   #106
Prime95
P90 years forever!
 
Prime95's Avatar
 
Aug 2002
Yeehaw, FL

2·132·23 Posts
Default

Quote:
Originally Posted by Prime95 View Post
Yes, the top FFT word has 24.53 bits.
Correction. FFT word 0 has 25 bits. FFT words 1,2 have 24 bits. FFT word 3 has 23.53... bits.

From the code:

// The FFT base for the j-th FFT word doing a b^n+c weighted transform is
// ceil (j*n/FFTLEN)

To calc whether the i-th word is a big word (25 bits):

/* Compute the number of b in this word. It is a big word if */
/* the number of b is more than NUM_B_PER_SMALL_WORD. */

base = gwfft_base (gwdata->dd_data, i);
next_base = gwfft_base (gwdata->dd_data, i+1);
return ((next_base - base) > gwdata->NUM_B_PER_SMALL_WORD);
Prime95 is online now   Reply With Quote
Old 2012-10-09, 19:47   #107
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

23·3·487 Posts
Default

Quote:
Originally Posted by Prime95 View Post
Comments from the code:

// The FFT weight for the j-th FFT word doing a b^n+c weighted transform is
// b ^ (ceil (j*n/FFTLEN) - j*n/FFTLEN) * abs(c) ^ j/FFTLEN

In your case b = 2, n = 96.53...., c = -1, FFTLEN=4.
Following your recipe, this is what I get for the weights (replacing FFTLEN with N for notational compactness):
Code:
j	ceil[n.j/N]	n.j/N		w_j
-	-----------	--------	--------------
0	0		0		2^0 = 1
1	25		24.13...	1.82406...
2	49		48.26... 	1.66360...
3	73		72.39...	1.51725...
I also note that if keep computing even past this, I get e.g. w_4 = 1.38378..., implying that these generalized weights do not cycle at j=4 like the classic mersenne-mod DWT weights. Correct?
ewmayer is online now   Reply With Quote
Old 2012-10-09, 22:01   #108
Prime95
P90 years forever!
 
Prime95's Avatar
 
Aug 2002
Yeehaw, FL

2·132·23 Posts
Default

Quote:
Originally Posted by ewmayer View Post
implying that these generalized weights do not cycle at j=4 like the classic mersenne-mod DWT weights. Correct?
Correct.

Now, does it work??
Prime95 is online now   Reply With Quote
Old 2012-10-09, 22:35   #109
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

23·3·487 Posts
Default

Quote:
Originally Posted by Prime95 View Post
Correct.

Now, does it work??
I wanted to wait for your reply before commenting on the results. Here is annotated Pari code (code in italics) - note that in the sample below I am so far only using the multiplier k to compute "equivalent power of 2" for the modified DWT; according to what you've noted so far k would appear again in the post-iFFT normalize/carry step.

n = 89; k = 185;
l2k = log(k)/log(2);
p = n+l2k;

Do mod-square of the 97-bit (but < 2^p) input x = 114159265358979323846264338327 below:

N = 4; ninv = 1.0/N;
j = 1;
w0 = 2^(ceil(p*j/N) - (p*j/N)); j++;
w1 = 2^(ceil(p*j/N) - (p*j/N)); j++;
w2 = 2^(ceil(p*j/N) - (p*j/N)); j++;
w3 = 2^(ceil(p*j/N) - (p*j/N)); j++;

Here are the 2 bases and the components of the input x w.r.to the mixed-base representation:

b0 = 2^24;b1=2*b0;
x0=x%b1;x1=(x>>25)%b0;x2=(x>>49)%b0;x3=(x>>73);

Checksum:

x0+b1*(x1+b0*(x2+b0*x3)) - x

gives 0, as expected. Now do a length-4 real-input weighted FFT/dyadic-square/iFFT:

x0 *= w0;
x1 *= w1;
x2 *= w2;
x3 *= w3;

y0 = x0+x1+x2+x3;
y1 = x0+I*x1-x2-I*x3;
y2 = x0-x1+x2-x3;
y3 = x0-I*x1-x2+I*x3;

y0 *= y0;
y1 *= y1;
y2 *= y2;
y3 *= y3;

x0 = y0+y1+y2+y3;
x1 = y0-I*y1-y2+I*y3;
x2 = y0-y1+y2-y3;
x3 = y0+I*y1-y2-I*y3;

x0 *= ninv/w0
x1 *= ninv/w1
x2 *= ninv/w2
x3 *= ninv/w3

Gives unnormalized outputs

x0 = 703887643638004.71907792172553111306890 + 0.E-43*I
x1 = 204197471363853.84715648872049568720197 + 0.E-43*I
x2 = 616272238041294.96214451135558685583677 + 0.E-43*I
x3 = 835670265851967.92537464503288200734149 + 0.E-43*I

which are not the expected "very close to a whole number". What went wrong?

(Note that I tried the above Pari DWT-testing code on a classic Mersenne-mod DWT for modulus 2^89-1, to verify that the results are as expected.)

Last fiddled with by ewmayer on 2012-10-09 at 22:36
ewmayer is online now   Reply With Quote
Old 2012-10-09, 23:49   #110
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

23×3×487 Posts
Default

Aha - found the bug: In my Pari code above, the computation of the weights w0-w3 should begin with index j = 0, not 1. (I computed these individually in non-loop-style fashion when I first posted them).

Using the corrected weights, we get unnormalized outputs

x0 = 476933840021096.17837837837837837837838 + 0.E-43*I
x1 = 216945451434081.81621621621621621621622 + 0.E-44*I
x2 = 438974751056908.94054054054054054054054 + 0.E-43*I
x3 = 460450104164716.00000000000000000000000 + 0.E-44*I

which looks more promising, since if I multiply each of these by 185 (dropping the negligible imaginary part resulting from roundoff error), I get

185*x0 = 88232760403902793.000000000000000000000
185*x1 = 40134908515305136.000000000000000000000
185*x2 = 81210328945528153.999999999999999999999
185*x3 = 85183269270472460.000000000000000000000 .

Very nice! So now one just needs to do the normalize/carry step - that will allow me to work out the details of the wraparound carry - and divide every resulting word by 185 before the next squaring?
ewmayer is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Is CEMPLLA 1.5 "the only software in the world capable of discovering" something? Not really. CRGreathouse Number Theory Discussion Group 51 2018-12-16 21:55
Official "World cup 2014/2018" teat LaurV Hobbies 74 2018-07-11 19:33
Problem E7 of Richard Guy's "Unsolved problems in number theory" Batalov Computer Science & Computational Number Theory 40 2013-03-16 09:19
Is the USA the "new" peacekeeper of the world?? outlnder Soap Box 20 2005-02-03 09:30
Would Minimizing "iterations between results file" may reveal "is not prime" earlier? nitai1999 Software 7 2004-08-26 18:12

All times are UTC. The time now is 20:17.


Sat Jan 22 20:17:40 UTC 2022 up 183 days, 14:46, 0 users, load averages: 2.34, 2.24, 2.00

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, 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.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔