[Ns-developers] ZIPf variable implementation

[Tommaso Pecorella]

Hi,

I've seen the Zipf variable implementation, and I have some questions  
about it.

I'd be happy to send them directly to Francesco, but I can't find his  
e-mail, so I'll use the list.

The actual implementation assumes a finite number of samples. As is a  
generation bound between zero and N.

While this is a possible variation of the classical Zipf random  
variable, maybe it should be pointed out in the name of the generator.

Moreover for very large values of N, the actual implementation is not  
computationally efficient, as it "scans" the whole distribution before  
returning the right value.

Last but not least, for extremely large values of N and "bad"  
combinations of the alpha parameter, there is the chance to have  
numerical errors, as we have:
sum_prob+=m_c/pow((double)i,m_alpha);
and the second operand might be very low.

Unfortunately I have not found an alternative algorithm for the bound  
Zipf distribution.

On the other hand there is a quite nice algorithm for the unbound Zipf  
distribution using the rejection method, and it have the nice property  
to have an uniformly bounded expected generation time.

The algorithm can be found on this post to the GNU GLS mailing list:
http://www.mail-archive.com/help-gsl@gnu.org/msg02113.html

Cheers,

Tommaso



--------------------------------------------------------------

The nice thing about standards is that there are so many to choose from.
And if you really don't like all the standards you just have to wait  
another year until the one arises you are looking for.
-- A. Tanenbaum, "Introduction to Computer Networks"

--------------------------------------------------------------

Tommaso Pecorella - Ph.D.

Assistant professor
Dpt. Elettronica e Telecomunicazioni
Università di Firenze

CNIT - Università di Firenze Unit

via di S. Marta 3
50139, Firenze
ITALY

email: tommaso.pecorella at unifi.it
        tommaso.pecorella at cnit.it

phone : +39-055-4796412
mobile: +39-320-4379803
fax   : +39-055-494569