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;
    }
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: