GMP战俘中的溢出处理 [英] Overflow handling in GMP pow
问题描述
(我只是GMP库的间接用户，主要是通过 swi-prolog 和 yap.但是我对解决此问题非常感兴趣.)
(I am only an indirect user of the GMP-library primarily through swi-prolog and yap. But I am very much interested in fixing this problem.)
当执行具有非常大的值的幂运算时，主机系统或GMP将不再能够适当地处理溢出.我已经与上述系统的开发人员进行了交谈，但是他们没有看到简单的解决方法.
When performing exponentiations with ridiculously large values, the host-systems or GMP are no longer able to handle the overflows appropriately. I have talked to the developers of above systems, but they do not see an easy fix for this.
其他GMP系统/用户是否知道此问题?您如何处理此类溢出?
Is this problem known to other GMP systems/users? How do you handle such overflows?
作为健全性检查，请首先测试7 ^ 7 ^ 7的值，该值应为:375982 ... 32343
As a sanity check first test the value for 7^7^7 which should be: 375982...32343
在32位系统上，例如查询?-X为13 ^ 1150000000.会产生这样的溢出.这是YAP提供的:
On 32-bit systems, for example the query ?- X is 13^1150000000. yields such an overflow. Here is what YAP gives:
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 see:
...
Reading symbols from /opt/gupu/src/yap-6.3/narch-gupu2/yap...done.
(gdb) run -f
Starting program: /opt/gupu/src/yap-6.3/narch-gupu2/yap -f
YAP 6.3.2 (i686-linux): Sun Nov 11 04:19:37 CET 2012
?- X is 13^1150000000.
Program received signal SIGSEGV, Segmentation fault.
0x001638d8 in ?? () from /usr/lib/libgmp.so.3
(gdb) bt
#0 0x001638d8 in ?? () from /usr/lib/libgmp.so.3
#1 0x00164470 in __gmpn_mul_fft () from /usr/lib/libgmp.so.3
#2 0x001646c2 in __gmpn_mul_fft_full () from /usr/lib/libgmp.so.3
#3 0x00165f28 in __gmpn_sqr_n () from /usr/lib/libgmp.so.3
#4 0x0014b58b in __gmpz_n_pow_ui () from /usr/lib/libgmp.so.3
#5 0x0014c4a1 in __gmpz_pow_ui () from /usr/lib/libgmp.so.3
#6 0x080c4a1d in Yap_gmp_exp_int_int (i1=13, i2=1150000000) at ../C/gmp_support.c:939
#7 0x0815f9df in p_exp (t1=, t2=3082051592) at ../C/arith2.c:609
#8 0x080b1f19 in Eval (t=0) at ../C/eval.c:147
#9 0x080b2251 in p_is () at ../C/eval.c:186
#10 0x0806b56a in Yap_absmi (inp=0) at ../C/absmi.c:6912
#11 0x080b3655 in exec_absmi (top=) at ../C/exec.c:1002
#12 0x080b3b1f in do_goal (t=, CodeAdr=, arity=,
pt=0x0, top=1) at ../C/exec.c:1068
#13 0x080b3d1d in Yap_RunTopGoal (t=135918154) at ../C/exec.c:1291
#14 0x08061a6f in YAP_RunGoalOnce (t=135918154) at ../C/c_interface.c:2511
#15 0x0805c2f5 in do_top_goal (argc=2, argv=0xbffff4c4) at ../console/yap.c:84
#16 exec_top_level (argc=2, argv=0xbffff4c4) at ../console/yap.c:131
#17 main (argc=2, argv=0xbffff4c4) at ../console/yap.c:172
(gdb)
Edit:对于64位系统也是如此；像这样:
This is also true for 64-bit systems ; like so:
Welcome to SWI-Prolog (Multi-threaded, 64 bits, Version 6.3.5)
Copyright (c) 1990-2012 University of Amsterdam, VU Amsterdam
SWI-Prolog comes with ABSOLUTELY NO WARRANTY. This is free software,
and you are welcome to redistribute it under certain conditions.
Please visit http://www.swi-prolog.org for details.
For help, use ?- help(Topic). or ?- apropos(Word).
?- X is 3445^2^62.
gmp: overflow in mpz type
Abort
但是，
?- X is 2^2^63.
ERROR: Out of global stack
?- X is 2^2^62.
gmp: overflow in mpz type
Abort
并从下面:
?- X is 2^2^36.
ERROR: Out of global stack
?- X is 2^2^37.
gmp: overflow in mpz type
Abort
因此，如果数量足够大，则SWI会检测到错误-从而可以由SWI处理(错误:消息由SWI来解决.)
So, if the number is large enough, the error is detected by SWI - and thus can be handled by SWI (The ERROR: message is by SWI).
推荐答案
不是真正的答案，而是对SWI-Prolog的解释.首先，它估计是否可能会发生溢出.如果可以确定，它将在调用GMP之前引发错误.否则的话依赖于GMP分配钩子，并在失败时执行longjmp().它跟踪哪个对什么进行分配，并取消分配为中止的GMP操作分配的内存.它之所以可以这样做，是因为内存永远不会永远受到GMP的控制.成功的结果GMP计算将复制到Prolog堆栈中，并接受Prolog内存管理.
Not really an answer, but an explanation what SWI-Prolog does. First of all, it estimates whether an overflow may occur. If it is sure, it will raise an error before calling GMP. Otherwise, it relies on the GMP allocation hook and performs a longjmp() on failure. It keeps track of which allocations are made for what and deallocates memory allocated for the aborted GMP operation. It can do so because memory is never permanently under control of GMP. The results of successful GMP computations are copied to the Prolog stack and subject to Prolog memory management.
这曾经起作用，但是在最新版本中不起作用.我怀疑GMP会估计大小如果知道这将失败，甚至不用费心调用malloc()钩子.我所需要的是一种确保始终调用该钩子的方法，即使其值大得离谱.大于size_t可以表示的所有内容都可以使用(size_t)-1来调用该钩子.
This used to work, but it doesn't work in recent versions. I suspect that GMP estimates the size and doesn't even bother calling the malloc() hook if it knows this is going to fail. All I need is a way to make sure that the hook is always called, even with a ridiculously large value. Everything that is larger than what size_t can represent could call the hook with (size_t)-1.
P.s.由于复制到(较小的)Prolog运行时堆栈，它的溢出时间比内存可以存储的时间要早得多.
P.s. it overflows much earlier than what memory can store because of the copying to the (smaller) Prolog runtime stacks.
这篇关于GMP战俘中的溢出处理的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
