Standard Forth versus Python: a case study

[Paul Rubin]

Fredrik Lundh <fredrik at pythonware.com> writes:
> >> Ok, I'll bite.  How do you compute the median of a list using just
> >> a single temp var?
> > Well there's an obvious quadratic-time method...
> 
> that does it without modifying the list?
> 
> if you can modify the list, there are plenty of algorithms that does
> it in expected O(n) or better, but I cannot think of a one that
> doesn't use at least a few variables (e.g. two list indexes and a pivot).

Hmm, whoops, I didn't count the list index for the quadratic time
version (but that version shouldn't need to modify the list).

If you can modify the list, let's see, you can swap two elements with
no temp vars:

   a[i] ^= a[i+1]
   a[i+1] ^= a[i]
   a[i] ^= a[i+1]

This assumes an indexed addressing mode so finding a[i+1] doesn't
require using a temp var to hold (i+1).  Let's say the list length is
n, which is not a variable, and constant expressions like n-1 are also
not variables.  I'm still envisioning some reasonable type of assembly
code.  So now we can straightforwardly sort the list with one index
var and one flag bit:

   flag = True
   while flag:
      flag = False
      for i in 0..(n-2):
         if a[i] > a[i+1]:
             swap a[i], a[i+1] as above
             flag = True

and then pick the median out of the middle.

> but I haven't had enough coffee yet, so I'm probably missing something
> simple here.

Yeah, it's night here, maybe after I get some sleep I'll look for a
way to get rid of the flag bit above.