Newsgroup: it.comp.os.dibattiti
Titolo: [ot] mi suggerite un algoritmo?

Per motivi didattici, mi serve un algoritmo che abbia molti if. Detta 
così sembra una scemenza, però diciamo che mi serve un algoritmo che 
faccia uso di molti if come l'algoritmo euclideo
  function gcd(a, b)
      if a = 0 return b
      while b ≠ 0
          if a > b
              a := a − b
          else
              b := b − a
      return a
che richiama l'if-else ad ogni loop.
Vi viene in mente un algoritmo che possa stimolare l'interesse e non 
essere un programmino idiota e noioso?

 essere un programmino idiota e noioso?
Il giochino del mastermind può andare?



ehmmmm... io ho dato per scontato che il "motivo didattico" era per 
insegnare qualcosa a qualcuno, se in realtà serve a te, mi rispondo da 
solo che non va bene :-D


l'assunzione era giusta. Più che il giochino del mastermind, cercherei 
qualche algoritmo che calcoli qualcosa di interessante...

 qualche algoritmo che calcoli qualcosa di interessante...
Forse ti conviene fare la richiesta su it.scienza.informatica 
le cose che mi vengono in mente ora sono tutte banali.



Si, la scelta random pesata. Vuoi tirar fuori dei valori random con le 
probabilita` associate:
A .5
B .2
C .3
Non ne ha tantissimi ma ne puoi tirar fuori a valanghe. Metti il caso 
poi di modificare e aggiungere valori.
-- 
Sensei <Sensei's e-mail is at Mac-dot-com>
$ cd /pub
$ more beer

 poi di modificare e aggiungere valori.
per non sbagliare mi sono preso the art of computer programming vol. 1, 
vediamo se ci sono idee. A, porca miseria, ho visto che il primo 
algoritmo del libro è proprio l'algoritmo E....



Cosa e` l'algoritmo E? Ammetto l'ignoranza, e google non m'ha aiutato.
-- 
Sensei <Sensei's e-mail is at Mac-dot-com>
There are 10 types of people in the world:
those who understand binary, and those who don't.

 Cosa e` l'algoritmo E? Ammetto l'ignoranza, e google non m'ha aiutato.
Ho dovuto trovare una copia di Knuth per vedere... E` l'algoritmo che 
hai scritto tu, e ne chiedevi uno interessante con vari if a parte GCD. 
Vedi te, inventalo, piglia Prim, Dijkstra,...
-- 
Sensei <Sensei's e-mail is at Mac-dot-com>
$ cd /pub
$ more beer

 Vedi te, inventalo, piglia Prim, Dijkstra,...
allora, il punto è il seguente: voglio un qualcosa per mostrare come nei 
processori arm nonostante la mancanza di un branch predictor sia 
possibile ottenere un'elevata efficienza grazie all'esecuzione 
condizionata delle istruzioni.
quindi mi serve un algoritmo con tanti if che faccia number crunching, e 
l'algoritmo E è un ottimo esempio. Tanto buono che è già stato usato 
come esempio e io ne cercherei un altro.
mi sa che adesso vado a cercarmi qualche cosa sulla generazione di 
variabili pseudo casuali.

 variabili pseudo casuali.
Hanno "if" quegli algoritmi?
Che mi dici di un sort?
Se fai l'unroll del loop, hai tutti gli "if" che vuoi
ed anche piu` "friendly" di quelli nested.
bye,
-- 
piergiorgio



Se e` *solo* per gli studenti puoi fare qualunque algoritmo anche 
inutile con variabili volatile, e mettere if anche a caso, leggi input 
da file e stampi qualcosa a seconda dell'input. Poi fai vedere 
l'assembly sia ARM che x86, PPC puo` essere interessante ma poco in 
voga.
Per un puro rompinumeri, calcola e^1 oppure Pi.
-- 
Sensei <Sensei's e-mail is at Mac-dot-com>
There are 10 types of people in the world:


 e non essere un programmino idiota e noioso?
la maggioranza degli italiani lo ha recentemente ritenuto molto 
interessante e per niente noioso.
-- 
Sans

 Per un puro rompinumeri, calcola e^1 oppure Pi.
guarda, ci avevo pensato, mi sono pure preso il paper di Rabinowitz e 
Wagon. Il calcolo di e si fa proprio pulito pulito, quello di pi invece 
ha invece un solo punto in cui si fa l'if alla fine dell'iterazione e 
prima hai un sacco di altre operazioni che nulla hanno a che fare...

 l'assembly sia ARM che x86, PPC puo` essere interessante ma poco in voga.
Oddio, tra xbox360, Wii e PS3 mi sa che il PPC e` una
CPU parecchio diffusa...
Anche se non comunemente accessibile...
bye,
-- 
piergiorgio

 prima hai un sacco di altre operazioni che nulla hanno a che fare...
Non capisco, pero`, perche` ti serve un number
crunching con "if".
Se vuoi dimostrare che l'esecuzione condizionata
e` meglio/peggio/equivalente del branch prediction,
devi usare un algoritmo in cui siano *dominanti*
gli "if", non le operazioni numeriche, altrimenti
ti perdi nel rumore di fondo di queste...
bye,
-- 
piergiorgio

 CPU parecchio diffusa...
nella lista ti mancano le fpga. xilinx li ha ficcati pure lì.

Piergiorgio Sartor ha scritto:

diciamo che sto cercando qualcosa che possa essere curioso per degli 
studenti. Srotolare un loop "anonimo" forse non è il massimo stimolo che 
si possa dare loro...



Per gli studenti (e non per te per divertirti o far test) allora 
qualunque algoritmo non numerico va bene Ottavio. Scrivi una stronzata 
tipo bubble sort, e poi eseguilo in assembly, non nel sorgente C o 
altro.
C'e` il modulo per VisualStudio Student's Edition che fa tipo il mio 
caro Programmer's Workbench. Non l'ho mai usato, ma se e` come PWB e` 
ottimo.
-- 
Sensei <Sensei's e-mail is at Mac-dot-com>
43rd Law of Computing: Anything that can go wr
fortune: Segmentation violation
Core dumped

 si possa dare loro...
Allora te ne suggerisco una un pelo piu` interessante.
Fai un "median filter".
E`, in pratica, un sort, ma ha qualche interessante
risvolto pratico (un filtro 2n+1 tap elimina... uhm
forse n impulsi consecutivi?).
Un median filter a 9 tap, 3x3, per applicazioni video
potrebbe interessare.
bye,
-- 
piergiorgio