## Approximate Median

### August 21, 2020

Jeff McClintock writes the program in C++:

```float median = 0.0f;
float average = 0.0f;

// for each sample
{
average += ( sample - average ) * 0.1f; // rough running average.
median += _copysign( average * 0.01, sample - median );
}```

It is a pleasure to translate that to Scheme:

```(define (copysign magnitude sign)
(* (abs magnitude) (if (negative? sign) -1 1)))```

```(define (median n gen tolerance)
(let loop ((n n) (x (gen)) (average 0.0) (median 0.0))
(if (zero? n) median
(let ((average (+ (* (- x average) 0.1) average)))
(loop (- n 1) (gen) average
(+ (copysign (* average tolerance) (- x median))
median))))))```

Our test generator returns a random number from 0 to 100, inclusive, so the median should be 50, given a sufficiently large stream:

`(define (gen) (randint 101))`
```> (median 100000 gen 0.01)
49.3059762897895```

That result was the best of about a dozen attempts, with a range from about 46 to about 57, so this algorithm clearly has a lot of noise.

We did something similar in a previous exercise. You can run the program at https://ideone.com/9pa1tx.

Pages: 1 2

### One Response to “Approximate Median”

1. Antonio said

I don’t understand why you would ever do this this way (other than for practice, of course). You can just store the current average and the number of terms used to calculate that average? I suppose the biggest problem is if you’re calculating the average of a number of terms larger than INT_MAX.

```#include <stdio.h>
#include <stdlib.h>

float newAvg(float, int*, float);

int main(void){
char str[100]; // general purpose string
int cnt = 0;
float avg, new;

while(1){
printf(
"\nCount: %d | Average: %s\nEnter a number ('Q' to quit).\n\t> ",
cnt, cnt ? str : "----" // there is no average initially
);

gets(str); // take input

if(str[0] == 'Q' || str[0] == 'q') break;
else{
new = atof(str);                // convert to float
avg = newAvg(avg, &cnt, new);   // calculate average
sprintf(str, "%-.2lf", avg);    // & create output string
}
}
}
/*  avg is current average
cnt is the number of terms used to calculate that average
new is the new number to be included in the average
*/
float newAvg(float avg, int* cnt, float new){
return (avg * *cnt + new) / ++*cnt;
}
```