mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Programming

Reply
 
Thread Tools
Old 2013-01-25, 11:41   #1
Sam Kennedy
 
Sam Kennedy's Avatar
 
Oct 2012

1228 Posts
Default Modular Inversion Bottleneck

I finally got my MPQS code working, it's much faster than my QS implementation, but it's still pretty slow once the numbers get up to around 70 digits.

I have experimented with smaller blocks which can fit into the CPU cache, as well as one large block, and many large blocks, I've found for my implementation using one large sieve array of around 500k values gives the best performance.

I've profiled my code and the bottleneck is calculating the modular inverse of A mod each prime in the factor base.

I'm using the GMP library's mpz_invert function, would I have any chance of writing a faster function myself?

Are there any optimisations to limit the number of times mpz_invert() is called? (I know SIQS would be one of them, but the MPQS is about as far as I want to go.)

Or is there a way of quickly calculating the inverse?

Thank You
Sam Kennedy is offline   Reply With Quote
Old 2013-01-25, 14:30   #2
Prime95
P90 years forever!
 
Prime95's Avatar
 
Aug 2002
Yeehaw, FL

41·193 Posts
Default

You can try doing fewer modular inverses.

It is easy to calculate 1/a and 1/b with one modular inversion of a*b.
Prime95 is offline   Reply With Quote
Old 2013-01-25, 15:33   #3
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

33·239 Posts
Default

Quote:
Originally Posted by Sam Kennedy View Post
I've profiled my code and the bottleneck is calculating the modular inverse of A mod each prime in the factor base.

I'm using the GMP library's mpz_invert function, would I have any chance of writing a faster function myself?
I expect you will be able to write a faster function yourself because the primes in the factor base are small so you can do everything in 64-bit integers whilst mpz_invert is using bignums.
fivemack is offline   Reply With Quote
Old 2013-01-25, 15:56   #4
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

1101110110012 Posts
Default

The slowness of modular inversion is the reason the fastest QS variant is the self-initializing quadratic sieve; in that case the cost of computing modular inverses is amortized over many changes of polynomial.
jasonp is offline   Reply With Quote
Old 2013-01-25, 16:50   #5
Sam Kennedy
 
Sam Kennedy's Avatar
 
Oct 2012

2·41 Posts
Default

Quote:
Originally Posted by fivemack View Post
I expect you will be able to write a faster function yourself because the primes in the factor base are small so you can do everything in 64-bit integers whilst mpz_invert is using bignums.
Would the extended Euclidean algorithm suffice? Or would I have to use something more advanced?
Sam Kennedy is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
The bandwidth bottleneck is apparently much older than I thought Dubslow Hardware 5 2017-11-16 19:50
How to do big integer inversion/division with middle product, power series? R. Gerbicz Math 1 2015-02-10 10:56
Matrix Inversion Paper flouran Math 2 2009-05-24 03:15
Modular Arithmetic Numbers Math 27 2005-11-30 15:41
Opteron Bottleneck?? Prime95 Hardware 31 2003-09-17 06:54

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


Tue Jul 5 16:47:07 UTC 2022 up 82 days, 14:48, 1 user, load averages: 2.46, 1.72, 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.

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