The Estimable Item 175

Here are some more recreations suggested by reading TAoCP Fascicle 4.1. This is a wonderful little book, reasonably priced and deserving of a place on every computer programmer’s bookshelf.

This example illustrates a famous “Gosper hack.” There is apparently some controversy over which Gosper hack merits the title THE Gosper hack. Often that title goes to MIT A.I. Laboratory HAKMEM Item 145. The code below is based on Gosper hack 175 from the same document, which is the one Knuth mentions.

The example below contains a series of experiments which should make it increasingly obvious what the Gosper function 175 computes. In case that’s not enough, another function in the same general class is also illustrated.

(Presented “as-is” and without warranty or implied fitness; use at your own risk.)

// HAKMEM Item 175 (Gosper) 
let g175 x = 
  let u = x &&& -x
  let v = x + u
  v + (((v^^^x)/u)>>>2)
  
  
// Some tests.

// x of 1 to 32.
let l0 = List.map (fun x->(x,(g175 x))) [1..32]


// Unfold x from 1 to <64.
let l1 = 
  Seq.toList(
    Seq.unfold (
      fun s -> 
        if s>=64 
          then None 
          else Some(s,(g175 s))) 
      1)


// Unfold x from 0x1f to <64.
let l2 = 
  Seq.toList(
    Seq.unfold (
      fun s -> 
        if s>=64 
          then None 
          else Some(s,(g175 s))) 
      0x1f)


// Hideously overly complex binary formatter
// just for the fun of it.
let binaryFmt =
  let rec binaryFmt0 f b =
    match b with 
    | 0 -> f("")
    | _ -> 
        match (b&&&1) with 
        | 0 -> binaryFmt0 (fun s -> s+f("0")) (b/2)
        | _ -> binaryFmt0 (fun s -> s+f("1")) (b/2)
  binaryFmt0 (fun s->s)    


// Unfold x from 7 to <64.
// Results in binary.
let l3 = 
  Seq.toList(
    Seq.unfold (
      fun s -> 
        if s>=64 
          then None 
          else Some((binaryFmt s),(g175 s))) 
      7)
      

// Another function in 
// the same general class.      
let ee n =
  let u = n&&&(-n)
  ((binaryFmt (n/u)),u)


// x from 1 to 64.
let l4 = List.map (fun n->ee n) [1..64]


printf "Your breakpoint here."