Newsgroup: it.comp.lang.c
Titolo: Addizione modulo 2^64

Ciao a tutti,
ho due variabili del tipo "unsigned long long int", che quindi hanno 64
bit.
Ora devo calcolarne la somma mod 2^64.
Ho provato cosi':
Pout[0] = (Pin[0] + Pin[1]) % 18446744073709551616;
e cosi':
Pout[0] = (Pin[0] + Pin[1]);
Nel primo caso il compiler dice
warning: integer constant is too large for its type
warning: division by zero
e facendo partire il programma ottengo una "floating exception".
Nel secondo caso il compiler non dice nulla. Il mio ragionamento � che
avendo 64 bits a disposizione, il riporto va perso e automaticamente
ottengo una somma modulo 2^64.
Mi sbaglio?
C'� qualche soluzione pi� pulita?
Grazie e ciao
Boiler
-- 
questo articolo e` stato inviato via web dal servizio gratuito 
http://www.newsland.it/news
 segnala gli abusi ad 
ab...@newsland.it

 Mi sbaglio? C'è qualche soluzione piú pulita?
Ciao
Giovanni
-- 
   A computer is like an air conditioner,
   it stops working when you open Windows.
   < 
http://giovanni.homelinux.net/
 >

 C'� qualche soluzione pi� pulita?
Perch� ti interessa fare le operazioni modulo 2^64? E' un caso che 64 
sia proprio la dimensione degli interi usati dalla tua CPU, oppure l'hai 
scelto apposta? A seconda di come rispondi a questa domanda la soluzione 
"pi� pulita" � diversa. Nel senso che bisognerebbe capire cosa ti 
aspetti che faccia il tuo programma su una macchina a 32 bit, oppure su 
una ipotetica macchina a 128 bit.
E.

 scelto apposta?
Ho scelto unsigned long long perch� ho visto che � largo 8 bytes e quindi
ci stanno i numeri che mi servono.
/proc/cpuinfo dice quanto segue:
model name      : Intel(R) Core(TM)2 Duo CPU     E8600  @ 3.33GHz
Credo (ma non sono sicuro) che sia un processore a 64 bits.
Il codice che sto scrivendo girer� al 99% solo ed esclusivamente su questa
macchina, ma non posso escludere il caso contrario.
Per questo chiedo se il mio approccio � corretto o meno.


 #define ULLONG_MAX   18446744073709551615ULL
Cosa fa esattamente questo comando?
Immagino che serva a settare il limite per il suddetto formato a 2^64-1.
E quindi se supero questo limite il numero "wrappa around"?


 ci stanno i numeri che mi servono.
No, in 64 bit ci stanno numeri fino a 2^64-1.
--
Andrea Bergia

Andrea Bergia ha scritto:


Esatto, e se tutte le addizioni sono modulo 2^64 il massimo che
raggiunger� � il valore da te citato.


 E quindi se supero questo limite il numero "wrappa around"?
Ho semplicemente riportato dal file <limits.h> la define di ULLONG_MAX 
per mostrarti come devi scrivere un numero a 64 bit


 raggiunger� � il valore da te citato.
No, perch� non puoi "scrivere" il numero 2^64 in una variabile, dato che
la sua rappresentazione binaria, in un ulong da 64 bit, � zero. Cio�,
scrivere 18446744073709551616 o scrivere 0 � la stessa cosa. Non puoi
fare il modulo per 2^64. Allo stesso modo, non puoi fare la somma di
numeri come 2^63 + 10 e 2^64 - 5, perch� la loro somma andrebbe in
overflow.
Se proprio devi fare operazioni modulo 2^64, hai bisogno di qualche
libreria che ti permetta di usare numeri di quella lunghezza. 
--
Andrea Bergia

 ci stanno i numeri che mi servono.
Varrebbe forse la pena usare uint64_t?
E' la stessa cosa, ma rende piu' chiaro a chi legge il codice cos'e' che
vuoi fare esattamente.
Pleg

 fare il modulo per 2^64.
Intendi dire che non puo' scrivere (n % 18446744073709551616) ?
Perche' il modulo 2^64 si' che lo puo' fare, basta non fare niente e
lasciare che i calcoli facciano wrap around automaticamente.
Pleg

 Varrebbe forse la pena usare uint64_t?
Con questo data type avrei la certezza che indipendentemente
dall'architettura, la memoria allocata � 64 bit, giusto?
E le addizioni le posso fare normali e automaticamente risultano wrappate,
giusto?
Grazie e ciao


 lasciare che i calcoli facciano wrap around automaticamente.
No, dar� overflow, che immagino (non ho voglia di provare) verr� gestito
dal runtime terminando il programma.
--
Andrea Bergia

Andrea Bergia ha scritto:


test = 18446744073709551615 + due;
dove test � del tipo "unsigned long long int" mentre due � uno "short int"
che contiene, ovviamente il valore 2.
Se mi faccio outputtare test con printf, ottengo 1.
Ergo funziona :-)


 giusto?
Io dico di si'... ma ne sto discutendo in un altro ramo del thread. In
hardware, ci metto la mano sul fuoco che e' quello che succede :) delle
interazioni col software, non sono sicuro al 100%.
Pleg

 dal runtime terminando il programma.
Ho provato questo:
#include <stdio.h>
#include <stdlib.h>
#include <inttypes.h>
int main()
{
        uint64_t a, b, c;
 
        a = 9223372036854775808ULL;     // 2^63
        b = 18446744073709551615ULL;    // 2^64 - 1
        c = a + b - 5;
 
        printf("%"PRIu64"\n%"PRIu64"\n%"PRIu64"\n", a, b, c);
 
        return 0;
}
compilato su linux con gcc 4.3.2 con
gcc -Wall -std=c99 test.c -o test
macchina con processore Intel Core 2 Duo (stessa famiglia di quello
dell'OP).
Nessun warning in compilazione, il programma ha eseguito senza problemi,
dando come risultato 9223372036854775802, che e' appunto mod(2^63 + 2^64 -
1 - 5, 2^64).
Immagino che se desse errore sarebbe un segnale SIGFPE ? Nel caso, potrebbe
gestirlo ignorandolo?
Pleg

 hardware, ci metto la mano sul fuoco che e' quello che succede :)
Ironia della sorte... sto facendo proprio il golden model per
un'implementazione hardware ;-)


 un'implementazione hardware ;-)
AH AH AH fantastico :)
I problemi del Golden Reference Model :D
Vien fuori che il tuo C ha dei problemi, e il tuo Verilog funziona
perfettamente :D
Cmq, come dicevo nell'altro ramo del thread, a me la cosa sembra funzionare.
Pero' vediamo, magari ci sono magagne sottili.
Al limite, potresti usare qualche libreria numerica per numeri "grandi" (ad
es. 
http://gmplib.org/
)?
Pero' potresti aver problemi di licenza e di performance.
Pleg

Andrea Bergia ha scritto:

No, affatto. Gli unsigned sono fatti apposta per lavorare in modulo 2^N, 
si pu� sfruttare questa particolarit� senza tema. Anzi, mi sono convinto 
che la semantica di "unsigned" � pi� questa che non la propriet� di 
essere sempre positivi.
E.

 sempre positivi.
Grazie della conferma, mi hai tolto un dubbio che ogni tanto mi riaffiorava 
da un pezzo.
Nel caso, segnalo dove l'ho appena trovato: Harbison&Steele, "C - A 
reference manual", fifth edition, pagina 129:
"Whether an integer is signed or unsigned affects the operations performed 
on it. All arithmetic operations on unsigned integers behave according to 
the rules of modular arithmetic modulo 2^n. [...] The behaviour of overflow 
is well defined."
Quindi, per Boiler: vai tranquillo che uint64_t fa esattamente quello che fa 
l'hardware che devi simulare :)
Pleg

 gestirlo ignorandolo?
Credo sia una questione dipendente dal sistema. Cio� � possibile che ci
siano sistemi/processori in cui il wrap around � automatico ed altri in
cui lo sforamento viene appunto gestito come overflow. Qunado si lavora
sui "limiti" non si pu� assumere nulla per certo.


 is well defined."
"The behaviour of overflow is well defined" � una conferma di ci� che �
scritto nel periodo precedente? Ovvero si pu� star certi che non ci sar�
mai overflow come "eccezione" ma tutti i calcoli tra unsigned avverranno
sempre in modulo 2^n, con n = numero di bit per il tipo unsigned specifico?


 cui lo sforamento viene appunto gestito come overflow.
Stando a quel che dice l'H&S questo non dovrebbe essere possibile...


 l'hardware che devi simulare :)
Perfetto, grazie a tutti!
Tra l'altro, � stato il mio primo thread su questo NG. E sono rimasto
impressionato dalla competenza e cortesia.
Grazie ancora


 specifico?
Si'.
Copio il periodo completo (ieri sera ero stanco e andavo di fretta):
"Whether an integer is signed or unsigned affects the operations performed 
on it. All arithmetic operations on unsigned integers behave according to 
the rules of modular (congruence) arithmetic modulo 2^n. So, for example, 
adding 1 to the largest value of an unsigned type is guaranteed to produce 
0. The behaviour of overflow is well defined."
Pleg

 Sì, è così.
non sempre, dipende dalla CPU.
quella che uso io ad esempio puo' saturare i risultati se metto a 1 un
bit nel registro di status della PCU prima dell'operazione.
Ciao Jack

 bit nel registro di status della PCU prima dell'operazione.
Si, ma il compilatore C questo lo sa e si comporter� di conseguenza. 
Almeno credo... hai fatto la prova con del codice C?
E.

 sui "limiti" non si pu� assumere nulla per certo.
Al di la del sistema sottostante, lo standard dice che la semantica
degli unsigned e' quella di aritmetica modulo 2^sizeof(unsigned integer
type).
"""
A computation involving unsigned operands can never overflow, because a
result that cannot be represented by the resulting unsigned integer type
is reduced modulo the number that is one greater than the largest value
that can be represented by the resulting type.
""" (C99 standard, 6.2.5 punto 9) 
-- 
-riko

 Almeno credo... hai fatto la prova con del codice C?
devo usare delle funzioni "intrinsiche", cioe' funzioni (fornite dal
produttore) contenenti assembly per utilizzare alcune features della
CPU, come la saturazione oppure l'istruzione mac (multiply and
accumulate).
La CPU e' un 56000/E della Freescale.
Ciao Jack

> La CPU e' un 56000/E della Freescale.
Quello e' un DSP, con cui notoriamente fai cose un po' diverse e che ha
appunto istruzioni particolari (come MAC con saturazione, eccetera).
Qui si parlava di C, e quello che lo standard dice e' stato riportato
nell'altro ramo del thread.
Pleg