标签: gmp

我正在尝试为bignums实施长期划分.由于嵌入式编程的局限性,遗憾的是我无法使用像GMP这样的库.此外,我希望学习如何实施它的智力练习.到目前为止,我已经使用任意长度的字节数组完成了加法和乘法运算(所以每个字节就像一个基数为256的数字).

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

如果有人可以推荐一个流行的算法,并指出一个简单易懂的解释,倾向于implmenentation,那就太棒了.

-edit:我需要的算法在被除数为~4000位时有效,除数为~2000位

-edit:这个算法能用base-256吗？http://courses.cs.vt.edu/~cs1104/BuildingBlocks/divide.030.html

-edit:这是我真的应该使用的算法(牛顿师)吗？http://en.wikipedia.org/wiki/Division_(digital)#Newton.E2.80.93Raphson_division

2 ^ 64离我的ram /硬盘可以处理的"无限"还有一段距离......

首先我想知道GMP如何与内存/处理器一起工作,因为它做了一些阴暗的优化......

我还想知道是否有一种方法可以在任意数量的字节上存储一个整数(无符号,更容易).例如,在50个字节上,我的上限为2 ^ 400 -1.要做的是使用携带以保持数字从一个字节到另一个字节保持一致,我对此有一些了解,但我真的不确定它是最快的方法.我甚至不确定我是否正确.

我猜GMP使用这种方式来存储它的数据,但我只想要一些(甚至很少)解释或某些理论转发(我没有任何博士学位,所以不要太难).

似乎GMP只提供了mpf(浮点)类型的字符串序列化:

mpf_get_str(), mpf_class::get_str()

mpz(整数)类型具有原始字节的附加接口: mpz_out_raw()

http://gmplib.org/manual/Function-Index.html

我错过了什么吗？有谁知道另一个可以序列化GMP浮点数的库？有谁知道另一个提供强大序列化的bignum lib？

编辑:我很高兴序列化MPFR的mpfr_t,同样似乎只提供字符串输出:http://www.mpfr.org/mpfr-current/mpfr.html#Function-Index

以下代码输出0,这是不正确的:

$r = gmp_pow(gmp_init('-1.7976931348623157'), 308);
echo gmp_strval($r);

我的印象是GMP库能够处理浮点数,或者我在代码中犯了错误？

作为漫长而肮脏的故事的一部分,其最终目标只是安装GMP以与Windows中的code :: blocks一起使用,我正在尝试配置gmp.我使用以下命令执行此操作:

./configure --prefix = $ {gmp_install}

一切都开始得很好.几分钟后,一点点进展,一切都停止了,我得到这个消息:

configure:error:$ PATH或/ usr5bin中没有可用的M4

我甚至不知道M4是什么,但我发现它是某种宏处理器.所以我下载它,并将文件夹添加到我的Path变量.然后我再次启动配置,但结果相同.

我需要做些什么让M4让它运转起来吗？我真的很茫然.谢谢你的帮助.

GMP库中是否有任何对数函数？

(我只是主要通过swi-prolog和yap的GMP库的间接用户.但我对解决这个问题非常感兴趣.)

当使用可笑的大值执行取幂时,主机系统或GMP不再能够适当地处理溢出.我已经与上述系统的开发人员进行了交谈,但他们没有看到一个简单的解决方案.

这个问题是否为其他GMP系统/用户所知？你如何处理这种溢出？

作为一个完整性检查首先测试7 ^ 7 ^ 7的值应该是:375982 ... 32343

例如,在32位系统上,查询会?- X is 13^1150000000.产生这样的溢出.以下是YAP给出的内容:

GNU gdb (GDB) 7.0-ubuntu
Copyright (C) 2009 Free Software Foundation, Inc.
License GPLv3+: GNU GPL version 3 or later 
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law.  Type "show copying"
and "show warranty" for details.
This GDB was configured as "i486-linux-gnu".
For bug reporting instructions, please …

对我之前的问题的回答表明Haskell表示plusWord2#为llvm.uadd.with.overflow.我希望使用进位进行长时间的添加,就像x86 ADC指令的工作方式一样.该指令不仅添加了两个参数,还添加了进位的内容.

然后可以添加如下的长数字:

ADD x1 y1
ADC x2 y2
ADC x3 y3
...

导致每个单词一个指令(忽略所需的任何周围移动等).

我查看了GMP库,以及它在通用C代码中如何进行长时间的添加.这是摘录自mpn/generic/add_n.c

sl = ul + vl;
cy1 = sl < ul;
rl = sl + cy;
cy2 = rl < sl;
cy = cy1 | cy2;

注意,它保存了原始加法和进位位加法的进位.这些操作中只有一个可以携带,因此或者之后的携带就足够了.

显然,GMP具有针对特定平台的特定汇编代码,但我认为通用代码是一个很好的基础,因为它可能被编写为编译成合理的代码.在plusWord2#原始的操作手段,我不需要做无聊的比较,以获得进位,所以我实现了GMP的通用代码就像在Haskell如下:

addWithCarry :: Word# -> Word# -> Word# -> (# Word#, Word# #)
addWithCarry x y c =
  let 
    (# c1, r1 #) = plusWord2# x y
    (# c2, r2 …

• 我想知道在MSP430上是否有任何方法,如果可能的话,用任何简单的方法对大于64位的整数进行算术运算？

我之所以这么具体,是因为我正在尝试在msp430g2553平台上实现加密算法(RSA,AES,哈希函数,数字签名等).

我通过互联网搜索,并通过误导的绝望,我安装了Linux发行版,以便使用GMP,但失败了.我安装了Kali,然后安装了一个USB(2.0)棒上的Lubuntu ,只是因为无法忍受的冻结而受到影响,并且不知道它是否会起作用.后来尝试了VMBox的魔力,之后事情变得更容易了,虽然没有定论.我最终得到了一个点mps430-gcc和mspdebug,我可以调试一些示例代码,并看到它们工作,但仍然无法进行GMP操作,因为主要是库错误(未定义引用mpz_t init ...等) .

据我所知,GMP是一个用于特定处理器架构的多精度算术库,而MSP430不是其中之一,但是,在这一点上,如果它是其中之一,我不会感到惊讶.我得到的最佳答案是,一些TI员工对此并不熟悉.所以;

• 是否可以在MSP430上使用GMP,或者更具体地说在msp430g2553上使用GMP？

我几乎没有在谷歌上看到任何与gmp交叉引用msp430的东西,而我正在努力实现一个可怜的64位密钥大小的RSA,如果有的话,几乎不能正常工作.所以我希望这篇文章及其答案可以帮助某些人,并希望以后能够帮助我.

我也忘了提到,我已经阅读了遗物工具包,(但是没有花时间尝试实施它,因为GMP看起来更像是该领域的标准),我想知道:

• 是否有可以链接的假人遗物指南,如果可以在MSP430上使用它,可以再次使用吗？

感谢大家.

我不确定这是不是一个bug.但我一直在玩,big我不明白为什么这段代码以这种方式工作:

https://carc.in/#/r/2w96

码

require "big"

x = BigInt.new(1<<30) * (1<<30) * (1<<30)
puts "BigInt: #{x}"

x = BigFloat.new(1<<30) * (1<<30) * (1<<30) 
puts "BigFloat: #{x}"
puts "BigInt from BigFloat: #{x.to_big_i}"

产量

BigInt: 1237940039285380274899124224
BigFloat: 1237940039285380274900000000
BigInt from BigFloat: 1237940039285380274899124224

首先,我认为BigFloat需要更改 BigFloat.default_precision为更大的数字.但是从这段代码看起来它只在尝试输出#to_s值时才有意义.

与BigFloat的精度设置为1024(https://carc.in/#/r/2w98)相同:

产量

BigInt: 1237940039285380274899124224
BigFloat: 1237940039285380274899124224
BigInt from BigFloat: 1237940039285380274899124224

BigFloat.to_s用途LibGMP.mpf_get_str(nil, out expptr, 10, 0, self).GMP在哪里说:

mpf_get_str (char *str, mp_exp_t *expptr, int base, size_t n_digits, const mpf_t op)

将op转换为基数中的数字字符串.基本参数可以在2到62之间或从-2到-36之间变化.最多将生成n_digits数字.不返回尾随零.不会产生比op准确表示的数字更多的数字. …