Probabilistic search - psearch.tar.gz

[Oskar Linde]

sundaresh skrev:
> I was told to post here by walter. I did think of posting it in the C newgroup
> but felt otherwise, since D is apparently upward compatible with C, or the
> specs in the site told me, so I presumed that every C program was a D program.
> As far as proof goes, I have included a test program. The results clearly
> indicate that for an array of size 512, of random numbers, with 2048 trials
> of different distibutions, and for each trial upto 2048 random selections
> of elements in the array to lookup, the number of comparisons is a constant
> at 9 or lg(512). Please run the test program. If it is a bug and you can point
> it out, I would be indebted. But that was why I posted it here. 
> If it is'nt a bug, I was hoping it would be my contribution.
> 
> I was hoping for an enlightened response.
> 
> You can lie all you want, but that does'nt change the truth.
> The sun does rise in the east. There are only 4 seasons in a year, and
> the value of pie is a fixed.
> 
> I would encourage users to please try it out and respond. The proof of the
> pudding is in the eating.
> 
> Not many experts here walter.I am dissapointed.

I'm not sure if this is intended as a joke or not, but I am sorry to 
tell that your code is not logarithmic. It is easy to prove that there 
are no better algorithm than O(n) for searching an unordered array on a 
deterministic single thread. I guess the error in your code is the 
computation of the number of comparisons:

comparisons = ++depth;

Cheers,

/Oskar