4

我正在用 C++ 编写我自己的长算术库，它已经完成得很好了，我什至用那个库实现了几个 Cryptogrphic 算法，但仍然缺少一件重要的事情：我想将双精度数（和浮点数/长双精度数）转换为我的号码，反之亦然。我的数字表示为一个可变大小的无符号长整数数组加上一个符号位。

我试图用谷歌找到答案，但问题是人们很少自己实现这些东西，所以我只找到关于如何使用 Java BigInteger 等的东西。

从概念上讲，这相当容易：我取尾数，将其移动由指数指定的位数并设置符号。在另一个方向上，我将其截断以使其适合尾数并根据我的 log2 函数设置指数。

但是我很难弄清楚细节，我可以玩一些位模式并将其转换为双精度，但我没有找到一种优雅的方式来实现这一点，或者我可以通过开始“计算”它用 2，取幂，乘法等，但这似乎不是很有效。

我希望有一个不使用任何库调用的解决方案，因为我试图避免为我的项目使用库，否则我本可以使用 gmp，此外，我经常在其他几个场合有两种解决方案，一个使用内联汇编程序高效且更独立于平台，因此任何一个答案对我都有用。

编辑：我使用 uint64_t 作为我的部件，但我希望能够根据机器进行更改，但我愿意使用一些#ifdefs 来实现一些不同的实现。

4

4 回答 4

2

我将在这里做出不可移植的假设：即，它unsigned long long的数字比double. （在我所知道的所有现代桌面系统上都是如此。）

首先，将最重要的整数转换为unsigned long long. 然后将其转换为 double S。让M是小于第一步中使用的整数的数量。乘以。S_ (1ull << (sizeof(unsigned)*CHAR_BIT*M)（如果移位超过 63 位，则必须将它们拆分为单独的移位并进行一些运算）最后，如果原始数字为负数，则将此结果乘以 -1。

这个舍入很多，但即使使用这种舍入，由于上述假设，不会丢失任何数字，但转换为双精度时无论如何都不会丢失。我认为这与 Mark Ransom 所说的过程类似，但我不确定。

要从双精度整数转换为大整数，首先将尾数分隔为 a double M，将指数分隔为int E，使用frexp. 乘以M，UNSIGNED_MAX并将结果存储在 中unsigned R。如果std::numeric_limits<double>::radix()是 2（我不知道它是否适用于 x86/x64），您可以轻松地左移R一位，E-(sizeof(unsigned)*CHAR_BIT)然后就完成了。否则，结果将改为R*(E**(sizeof(unsigned)*CHAR_BIT))（其中**意味着力量）

如果性能是一个问题，您可以为您的 bignum 类添加一个重载来乘以std::constant_integer<unsigned, 10>，它只是返回(LHS<<4)+(LHS<<2)。如果您愿意，您可以类似地优化其他常量。

于 2012-09-07T19:04:23.303 回答
1

这篇博文可能会帮助您 澄清和优化 Integer>>asFloat

否则，您还可以通过这个 SO 问题对算法有所了解

于 2012-09-07T19:50:26.887 回答
0

要从大整数变为双精度，只需按照解析数字的方式进行即可。例如，您将数字“531”解析为“1 + (3 * 10) + (5 * 100)”。使用双精度计算每个部分，从最不重要的部分开始。

要从双精度整数变为大整数，请以相同的方式进行操作，但从最重要的部分开始反向操作。所以，要转换 531，首先你会看到它大于 100 但小于 1000。你通过除以 100 找到第一个数字。然后减去得到 31 的余数。然后通过除以 10 找到下一个数字。并且很快。

当然，您不会使用十位（除非您将大整数存储为数字）。究竟如何将其拆分取决于大整数类的构造方式。例如，如果它使用 64 位单位，那么您将使用 2^64 的幂而不是 10 的幂。

于 2012-09-07T18:53:32.310 回答
0

你没有明确说，但我假设你的库只是整数，无符号长整数是 32 位和二进制（不是十进制）。转换为double 很简单，所以我先解决这个问题。

从当前作品的乘数开始；如果数字为正，则为 1.0，如果为负，则为 -1.0。对于 bignum 中的每个无符号长整数，乘以当前乘数并将其添加到结果中，然后将乘数乘以pow(2.0, 32)(4294967296.0)（对于 32 位）或pow(2.0, 64)(18446744073709551616.0)（对于 64 位）。

您可以通过仅使用 2 个最重要的值来优化此过程。即使整数类型中的位数大于 double 的精度，您也需要使用 2，因为最高有效值中使用的位数可能仅为 1。您可以通过取幂来生成乘数2 到跳过的位数，例如pow(2.0, most_significant_count*sizeof(bit_array[0])*8). 您不能使用另一个答案中给出的位移，因为它会在第一个值之后溢出。

要从双精度转换，您可以使用函数将指数和尾数彼此分开frexp。尾数将作为 0.5 和 1.0 之间的浮点值出现，因此您需要将其乘以 pow(2.0, 32) 或 pow(2.0, 64) 以将其转换为整数，然后将指数调整为 -32 或-64 进行补偿。

于 2012-09-07T18:56:23.133 回答