manipolazione in GMP pow

Question

Overflow (io sono solo un utente indiretta del GMP-biblioteca principalmente attraverso swi-prolog e yap. Ma io sono molto interessato a risoluzione di questo problema.)

Quando si esegue exponentiations con valori ridicolmente grandi, i sistemi host o GMP non sono più in grado di gestire gli overflow in modo appropriato. Ho parlato con gli sviluppatori dei sistemi di cui sopra, ma non vedono una soluzione semplice per questo.

Questo problema è noto ad altri sistemi/utenti GMP? Come gestisci tali overflow?

Come controllo di integrità prima verificare il valore 7^7^7 che dovrebbe essere: 375.982 ... 32343

Nei sistemi a 32-bit, per esempio le rese interrogazione ?- X is 13^1150000000. come un overflow. Ecco ciò che dà 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 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: Questo è vero anche per i sistemi a 64 bit; in questo modo:

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 

Tuttavia,

?- X is 2^2^63. 
ERROR: Out of global stack 
?- X is 2^2^62. 
gmp: overflow in mpz type 
Abort 

E dal basso:

?- X is 2^2^36. 
ERROR: Out of global stack 
?- X is 2^2^37. 
gmp: overflow in mpz type 
Abort 

Quindi, se il numero è abbastanza grande, l'errore viene rilevato da SWI - e quindi possono essere gestito da SWI (The ERROR: message is by SWI).

Answer 1

Bene, sembra che io sono fuori di fortuna:

Even the most recent version fa

 
    fprintf (stderr, "gmp: overflow in mpz type\n"); 
    abort(); 

Almeno questo overflow viene gestito e non può essere utilizzato come un exploit.

E qualsiasi sistema utilizzando GMP che non ha questo problema deve utilizzare una libreria modificata o duplicare la funzionalità per la stima della dimensione.

Answer 2

13^1.150.000.000 è di circa 2^4.255.505,675 mila che prendono 4,255,505,675 bit per rappresentare. Con 8 bit per byte, si tratta di circa 500 MB di memoria. Sembra che dovrebbe adattarsi.

Forse ci sono una coppia di variabili temporanee coinvolti nel calcolo e superato il limite di dimensione processo.

Answer 3

Sembra che se si dispone di un Cray, che in giro, che avrebbe funzionato.

#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 

Answer 4

Qualcosa che alcune persone fanno per aggirare il problema (non supportata e perde un po 'di memoria, ma trovano che sia meglio di niente): GMP consente di specificare un allocatore di sostituzione (mp_set_memory_functions). Da questo allocatore, puoi chiamare malloc e se fallisce puoi lanciare un'eccezione C++ (se usi gcc, per favore ricompila gmp con -fexceptions) o chiama longjmp o qualcosa di simile per bypassare la gestione degli errori di GMP e tornare al codice che controlli.

Answer 5

Non proprio una risposta, ma una spiegazione che cosa fa SWI-Prolog.Prima di tutto, stima se potrebbe verificarsi un overflow. Se è sicuro, genererà un errore prima di chiamare GMP. Altrimenti, lo si basa sul gancio di allocazione GMP ed esegue un longjmp() in caso di errore. Tiene traccia di quali allocazioni vengono effettuate per cosa e rilascia la memoria allocata per l'operazione GMP interrotta. Lo può farlo perché la memoria non è mai sotto controllo permanente di GMP. I risultati dei calcoli GMP con successo vengono copiati nello stack di Prolog e soggetti alla gestione della memoria di Prolog.

Questo funzionava, ma non funziona nelle versioni recenti. Sospetto che GMP stima la dimensione e non si preoccupi nemmeno di chiamare l'hook di malloc() se sa che questo fallirà. Tutto ciò di cui ho bisogno è un modo per assicurarsi che il gancio venga sempre chiamato, anche con un valore ridicolmente grande. Tutto ciò che è più grande di ciò che size_t può rappresentare potrebbe chiamare il gancio con (size_t) -1.

P.s si espande molto prima di quello che la memoria può memorizzare a causa della copia degli stack (più piccoli) di runtime di Prolog.