Newsgroup: it.comp.hardware.cpu
Titolo: Differenze nei calcoli di P4 e AMD?


Riporto qui i passi salienti:
    I have an 512x512 non-symmetric complex matrix M.
    When i use the command eigsys = Eigensystem[M]...
    [snip]
    ...[t]he eigenvalues calculated with Mathematica 4.1 at all
    machines (AMD & Intel) and Mathematica 5.0 at the AMD
    machines solve both the equation and the system of equations
    rather perfectly !!
    [snip]
    in Mathematica 5.0, [...] on a Pentium4 2,6 GHz stand-alone machine
    and a Pentium4 3,06 HT notebook [...] the eigenvalues were
    not the eigenvalues I expected !
Insomma, stando all'OP, usando Mathematica 5 ottiene risultati diversi a
seconda che utilizzi una CPU Intel o una CPU Amd. Considerando che
l'eseguibile è lo stesso per entrambe le architetture, secondo voi la
differenza dei risultati può essere dovuta all'hardware?
La differenza è stata riscontrata su architetture a 32 bit che usano la
stessa rappresentaizone IEEE 754. Questo significa che le operazioni
elementari - incluso l'arrotondamento - sono le stesse su entrambi i
sistemi. Ci possono essere differenze nelle funzioni trascendenti, forse?
L'alternativa è che il programma identifichi la CPU e usi un codice
differente a seconda di quello che trova. So che Mma 5 è compatibile
con le architetture a 64 bit, ma credo che si tratti di un differente
eseguibile per cui il problema per l'eseguibile a 32 bit rimane.
Spulciando Google ho trovato che differenti opzioni di compilazione per lo
stesso processore possono dare eseguibili con codici che producono risultati
diversi, ma ancora: qui si tratta dello stesso eseguibile.
Che ne pensate?
(l'OP non ha -ancora- fornito i dati per replicare il problema. a me cale
poco visto che non ho accesso a mma 5)
saluti,
Peltio
comunque curioso

 Che ne pensate?
Bah è assurdo. Comunque menomale che uso AMD :-P
-- 
Saluti
Alec
(26,72+,CT)
Powered by AMD
AthlonXP-M 3400+

 diversi, ma ancora: qui si tratta dello stesso eseguibile.
Non vuol dir nulla, potrebbe benissimo essere:
if(p4) eigen_sse2();
else eigen_fp();
stesso eseguibile, codice diverso a seconda della CPU.
In particolare, per il processamento di matrici, l'uso
di istruzioni tipo sse e` caldamente consigliato in
termini prestazionali (cosa non specificata nel post,
cioe` se vi sono sostanziali differenze in termini di
tempo di esecuzioni), pero` non sarei sicuro che sse
sia perfettamente nello standard 754.
bye,
-- 
   Piergiorgio Sartor

 termini prestazionali...
Si ma l'uso di calcoli aderenti allo standard IEEE754 in teoria dovrebbero
essere eseguiti senza utilizzare eventuali ottmizzazioni come appunto
le SSE, sempre se si vuole misurare con esattezza l'efficienza
dell'unità FP di una determinata cpu... almeno credo.
Ciao

 dell'unità FP di una determinata cpu... almeno credo.
Ma Mathematica non serve per misurare l'esattezza
dell'unita` FP, bensi` per risolvere problemi.
Ora, potrebbe essere (dico potrebbe, dato che non ho
la piu` pallida idea di come Mathematica sia fatto),
che abbiano deciso di ottimizzare parti del codice
ed usare sse, che magari effettuano arrotondamenti
non confacenti lo standard, quindi, in certi casi,
potrebbero portare risultati _diversi_ dal 754.
Tra l'altro non e` neanche detto che sia colpa di sse,
potrebbe semplicemente essere una diversa implementazione
del codice nel caso di diverse CPU.
Infatti l'ordine di esecuzione di istruzioni FP, pur
essendo matematicamente uguale, puo` portare a risultati
diversi (vedi realizzazione di filtri).
Infine, non e` dato sapere come di possa, data la matrice
512x512 complessa, dire quali siano effettivamenti i
risultati corretti... :-)
bye
-- 
   Piergiorgio Sartor


Insomma... alla fin fine il risultato finale non dovrebbe cambiare per le
due
piattaforme ;-)
Ciao

 due piattaforme ;-)
Non necessariamente.
Immagina che abbiano codice ottimizzato per P4.
E questo a partire da 5.0.
Immagina che il risultato piu` corretto sia, per
puro caso, proprio quello di 5.0 su P4.
Come si fa a dire che non vi sia un bug o simile
nelle versioni precedenti?
Bug che, ovviamente, non e` visibile, finche` non si
cambia implementazione, cosa che, incidentalmente, e`
successa per ottimizzare per il P4.
Tutta fantasia, ovviamente, pero` non e` detto che
sia troppo lontano dalla realta`.
Che vi sia codice P4 specifico e` quasi indubbio,
dato che per < 5.0 il risultato risulta identico
per tutto le piattaforme, mentre per 5.0 cambia.
Tra l'altro non ha scritto quanto sono diversi.
Cioe` se gli autovalori sono 1, 2, 3 in un caso
e 1.0001, 2.0001, 3.0001 nell'altro e` un conto,
ma se sono 57, 31, 0.000015 e` un'altro...
bye,
-- 
   Piergiorgio Sartor


eh no un bel corno!!! un errore del 0.00001 su una macchina digitale è un
errore grandissimo...che può solo essere causato dalla sbagliata
implementazione HARDWARE di qualcosa...

 implementazione HARDWARE di qualcosa...
Ma per favore, ripassa calcolo numerico e torna a Settembre.
bye,
-- 
   Piergiorgio Sartor

 else eigen_fp();
La cosa curiosa è che non mi risulta che Mathematica sia ottimizzato per
SSE/SSE2, tant'è vero che gli Athlon (anche XP) hanno sempre dato la paga ai
Pentium con Mathematica.
MaxArt

 Pentium con Mathematica.
Potrebbe semplicemente essere codice diverso
a secondo della CPU.
Cosa che, da quello che dici, potrebbe essere
logica, dato che la maggior parte delle CPU in
circolazione sono Pentium, conviene tentare di
avere codice specifico.
Solo supposizioni, ovviamente.
bye,
-- 
piergiorgio


Il tipo stava estraendo gli autovalori di una matrice 512x512
non simmetrica, se con i P4 Mathematica 5.0 usa le SSE/SSE2
e' facile che ci sia stato un accumulo di arrondamenti e troncamenti
tale da produrre differenze tangibili.
Usando i float ad 80bit della FPU x87 si hanno 64bit di mantissa
mentre usando i float a 64bit si ha una mantissa di 56 bit
(l'errore di troncamento diventa circa 256 volte piu grande).
Anche se si usano "esternamente" (dimensione delle variabili in memoria)
variabili float a 32bit o 64bit, con la FPU x87 i valori temporanei
nei registri dello stack della FPU sono comunque ad 80bit, quindi
del codice che usa float a 32bit o a 64bit che con la FPu x87
fornisce una certa precisione, se lo si converte in modo da
usare SSE/SSE2 "perde precisione" (perche tutte le operazioni
intermedie diventano minimo 256 volte piu "imprecise" rispetto
a prima).
Se si guarda in rete si trovano diverse pubblicazioni
(principalmente in inglese) con titoli tipo
"perche i numeri floating point *non sono* numeri reali"
oppure "come non uccidere qualcuno usando i floating point". ;-)
Non e' un caso se molti compilatori hanno opzioni tipo -ffast-math
disabilitate per default; gia e' una rogna garantire la massima
precisione in condizioni "normali", figurarsi se ci si mette pure
il compilatore a rimescolare le carte.
L. Micheletto

matrice?
Non volevo iniziare una guerra di religione : |
Comunque, no, non credo che sia un bug tipo quello del P1. Sarebbe stato
scoperto da tempo e con molte altre applicazioni. Forse qualche funzione
evoluta che sacrifica la precisione in cambio dele prestazioni, come ha
fatto notare Sartor. Volevo però sapere se ci fossero delle differenze nella
rappresentazione e nelle operaazioni elementari tra le architetture AMD e
Intel, e la risposta è stata:no.
Riguardo allo sbagliare, non è così grave come potrebbe sembrare a prima
vista. Basta una piccola differenza nel modo in cui si decide di terminare
lo sviluppo binario della mantissa per produrre errori che, propagandosi in
calcoli complessi, diventano macroscopici.
Anzi, a volte basta poco per produrre errori sensibili.
Prova a calcolare 34.123*89 in doppia precisione e guarda l'ultima cifra.
O confronta int[(1.65-1.3)/0.07] con int[0.35/0.07] (int è la parte intera).
Erore?
: )
saluti,
Peltio

sia perfettamente nello standard 754.
Beh, sarebbe interessante scoprire la causa delle discrepanza, perchè è
giusto che uno che usa un P4 per calcoli matriciali sfruttando le SSE2
sappia quali sono i limiti in termini di precisione.
Ammesso che poi le colpe siano lì e non dipendano semplicmente da qualche
piccola discrepanza tra codice per P4 e codice per AMD.
saluti,
Peltio

Piergiorgio Sartor ha scritto:

In un software di quel tipo, non ha senso variare l'algoritmo di calcolo
per motivi di prestazioni: viene sempre scelto l'algoritmo che genera gli
errori minimi.
Probabilmente negli Athlon viene veramente utilizzata la
FPU x87 con float a precisione estesa, mentre nei Pentium si usano le SSE
e quindi float con precisione double...
Saluti.
-- 
\/               
wirix...@libero.it
          ICQ UIN: 3233084
/\ e l l o s s   (per rispondermi in privato, elimina il DEMONE)

 implementazione HARDWARE di qualcosa...
Quando si lavora con i reali i calcolatori sono costretti ad approssimare.
E a seconda del problema che occorre risolvere, e dell'algoritmo che
si usa per risolverlo, l'approssimazione dei dati in input (che si
può supporre buona ma non perfetta) può essere amplificata di un
fattore costante (nel migliore dei casi) o variabile e potenzialmente
molto grande (nel peggiore dei casi).
C'è una (pallosissima) branca della matematica, il calcolo numerico, che
si occupa proprio di queste cose...


 e quindi float con precisione double...
Cioe` implementano codice diverso.
bye,
-- 
piergiorgio

 Cioe` implementano codice diverso.
Codice diverso ma algoritmo identico. Per cui, ad esempio, l'algoritmo
permette di ottenere sempre la precisione ottima, che su una macchina è
minore che sull'altra perché ci sono meno cifre significative. E in
questo caso non ci sarebbe nulla di strano, comunque.
Saluti.
-- 
\/               
wirix...@libero.it
          ICQ UIN: 3233084
/\ e l l o s s   (per rispondermi in privato, elimina il DEMONE)
***      La macchina di Turing ha un baco nel programma      ***
***             e noi l'aggiusteremo con il C++!             ***

 questo caso non ci sarebbe nulla di strano, comunque.
La precisione non dipende dall'algoritmo solamente, ma anche
dall'implementazione dello stesso.
Anche perche` non e` detto che l'algoritmo tenga in considerazione
il fatto che i numeri siano in precisione finita.
Da quello che mi ricordo, quasi tutti gli algoritmi di calcolo
numerico, tipo Newton-Rapson o quelli di Gauss, non considerano
il fatto che i numeri sono "finiti".
bye,
-- 
piergiorgio

 dall'implementazione dello stesso.
Quando parlo di algoritmi numerici la mia definizione di algoritmo è
molto più rigida del solito, in quanto per l'algoritmo pretendo la
correttezza, che in questo caso è ottenere la massima precisione
possibile su un hardware dato. E a-b*d+c*d è più preciso di a-(b-c)*d su
qualsiasi hardware.


 modifichi il risultato finale.
Qui stiamo facendo un po' di confusione.
Un algoritmo, in generale, non si preoccupa della precisione,
per cui tutte le infinite possibili rappresentazioni danno lo
stesso identico risultato.
Se invece consideriamo _dentro_ l'algoritmo anche la rappresentazione
dei numeri e il modo di fare le operazioni (ad es. accumulatore doppio,
etc.) allora e` chiaro che diverse rappresentazioni possono dare
risultati diversi, infatti si tratta di algoritmi diversi.
Pero` questa seconda definizione non e` proprio comune,
o perlomeno va specificata.
Il metodo di Newton-Rapson non dice nulla riguardo la
precisione delle operazioni, per lui moltiplicazioni e
somme hanno sempre precisione infinita.
Sta poi a chi implementa rendersi conto che un confronto
con zero e` una sciocchezza e magari e` meglio segliere
un epsilon opportuno.
D'altro canto anche la somma di due numeri FP e` un algoritmo,
che lavora su interi (finiti), solo che fa parte dell'algoritmo
stesso la rappresentazione dei dati.
bye,
-- 
piergiorgio

 L'algoritmo e` lo stesso, l'implementazione e` diversa.
Su, non giriamo attorno al significato delle parole. Per come la vedo io
applicare delle trasformazioni aritmetiche a un algoritmo significa
ritrovarsi con un altro algoritmo; come minimo, rischi di variare il
numero di passi necessari per il calcolo, in quanto a*(b+c) sono
un'addizione e una moltiplicazione, mentre a*b+a*c sono due
moltiplicazioni e un'addizione. Quando poi le trasformazioni aritmetiche
utilizzate sono addirittura illecite lavorando con i numeri finiti,
ottieni quelle anomalie nei risultati.
Ma utilizziamo pure la tua terminologia: nessun programma di calcolo serio
utilizzerebbe un'implementazione che riduce la precisione per migliorare
l'efficienza; perlomeno non senza informare l'utente consentendogli, se
necessario, di disattivare l'ottimizzazione.


 L'algoritmo e` lo stesso, l'implementazione e` diversa.
Voglio fare un po' di chiarezza anche dal punto di vista della
terminologia. Così forse le mie posizioni risulteranno più chiare.
Quando prendiamo una funzione y = f(x) possiamo riferirci a due aspetti
diversi:
- la funzione come entità matematica, ossia un'insieme (possibilmente
infinito) di coppie (x, y)
- la funzione intesa come entità calcolabile, ossia l'elenco di passi
necessari per calcolare y dato x, cioè l'algoritmo
Altri modi per rendere la distinzione sono i concetti di
semantica/sintassi o di denotazione/notazione (*).
Certamente, quando parliamo informalmente di algoritmo ci riferiamo a
un'entità che sia sufficientemente distante dai linguaggi di
programmazione reali. Ma tecnicamente un algoritmo è già
un'implementazione, come si può concludere da questa definizione tratta
da un testo anzianotto e molto accreditato (**): 
"2) Esiste un agente calcolatore, anche umano, che può reagire alle
istruzioni e portare a termine il calcolo"
Ossia un algoritmo è dato come implementazione di se stesso su una
particolare macchina realmente esistente.
Lavorando con linguaggi sufficientemente espressivi, dando per buona la
Tesi di Church possiamo ottenere un algoritmo equivalente su qualsiasi
altra macchina. Ma equivalente significa che deve dare lo stesso
risultato: in particolare a*(b+c) non è equivalente a a*b+a*c quando si
lavora in aritmetica float finita.
Un compilatore che si permettesse di fare certe "ottimizzazioni" sarebbe
un pessimo compilatore perché effettua trasformazioni sintattiche
che modificano la semantica del programma - a casa mia si dice che le
trasformazioni sintattiche applicate non sono corrette, per cui lo stesso
compilatore non è corretto.
Note:
(*) Concetti fondamentali in logica e informatica teorica. A tal scopo si
può leggere Proofs and Types di Jean-Yves Girard, disponibile presso
l'indirizzo 
http://www.dcs.qmw.ac.uk/~pt/stable/Proofs+Types.html
(**) Hartley Rogers, Theory of Recursive Functions and Effective
Computability, The MIT Press, pagina 2


 necessario, di disattivare l'ottimizzazione.
Qui si parla di risultati diversi, non di perdita di
precisione, per prima cosa, secondariamente dipende
da cosa si vuole ottenere.
In campo video, per esempio, i filtri sono ad 8bit, per
il semplice fatto che devi andare real-time e la precisione
viene considerata sufficiente.
Mentre in campo audio devi come minimo andare a 24bit, dato
che altrimenti gli errori diventano "udibili".
Quindi si fanno delle scelte.
Se usando le sse si va il doppio piu` veloce, perdendo
lo 0.1% in precisione, magari si puo` scegliere quella
strada, o magari no. Il fatto e` che non esiste nessuna
"legge" o "regola" che stabilisca cosa sia meglio.
bye,
-- 
piergiorgio

Xelloss dal portatile wrote:

-- 
piergiorgio

 lavora in aritmetica float finita.
Gli algoritmo non c'entrano nulla con le macchine sulle
quale li implementi.
Prendi il calcolo dell'inverso di una funzione monotona.
y=f(x)
trovare x dato y.
Un metodo (algoritmo) di procedere e`:
1) prendo due estremi H e L.
2) calcolo m=(H+L)/2
3) calcolo t=f(m)
4) se t<y L=m
5) se t>y H=m
6) se t!=y vai 2)
(4 e 5 potrebbero essere invertiti, non ho controllato)
Questo algoritmo e` sempre vero.
Se lo implementi, forse non terminera` mai, dato che potrebbe
sempre essere t!=y.
Ovviamente uno potrebbe scrivere:
6) se abs(t-y)>e vai 2)
Il che modifica l'algoritmo, ma e` sempre indipendente
dall'implementazione.
L'implementazione FP e` _differente_ da quella integer 16bit,
che e` ancora differente da quella integere a 32bit.
L'algoritmo e` comunque sempre lo stesso, ma le implementazioni
sono diverse, perche` nell'algoritmo _non_ si considerano anche
i modi di fare le operazioni, cioe` si considera sempre precisione
infinita, cioe` precisione matematica.
Se invece ci metti dentro anche come fai le operazioni, cioe` se
consideri l'algoritmo _diverso_:
y=f(x) trovare x intero dato y intero.
Allora la cosa cambia, cosi` come cambia con trovare x entro
l'1% od il 10% o 0.1% dato y.
Tra l'altro anche "fare il the" e` un algoritmo.
bye,
-- 
piergiorgio

 Non e` la mia, e` quella corretta... ;-)
Vallo a dire a Rogers, non mi risulta sia ancora morto...


 infinita, cioe` precisione matematica.
Un algoritmo numerico, invece, dovrebbe tenere conto dell'aritmetica
finita.
E comunque, per farla breve, io non capisco come fai a considerare "lo
stesso algoritmo" due "implementazioni" che generano risultati diversi. E
che cavolo! Sono sintatticamente diversi e sono pure semanticamente
diversi! E allora dove sta la loro equivalenza??


 Vallo a dire a Rogers, non mi risulta sia ancora morto...
Tu confondi i contesti.
bye,
-- 
piergiorgio

 diversi! E allora dove sta la loro equivalenza??
Ma neanche per sogno sono diversi, il problema e` che quello
che tu definisci sintassi e semantica la applichi al linguaggio
sbagliato, cioe` al linguaggio implementativo e non a quello
descrittivo.
Se preferisci, considera a/b.
Questo e` un algoritmo, nota che non specifico _come_ viene
calcolato a/b, ma solo che viene calcolato.
E` un algoritmo, semplicissimo, ma lo e`.
Ora se _implementi_ quella cosa in FP, oppure interi finiti
oppure infiniti, avrai lo _stesso_ algoritmo (la divisione),
che da risultati diversi.
La _divisione_ e` l'algoritmo, non si distingue su come questa
sia fatta, quello e` un altro _livello_.
Il fatto che la CPU possa avere fdiv e/o idiv e quindi, nel linguaggio
nella CPU, siano algoritmi _diversi_, non e` in discussione, ma non
e` quello il linguaggio in cui l'algoritmo e` specificato.
Allo stesso modo, lo ripeto per l'ennesima volta, esiste l'algoritmo
di Newton-Rapson, questo e` stato inventato _prima_ dei linguaggi
formali e descrive un procedimento per trovare f(x)=0 dato un x=P
iniziale. L'algoritmo descrive, in modo matematico, i passi per
ottenere il risultato e, credo, anche l'errore ad ogni passo.
Il linguaggio usato non e` C, non e` assembly, non e` MdT, eppure
e` un algoritmo.
Quando vai a realizzare N-R con un computer, dovrai decidere un
paio di cosette, una puo` essere la precisione, l'altra la velocita`.
Puoi implementare N-R per dare la soluzione velocemente, oppure per
darla molto precisa, ma sfido, sia te che Rogers, a dire che sono
algoritmi diversi (andatelo a dire a Newton ed a Rapson).
Ovviamente uno potrebbe descrivere un'algoritmo in modo piu`
dettagliato, magari specificando esattamente come le operazioni
elementari debbano essere eseguite e magari con che precisione.
Ma questo _deve_ essere specificato come parte procedurale, se
parli di N-R, questo non c'e`.
Il calcolo numerico degli autovalori di una matrice e` un altro
algoritmo, descritto non in C, ne` in assembly.
Dira` cose come "somma x ed y", "dividi la somma per la differenza",
etc., non dira` nulla sulle specifiche implementative.
Si conoscera` forse la complessita` e la sensibilita` dell'algoritmo,
ma questo restera` sempre indipendenta dal linguaggio formale che
lo implementa. In tutte le infinite forme.
bye,
-- 
piergiorgio

 non e` C, non e` assembly, non e` MdT, eppure e` un algoritmo.
Questo non l'ha negato nessuno; solo che quelle che tu chiami
"implementazioni" non sono l'algoritmo originale ma suoi adattamenti. Lo
ripeto ancora una volta: se sono diversi sintatticamente e diversi
semanticamente, non esiste un metodo per metterli in relazione uno a uno,
quindi non ci può essere equivalenza.
(*) Difficile ma non impossibile. Non esiste computazione eseguibile da un
essere umano ma non da una macchina turing-equivalente. Oppure mostramela
e diventa famoso come colui che ha confutato la tesi di church.


 Se non specifichi oltre, quello vale.
Anche qui, la somma prevede un addendo #1 e un addendo #2.
a + b e b + a sono uguali dal punto di vista della semantica (del
risultato) e lo sono perché c'è un teorema che lo dimostra, non perché
siano "lo stesso calcolo". Infatti la prima scrittura significa
"incrementa b volte a", la seconda scrittura "incrementa a volte b". Dal
punto di vista sintattico (dell'algoritmo) sono due cose diversissime.
Ma il bello è che tutto questo è nato perché esistono due procedimenti
di calcolo diversi, che danno risultati diversi, ma che secondo te
sarebbero lo stesso algoritmo in quanto derivati dallo stesso
algoritmo astratto, diverso da entrambi sia nel procedimento di calcolo
sia nei risultati, che però, in virtù di una definizione imprecisa o del
tutto mancante della macchina che lo dovrebbe eseguire, può essere
considerato un sovrainsieme di entrambi. Ecco, su tutta questa
imprecisione non si può basare una definizione matematica.


oppure "come non uccidere qualcuno usando i floating point". ;-)
Ho fatto una ricerca con parole chiave "how not kill floating" "why floating
not real" e altre varianti, ma non ho trovato nulla del genere. Riesci a
riesumare qualche indizio più significativo?
Quel "come non uccidere nessuno con i floating point" mi ispira : )))
Grazie.
saluti,
Peltio
PS
Il thread originale è stato aggiornato: pare che venissero cannato gli
autovalori di tutte le matrici con dimensioni superiori a 256. (!) Forse da
quel punto in poi per guadagnare in prestazioni passava alle più efficienti
ma meno precise SSE...
Riporto la parte di messaggio con il codice per testare (per chi ha accesso
alla versione 5 di Mma):
============
myrand:=Random[Complex];
estest[dimension_] := Module[{m,evals,evecs},
  m = Table[myrand,{dimension},{dimension}];
  m = (m+Transpose[Conjugate[m]])/2;
  {evals,evecs} = Eigensystem[m];
  Conjugate[evecs].m.Transpose[evecs]-DiagonalMatrix[evals]//Chop
]
testdims[min_, max_]:= Module[{res},
  Do[res = estest[dim];
     If[res == Table[0,{dim},{dim}],
        Print[dim, ": ok"], Print[dim, ": ", Norm[res]]]
     ,{dim,min,max}
  ]
]
estest[d] tests the Eigensystem[] function by diagonalizing
a dxd random hermitian matrix. The result of estest[] should be
a zero matrix. If it is not, testdims[] prints the Norm of the matrix.
In the interesting range it gives for example:
In:= testdims[252,262]
252: ok
253: ok
254: ok
255: ok
256: ok
257: 28.0521
258: 16.3056
259: 23.794
260: 18.0421
261: 25.0661
262: 26.4264
============================

 imprecisione non si può basare una definizione matematica.
Allora, vediamo di fare un altro esempio.
Prendiamo gli algoritmi di ordinamento, due a caso, bubblesort
e quicksort.
Indubbiamente questi sono due algoritmi _diversi_, sia dalla
descrizione che dalla complessita`.
Prendiamone uno, per esempio bubblesort.
Con questo algoritmo si possono ordinare insiemi di byte, long int,
float e carte da gioco.
Secondo quello che mi dici, almeno quello che io capisco,
l'implementazione di bubblesort per long in sarebbe un algoritmo
completamente diversa dall'implementazione per float, poiche`
invece di una "cmp" c'e` un "fcmp" e quindi il codice macchina
diverso ci direbbe che gli algoritmi sono diversi.
A mio avviso il bubblesort resta sempre lo stesso, che ordini
byte, long int, float o carte da gioco, ma l'implementazione
puo` cambiare.
Nel caso pensassi che, comunque, nonostante le implementazioni
i risultati sarebbe "uguali", ti vorrei far notare un paio di
particolari.
Per prima cosa i 4 tipi considerati non hanno internamente un
superset che include tutti, quindi esistono insiemi di un certo
tipo che non possono essere realizzati con un altro tipo,
portandoci direttamente alla conclusione che possono esistere
risultati "diversi".
Secondo, se consideriamo, come tipi, dei vettori, per cui
l'operazione di confronto non e` univocamente definita, si
possono avere diverse implementazioni di bubblesort che, con
lo stesso identico insieme di vettori, producono un risultato
diverso.
Resta sempre il fatto che l'algoritmo di ordinamento e` bubblesort
e niente altro.
L'implementazione dell'algoritmo cambia, cambiano i risultati,
ma non cambia l'algoritmo.
bye,
-- 
piergiorgio

 e diventa famoso come colui che ha confutato la tesi di church.
Beh, un essere umano potrebbe risolvere l'halting problem,
una MdT no... ;-)
bye,
-- 
piergiorgio

 ;-)
E potrebbe anche non riuscirci! Le MdT possono risolvere l'halting problem
per certe classi di programmi: quello che non esiste è un algoritmo
universale per l'halting problem.


 di confronto non e` univocamente definita, 
*deve* essere univocamente definita. Nell'algoritmo può essere
considerata primitiva, ma la sua semantica *deve* essere univoca.


 universale per l'halting problem.
Questo lo so, lo vado dicendo sempre su icod, ma molti
non mi credono...
bye,
-- 
piergiorgio

 considerata primitiva, ma la sua semantica *deve* essere univoca.
Non per il sorting, in particolare per il bubblesort.
Io ho dei vettori e voglio ordinarli per modulo usando
il bubblesort.
Oppure voglio ordinarli per fase.
Calcolare la fase od il modulo sono operazioni completamente
diverse, ma il modo di ordinare i vettori rimane sempre lo
stesso, cioe` il bubblesort.
Non e` che l'implementazione che considera la fase, che e`
molto diversa da quella che considera il modulo, sia un
algoritmo diverso, sempre bubblesort e`.
E`, forse, diversa se consideriamo il linguaggio formale,
ma non la descrizione "ideale" dell'algoritmo.
Cioe` bubblesort dice: confronta e scambia, procedi in
questo e questo modo fino a questo punto.
Confronta e scambia sono generici, non sono specifici
di un certo tipo di dati o di un certo linguaggio.
Tant'e` che potrebbe essere:
if(confronto) scambia()
oppure:
cmpxchg()
non mi pare siano la stessa cosa, ma direi che l'algoritmo
sia identico.
Neppure cmp o fcmp sono la stessa cosa.
Cosi` come cmp(mod(v1),mod(v2)) non e` lo stesso di
cmp(phase(v1),phase(v2)).
Eppure sempre bubblesort avremo alla fine e nessuno puo`
negarlo, anche perche` quanti nomi dovremmo dare agli
algoritmi, solo perche` cambiamo un tipo di dati od una
operazione di confronto?
Ma capisco il fatto che si voglia formalizzare gli algoritmi
nello spazio delle implementazioni, dato che in questo contesto
e` probabilmente possibile.
Pero`, ancora, gli autovalori non c'entrano con questo discorso,
non nel senso che viene dato a chi deve poi realizzare in qualche
linguaggio la cosa, cioe` deve risolvere il problema date certe
limitazioni (precisione, velocita`, etc.).
bye,
-- 
piergiorgio

 all'elaboratore, la cui sequenza costituisce un programma."
Questa mattina mi e` venuta in mente un'altra cosa.
In quale di queste 3 definizioni si trovano gli
algoritmi non-determistici (o caotici)?
(se hai dubbi, cerca con google, troverai un universo, ci
sono anche le MdT non-deterministiche).
Un esempio potrebbe forse essere un algoritmo genetico.
Essendo questo in parte basato su decisioni casuali, che
non possono essere realizzate con MdT, ma essendo comunque
chiamato "algoritmo", come si colloca nelle tue definizioni?
Nota che qualunque rappresentazione di un AG con generatori
pseudocasuali e` sicuramente un'approssimazione, magari
funzionante, ma sempre un'approssimazione.
E` cioe` un'implementazione su MdT di qualcos'altro che non
puo` essere implementato.
bye,
-- 
   Piergiorgio Sartor

 :-)
Perché sono migliore di molte euristiche :-) ma non perfetto però :-(


 puo` essere implementato.
Leggevo ieri sera che secondo alcuni l'intero universo si comporta come
una MdT, per cui forse macchine più espressive della MdT sono fisicamente
impossibili da implementare.


 Perché sono migliore di molte euristiche :-) ma non perfetto però :-(
:-)
Ma come, avresto dovuto rispondermi:
"No, non faccio debugging, il mio codice funziona sempre" :-)
Regola #1 del buon programmatore: mai ammettere di sbagliare
a programmare.
bye,
-- 
   Piergiorgio Sartor

 impossibili da implementare.
Dubito, dato che le MdT sono un subset della matematica,
la quale non e` in grado di spiegare se stessa, quindi
almeno una cosa nell'universo non puo` essere rappresentata
con una MdT.
bye,
-- 
   Piergiorgio Sartor

 programmare.
La programmazione è un hobby, l'informatica è il mestiere


 operazione di confronto?
La questione va vista a due livelli:
1) il livello teorico/astratto che non si cura del fatto che esistano
istruzioni tipo "compare & exchange", ma solo che certe operazioni di base
possano essere eseguite in una certa maniera rispettandone la semantica.
Quindi chiamaremo bubblesort tutti i procedimenti di calcolo che possono
essere descritti in una certa maniera in un linguaggio formale. Se poi
questo linguaggio viene tradotto e certi vincoli non vengono più espressi
nello stesso modo, anche se formalmente abbiamo ottenuto un altro
algoritmo, faremo finta di nulla.
2) il livello pratico: se esistono due programmi che, applicati a dati
uguali per tipo e valore, danno risultati diversi (perché la situazione
che stavamo trattando è questa), questi due programmi potranno essere
imparentati quanto ti pare, io però mi rifiuto di dire che siano lo
stesso algoritmo. Due ottimizzazioni non equivalenti in pratica generano
due algoritmi diversi. Per me :-P.


 Fantastico no? :-)
Non sarebbe proprio corretto, dato che dovresti includere
la macchina (virtuale) che lo esegue, quindi non sarebbe
piu` solo un bubblesort, sarebbe un bubblesort + emulatore.
In piu` vai a modificare i dati, cioe` non hai piu` _solo_
un'elenco di qualcosa, ma anche altro.
Un file gif che contiene il suo decoder, non e` piu` un
file gif e l'algoritmo per la decodifica non funziona piu`
(ma forse anche si, dipende).
Cioe`, detto in altre parole, cosi` non vale ;-)
bye,
-- 
   Piergiorgio Sartor

 con una MdT.
Un concetto su cui cercherò di riflettere un po' :-)


 due algoritmi diversi. Per me :-P.
Questo no. Non e` possibile che lo sia, per una semplice
ragione pratica: "N" ottimizzazioni ti darebbero "N" diversi
algoritmi, come li chiami?
Non e` una cosa che normalmente si usa fare.
Ti diro` di piu`.
Il bubblesort si puo` implementare con sequenze di max e min
(loop unrolling ed ottimizzazione del cmp ed xchg).
Supponiamo che sia il compilatore a fare questa cosa, invece
che il programmatore, tu diresti che hai un algoritmo diverso?
Nota che il bubblesort max/min e` quasi irriconoscibile dal
bubblesort classico.
bye,
-- 
   Piergiorgio Sartor

 bubblesort classico.
Mettiamola così.
Per me un'ottimizzazione è una qualunque funzione calcolabile che
trasforma programmi in altri programmi che calcolano la stessa funzione.
Il compilatore di cui sopra è una funzione calcolabile che trasforma un
certo codice in un codice diverso ma equivalente.
Per il resto, ti ringrazio di avermi aiutato a fissare in memoria certi
argomenti di informatica teorica e teoria dei tipi che avevo studiato ma
forse non metabolizzato ;)


 forse non metabolizzato ;)
Ma per quale motivo credi faccia tutto questo!!! ;-)
bye,
-- 
   Piergiorgio Sartor

 ballo la probabilità.
Potrebbe coincidere con quanto detto sopra, in qualche modo,
dovrei pensarci un attimo.
bye,
-- 
   Piergiorgio Sartor

 ma meno precise SSE...
Oppure l'errore accumulato oltre 256 righe/colonne diventava eccessivo.
L. Micheletto

Oppure l'errore accumulato oltre 256 righe/colonne diventava eccessivo.
Di colpo?
Guarda la norma della matrice: passa di colpo da 0 a 24 e rotti...
C'è sicuramente un cambio di algoritmo. Forse sopra i 256 subentrava la
gestione delle matrici sparse di mma5.
saluti,
Peltio