Torben Moving Median

Median filtering is a commonly used technique in signal processing. Typically used on signals that may contain outliers skewing the usual statistical estimators, it is usually considered too expensive to be implemented in real-time or CPU-intensive applications.

Let us define the median of N numerical values by:

• The median of a list of N values is found by sorting the input array in increasing order, and taking the middle value.
• The median of a list of N values has the property that in the list there are as many greater as smaller values than this element.

Example:

input values: 19  10  84  11  23
      median: 19

Torben’s method

This method was pointed out by Torben Mogensen.

It is certainly not the fastest way of finding a median, but it has the very interesting property that it does not modify the input array when looking for the median. It becomes extremely powerful when the number of elements to consider starts to be large, and copying the input array may cause enormous overheads. For read-only input sets of several hundred megabytes in size, it is the solution of choice, also because it accesses elements sequentially and not randomly. Beware that it needs to read the array several times though: a first pass is only looking for min and max values, further passes go through the array and come out with the median.

Credits to Fast median search: an ANSI C implementation.

PRT implementation

I have translated that C implementation by N. Devillard of Torben Mogensen algorithm in PRT, obtaining this moving median indicator:

// Settings: length = 20, closedbar = t
//
// Algorithm by Torben Mogensen
// For more see "Fast median search: an ANSI C implementation":
// http://ndevilla.free.fr/median/median/index.html
// Translated by Daniele Maddaluno from torben.c implementation (Algorithm by Torben Mogensen, implementation by N. Devillard):
// http://ndevilla.free.fr/median/median/src/torben.c
//
// 04.11.2020
// Author: Daniele Maddaluno

median = undefined

if barindex>length then

	// find series min and max
	price = customclose[closedbar]
	smin = lowest[length](price)
	smax = highest[length](price)

	while(1) do

		guess = (smin+smax)/2
		less = 0
		greater = 0
		equal = 0
		maxltguess = smin
		mingtguess = smax

		for i = 0 to length-1 do

			if (price[i]<guess) then
				less = less + 1
				if (price[i]>maxltguess) then
					maxltguess = price[i]
				endif
			elsif (price[i]>guess) then
				greater = greater + 1
				if (price[i]<mingtguess) then
					mingtguess = price[i]
				endif
			else
				equal = equal + 1
			endif

		next

		if (less <= (length+1)/2 and greater <= (length+1)/2) then
			break
		elsif (less>greater) then
			smax = maxltguess
		else
			smin = mingtguess
		endif

	wend

	// Set return value
	if (less >= (length+1)/2) then
		median = maxltguess
	elsif(less+equal >= (length+1)/2) then
		median = guess
	else
		median = mingtguess
	endif

endif


return median