Cyclotomic

这是一个用于高斯整数域中精确运算的库，经过良好测试和文档编写，并在某些用例中追求速度。可以从 C、C++ 或 Rust 中使用。

待办事项

• 从有理数实现中移除克隆。

• 看看我们是否可以在答案将是整数的情况下使用 f64。

• 看看如果我们使用浮点数，结构常数是否可以具有竞争力。

• 密集表示

  • 具有对高斯多项式的取模计算的密集多项式

• 移除所有复制粘贴，做一些有意义的抽象。

• C FFI 接口，用于从其他语言调用我们的 Rust 代码

• 显式构造为整数环的分数域。当只是乘法时，简单的逆元，效果很好？

• 对 SIMD 的使用进行更多调查和思考。

为什么使用这个库？

还有其他库用于更通用的用例，例如

• antic
• e-antic
• Arb
• FLINT

它们都做 很多 事情，范围很广。我们的库只做一件事，而且做得非常 快：高斯整数域运算。不仅如此，我们还针对高斯线性代数的特定用例进行了优化，旨在在代码更快的任何地方使用 SIMD 操作（由广泛的基准测试支持）。

所有数域都有许多共同的结构，可以合理地快速执行数域运算。但是，针对高斯整数域有更多特定的事情，这使得我们可以在某些用例中更快（关注 arXiv 以获取一些细节）。

有关与 antic 的基准测试，请参阅 以下内容。

功能

• 稀疏表示

  • 使用 Zumbroich 基础（GAP 启发）和指数的哈希映射（64 位整数）到系数
  • 与上面相同，但具有任意整数指数 - 这用于非常大的次数域。

• 密集表示

  • 系数向量和 Zumbroich 基础（与 GAP 相同，未打包）
  • 通过结构常数乘法得到的系数向量（视为一个Q代数）。

性能

当元素稀疏时，稀疏表示比密集表示性能更好。即使是对于非稀疏元素，性能也仍然可以接受。

待办：一些图表来展示这一点

快速入门

待办：您还需要安装antic和flint库，为此添加一些说明。

在Rust程序中使用高斯数

要安装最新版本，请安装cargo以获得功能齐全的Rust安装，包括cargo包管理器。然后将cyclotomic crate添加到您的Cargo.toml

[dependencies]
cyclotomic = "1.*"

如果您在版本1发布之前使用此软件，请将其更改为"0.*"，但会有很多破坏性更改。

在C或C++程序中使用高斯数

待办，但这一点非常重要。

更多文档

请参阅此处获取完整的API文档以及代码示例。

开发人员快速入门

1. 按照他们网站上的说明安装Rust
2. 通过在终端中运行以下命令来检查Cargo是否在您的PATH上：cargo --version
3. 使用以下命令克隆此存储库：git clone https://github.com/CyclotomicFields/cyclotomic.git
4. 通过运行bash脚本./download_prime_tables.sh下载素数表。然后，您可以使用J脚本./convert_prime_tables_to_csv.ijs将其可选地转换为CSV，这将使程序能够更快地将素数加载到内存中。
5. 使用以下命令检查所有测试是否通过：cargo test
6. 将您的姓名添加到此README中的贡献者名单，并推送，以确认您具有推送权限。
7. 检查您的推送是否在Travis上触发了管道构建。
8. 通过首先使用以下命令安装nightly rust：rustup install nightly，然后运行以下命令来运行基准测试：cargo +nightly bench。

构建文档

只需运行以下命令：cargo doc --no-deps，然后使用网络浏览器查看target/doc/cyclotomic。

即将推出：在文档中使用MathJax渲染的LaTeX数学公式。

动机

这个项目的动机大部分来自表示论。特别是，给定一个有限群G，其中m是G中元素的阶的最小公倍数，设K是一个包含m次单位根的阿贝尔数域。

然后，您可以使用K中的系数来实现G的所有表示。因此，在某种意义上，高斯数在有限群的表示理论中是“您所需要的所有”。

本项目的目标是（按顺序）

1. 实现任意次数阿贝尔数域的字段运算和相等性。这包括测试，否则我们不知道它是否工作。

2. 使其易于阅读、有良好的文档，并且不会使贡献者陷入混乱。文档可能包括详细和严谨（在数学意义上）的任何性能增强技巧的证明，也可能不包括。

3. 全面评估和基准测试所有内容，以确保这个库的性能足够好，可以用来解决非平凡问题。

灵感来源

我们从GAP计算机代数系统（cyclotom.c）的实现中借鉴最多，该实现使用各种基技巧实现了对高次单位根域的特定逻辑。这与我们的做法精神最为接近，但不是独立的。

另一个库是cyclotomic，它是同样的东西，但用Haskell编写。这只是对GAP算法的重实现，但有时我发现Haskell代码比C代码更容易阅读，所以这也值得提一下。

基准测试

在benchmarks/目录中有一个README文件，还有一些用于绘制结果的实用程序。

贡献者

Rob Moore, Kaashif Hymabaccus

版权

版权（C）2020 Rob Moore, Kaashif Hymabaccus

本程序是免费软件；您可以按照自由软件基金会发布的GNU Lesser General Public License的条款重新分发和/或修改它；许可证的版本可以是3，或者（根据您的选择）任何更新的版本。

本程序的分发是希望它将是有用的，但没有任何保证；甚至没有关于其商誉或适用于特定目的的隐含保证。有关详细信息，请参阅GNU Lesser General Public License。

完整的许可文本可以在LICENSE文件中找到。