# Re: [ROOT] Problem with Median()

From: cstrato (cstrato@aon.at)
Date: Fri Sep 24 2004 - 21:23:06 MEST

```Dear Rene

Thank you for your explantion. I understand that for N>1000 the
difference between the faster and the more exact version should be
small (with the exeption of the unlucky case that exactly at this
position the difference between successive values is large).
It is great to be able to choose between two versions.

Best regards
Christian

Rene Brun wrote:

> Hi Christian,
>
> Your algorithm crashes in CINT when calling the qsort function.
> I have no time to understand this problem in your function.
>
> The current median calculation algorithm doesn't use sorting and instead
> uses the function that finds k-th order statistic. This way, it only
> takes O(N) operations (sorting is O(NlogN)). So, when N is even, and the
> median is the arithmetic mean of the elements k=N/2-1 and k=N/2, the
> selection has to be performed twice. That is why, for N>1000, we defined
> k=N/2 to be the median element - just as the "Numerical Recipes" book
> recommends.
> To be consistent with R, we have changed the original definition
> as arithmetic mean, making it slower for even numbers of elements.
> The change will appear in the released version 4.01/02.
>
> Rene
>
> On
> Fri, 24
> Sep 2004, cstrato wrote:
>
>
>>Dear Rooters
>>
>>The attached macro "macroMedian.C" contains three implementations
>>of "median" with the following problems:
>>- Why does implementation Median (CRAN) only run when compiled
>>   with ACLiC but not with CINT?
>>- Why is the output of TMath::Median() different?
>>
>>root [0] .x macroMedian.C
>>Median (ROOT) = 0.509148
>>Median (C.S.) = 0.508224
>>
>>  *** Break *** illegal instruction
>>
>>root [0] .x macroMedian.C+
>>Info in <TUnixSystem::ACLiC>: creating shared library
>>/Users/rabbitus/ROOT/rootcode/xpsx/./macroMedian_C.so
>>Median (ROOT) = 0.496104
>>Median (C.S.) = 0.495683
>>Median (CRAN) = 0.495683
>>root [1] .x macroMedian.C+
>>Median (ROOT) = 0.509148
>>Median (C.S.) = 0.508224
>>Median (CRAN) = 0.508224
>>
>>Best regards
>>Christian
>>-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-
>>C.h.r.i.s.t.i.a.n. .S.t.r.a.t.o.w.a
>>V.i.e.n.n.a.         .A.u.s.t.r.i.a
>>-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-
>>
>
>
>
>
```

This archive was generated by hypermail 2b29 : Sun Jan 02 2005 - 05:50:09 MET