Newsgroup: it.comp.lang.c
Titolo: Sondaggio 2: Variabili globali (traendo ispirazione da "C'è il trucco?")

Immaginate di avere la funzione callf (di cui non conoscete
l'implementazione) con il seguente prototipo:
typedef void (*pf)();
void callf(pf *f, unsigned n, unsigned k);
La funzione callf riceve quindi un array di n puntatori a funzioni senza
parametri ed esegue una singola volta n-k funzioni, scelte tra le n
passatele, in ordine casuale. Vengono sempre eseguite n-k funzioni e
nessuna funzione viene eseguita più di una volta.
Il vostro compito è quello di ideare le funzioni f_1, ..., f_n in modo
da poter determinare (cambiano ad ogni esecuzione) quali sono le k
funzioni che non vengono chiamate. Dato che le funzioni non ammettono
parametri, dovrete usare delle variabili globali.
Lo scopo è quello di usare meno memoria possibile.
Come fareste per n = 2^32 - 1 e k = 2?
Kiuhnm
P.S. Si accetta, anzi si auspica, pseudo-codice parziale oppure una
descrizione del metodo, piuttosto che codice banalmente ridondante.
Attenzione: qualsiasi codice che superi il terabyte di lunghezza non 
verrà neppure preso in considerazione.

Il vostro compito [...]
Kiuhnm, solo una nota: questo gruppo nasce con scopi diversi da quelli
di raccogliere gli esercizi da te proposti.  Pubblica i tuoi
"esercizi" su un sito e cerca di rispettare il topic di questo gruppo.

 "esercizi" su un sito e cerca di rispettare il topic di questo gruppo.
---
it.comp.lang.c	Il linguaggio di programmazione C
Il newsgroup tratterà del linguaggio C, ideato da Brian W. Kernighan e 
Dennis
M. Ritchie.
[...]
Argomenti compresi:
  - Il linguaggio in generale;
  - Gli algoritmi;
  - Le ottimizzazioni;
  - La portabilità;
  - I sistemi di sviluppo.
---
Quindi il mio post è perfettamente "in topic".
Ti faccio anche notare che questo non è un helpdesk.
Prima di lamentarti leggi il manifesto.
Kiuhnm

Quindi il mio post è perfettamente "in topic".
Kiuhnm, il manifesto lo conosco bene, frequento questo ng da anni.
Pur non essendo quest ng un helpdesk, cosa su cui concordo pienamente,
non è neanche un luogo dove proporre esercizi da risolvere,
specialmente quando non hanno nulla di realmente educativo.
In generale, non è bene che il ng si focalizzi solo su determinati
argomenti ed io, ora che hai preso il via, non vorrei vedere
proliferare come funghi i tuoi "esercizi".  Io non ho detto che tu sia
del tutto off topic, ma preferirei (è il mio punto di vista) che si
discutesse di argomenti legati a problemi reali.

 del tutto off topic, ma preferirei (è il mio punto di vista) che si
Bene, adesso l'uno conosce il punto di vista dell'altro.
Kiuhnm

Come tutte le cose che non si capiscono.
E certo, spiegacela allora la validità educativa dei tuoi giocattoli
;-)

 ;-)
Le persone corrette e coerenti, prima mostrano di sapere la soluzione e 
poi contestano la validità del problema mostrando che la ricerca di tale 
soluzione non ha coinvolto elementi quali intuito, utilizzo di nozioni 
utili, ecc...
Dammi la tua soluzione al problema, altrimenti taci.
In caso contrario stai chiamando stupido un problema che non riesci 
neppure a risolvere.
Kiuhnm

 Come fareste per n = 2^32 - 1 e k = 2?
Dunque, la soluzione è brutta, sporca e cattiva.
Dato che, se non ho capito male, la funzione callf riceve un piccolissimo
array, che su un sistema a 32bit avrà una dimensione tipo 
17179869184
bytes, credo che si possa trovare un po' di spazio in quell'array per
memorizzare qualcosa di utile, anche se sì, non bisognerebbe modificare
l'array e blablabla.
Supponendo che l'array in posizione "i", contenga l'indirizzo di f_"i", avrò
bisogno di una variabile globale che contiene l'indirizzo dell'array
stesso. Quando viene chiamata la funzione f_"i", questa accederà all'array
(utilizzando la variabile globale), posizionandosi sull'elemento "i". A
questo punto modificherà il _primo_ bit dell'elemento (che è l'indirizzo
della funzione), impostandolo a 1 (ragionevolmente prima era a 0, in quanto
le funzioni in memoria non sono mappate ad indirizzi così alti). Dato che
la stessa funzione viene chiamata 1 sola volta non ci sono problemi di
segfault.
Quando callf avrà eseguito tutte le sue n-k funzioni, percorrerà l'array,
cambierà i bit da 1 a 0 (ripristinando gli indirizzi corretti) e quando
incontrarà un indirizzo con il primo bit a 0, saprà che la rispettiva
funzione non è stata chiamata. Ovviamente come soluzione è
inefficientissima (che fa rima con deficientissima), ma tu hai detto che lo
scopo è usare meno memoria possibile... in un sistema a 32bit, con questo
metodo, vengono usati solo 4 bytes.
-- 
none

 metodo, vengono usati solo 4 bytes.
ROTFL. Come ha fatto a sfuggirmi questa possibilità? :)
Aspetta che aggiungo una condizione al problema :)
Kiuhnm

 Come fareste per n = 2^32 - 1 e k = 2?
AGGIUNTA:
Onde evitare una soluzione banale, supponete che l'array passato a callf 
*non* sia una variabile globale e che quindi non sia utilizzabile da f.
Kiuhnm

 *non* sia una variabile globale e che quindi non sia utilizzabile da f.
Eddai... sentite, non usate l'array passato a callf!
Kiuhnm

 Eddai... sentite, non usate l'array passato a callf!
ok, _meno memoria possibile_ ma niente array, lol.
Dunque, suppongo di non compilare con -fomit-frame-pointer e di essere su
x86-32:
dato che ogni funzione ha come prologo "push ebp", che ha come opcode \x55,
le funzioni f_i saranno più o meno così:
#define PAGE 0x1000
void f_1()
{
char *p;
p=&f_1;
/*
blah
*/
mprotect((int)p&~(PAGE-1),0x1000,PROT_READ|PROT_WRITE|PROT_EXEC);
*p+=1;
}
La funzione callf non dovrà fare altro che scorrere l'array dei puntatori a
funzione per trovare quelle che hanno il prologo ancora a \x55 (quelle non
eseguite). Negli altri casi correggerà gli opcode modificati riportando
tutto alla normalità:
#define PROLOGUE 0x55
void (*p[])();
char *c;
/*
uiui
*/
for(i=0;i<$numeromoltomamoltoalto;i++){
        c=p[i];
        if (*c==PROLOGUE) printf("funzione %d non eseguita\n",i);
        else *c-=1;
}
Ancora meno efficiente del metodo precedente, ma questa volta spreca 0 bytes
di memoria.
-- 
none

 x86-32:
La soluzione deve essere in C puro cioè assolutamente portabile.
Altrimenti, per es., nel sondaggio 1 avresti benissimo potuto usare 
codice macchina assemblato manualmente e fatto puntare da un puntatore a 
funzione.
Kiuhnm

 metodo, vengono usati solo 4 bytes.
In realtà non era necessario modificare il testo del problema perché la 
tua soluzione, oltre ad avere il problema di portabilità, non tiene 
conto del fatto che l'implementazione di callf è sconosciuta e quindi 
quest'ultima potrebbe modificare l'array passatole in qualsiasi momento, 
invalidando il metodo.
Kiuhnm

 poi contestano la validità del problema[...]
Non è necessariamente così.  Io potrei non darti la soluzione, ma
contestare ugualmente il problema.  Non puoi da ciò dedurre che io non
conosca la soluzione.
-- 
questo articolo e` stato inviato via web dal servizio gratuito 
http://www.newsland.it/news
 segnala gli abusi ad 
ab...@newsland.it

 conosca la soluzione.
Contestare senza argomentare è uno degli sport che abolirei per legge.
Kiuhnm

Hint 1
Il valore di due variabili var1 e var2 si può scambiare in questo modo:
tmp = var1;
var1 = var2;
var2 = tmp;
Si può però scambiare anche senza utilizzare una terza variabile tmp. Come?
Kiuhnm

Kiuhnm ha scritto:

var1 = var1 ^ var2;
var2 = var1 ^ var2;
var1 = var1 ^ var2;
Ciao
Giuseppe

 var1 = var1 ^ var2;
<CUT>
Piu' coinciso:
var1 ^= var2;
var2 ^= var1;
var1 ^= var2;
Ciao
Giuseppe

Contestare senza argomentare è uno degli sport che abolirei per legge.
Ho argomentato dall'inizio, se è per questo.

var1 ^= var2;
Questo modo di scambiare due valori è scorretto, perché non portabile.
Leggi le faq di comp.lang.c.

 Questo modo di scambiare due valori è scorretto, perché non portabile.
Non è un metodo generico, ma è portabilissimo.
Non è nemmeno il più efficiente oramai (CPU diverse e compilatori più 
"intelligenti").
Kiuhnm

 var1 ^= var2;
In realtà puoi usare anche somma e sottrazione, però con una 
complicazione in più: in complemento a 2 si lavora praticamente in mod 
2^8, 2^16, ecc... a seconda della dimensione della variabile quindi non 
c'è problema, ma in altre rappresentazioni vi possono essere problemi.
Per evitare l'overflow conviene usare una variabile più grande.
Per il quesito generale potete anche ignorare gli overflow e 
concentrarvi sul ragionamento "matematico" di fondo.
Kiuhnm

Non è un metodo generico, ma è portabilissimo.
Non lo è, esistono piattaforme su cui un'operazione del genere non
produce i risultati corretti.  Come già detto, leggi le FAQ.

 La soluzione deve essere in C puro cioè assolutamente portabile.
bon, stai parlando ad uno che non è mai stato un fan del C puro e portabile
(si nota tanto? rotfl).
Comunque, un'altra soluzione prevede di usare 1po' di matematica (non so se
funziona in tutti i casi, mboh), abbozzo 1 idea di soluzione che se avrai
voglia potrai rifinire/correggere/approfondire/smontare.
Dato che k=2, si può provare a giocare con le somme:
- ogni funzione è numerata da 0 a 2^32-1
- quando viene chiamata una funzione, questa incrementa alcuni contatori di
un valore pari al numero associato alla funzione stessa (f_6 incrementerà
di 6)
- tutte le funzioni con indice pari incrementano un contatore
- tutte le funzioni con indice dispari faranno altrettanto con un altro
contatore
- a questo punto, a fine ciclo controllo i 2 contatori, se sono entrambi
diversi dal valore che dovrebbero assumere [che è facilmente calcolabile],
ho trovato gli indici delle subroutine non eseguite. se solo 1 di questi 2
valori differisce significa che entrambi gli indici sono o pari o dispari,
comunque ora so a quanto ammonta la loro somma (mi riferisco sempre agli
indici).
- le funzioni dovranno incrementare quindi degli altri contatori, associati
alle subroutine che hanno indice esprimibile come 3x, 1+3x, 2+3x, 5x, 1+5x,
2+5x, 3+5x, 4+5x.... A fine ciclo, controllo i valori assunti, se vi è una
differenza inferiore alla somma degli indici calcolata al punto precedente,
sono apposto, diversamente ce l'ho nel c... e verificherò gli altri
contatori...
- quanti contatori servono? abbò, la parola a qualcuno che ha voglia di
studiarsi seriamente il problema a livello matematico.
-- 
none

 produce i risultati corretti.  Come già detto, leggi le FAQ.
Quello che dici è assurdo *A PRIORI*.
Rileggi le FAQ!
Kiuhnm

Andrea Laforgia ha scritto:

Ciao,
siccome non riesco a trovarle, saresti piu' preciso?
Su quali piattaforme puo' dare un risultato non corretto, sempre tenendo 
come punto fermo che si lavora in integer?
Giuseppe

 studiarsi seriamente il problema a livello matematico.
Bravo, il metodo è quello giusto, però c'è ancora una difficoltà da 
superare: come minimizzare il numero di contatori?
Magari qualcuno ha voglia di fornire la parte conclusiva...
Kiuhnm

 Quello che dici è assurdo *A PRIORI*.
Non lo è, leggi le FAQ, come già consigliato ben due volte.


 Non lo è, leggi le FAQ, come già consigliato ben due volte.
Io le ho appena lette, per esempio qui:
http://www.uni-giessen.de/faq/archiv/c-faq.faq/msg00000.html
e nonostante sia sconsigliato perche'
semplicimente non conveniente, del codice:
a ^= b;
b ^= a;
a ^= b;
non viene detto che non sia portabile, ma solo
che ha l'ovvia limitazione di poter funzionare solo su tipi interi
e non su float o puntatori.
Invece dell'orrore:
a ^= b ^= a ^= b
viene detto esplicitamente che su alcuni
compilatori puo' dare risultati errati.
Se hai accesso ad altre FAQ posta il link.
ciao,
g.

 compilatori puo' dare risultati errati.
Mi ricordavo di quest'ultima implementazione.  Un tempo, sulle FAQ, veniva
specificata anche la piattaforma in cui si riscontrava l'errore.  In ogni
caso, la tecnica di usare uno xor per "swappare" il contenuto di variabili
intere č da evitare: molto meglio usare una variabile intermedia, anche
perché si mette il compilatore in grado di capire se usare l'istruzione
"swap" che molti processori possiedono.


 Ho argomentato dall'inizio, se è per questo.
Vedo che ti piace cambiare le carte in tavola. Non si parlava di 
argomentazioni riguardanti la pertinenza dei miei post in questo ng, ma 
riguardanti il contenuto didattico dei miei esercizi. Non ho visto 
argomentazioni in proposito.
Kiuhnm

- Soluzione -
Per maggiore portabilità possiamo usare lo xor invece della somma e
della sottrazione.
Si assegna ad ognuna delle 2^32-1 funzioni un valore in [1,2^32-1] in
modo che non esistano due funzioni che abbiano lo stesso valore.
Indichiamo con f_i la funzione alla quale è stato assegnato il valore i
e con val(f_i) il valore i.
Utilizziamo 33 variabili globali v_1, ..., v_33 che inizializziamo nel
seguente modo:
G_{i,j} = XOR_{k=i}^{i+2^(j-1)-1} val(f_k)
v_i = XOR_{j=0}^{2^(32-i+1)-1} G_{j*2^(i-1)+1,i}
dove per semplicità ho assunto che le funzioni siano esattamente 2^32.
Ogni funzione f_i eseguirà lo xor solo sulle variabili alle quali ha
contribuito durante tale inizializzazione.
Se vengono chiamate tutte le funzioni, v_i = 0 per ogni i.
A questo punto l'algoritmo è banale.
Facciamo un esempio con 16 funzioni.
I numeri in alto rappresentano le 16 funzioni f_1, ..., f_16, mentre v1,
v2 e v3 sono le 3 variabili globali.
Un asterisco situato in corrispondenza della variabile v_i e della
funzione f_j indica che la funzione f_j contribuisce alla variabile v_i.
    1234567890123456
v1 ****************
v2 ********
v3 ****    ****
v4 **  **  **  **
v5 * * * * * * * *
Lo schema è semplice.
Dal grafico si evince che le inizializzazioni sono le seguenti:
v1 = 1^2^3^...^16;
v2 = 1^2^...^8;
v3 = 1^2^3^4 ^ 9^10^11^12;
v4 = 1^2 ^ 5^6 ^ 9^10 ^ 13^14;
v5 = 1^3^5^7^9^11^13^15;
Alla fine delle 14 chiamate (n = 16, k = 2) possiamo determinare le due
funzioni f_x ed f_y (dai valori x e y) non chiamate esaminando le
variabili v_i.
Se v1 != v2 allora v1 = x^y mentre, senza perdita di generalità, v2 = x.
Abbiamo che v2 = x e v1^v2 = x^y^x = y.
Se v2 = y il discorso è analogo.
Se v1 = v2 allora x,y <= 8 e quindi le funzioni f_i con 9 <= i <= 16 non
contribuiscono alle variabili v3,v4,v5 quindi si ripete il ragionamento
con v2 e v3 in quanto di fatto v3 può solo contenere i contributi delle
prime 4 funzioni.
L'ultimo caso si verifica quando v1 != v2 con v2 = 0. In tal caso 9 <=
x,y <= 16 e quindi, in modo simile a prima, possiamo assumere che le
variabili v_i siano state inizializzate nel seguente modo:
v1 = 9^...^16;
v2 = 0;
v3 = 9^10^11^12;
v4 = 9^10 ^ 13^14;
v5 = 9^11^13^15;
Induttivamente è possibile dimostrare che l'algoritmo funziona e 
richiede soltanto 33 variabili globali nel caso che n =
2^32-1 e k = 2.
Non ho richiesto che n valesse 2^32 perché in tal caso variabili a 32
bit non sarebbero state sufficienti, infatti non si può assegnare valore
0 a una funzione poiché il suo contributo sarebbe nullo.
Kiuhnm

 argomentazioni riguardanti la pertinenza dei miei post in questo ng[...]
Invece io parlavo proprio di questo.  Leggi il post originale.


 Invece io parlavo proprio di questo.  Leggi il post originale.
Appunto.
Kiuhnm

Appunto.
Appunto non c'era nulla da "argomentare".

della sottrazione.
Non credo vi sia nulla di più portabile della somma e della
sottrazione.

 Appunto non c'era nulla da "argomentare".
Hai detto che i miei esercizi non hanno contenuto didattico, ma non hai 
argomentato.
Ho scritto:
"Le persone corrette e coerenti, prima mostrano di sapere la soluzione e 
poi contestano la validità del problema mostrando che la ricerca di tale 
soluzione non ha coinvolto elementi quali intuito, utilizzo di nozioni 
utili, ecc... "
(Ogni tanto metto la virgola tra soggetto e verbo. E' un'abitudine che 
dovrò cercare di perdere.)
E tu hai risposto:
"Non è necessariamente così.  Io potrei non darti la soluzione, ma
contestare ugualmente il problema.  Non puoi da ciò dedurre che io non
conosca la soluzione."
Quindi sapevi benissimo in merito a cosa ti veniva chiesto di argomentare.
Kiuhnm

 sottrazione.
Il comportamento non è definito in caso di overflow e se non vuoi 
overflow ti servono più di 32 bit.
I casi sono 4:
1) usi lo xor con variabili a 32 bit;
2) usi somma e sottrazione con v. a 32 bit su CPU che usano la 
rappresentazione in complemento a 2;
3) usi somma e sottrazione con v. di almeno 33 bit (probabilmente 64);
4) lavori esplicitamente in Z_{2^32} emulando di fatto la 
rappresentazione in complemento a 2.
Lo xor rappresenta sicuramente la scelta migliore (portabile con meno 
memoria).
Kiuhnm

3) usi somma e sottrazione con v. di almeno 33 bit (probabilmente 64);
Il riporto č gestibile comunque mediante carry flag del processore,
non serve il bit in piů.

argomentato.
Io ho detto che non vorrei che questo gruppo diventasse il ricettacolo
dei tuoi esercizi.  Poi ho spiegato (dopo averne risolto uno, di
questi tuoi esercizi, quindi conoscendone benissimo la soluzione) che
non mi sembra abbiano alcunché di didattico.
Tu rispondi dicendo: "sei tu che non capisci la mia arte".
Il succo del discorso non è se i tuoi esercizi abbiano o meno qualche
scopo educativo valido, ma se sia opportuno che tu li posti qui
dentro.  Non citare il manifesto, perché non avalla i tuoi post.

 c'e' sempre qualcuno che rompe le palle.
Taci, idiota.


 
Non c'e` limite alla tua presunzione, vero?
Quando un pazzo sembra perfettamente ragionevole, e' tempo, credetemi, 
di mettergli la camicia di forza.
                 -- Edgar Allan Poe, scrittore


 non serve il bit in più.
E per fortuna che i miei esercizi non hanno contenuto didattico...
Prima osi chiarmali "stupidotti" e poi te ne esci con un post dove 
dimostri chiaramente di non aver capito un accidente?
Con te non ci perdo più neanche un secondo.
Kiuhnm

 questi tuoi esercizi, quindi conoscendone benissimo la soluzione)
ROTFL. Il problema è che non sei nemmeno un troll. In tal caso avresti 
avuto una scusante.
Kiuhnm


quoto.


 Non c'e` limite alla tua presunzione, vero?
Taci, cretino.


 [...]In tal caso avresti avuto una scusante.
Ne riparliamo quando avrai imparato a firmarti nome e cognome.
Ci sono molte più ragioni di credere che il vero troll sia tu, piuttosto
che io.  Ora sparisci.


 dimostri chiaramente di non aver capito un accidente?
Dimostra che gli altri non hanno capito un accidente e poi ne riparliamo.
Altrimenti, fai solo la figura del cazzone (per non parlare dell'imbecille
che ti quota).


 
LOL


 LOL
Taci, idiota.
