Tag: biginteger

如何准确地乘以和除以64位整数？

我有一个C函数： int64_t fn(int64_t a, int32_t b, int32_t c, int32_t d) { /* should return (a * b * c)/d */ } a可能接近INT64_MAX，但最终结果不会溢出，例如，如果b = 1，则c = d = 40.但是，我无法弄清楚如何计算这个以便我永远不会丢失数据舍入（通过先进行除法）或中间结果溢出。 如果我可以访问足够大的数据类型以适应a，b和c的整个产品，我只会在该类型中进行数学运算然后进行截断，但是有一些方法可以在没有大整数的情况下执行此操作吗？

OpenSSL的BN_bn2binfunction出现问题

我正在尝试在OpenSSL中使用BN_ *函数。 具体来说，我有以下代码： #import BIGNUM * num = BN_new(); BN_set_word(num, 42); char * buffer = malloc((BN_num_bytes(num)+1) * sizeof(char)); buffer[BN_num_bytes(num)] = ‘\0’; int len = BN_bn2bin(num, buffer); printf(“42 in binary is %s\n”, buffer); 但是，当我这样做时，我没有得到一串零和一个零。 相反，它打印”42 in binary is *” 。 据我所知，从网上可用的非常有限的例子我已经比较过这个例子，我已经正确地实现了这一点。 任何想法为什么它不起作用？

c ++中的大整数

我知道这个问题可能已在本论坛多次和网络上提出过。 我被要求在c ++中创建一个大整数的实现，但是有一个约束，我的一个构造函数应该将一个int作为一个参数…所以我猜我会有多个非默认的构造函数..所以我的问题是，最简单的方法是什么？

C中x64的128位算术运算

在x86上实现bignums时，显然数字大小的最有效选择是32位。 但是，您需要算术最多两倍的数字大小（即32 + 32 = 33,32 * 32 = 64,64 / 32 = 32）。 幸运的是，x86不仅提供了这一function，而且还可以从便携式C（uint64_t）访问它。 类似地，在x64上，希望使用64位数字。 这将需要128位算术（即64 + 64 = 65,64 * 64 = 128,128 / 64 = 64）。 幸运的是，x64提供了这个function。 不幸的是，它无法通过便携式C接入，但显然有人可以进入组装。 所以我的问题是它是否可从非便携式C访问.X64上的任何C编译器是否提供对此的访问，如果是，那么语法是什么？ （注意，我不是在谈论128位向量，它们被严格地视为32或64位字的集合，它们之间没有进位传播，但是关于实际的128位整数运算。）

如何处理不适合任何语言数据结构的大整数

我正在尝试解决编程竞赛的初步问题以及我必须计算的两个问题，并打印一些非常大的整数（如100！，2 ^ 100）。 我还需要一种快速的方法来计算这个大整数的幂。 你可以为我建议一些算法或数据结构吗？（顺便说一下，我读过C接口和实现的’任意精度算术’部分，但它对pow（）没有帮助） 编辑：我认为通过平方法和位移的取幂对功率起作用，但我还需要一种快速的方法来计算这个因子的阶乘。 谢谢。 EDIT2：对于那些感兴趣的人; 找到包含长度为N的所有位串的最短位串长度（对不起我的英文，我会给出一个例子）。 N <= 10000 例如，包括长度为2（00,01,10,11）的所有位串的最短位串长度是5（11001）。 我对这个问题的解决方案是2 ^ n + n – 1.（所以我应该计算2的幂，我想我会使用位移） 其他问题是，给定2个长度，找到你可以通过多少种方式达到长度N.例如，输入是10,2,3。那么你应该用2和3达到10（例如，2 + 3） 2 + 2 + 2 + 2,2 + 2 + 3 + 3,3 + 2 + 2 + 3,3 + 3 + 2 + 2 ……）。 1 <= N <2 ^ 63。 […]

将bignum类型结构转换为人类可读字符串的有效方法是什么？

我有点问题。 为了增长我对C的了解，我决定尝试实现一个基本的bigint库。 bigint结构的核心是一个32位整数数组，因为它们适合寄存器而被选中。 这将允许我在数字之间进行操作，这些数字将以64位整数溢出（这也适合寄存器，因为我在x86-64上），并且我可以对结果的每个部分进行位移位。 我已经实现了基本的添加，并且为了测试它是否正常工作，我必须打印数组。 对于我自己的测试目的，如果我使用printf()并以hex输出每个数字就没问题。 我可以读到这很好。 但是，大多数人都读不懂hex。 由于数字存储在（基本上）基数2 ^ 32中，因此打印有点问题。 什么是转换到基数10的好方法？ 编辑： 这不涉及知道如何从基数转换为基数，而是关于实现这一点的好方法。 我正在考虑用另一个基础制作另一个bigint并转换打印。

将大整数转换为十进制字符串

如果将这个问题投票为重复，甚至将其关闭，那么我就有了这个问题。 背景 在“正常”数据类型（如int，long long等等）中，要从二进制数值转换为十进制字符串，您将执行以下操作（在伪代码中）： Set length = 0 Set divisor to largest base10 value the data type will hold (Divisor). Loop Divide number in question by divisor. Place result in a string at position length. Increment the length by 1. Divide the divisor by 10. Reverse the string. Print the string. （大多数）任何语言的实际实现都是微不足道的。 问题 我遇到的上述方法的问题是，对于大整数（也称为任意精度算术 ），没有最大的基数10值开始。 […]

我应该使用什么算法进行高性能大整数除法？

我将大整数编码为size_t数组。 我已经有其他操作工作（加，减，乘）; 以及一位数的除法。 但是如果可能的话，我想匹配我的乘法算法的时间复杂度（目前是Toom-Cook）。 我收集有线性时间算法，用于采用我的红利的乘法逆的各种概念。 这意味着我理论上可以在与乘法相同的时间复杂度中实现除法，因为无论如何，线性时间操作通过比较是“无关紧要的”。 我的问题是，我该怎么做呢？ 什么类型的乘法逆在实践中最好？ Modulo 64^digitcount ？ 当我将乘法逆乘以我的除数时，我可以推卸计算由于整数截断而丢弃的数据部分吗？ 任何人都可以提供C或C ++伪代码或准确解释应该如何做到这一点？ 或者是否存在比基于逆的方法更好的专用除法算法？ 编辑：我挖出了上面提到的“反向”方法。 在“Art of Computer Programming，Volume 2：Seminumerical Algorithms”的第312页上，Knuth提供了“算法R”，它是一种高精度的倒数。 他说它的时间复杂度小于乘法的时间复杂度。 然而，将它转换为C并测试它并且不清楚将消耗多少开销内存等直到我对其进行编码是非常重要的，这将需要一段时间。 如果没有人打败我，我会发布它。

为什么要使用更高的基数来实现BigInt？

我正在尝试实现BigInt并阅读了一些关于它的线程和文章，其中大多数建议使用更高的基数（256或2 ^ 32甚至2 ^ 64）。 为什么更高的基数有利于此目的？ 我有的其他问题是我应该如何将字符串转换为更高的基数（> 16）。 我读过没有标准的方法，除了base64。 最后一个问题，我如何使用这些更高的基础。 一些例子会很棒。

最快的128位整数库

我正在研究CPU繁重的数值计算应用程序。 没有进入很多细节，它是一个计算数学研究项目，涉及计算大整数x的某个函数f（x）。 现在一切都是在x64模式下用C ++实现的，使用本机64位整数。 这限制了我x <2 ^ 64~1.8 * 10 ^ 19。 我想更进一步，为此，我需要一个可以进行128位运算的库。 它必须非常快。 特别是，整数除法应该很快。 否则我会坐在这里等待结果直到感恩节。 而且我宁愿不重新发明轮子。 我在维基百科上找到了一个大约20个大整数库的列表，但其中大多数似乎都是针对任意精度的数字，这对我的任务来说太过分了，而且我不需要额外的费用。 有谁知道哪个库可以最快地运行128位整数？