如何将GMP的MPZ_T实例分为两个实例,有效地为内存?

发布于 2025-01-18 10:00:15 字数 1153 浏览 2 评论 0原文

tl; dr
是否有一种方法可以将一个mpz_t的数据分为两个mpz_t实例,并将数据放在内存中,因此具有恒定的时间操作,无论多少数据分为两个部分?

我需要仅在四肢的边界(mpz_t)的边界上进行拆分,即不需要子元素位移动。

细节
我想优化已经有效的算法。该算法旨在处理单个数字的几个GB范围内的数字。

我的问题类似于有效地取得了最低的GMP MPZ_T < /a>。不同之处在于,我还需要避免复制大量数据。我不想复制现有号码的数据。取而代之的是,我正在寻找一种将数字数据固定在适当位置的方法,但是在同一数据的不同区域中有两个实例mpz_t点。

为什么我想要这个:
我以前的性能优化之一是从数字的最小末端开始进行迭代处理数字。这可以提高性能。但是,为了从该末端删除数据,我当前的实现将来自原始数字的数据(请参阅其他链接问题),然后移动原始数字。这具有缺点,即在操作过程中需要更多的时间,最值得注意的是更多的内存。如果一个数字有几个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 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。
列表为空,暂无数据
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文