9

(私は、主にとを介して 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.
ライセンス GPLv3+: GNU GPL バージョン 3 以降
これはフリー ソフトウェアです。自由に変更して再配布してください。
法律で許可されている範囲で、保証はありません。「コピーを表示」と入力します
詳細については、「保証を表示する」を参照してください。
この GDB は「i486-linux-gnu」として構成されました。
バグ報告の手順については、次を参照してください。
...
/opt/gupu/src/yap-6.3/narch-gupu2/yap からのシンボルの読み込み...完了。
(gdb) 実行 -f
プログラムの開始: /opt/gupu/src/yap-6.3/narch-gupu2/yap -f
YAP 6.3.2 (i686-linux): 2012 年 11 月 11 日 04:19:37 CET
?- X は 13^1150000000 です。

プログラム受信信号 SIGSEGV、セグメンテーション違反。
0x001638d8 in ?? () /usr/lib/libgmp.so.3 から
(gdb) ところで
#0 0x001638d8 in ?? () /usr/lib/libgmp.so.3 から
#1 /usr/lib/libgmp.so.3 からの __gmpn_mul_fft () の 0x00164470
#2 /usr/lib/libgmp.so.3 からの __gmpn_mul_fft_full () 内の 0x001646c2
#3 /usr/lib/libgmp.so.3 からの __gmpn_sqr_n () 内の 0x00165f28
#4 /usr/lib/libgmp.so.3 からの __gmpz_n_pow_ui () の 0x0014b58b
#5 /usr/lib/libgmp.so.3 からの __gmpz_pow_ui () 内の 0x0014c4a1
#6 ../C/gmp_support.c:939 の Yap_gmp_exp_int_int (i1=13、i2=1150000000) の 0x080c4a1d
#7 0x0815f9df in p_exp (t1=, t2=3082051592) at ../C/arith2.c:609
../C/eval.c:147 の評価 (t=0) で #8 0x080b1f19
#9 p_is () の 0x080b2251 at ../C/eval.c:186
#10 ../C/absmi.c:6912 の Yap_absmi (inp=0) の 0x0806b56a
#11 ../C/exec.c:1002 の exec_absmi (top=) の 0x080b3655
#12 0x080b3b1f in do_goal (t=, CodeAdr=, アリティ=,
    pt=0x0、top=1) ../C/exec.c:1068
#13 Yap_RunTopGoal の 0x080b3d1d (t=135918154) ../C/exec.c:1291
#14 0x08061a6f in YAP_RunGoalOnce (t=135918154) at ../C/c_interface.c:2511
#15 do_top_goal の 0x0805c2f5 (argc=2, argv=0xbffff4c4) at ../console/yap.c:84
#16 exec_top_level (argc=2, argv=0xbffff4c4) at ../console/yap.c:131
#17 メイン (argc=2, argv=0xbffff4c4) at ../console/yap.c:172
(gdb)

編集:これは 64 ビット システムにも当てはまります。そのようです：

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 によるものです)。

4

5 に答える 5

5

本当の答えではありませんが、SWI-Prolog が行うことの説明です。まず、オーバーフローが発生する可能性があるかどうかを推定します。確実な場合は、GMP を呼び出す前にエラーが発生します。それ以外の場合は、GMP 割り当てフックに依存し、失敗時に longjmp() を実行します。どの割り当てが何に対して行われたかを追跡し、中止された GMP 操作に割り当てられたメモリの割り当てを解除します。これが可能なのは、メモリが GMP の制御下に永続的に置かれることはないためです。成功した GMP 計算の結果は Prolog スタックにコピーされ、Prolog メモリ管理の対象となります。

これは以前は機能していましたが、最近のバージョンでは機能しません。GMP はサイズを推定し、これが失敗することがわかっている場合は malloc() フックを呼び出すことさえしないのではないかと思います。必要なのは、途方もなく大きな値であっても、フックが常に呼び出されるようにする方法だけです。size_t が表現できるものよりも大きいものはすべて、(size_t)-1 でフックを呼び出すことができます。

（小さい）Prologランタイムスタックへのコピーのため、メモリが保存できるよりもはるかに早くオーバーフローします。

于 2013-01-09T20:11:46.367 に答える
4

この問題を回避するために一部の人が行っていること (サポートされておらず、メモリ リークが発生しますが、何もしないよりはましです): GMP では、代替アロケータ (mp_set_memory_functions) を指定できます。このアロケーターから malloc を呼び出すことができます。それが失敗した場合は、C++ 例外をスローするか (gcc を使用している場合は、-fexceptions を使用して gmp を再コンパイルしてください)、longjmp などを呼び出して GMP の失敗処理をバイパスし、制御しているコードに戻ることができます。

于 2013-01-09T15:40:43.557 に答える
2

13^1,150,000,000は約2^4,255,505,675で、表現に4,255,505,675ビットかかります。1バイトあたり8ビットの場合、これは約500MBのメモリです。収まるようです。

おそらく、計算に関係する一時変数がいくつかあり、プロセスサイズの制限を超えています。

于 2012-12-11T22:52:46.493 に答える
2

さて、私は運が悪いようです：

最新バージョンでも

   fprintf (stderr, "gmp: mpz 型のオーバーフロー\n");
   中止 ();

少なくともこのオーバーフローは処理され、エクスプロイトとして使用することはできません。

また、この問題のない GMP を使用するシステムでは、変更されたライブラリを使用するか、サイズを見積もるための機能を複製する必要があります。

于 2012-11-14T14:54:53.337 に答える
1

あなたがクレイを置いているなら、それはうまくいくように見えます。

#if defined (_CRAY) && ! defined (_CRAYMPP)
/* plain `int' is much faster (48 bits) */
#define __GMP_MP_SIZE_T_INT     1
typedef int         mp_size_t;
typedef int         mp_exp_t;
#else
#define __GMP_MP_SIZE_T_INT     0
typedef long int        mp_size_t;
typedef long int        mp_exp_t;
#endif
于 2012-12-13T02:04:06.350 に答える