如何将GMP的MPZ_T实例分为两个实例,有效地为内存?
tl; dr :
是否有一种方法可以将一个mpz_t
的数据分为两个mpz_t
实例,并将数据放在内存中,因此具有恒定的时间操作,无论多少数据分为两个部分?
我需要仅在四肢的边界(mpz_t
)的边界上进行拆分,即不需要子元素位移动。
细节:
我想优化已经有效的算法。该算法旨在处理单个数字的几个GB范围内的数字。
为什么我想要这个:
我以前的性能优化之一是从数字的最小末端开始进行迭代处理数字。这可以提高性能。但是,为了从该末端删除数据,我当前的实现将来自原始数字的数据(请参阅其他链接问题),然后移动原始数字。这具有缺点,即在操作过程中需要更多的时间,最值得注意的是更多的内存。如果一个数字有几个GB,那将是重要的。
我目前要做的:
mpz_class n = ...; // huge number
mpz_class chunk; // will hold the part of n that we chopped off
size_t limbs_to_chop_off = 12345;
size_t bits_to_chop_off = sizeof(mp_limb_t) * 8 * limbs_to_chop_off;
mpz_tdiv_r_2exp(chunk.get_mpz_t(), n.get_mpz_t(), bits_to_chop_off);
n >>= bits_to_chop_off;
// process chunk ...
tl;dr:
Is there a way to split the data of one mpz_t
into two mpz_t
instances and leave the data in its place in memory, thus having a constant time operation, no matter how much data is getting split in two parts?
I need to split it only at the boundaries of the limbs (elements of the mpz_t
), i.e. no sub-element bit shifting is required.
Details:
I want to optimize an algorithm that's already working. The algorithm is intended to process numbers in the range of a few GB for a single number.
My question is similar to Efficiently take N lowest bits of GMP mpz_t . The difference is that I also need to avoid the copying of large amounts of data. I don't want to copy data from an existing number. Instead, I am looking for a way to keep the number's data in place, but have two instances of mpz_t
point at different regions of the same data.
Why I want this:
One of my previous performance optimizations is to process the number iteratively, starting from the least significant end of the number. That yields a good performance boost. However, for chopping off data from that end, my current implementation copies data from the original number (See other linked question) and then the original number is shifted. This has the disadvantages that it takes more time and, most notably, more memory during the operation. That's significant if a single number has a few GB.
What I currently do:
mpz_class n = ...; // huge number
mpz_class chunk; // will hold the part of n that we chopped off
size_t limbs_to_chop_off = 12345;
size_t bits_to_chop_off = sizeof(mp_limb_t) * 8 * limbs_to_chop_off;
mpz_tdiv_r_2exp(chunk.get_mpz_t(), n.get_mpz_t(), bits_to_chop_off);
n >>= bits_to_chop_off;
// process chunk ...
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论