mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2007-10-17, 20:40   #1
TheJudger
 
TheJudger's Avatar
 
"Oliver"
Mar 2005
Germany

45716 Posts
Default division/remainder algorithm (trial factoring)

Hello,

can somebody give me a hint how to calculate a division / remainder with software integers in an efficent way?
Size of the numbers: up to ~80/160 bits (Trialfactoring of factors up to ~80 bits)

Limitations:
- (virtually) NO if/then/else!
- only 16/32bit integers
- only single precission floats (non IEEE rounding)
- no assembler (no carry flag, ...), only C

if/then/else is OK if (and only if) the code takes in >99.9% of the cases (different input data) the same code path.

Background: I'm thinking of trial factoring on graphics cards (Nvidia).
There are so many limitations for running calculations on Nvidia cards but TF might be possible ;)

Currently I've done a quick&dirty implemantation with the limitations above which runs on my main CPU (C2D @ 3GHz). For 65+ bit factors the performance is about 60 times slower than prime95. I think if I can improve the speed to lets say "only" 10-15 times slower than prime95 it might be worth to try it on the GFX.

e.g.: Geforce 8800GTX (128 shader units, 768MiB memory)
some recommendations for optimal performance:
- at least 6 threads per shader unit to hide the latency of the memory (so we will need 768 threads <=> only 1MiB per thread available)
- these threads should be strictly SIMD otherwise the threads won't be done in parallel... that's why I've said no if/then/else. Loops are OK if (and only if) the number ot iterations for each thread are the same.

TheJudger

P.S. I'm pretty sure that the lack of double precission isn't the main reason for not doing LL on the current GFX cards. The limitations mentioned above should be even more problematic... we'll need a thread-parallel multiplication algorithm which is SIMD for all threads and which doesn't need much communication between the threads...
TheJudger is offline   Reply With Quote
Old 2007-10-17, 20:52   #2
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by TheJudger View Post
Hello,

can somebody give me a hint how to calculate a division / remainder with software integers in an efficent way?
Size of the numbers: up to ~80/160 bits (Trialfactoring of factors up to ~80 bits)

...
Read

Knuth, The Art of Computer Programming, Vol II
R.D. Silverman is offline   Reply With Quote
Old 2007-10-18, 03:18   #3
ShiningArcanine
 
ShiningArcanine's Avatar
 
Dec 2005

22·23 Posts
Default

Why not just use GMP and test a different number in each thread? You could be doing 768 tests in parallel.

Last fiddled with by ShiningArcanine on 2007-10-18 at 03:19
ShiningArcanine is offline   Reply With Quote
Old 2007-10-18, 13:59   #4
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

746010 Posts
Default

Quote:
Originally Posted by ShiningArcanine View Post
Why not just use GMP and test a different number in each thread? You could be doing 768 tests in parallel.
We must have read different posts. I could swear that the O.P. asked
"how to calculate" and not "what code do I use".
R.D. Silverman is offline   Reply With Quote
Old 2007-10-18, 19:01   #5
TheJudger
 
TheJudger's Avatar
 
"Oliver"
Mar 2005
Germany

11·101 Posts
Default

Quote:
Originally Posted by ShiningArcanine View Post
Why not just use GMP and test a different number in each thread? You could be doing 768 tests in parallel.
Yes, that's what I want to do.. test alot of possible factors for a single exponent at the same time.

I'm pretty sure the GMP won't fit to the limitations...
TheJudger is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Sublinear complexity of trial division? yih117 Math 5 2018-02-02 02:49
Mersenne trial division implementation mathPuzzles Math 8 2017-04-21 07:21
trial division over a factor base Peter Hackman Factoring 7 2009-10-26 18:27
P95 trial division strategy SPWorley Math 8 2009-08-24 23:26
Need GMP trial-division timings ewmayer Factoring 7 2008-12-11 22:12

All times are UTC. The time now is 06:11.


Sun May 29 06:11:41 UTC 2022 up 45 days, 4:13, 0 users, load averages: 1.74, 1.64, 1.43

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.

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