mersenneforum.org LLR / Gwnums version
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2005-09-16, 13:49 #12 Cruelty     May 2005 22·11·37 Posts So testing k*2^n-b for k=736320585 is not the optimal way to use LLR? Last fiddled with by Cruelty on 2005-09-16 at 13:49
2005-09-16, 15:27   #13
Jean Penné

May 2004
FRANCE

2·5·59 Posts
Using LLR with big k's

Quote:
 Originally Posted by Cruelty So testing k*2^n-b for k=736320585 is not the optimal way to use LLR?
If b != 1, LLR will do a PRP test...
If b == 1, LLR will do a proving test ; k being large, gwnum will work in generic mode in both cases, so you will not get the IBDWT performances, but I don't know if a faster program is presently available (try Openpfgw, but it also uses the gwnum code...).

Jean

 2005-09-18, 19:11 #14 Citrix     Jun 2003 30648 Posts Jean, which is the fastest k to test, in terms of speed. Are all k under 2^20 the same speed? What is the difference in speed between a k under 2^20 and a k between 2^20 and 2^21? Citrix
2005-09-19, 07:40   #15
Jean Penné

May 2004
FRANCE

2·5·59 Posts

Quote:
 Originally Posted by Citrix Jean, which is the fastest k to test, in terms of speed. Are all k under 2^20 the same speed? What is the difference in speed between a k under 2^20 and a k between 2^20 and 2^21? Citrix
It is rather more complicated... and it requires to give precisions about how the gwnum code proceeds to do multiplications modulo N = k*2^n+-b numbers (surely, George Woltman would do that better than me...).
1) The speed is determined by the FFT length necessary to process a number N of given bit length.
2) According to the k size, the gwnum code uses three different algorithms to do multiplications : pure IBDWT, Zero paded IBDWT, generic mode.
3) The pure IBDWT algorithm can only be used with k values from 1 to around 2^20 ; it is the most efficient, because it requires the smallest FFT length, and makes the modular reduction totally free. Nevertheless, the FFT length for a given size of N increases smoothly by a factor of 2 when k goes from 1 to 2^20, then, the Zero padded algorithm becomes the better.
4) The Zero padded IBDWT can be used for k values up to around 2^48, and the performances continue to decrease smoothly.
5) For higher k values, the generic mode is used, and the speed for given size of N is around three times smaller than the IBDWT one.

I hope this rather involved explanation will satisfy you.

Jean

 2005-09-19, 07:43 #16 Citrix     Jun 2003 110001101002 Posts The smaller the k the faster it will be? Did I get it right? Citrix
2005-09-19, 08:25   #17
Jean Penné

May 2004
FRANCE

10010011102 Posts

Quote:
 Originally Posted by Citrix The smaller the k the faster it will be? Did I get it right? Citrix
Yes, for a given bit length of the number to test !

 2005-11-26, 21:39 #18 Ken_g6     Jan 2005 Caught in a sieve 5×79 Posts I've been trying to find a generic top-5000 prime with LLR 4.62 recently. I chose Proth tests with n=409600, k increasing from 600 to 1000000, since 2^20 is 1048576. But around k=65487, running on a P4 2.8GHz non-hyperthreaded, I noticed that LLR said I was using a zero-padded FFT. Which according to the thread above shouldn't happen, right? Looking through the log, there seems to have been a big jump in time taken between 60000 and 62000. While I can't completely rule out other processes for this jump, considering the size of the k, that zero-padded message is weird.

 Thread Tools

 Similar Threads Thread Thread Starter Forum Replies Last Post Jean Penné Software 11 2011-02-20 18:22 Jean Penné Software 30 2010-09-21 16:43 richs Software 41 2009-01-07 14:40 Cruelty Riesel Prime Search 8 2006-05-16 15:00 Prime95 Software 13 2006-02-15 16:32

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

Sun Jul 3 17:16:15 UTC 2022 up 80 days, 15:17, 0 users, load averages: 1.10, 1.46, 1.48

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.

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