Newsgroup: it.discussioni.misteri
Titolo: Irlanda Magica


wrote:
 >>> >>>Ma, ancor più di comodo ed ancor più vigliaccamente spregevole, 
è chi
 >>> >>>utilizza
 >>> >>>queste sentenze per diffamare un antagonista
 >> >> Vero? E non e' tutto: questa persona che si comportava nel modo 
che tu
 >> >> definisci "vigliaccamente spregevole", beh, SCRIVEVA DAL TUO ACCOUNT!
 >> >> Io lo denuncerei. Oh, mica per altro, ma ti sta facendo fare di 
quelle
 >> >> figure...
 > >Per ridursi a morphare in questo modo bisogna essere ridotti un po'
 > >maluccio...
Oh, ciccio! Tu m'offendi. "
palm...@tin.it
" e' una e-mail __VERA__,
registrata presso un major provider che non da', almeno credo, mail
free a cani & porci, che io leggo regolarmente, e a cui rispondo.
E fa capo al Palm [Pilot] Linux Special Interest Group, entita' con
una sua esistenza su un newsgroup indipendente ospitato su un altro
server: se e' per questo c'e' anche il Mathematica SIG o WolframSIG
che dir si voglia, il PerlSIG, il CSIG, il PHPSIG, il LambdaSIG, l'
ApacheSIG - da non confondere con l'Apache2SIG o il thttpdSIG.
Oh, io sono un uomo dai molteplici interessi... pensa, appartengo a
piu' di 300 Special Interest Groups, e ovviamente sempre da caselle
di posta valide, registrate e che seguo; lo sai che io sono un tipo
ligio, no?
Per l'appunto stavo smistando messaggi relativi a TuSSH - ed eccoti
spiegato il mistero di quel "
palm...@tin.it
" (per altro, l'ho gia'
anche usato varie altre volte in passato).
Diamine! Se QUELLO me lo chiami morphing, quando TU cambi email per
guasti al PC, casini col GPRS, e via andare, quello cos'e'?
Suvvia: e' solo un debolissimo assaggio di quello che il buon noizn
credo faccia tuttora, un post si' e l'altro pure. Se proprio ti da'
fastidio puoi plonkarmi sulla base di "Organization:", oppure della
firma: non vedo la difficolta'.
O metti un basso punteggio a 
individual.net
: blocchi me, feynman, e
cinque o sei cicappini. Io faccio circa lo stesso con 
aioe.org
, con
un punteggio meta' del normale. Tu lo metti a zero e sei lesto.
 > >Direi, tanto per dare un' idea, come chi non è nemmeno capace di
 > >distinguere un calcione di difesa da una mazzata in testa (a dire il 
vero
 > >*continue*!) da parte di un aggressore psicopatico.
Uhm! M'ero domandato in effetti come mai tu scrivessi come scrivi -
e, devo dire, la teoria delle continue mazzate in testa non l'avevo
considerata... ma ora che mi ci attiri l'attenzione, ha del merito,
spiega parecchie cose: l'incoerenza, i vuoti di memoria, gli sbalzi
di umore... gia'; chissa' perche' non ci ho mai pensato. D'istinto,
ho sempre dato per scontato che a darti una mazzata in testa, tutt'
al piu' s'incrinasse la mazza  :-D
Quanto al distinguere, cosa vuoi... bisognerebbe esser li'; sentire
le persone; toccare con mano, magari anche dar du' colpi. Con tutti
i miei impegni, non ce la farei mai (ora per dire sto aspettando la
conferma numerica di un trucchetto per calcolare rapidamente il log
base 2 di un numero usando i numeri di Mersenne, almeno fino a 263
("64 bit numbers will be enough for anyone - L. Serni 2008 ]:-)") )
 > >Piena decadenza, eh?...;-)
Oh si', sono agli sgoccioli, come ripeti ossessivamente da... fanno
cinque anni, o sono di gia' sei?
Ma mica per questo ti do del neurotico, che diamine  :-)
Leonardo, yanking the chain
P.S. Oh, ovviamente scherzavo, quando ho detto che m'offendevi. Era
      una cosa detta cosi', in senso simbolico :-)... figurati se mi
      posso offendere per qualcosa che hai detto tu! (Che idea!)
-- And where the black and corkscrew towers climb, Lost and athirst the 
ragged pack abides, Old as the aeons, trapped in tombs of time, Sailing 
the tortuous temporal tides

("64 bit numbers will be enough for anyone - L. Serni 2008 ]:-)") )
Logaritmo in base 2? banale. Magari logaritmo discreto in modulo 2^N e
base dispari qualsiasi, con N qualsiasi. Un algoritmo efficiente e che
prescinde dai numeri di Mersenne c'e', se ti interessa. Ciao

prescinde dai numeri di Mersenne c'e', se ti interessa. Ciao
Si' che mi interessa! 8-9. In email, magari.
(una delle implementazioni comunque e' soltanto un test sul fatto che
il numero in esame SIA una potenza intera del 2; quello e' il test di
maggiore impatto computazionale).
Ed e' per quello che mi contenterei, in verita', che funzionasse solo
per i numeri addirittura fino a 2 alla 31 (certo - 63 o 64 sarebbe un
bel po' meglio, ma per qualche anno ancora 31 bastano).
===
Comunque, "banale"... banale per te! Nel mio universo locale dovresti
vedere cosa viene adoperato ogni tanto per ordinare le liste: roba da
far sembrare il bubblesort l'opera visionaria di Greg Egan. Arrivando
a cose vàstase come i logaritmi, s'entra nella selva oscura (io forse
arrivo due metri piu' dentro della media [1], ma so bene che prima di
arrivare nel mezzo mi mancano un par di miglia).
Leonardo
[1] cosa che ovviamente sfrutto per atteggiarmi da Grande Esploratore
    Bianco: oh, e' uno dei classici trucchi dell'esoterista ;-)


prescinde dai numeri di Mersenne c'e', se ti interessa. Ciao
Um, mi domandavo perche' avessi aperto un thread. Quella cui stavi
rispondendo e' una copia, spero fedele, del messaggio originale, e
non e' opera mia: non uso mai quello pseudonimo in pubblico, io.
Leonardo


 maggiore impatto computazionale).
Non vedo faccine. Non basta un (n-1)&n?
UV K&R

il numero in esame SIA una potenza intera del 2
Allora e' proprio un logaritmo in base 2... non credo di aver capito.
Ripartendo da capo, qual e' il problema? Dato un numerone intero N in
base 10, stabilire se N e' potenza intera di 2? Se si', non e' quello
che intendevo. Comunque si tratta lo stesso di un problema ampiamente
noto. Cos'ha un qualunque algoritmo di conversione decimale-->binario
che non va bene come efficienza? Ciao





E' complicato. Si': basterebbe. Ma n e' un numero che viene incrementato
ogni volta, e volevo verificare intanto se era possibile fare un test di
tipo piu' semplice [il sistema qui lavora in assembler], e poi se questa
semplicita' computazionale, che si traduce in un colossale casino quando
si va a implementare la cosa (n&(n-1), e' una riga, voglio dire), vale o
no la candela.
(Domanda tendenziosa: conviene di piu' salvarmi (n-1)&n o ricalcolarmelo
ogni volta? Risposta: dipende dalla fottuta piattaforma del ca%%o... e a
proposito, se testo 1, mi ritorna 1 o 0? Ah-ha! CHI?).
Ergo, quintalate di valgrind & co. per vedere quanto uno spende nei vari
punti, test, legge di Amdahl e cosi' via.
OK, OK, sono seghe, eh. Mai detto il contrario :-D
Leonardo


Comunque si tratta lo stesso di un problema ampiamente noto.
Ho googlato parecchio e ho fatto un giro su NR... ora, devo precisare
che l'implementazione originaria, non scherzo, conteneva cose come
	// Q e' una potenza intera del 2?
	if (log(Q)/log(2) == floor(log(Q)/log(2)))
e l'"ottimizzazione" era
	double log2 = log(Q)/log(2);
	if (log2 == floor(log2))
(Q e' sempre intero)
(e gcc-4.3.3, non ho controllato il .S, ma dai tempi sospetto che fin
dall'inizio si fosse accorto di questa possibilita' e l'avesse svolta
cosi' senza dire niente a nessuno)
La versione attuale era... parecchio piu' veloce :-), al punto che e'
nata l'idea di un porting su un'altra piattaforma, dove e', comunque,
troppo lenta. Da li' studi al limite del masturbatorio per fare stare
le cose dentro col calzascarpe, consistenti nel prendere i kernel dei
vari algoritmi, infilarli in un eseguibile di test e farli girare una
milionata di volte, raccogliendo statistiche e guardando pornacci nel
frattempo.
Finisce che il grande successo nell'ottimizzazione della v2.0 diventa
l'umiliante fallimento nel porting alla v3.0 :-)
Leonardo "McCain secondo, Obama penultimo"


cosi' senza dire niente a nessuno)
Ho capito: magari ne riparliamo il 01/04 prossimo. Ciao

Ho capito: magari ne riparliamo il 01/04 prossimo. Ciao
No, guarda, nella lista di quelli che prenderei per i fondelli in questo
gruppo (e altrove), se non sei in fondo pero' sei nella "bottom ten".
Ho spiegato male la storia; ho usato male la terminologia; ma t'assicuro
che il "problema" in se' ce l'avevo e ci stavo lavorando sul serio. E se
non mi servisse in questa roba qui, la "dritta" che ti dicevo mi farebbe
piacere comunque per mia cultura personale.
Quanto alle righe che quoti, se il codice non era proprio quello poco ci
manca: e chi ha messo le mani in applicazioni nate in certi ambienti con
ogni probabilita' ha visto anche di peggio.
Leonardo


 quella quantita' meno uno, e vedo se il risultato e' pari o dispari.
Deduco che quella piattaforma sia abbastanza sfigata da non avere
un'istruzione assembler per trovare l'uno piu' significativo. Allora
il miglior algoritmo che mi venga in mente cosi' su due piedi prevede
due if in cascata (tre per 64 bit) e una lut di 256 byte:
m=0;
if (n>=0x100000000LL) { n>>=32; m+=32; }
if (n>=0x10000) { n>>=16; m+=16; }
if (n>=0x100) { n>>=8; m+=8; }
return lut[n]+m;
oppure, in base all'architettura, puo' andar meglio cosi':
if (n>=1LL<<32)
    if (n>=1LL<<48) m=(n>=1LL<<56) ? 56 : 48;
    else m=(n>=1LL<<40) ? 40 : 32;
else
    if (n>=1<<16) m=(n>=1<<24) ? 24 : 16;
    else m=(n>=1<<8) ? 8 : 0;
return lut[n>>m]+m;
Mi rendo conto che la pipeline non ne goda, ma tanto le piattaforma
sfigate non hanno una superpipeline. Se alla fine trovi qualcosa di
meglio, ce lo fai sapere che interessa anche a me?
UV

la "dritta" che ti dicevo mi farebbe piacere comunque per mia cultura personale.
LOGARITMO DISCRETO IN MODULO 2^n (per il codice Pascal, jump to ##)
Convenzioni e notazioni: tutte le operazioni sono intese modulo 2^n.
Anzitutto, ci si puo' limitare al calcolo di logaritmi con base dispari
ed argomento dispari. Infatti, se la base e' pari, ha al piu' n potenze
diverse da zero, pertanto risulta molto veloce accertare se l'argomento
e' una potenza della base oppure no. Inoltre un argomento pari non puo'
essere potenza di una base dispari.
Intanto ricordiamo che i numeri dispari formano un gruppo rispetto alla
moltiplicazione mod 2^n. Questo gruppo ha ordine 2^(n-1). Per n>2, esso
gruppo non e' ciclico: secondo il teorema di Lagrange, l'ordine o(x) di
un qualunque suo elemento x e' una potenza di 2 che puo' variare da 2^0
(per x=1) a 2^(n-2). L'ordine (meglio: l'esponente di 2 dell'ordine) di
un qualsiasi elemento x si puo' quindi determinare facilmente, mediante
elevazioni successive a quadrato (function EspOrdine sottoriportata).
Si supponga ora che x sia il logaritmo di p in base b, cioe' che b^x=p,
ovvero p e' un elemento di ordine o(p)=2^k del gruppo ciclico di ordine
o(b)=2^h generato da b. Poiche' l'ordine di una potenza non puo' essere
maggiore dell'ordine della sua base, si ha evidentemente k<=h. Ora, fra
x, h e k c'e' una semplice relazione: si esprima x come il prodotto tra
una potenza di due e un dispari y: sia x=2^t y. Un algoritmo efficiente
per il logaritmo discreto mod 2^n e' basato sul fatto che, in gruppo in
cui gli elementi hanno per ordini delle potenze di 2, l'esponente t del
fattore 2 in x non e' altro che la differenza fra h e k: t=h-k
Dimostrazione: poiche' o(p)=2^k, si ha p^(2^k) = 1. Del resto, e' anche
p^(2^k) = (b^x)^(2^k) = b^(2^t y)^(2^k) = b^(2^t 2^k y) = b^(2^(t+k) y)
Allora si ha b^(2^(t+k) y) = 1, pertanto 2^(t+k) y deve essere multiplo
di o(b)=2^h; essendo y dispari, ne consegue che h<=t+k ossia h-k<=t.
Analogamente, p^(2^(k-1))<>1 significa che b^(2^(t+k-1)y)<>1 e pertanto
2^(t+k-1) y non e' multiplo di 2^h: ne deriva che t+k-1<h ossia t<=h-k.
In conclusione, t=h-k.
Una volta determinato t in funzione di h e k, la strategia e' quella di
costruire un elemento q che abbia un ordine o(q)=2^j inferiore ad o(p).
A tale proposito, si ponga
q = p b^(2^t) = b^x b^(2^t) = b^(2^t y) b^(2^t) = b^(2^t (y+1)). 
Essendo y+1 pari, 2^t (y+1) e' multiplo di una potenza di 2 la quale ha
esponente v maggiore di t: da v=h-j, si ha j<k. Calcolando o(q)=2^j, si
e' in grado di determinare v facendo h-j. A questo punto ripetiamo su q
quanto fatto su p; moltiplicando q per b^(2^v) avremo un elemento r che
ha ordine ancora minore di quello di q. Procedendo in questo maniera si
arrivera' massimo dopo n-2 iterazioni all'elemento di ordine minimo: 1.
Ma allora
p b^(2^t) b^(2^v)....b^(2^z) = 1
ossia
b^x b^(2^t) b^(2^v)....b^(2^z) = b^(2^h)
da cui x = 2^h - 2^t - 2^v - ..... - 2^z.
NOTA IMPORTANTE: le considerazioni fatte valgono esclusivamente a patto
che quel logaritmo richiesto esista. Quando log(p) in base b esiste, la
successione p,q,r... raggiunge 1 dopo al piu' h iterazioni. Se invece p
non e' una potenza di b, moltiplicandolo per potenze di b come e' stato
fatto sopra non si otterra' mai un elemento del gruppo ciclico generato
da b: quindi non si arrivera' mai ad 1. Pertanto, condizione necessaria
e sufficiente per l'esistenza di log(p) in base b e' che la successione
p,q,r,... raggiunga 1 dopo al piu' h iterazioni.
Esempio: sia n=8; b=17; p=177.
Calcolare x=log(177) base 17 mod 2^8.
Si ha: o(177)=2^4, o(17)=2^4. Poiche' 4-4 = 0, non ci sono fattori 2 in
x; x = 2^0 y.
q = p b^(2^0) = 177 17 = 193. o(q)=2^2; poiche' 4-2 = 2, q = b^(2^2 w);
r = q b^(2^2) = 193 17^4 = 1. Allora  b^x b^(2^0) b^(2^2) = b^(2^4), da
cui x = 2^4 - 2^2 - 2^0  = 11. Infatti 17^11=177.
##
Ora si descrivono quattro funzioni Pascal per il suddetto algoritmo. Le
prime tre sono accessorie a quella che esegue il calcolo vero e proprio
del logaritmo. Number rappresenta un tipo intero senza segno a n bit, e
***tutte le operazioni che lo riguardano sono intese modulo 2^n.***
Type da0an = 0..n;
Function EspOrdine(x: Number): da0an;
{calcola l'esponente k di 2 dell'ordine o(x)=2^k
mediante elevazioni successive a quadrato;
il ciclo viene eseguito al max n-2 volte}
var eo: da0an;
begin
 eo:=0;
 while x<>1 do begin
                x:=x*x;
                eo:=eo+1
               end;
 EspOrdine:=eo
end;
Function DueAlla(x: da0an): Number;
{calcola 2^x}
Var d: Number;
    i: da0an;
begin
  d:=1;
  for i:=1 to x do d:=d*2;
  DueAlla:=d
end; 
Function SuperExp2(b: Number; m: da0an): Number;
{calcolo veloce di b^(2^m)}
Var i: da0an;
begin
  for i:=1 to m do b:=b*b;
  SuperExp2:=b
end;
Function Logaritmo(b,pow: Number): Number;
{calcola il logaritmo di pow in base b, se esiste;
 se non esiste segnala errore}
Var h,diff,c: da0an;
    lg: Number;
begin
  if pow=1 then Logaritmo:=0
   else begin
         h:=EspOrdine(b);
         c:=0;
         {c conta le iterazioni del ciclo while.
         se sono piu' di h il logaritmo non esiste}
         lg:=DueAlla(h);
         while (pow>1) and (c<=h) do
         begin
           diff:=h-EspOrdine(pow);
           {diff conterra' successivamente:
            t=h-k, v=h-j, ecc.}
           pow:=pow*SuperExp2(b,diff);
           {pow conterra' successivamente: p, q, r, ecc.}
           lg:=lg-DueAlla(diff);
           {gli esponenti 2^t, 2^v ecc. sono sottratti
           uno dopo l'altro da 2^h}
           c:=c+1
         end;
         if c<=h then Logaritmo:=lg
                 else writeln('Log non esistente')
        end;
end;
Nota: Poiche' le differenze h-k, h-j ecc. sono crescenti, si potrebbero
sostituire con h-k, k-j ecc.ecc., mediante la memorizzazione dei valori
delle funzioni SuperExp2, DueAlla ottenuti nelle iterazioni precedenti.
Infatti
SuperExp2(b,h-j)=SuperExp2(SuperExp2(b,h-k),k-j);
DueAlla(h-j)=DueAlla(h-k) DueAlla(k-j).
Si tratta comunque di un'ottimizzazione non essenziale.
Generalizzazioni. Quanto sopra si puo' estendere immediatamente al caso
in cui il modulo e' un primo di Fermat p=2^(2^m)+1, essendo l'ordine di
ogni elemento ancora una potenza di 2. Ovviamente nessuno sano di mente
impiega come modulo una potenza di 2 o un primo di Fermat per crittare.
Ciao

Convenzioni e notazioni: tutte le operazioni sono intese modulo 2^n.
Uhm. Intanto, grazie... mi ci vorra' un po' per masticarlo. Spero che tu
non abbia sopravvalutato i miei molari... gia' vedo che mi devo chiarire
un bel po' di termini.
Ho visto questo tipo di calcoli in algoritmi per crittografia, ma non li
ho mai approfonditi; magari e' il momento di provarci.
Ora me lo stampo e me lo studio con calma. A buon rendere :-)


return lut[n]+m;
In effetti questo e' anche l'algoritmo a cui sono pervenuto io, anche se
non mi era mica venuta in mente l'idea della LUT.
Se mai tu o El Filibustero passate da Firenze, vi devo una cena :-)
Preliminarmente ottengo risultati migliori con una LUT di 16-32 byte, ma
ovviamente variera' da piattaforma a piattaforma... questo e' il massimo
che posso fare ora per ricambiare.
inline int logzoom(ULL z)
{
        int     l = 0;
        if (z & 0xffffffff00000000LLU)  z >>= 32,       l |= 32; [1]
        if (z & 0xffff0000)             z >>= 16,       l |= 16;
        if (z & 0xff00)                 z >>= 8,        l |= 8;
        //if (z & 0xf0)                   z >>= 4,        l |= 4;
        if (z & 0xe0)                   z >>= 3,        l += 3; // no |!
        return l+lut[z];
        //if (z & 0xc)                    z >>= 2,        l++, l++;
        //if (z & 0x2)                                    l++;
        //return l;
}
E, si', lo so che quando uno comincia a distinguere fra l+=1, l++ e l|=1
vuol dire che e' oltre la frutta e ormai all'ammazzacaffe'... ho chiesto
al "padre" dell'algoritmo alcune modifiche ad alto livello, per ottenere
prestazioni migliori senza far a gara col compilatore a chi ce l'ha piu'
lungo [2]
(Tanto per dire, fra -O0 ed -O3 con gcc, lo stesso programma di prova va
da user time 13.893s a user time 5.916s. Avere o non avere la LUT cambia
da 13.893 (con) a 16.845 (senza)) {ho anche i dati di Cachegrind, ma con
time si ha un dato piu' marketable ;-) }.
Leonardo (S.E.&O.)
[1] a seconda della piattaforma, puo' essere piu' veloce e pericoloso |x
    che non +x. Se si e' certi che numero originale & x = 0.
[2] occupazione affine al fare a gara di cornate con uno stambecco


ho mai approfonditi; magari e' il momento di provarci.
Non credo che il logaritmo discreto in modulo 2^n possa essere di qualche
utilita' in crittografia: nessun crittografo sarebbe tanto folle da usare
2^n per modulo. Pero' 2^n e' un modulo comune nella generazione di numeri
pseudorandom mediante congruenze lineari, cioe'
X_0 := seed
X_{i+1} := a * X_i + b (mod 2^n)
e cosi' un'applicazione del logaritmo discreto modulo 2^n potrebbe essere
la magica previsione del momento di uscita di un dato termine X qualunque
noti tre termini consecutivi qualsiasi della successione, a patto che a,b
siano dispari (come di consueto). Ciao

 vuol dire che e' oltre la frutta e ormai all'ammazzacaffe'...
Piu' che altro rischia di dare la caccia ai fantasmi. Una volta ho
scoperto che un programmino di test di un algoritmo che stavo
ottimizzando filava piu' veloce aggiungendo in un punto del codice
inutile. L'unica spiegazione che mi sono dato e' che nel mondo x86
conta anche come le istruzioni finiscono allineate, cosa di cui
probabilmente il gcc non tenta nemmeno di tenere conto. Ma era solo
una supposizione, non ho studiato il codice prodotto.
Che l'or sia piu' veloce dell'add mi sorprende, ma tanto ormai
non mi stupisco piu' di nulla.
Comunque, se la versione x86 del tuo codice deve girare su una CPU
ragionevole (>=PPro), io la bsr la userei comunque (non so se l'hai
gia' fatto), anche se non e' un caso critico come quello embedded.
Male non fa; certo, e' un po' una scocciatura con gli ifdef.
static inline int msb(unsigned long n)
{
int bit;
asm("bsr %1,%0;" : "=r" (bit) : "r" (n));
return bit;
}
condizionando opportunamente la cosa, gestendo a parte il caso n=0 e
usando il -O per attivare l'inlining.
BTW puoi mettere l'or anche al 3, se serve.
UV

non mi stupisco piu' di nulla.
Io credo d'essermi rassegnato un dieci anni fa. Adesso provo un po'
a casaccio, poi m'invento una teoria che spieghi i risultati. Tanto
ci saranno tre persone al mondo in grado di smentirmi, stanno fisse
nei laboratori della Intel e comunque non ne sarebbero certissime.
Leonardo cinico


 nei laboratori della Intel e comunque non ne sarebbero certissime.
Io sono anche piu' pessimista. Se con una modifichina senza senso
ottengo un piccolo miglioramento di prestazioni, non ne tengo conto e
faccio di testa mia, tanto per quanto ne so potrebbe bastare
aggiungere un'instruzione in una routine circostante per far cambiare
tutto di nuovo.
UVC il dannoso

Io sono anche piu' pessimista.
Non si e' mai abbastanza pessimisti :-D
Leonardo
