问题标签 [arbitrary-precision]

我需要在整数环中使用 FFT 将长整数与任意 BASE 数字相乘。n = 2^ksome的操作数总是有长度的k，并且卷积向量具有2n分量，因此我需要一个2n'th原始单位根。

我不是特别关心效率问题，所以我不想使用 Strassen & Schönhage 的算法——只计算基本卷积，然后进行一些进位，仅此而已。

尽管对很多数学家来说似乎很简单，但我对代数的理解真的很糟糕，所以我有很多问题：

1. 2^n + 1在整数环模（可能是复合）和整数 FIELDS 模一些素数中执行 FFT 之间有什么本质区别或细微差别p？
   
   我问这个是因为在这样一个环中2是一个(2n)th原始的统一根，因为2^n == -1 (mod 2^n+1)。相反，整数字段需要我搜索这样的原始根。
   
   但也许还有其他细微差别会阻止我将这种形式的环用于 FFT。

2. 2^n如果我选择整数环，那么在这个领域中存在 -th 单位根的 充分条件是什么？
   
   所有其他2^k小阶单位的根都可以通过平方这个根来获得，对吧？..

3. 环模乘法有哪些基本限制？也许在它们的长度上，也许在数字基础上，甚至可能在用于乘法的数字类型上。
   
   我怀疑如果通过模运算减少卷积的系数，可能会丢失一些信息。这是真的吗？为什么？.. 有哪些一般条件可以让我避免这种情况？
   
   

4. long对于 FFT 向量、它们的乘积和卷积向量，是否有可能仅原始类型的动态列表（即）就足够了？或者我应该将系数转换为BigInteger以防万一（我真正应该的“情况”是什么）？

如果对这些问题的一般回答需要太长时间，我会特别满意在以下条件下的回答。我2^30在字段 Z_70383776563201 中找到了顺序统一的原始根表：

http://people.cis.ksu.edu/~rhowell/calculator/roots.html

因此，如果我使用2^30th 单位根来乘以 length 的数量，2^29我应该考虑哪些精度/算法/效率的细微差别？..

非常感谢您！我将奖励最佳答案 - 请考虑帮助提供一些示例。

下午好！

我正在尝试基于我已经拥有的朴素递归 FFT 实现来开发 NTT 算法。

考虑以下代码（coefficients' 长度，顺其自然m，是 2 的精确幂）：

它适用于复杂的 FFT（替换BigInteger为复杂的数字类型（我有自己的））。即使我适当地更改了找到统一的原始根源的程序，它也不起作用。

假设，问题是这样的：rootsOfUnity传递的参数最初只包含第m-th 个复单位根的前半部分，顺序如下：

omega^0 = 1, omega^1, omega^2, ..., omega^(n/2)

就足够了，因为在这三行代码中：

我最初利用了这样一个事实，即在任何递归级别（对于任何nand i），unity 的复杂根-omega^(i) = omega^(i + n/2)。

但是，该属性显然不适用于有限域。但是是否有任何类似物可以让我仍然只计算根的前半部分？

或者我应该将循环从n/2to扩展n并预先计算所有m-th 统一的根？

也许这段代码还有其他问题？...

非常感谢您！

我正在做一个项目（在 Scala 中），我需要处理一些非常大的数字；太大而无法用整数类型表示。Java 提供了 BigInteger 和 BigDecimal 类（scala 提供了一个很好的瘦包装器）。但是，我注意到这些库比我过去使用过的其他任意精度库（即http://www.ginac.de/CLN/）要慢得多，而且速度差异似乎比可以归因的更大单独的语言。

我对我的程序进行了一些分析，44% 的执行时间花费在 BigInteger 乘法方法上。我想加快我的程序速度，所以我正在寻找比 BigInteger 类（及其 Scala 包装器）更快、更高效的选项。我看过 LargeInteger（来自 JScience）和 Aint（来自 Afloat）。但是，两者的执行似乎都比标准 BigInteger 类慢。

有谁知道专注于高性能整数乘法和加法的 Java（或在 JVM 上可用）任意精度数学库？

任何人都可以建议一个预构建的 Windows 二进制文件附带的多精度库。我需要将它与现有的 Visual Studio 2010 项目一起使用（或者我可以获得用于 GMP 的 win7 64bit 的预构建二进制文件）。

我尝试过编译 GMP 和 MPIR 以及其他项目但都失败了，它们都没有处理各种令人沮丧和模棱两可的错误。不幸的是，时间压力越来越大，如果我可以构建/下载库，我需要实现的东西很简单。

我需要浮点支持，所以一个 bigint 库是不够的。

谢谢，

vpa关于在 MatLab 中评估符号表达式时可以使用的命令，我有一个简短的问题。

我的教科书是这样说的：

“在使用数字等函数时需要小心sqrt，默认情况下会产生双精度浮点数。您需要将此类输入vpa作为符号字符串传递给以进行正确评估：vpa('sqrt(5)/pi').”

我不太明白这里的行话。vpa(input)为什么对于大多数输入，无论我输入or ，我都会得到完全相同的答案vpa('input')，但对于平方根却不是？例如，如果我输入vpa(sin(pi/4))or vpa('sin(pi/4)')，我会得到完全相同的答案，但如果我输入上面给出的问题作为vpa(sqrt(5)/pi)，我不会得到与输入时相同的答案vpa('sqrt(5)/pi')。

如果有人能比我上面的书更详细地解释这一点，我将不胜感激！

在汇编语言中，通常有一条指令添加两个操作数和一个进位。如果要实现大整数加法，只需添加不带进位的最低整数和带进位的下一个整数。在我无法访问进位标志的 C 或 C++ 中，我将如何有效地做到这一点？它应该适用于多个编译器和架构，所以我不能简单地使用内联汇编等。

使用 GMP 进行操作时，有什么方法可以更改舍入模式？还是我必须为此使用 MPFR？

提前致谢！

什么是手动打印其值不适合的 N 二进制数字整数的可扩展算法long long。我认识printf和朋友，以及<iostream>（最有可能搭载的<cstdio>是标准类型的内置函数，但我想对由 N 个字节组成的整数执行此操作。

我已经考虑过这一点并在谷歌上搜索了一下，但它总是归结为使用预先存在的 bigint 库，如 GMP（我完全不熟悉的代码库）或“使用 printf”或最有用的“这很难” .

整数基本上是：

所以重新解释 aInteger<4>的字节会给你一个int32_t. 我想将其缩放到 N>8。目前，效率并不是我真正关心的问题。字节顺序也不是（这是针对 x86 的）。

我已经尝试过GMP，MPFR。但我无法完成像下面这样的简单划分。顺便说一句，我在 Xcode 中有 LLVM 编译器。我尝试编译，运行到IOS模拟器。

mpf_t 一个；

mpf_init2（一，256）；

mpf_set_d(a, 0.7);

mpf_t b; mpf_init2 (b, 256);

mpf_set_d(b, 1.0);

mpf_t l; mpf_init2 (l, 256);

gmp_printf ("%.*Ff \n", 5, a); --- 0.70000

gmp_printf ("%.*Ff \n", 5, b); --- 1.00000

mpf_div(l, a, b);

gmp_printf ("%.*Ff", 5, l); --- 0.52502

MPFRC++我需要 C++ 程序中的任意精度，因此我在多精度浮点 C-library 上使用众所周知的轻量级 C++ 包装器MPFR。

我一直有记忆问题。即，malloc在 MPFR 功能内失败。（如果您有兴趣，请在底部显示一小段错误消息）。

MPFR 手册说（第 10 页）

MPFR 函数可能会创建缓存，例如，在计算诸如 pi 之类的常量时，要么是因为用户直接调用了类似 mpfr_const_pi 的函数，要么是因为 MPFR 库本身在内部调用了这样的函数来计算某个其他函数。

在任何时候，用户都可以使用 mpfr_free_cache 释放各种缓存。强烈建议在终止线程之前执行此操作...

我的程序是多线程的，所以我想我需要开始使用这个mpfr_free_cache.

问题： 我可以简单地放入包装类mpfr_free_cache()的析构函数吗？这是安全和良好的做法吗？是否足以解决问题？（假设我已经正确识别出内存泄漏）

例如

// mpreal.cpp - 包装器的实现

我不是专业的开发人员，所以我不知道这是否真的是解决问题的最佳方法。但我对进入每个 OpenMP 多线程区域/for-loop 并挤进一个mpfr_free_cache()...

注意：我已经使用线程安全选项构建了 MPFR。

这是错误消息，如果您有兴趣...

错误消息中引用的代码：