问题标签 [bignum]

我正在尝试为任意大整数实现 Solovoy-Strassen 素数测试。我还将编写一个 bignum（不能使用 3rd 方实现，因为这是一个学术项目）。我已经决定了 bignum 的以下结构：

我将使用 base-32 作为我的数字（因此 uint64_t，对于部分产品，至少我认为它们将是部分产品）。这个决定是基于之前提出的问题。

我处于静止状态。我无法想象如何将一个字符串表示为任意大小的小数并将其转换为上面的 bignum 结构。

有人可以启发我。即使是一个更小的例子也会很好，例如将任意字符串转换为八进制数字，这些数字将存储在 uint16_t 数组中。

谢谢。

我正在为一个家庭作业项目编写一个小型 bignum 库。我要实现 Karatsuba 乘法，但在此之前我想编写一个简单的乘法例程。

我正在关注 Paul Zimmerman 编写的名为“现代计算机算术”的指南，该指南可在线免费获得。

在第 4 页，有一个名为 BasecaseMultiply 的算法的描述，它执行小学乘法。

我理解第 2、3 步，其中 B^j 是 1、j 次的数字移位。但我不明白第 1 步和第 3 步，我们有 A*b_j。如果尚未定义 bignum 乘法，该乘法将如何进行？

该算法中的“*”操作是否只是重复添加方法？

这是我到目前为止写的部分。我已经对它们进行了单元测试，因此它们在大多数情况下似乎是正确的：

我用于我的 bignum 的结构如下：

当前可用的例程：

只是想知道是否有人有任何真实世界的示例或知道何时可以在 Ruby 中使用 NOT、AND、OR、XOR、<<、>> 运算符。

我已经编程了 4 年，从来没有遇到过需要使用其中的任何一个，想知道实际用法有多普遍以及我是否应该完全理解它。

谢谢，-J

Ruby 到底是怎么做到的？Jörg 或其他人是否知道幕后发生的事情？

不幸的是，我不太了解 C，所以bignum.c对我帮助不大。我只是有点好奇，有人可以（用简单的英语）解释它使用的任何奇迹算法背后的理论。

368063488259223267894700840060521865838338232037353204655959621437025609300472231530103873614505175218691345257589896391130393189447969771645832382192366076536631132001776175977932178658703660778465765811830827876982014124022948671975678131724958064427949902810498973271030787716781467419524180040734398996952930832508934116945966120176735120823151959779536852290090377452502236990839453416790640456116471139751546750048602189291028640970574762600185950226138244530187489211615864021135312077912018844630780307462205252807737757672094320692373101032517459518497524015120165166724189816766397247824175394802028228160027100623998873667435799073054618906855460488351426611310634023489044291860510352301912426608488807462312126590206830413782664554260411266378866626653755763627796569082931785645600816236891168141774993267488171702172191072731069216881668294625679492696148976999868715671440874206427212056717373099639711168901197440416590226524192782842896415414611688187391232048327738965820265934093108172054875188246591760877131657895633586576611857277011782497943522945011248430439201297015119468730712364007639373910811953430309476832453230123996750235710787086641070310288725389595138936784715274150426495416196669832679980253436807864187160054589045664027158817958549374490512399055448819148487049363674611664609890030088549591992466360050042566270348330911795487647045949301286614658650071299695652245266080672989921799342509291635330827874264789587306974472327718704306352445925996155619153783913237212716010410294999877569745287353422903443387562746452522860420416689019732913798073773281533570910205207767157128174184873357050830752777900041943256738499067821488421053870869022738698816059810579221002560882999884763252161747566893835178558961142349304466506402373556318707175710866983035313122068321102457824112014969387225476259342872866363550383840720010832906695360553556647545295849966279980830561242960013654529514995113584909050813015198928283202189194615501403435553060147713139766323195743324848047347575473228198492343231496580885057330510949058490527738662697480293583612233134502078182014347192522391449087738579081585795613547198599661273567662441490401862839817822686573112998663038868314974259766039340894024308383451039874674061160538242392803580758232755749310843694194787991556647907091849600704712003371103926967137408125713631396699343733288014254084819379380555174777020843568689927348949484201042595271932630685747613835385434424807024615161848223715989797178155169951121052285149157137697718850449708843330475301440373094611119631361702936342263219382793996895988331701890693689862459020775599439506870005130750427949747071390095256759203426671803377068109744629909769176319526837824364926844730545524646494321826241925107158040561607706364484910978348669388142016838792902926158979355432483611517588605967745393958061959024834251565197963477521095821435651996730128376734574843289089682710350244222290017891280419782767803785277960834729869249991658417000499998999

这是来自 Project Euler 网站的问题 3

我没有解决这个问题，但我可能猜你会知道我的方法是什么。现在我的问题是，如何处理超过 unsigned int 的数字？

有没有一种数学方法，如果有，我在哪里可以读到它？

我想在 C++ 中添加 2 个任意大小的整数。我该怎么做呢？

是否有一个用于 JavaScript 的 bignum 库或我可以包含的内置库，例如

?

我认为我的用户更愿意在网页中输入数字并等待 7 秒的结果，而不是下载可执行文件并单击一堆“此可执行文件可能会损害您的计算机”警告屏幕来安装它。

我考虑过基于http://github.com/silentmatt/javascript-biginteger或http://www.mainebrook.com/john/fun/euler.html。或者你会推荐从 JavaScript 调用到一个 Java bignum 库，比如 apfloat？

是否有一些数学“最佳”基础可以加快阶乘计算？

背景：只是为了好玩，我正在实现我自己的 bignum 库。（-：这是我的第一个错误吗？:-)。我正在试验内部表示和回归测试中使用的各种基础，方法是打印出 n 阶乘（n！）的精确值（十进制）。

我的 bignum 库表示整数并进行乘法的方式，时间与内部表示 n! 中“1”位的总数成正比。在我的内部表示中使用基数 2、4、8、16、2^8、2^30 等，对于任何特定数字，我都会给出完全相同的“1”位总数。

除非我犯了一些错误，否则以 18 为基数表示的任何给定阶乘（n！）的“1”位少于以 10 为基数或以 16 为基数或以 19 为基数表示的相同值。因此（原则上）使用基数18 将使我的 bignum 库比使用基数 10 或一些二进制 2^w 基数或基数 19 运行得更快。我认为这与 n! 以 18 为基数打印时比以 10 为基数或以 16 为基数或以 19 为基数打印时，要么更短，要么有更多的“尾随零”或两者兼有。还有其他一些比以 18 为基数更好的基础吗？换句话说，是否有一个表示 n 的基数！“1”位比基数 18 还要少？

这不是“什么是 bignum 库和素数测试算法的方便基础？”的重复。因为我怀疑“处理已知为大因子的整数的最佳基数，有很多 2 和 3 的因子”不同于“处理没有任何小因子且可能的整数的最佳基数”主要”。（-：加速阶乘计算——也许以牺牲其他类型的计算为代价——我的第二个错误？:-)

编辑：例如：

（我或多或少地将数字存储在右侧，没有逗号，加上一些元数据开销）。（虽然有人可能会认为“随着基数的增加，您将使用更少的“1”位来表示给定的数字”，或者“随着基数的增加，您将使用更少的非零数字来表示给定的数字”，以上示例表明这并不总是正确的。）

我将每个数字存储为一个小整数（“int”或“long int”或“byte”）。有没有其他合理的方式来存储数字？我很确定我的计算机以二进制形式存储这些整数——每个“1”、“2”、“4”、“8”和“G”数字使用一个“1”位；每个“3”、“5”、“6”、“9”和“A”数字使用两个“1”位；每个“7”和“B”位使用三个“1”位；每个“F”位使用四个“1”位，依此类推。

该值的十进制和十八进制表示（16！）都需要 14 个“1”位。所以我在之前的计算中犯了一个错误：对于每一个n，代表n！以八进制表示的“1”位并不总是比以十进制表示相同的值少。但是问题仍然存在：是否还有其他一些“最佳”基数需要最少的 1 位来存储大阶乘？

有人问：“你如何存储这些数字？” 好吧，这正是我的问题——存储 n 形式的数字的最佳方式是什么！? 我可以在内部使用以 10 为基数的数字，或以 2 的幂为基数，或以 18 为基数，或以其他一些为基数。哪个最好？我可以在内部将这些整数存储为一维数字数组，但长度需要很长才能存储所有数字。有什么合理的方法可以打印出100！十进制没有这样的数组？

我试图弄清楚如何从头开始实施 RSA 加密（仅用于智力练习），我坚持这一点：

对于加密，c = m ^e mod n

现在，e 通常是 65537。m 和 n 是 1024 位整数（例如 128 字节数组）。这对于标准方法来说显然太大了。你将如何实现这一点？

我在这里读了一些关于幂运算的文章，但对我来说并没有点击：

维基百科-平方求幂

本章（见第 14.85 节）

谢谢。

编辑：也发现了这个 - 这是我应该看的更多吗？维基百科-模幂

我正在尝试为 bignums 实现长除法。不幸的是，由于嵌入式编程的限制，我不能使用像 GMP 这样的库。此外，我想要学习如何实施它的智力练习。到目前为止，我已经使用任意长度的字节数组完成了加法和乘法（所以每个字节就像一个 base-256 数字）。

我只是想开始实施除法/模数，我想知道从哪里开始？我在网上发现了很多高度优化（又名不可读）的代码，这对我没有帮助，而且我发现了很多高科技的数学白皮书，我无法从中弥合理论和实现之间的差距.

如果有人可以推荐一种流行的算法，并为我指出一个易于理解的易于实现的解释，那就太好了。

-edit：我需要在被除数为~4000bits，除数为~2000bits 时工作的算法

-edit：这个算法是否适用于 base-256 ？http://courses.cs.vt.edu/~cs1104/BuildingBlocks/divide.030.html

-编辑：这是我真正应该使用的算法（牛顿除法）吗？http://en.wikipedia.org/wiki/Division_(digital)#Newton.E2.80.93Raphson_division