Learn A New Language

February 21, 2012

I’ve programmed in C before — it’s hard to avoid if you’re a professional programmer — but I won’t claim any particular level of proficiency. Lately I’ve been experimenting with the GMP library for handling multi-precision integers. So it makes sense to rewrite some of my favorite prime-number functions in C/GMP, which you can see on the next page.

I had some trouble getting that to work, both of the C variety and of the GMP variety. Actually, it doesn’t work; there is still something wrong with the is_prime function. Of course, that’s part of the learning process; if I come back to this in six months, I’ll likely cringe.

You can run the program at http://programmingpraxis.codepad.org/ZfVUDHVf.

Pages: 1 2 3

3 Responses to “Learn A New Language”

  1. Paul G. said

    I’m a little surprised (and humbled) to be the first to post an answer to this challenge. Back when I was in College, I learned about Touring Completeness. At the time, I didn’t give it much thought until about 5 or so years ago, I stumbled across a programming language called BrainF**k (BF for short). I didn’t care for the name, but the concept was truly fascinating. The language simulates a one tape Touring Machine using only 8 instructions which manipulate one pointer and tape data under that pointer. In theory, this is all that’s needed to write any program in the world. When I saw this 5 years ago, I wrote a Hello World to prove the concept to myself, and didn’t give it another thought … until now.

    I decided to write a program which would output the HailStone sequence defined by the previous exercise, using BF. Well, almost. I actually used Procedural BF (pBrain for short) which slightly extends the instruction sets to add capability to define and call functions in 3 additional instructions. You can read more about pBrain at http://www.parkscomputing.com/code/pbrain/. To simplify my work, I made a couple of assumptions. The user input of the starting number must be between 01 and 99, always entered as two characters with a leading zero. The output will always be displayed as a 3 digit number with leading zeros. This touring machine has an 8-bit memory, so no single number within the sequence must exceed 255.

    Without further ado, here is my Touring Machine (with procedural enhancements) implementation of a HailStone sequence. There are plenty of comments in the code. Frankly, I needed them to keep myself sane. Of course, the nice side effect of the comments is that everyone should be able to understand what is going on. As an example, when run with an input like 07, the output is 007 022 011 034 017 052 026 013 040 020 010 005 016 008 004 002 001

    /**************************************/
    /* HAILSTONE SEQUENCE PROGRAM */
    /* in pBrain */
    /**************************************/

    // Memory map
    // 0: ASCII_MSB
    // 1: ASCII_LSB
    // 2: User_Input
    // 3: R1
    // 4: R2
    // 5: R3
    // 6: R4
    // 7: R5
    // 8: R6
    // 9: R7
    // A: R8
    // B: R9
    // C: R10
    // D: R11
    // E: R12
    // F: R13
    // 10: R14
    // 11: R15
    // 12: R16

    /**************************************/
    /* Function 1 – Convert ASCII(n) to integer N by subtracting 6*8=ASCII(0) */
    /* Input: @(-1) – the ASCII value of n */
    /* Output: @(-1) – the integer value N */
    /* Local: @(+1) and @(+2) */
    +(
    // loop 6*8 times, decrementing @(-1)
    >++++++++[
    >++++++[
    <<<-
    >>>-
    ]<-
    ]

    // Exit with calling register set back to zero
    <-
    )

    /*************************************/
    /* Function 2 – Divide A/B */
    /* Input: @(-2) – Divident A */
    /* Input: @(-1) – Divisor B */
    /* Local: @(+1) – Copy of dividend */
    /* Local: @(+2) – Copy of dividend */
    /* Local: @(+3) – Remainder */
    /* Local: @(+4) – Copy of divisor */
    /* Local: @(+5) – Quotient */
    /* Local: @(+6) – Zero */
    /* Local: @(+7) – Zero */
    /* Output: @(+5) – Quotient */
    /* Output: @(+3) – Remainder */
    +(
    // make sure the local variables are zero’d out
    >[-]>[-]>[-]>[-]>[-]>[-]>[-]<<<<<<<
    // copy dividend to @(+1) and @(+2) destroying @(-2)
    <<[>>>+>+<<<<-]
    // copy divisor to @(+4) destroying @(-1)
    >[>>>>>+<<<<<-]

    // point to first copy of dividend and start division
    >>
    [
    >+>+>-[>>>]
    <[[>+<-]>>+>]
    <<<<<-
    ]

    // Exit with calling register set back to zero
    <–
    )

    /**************************************/
    /* Function 3 – display integer 0-255 as ASCII */
    /* Input: @(-1) – the ASCII value of n */
    /* Local: @(+1), @(+2), @(+3) – ASCII result */
    /* Local: @(+4) through @(+13) – used in division */
    +(
    // Make sure that we start with a clean slate for internal output registers
    [-]>[-]>[-]>[-]

    // Figure out the 100’s digit.
    // Copy number to divident
    <<<<[>+>>>>+<<<<<-]>[<+>-]
    // Set divisor to 10*10=100
    >>>>>>++++++++++[>++++++++++[<<+>>-]<-]<
    // Call division function
    >++:
    // Process results of division
    >>>>>
    [
    // Copy quotient into MSB
    <<<<<<<<+
    // subtract quotient*100 from number
    >++++++++++ [>++++++++++ [<<<<<<->>>>>>-]<- ]
    >>>>>>>-
    ]
    // Convert to ascii by adding 6*8=48
    <<<<<<[-]<[-]++++++ [ >++++++++ [<<+>>-]<- ]

    // Figure out the 10’s digit
    >>>[-]<[-]<[-]
    // Copy number to divident
    <<<<<<[>+>>>>+<<<<<-]>[<+>-]
    // Set divisor to 2*5=10
    >>>>>>++[>+++++[<<+>>-]<-]<
    // Call division function
    >++:
    // Process results of division
    >>>>>
    [
    // Copy quotient into Middle digit
    <<<<<<<<<+
    // subtract quotient*10 from number
    >>++ [ >+++++ [<<<<<<->>>>>>-]<- ]
    >>>>>>>-
    ]
    // Convert to ascii by adding 6*8=48
    <<<<<<[-]<[-]++++++ [ >++++++++ [<<<+>>>-]<- ]

    // Copy the remainder (1’s digit) into LSB
    >>>>>[<<<<<<<<+>>>>>>>>-]
    // Convert to ascii by adding 6*8=48
    <<<<[-]<[-]++++++ [ >++++++++ [<<<<+>>>>-]<- ]

    // Display the number with a space after it
    <.<.<.[-]>[-]>[-]< ++++ [ >++++++++ [<<+>>-]<- ] <.

    // exit with calling register set to zero
    <[-]
    )

    /**************************************/
    /**************** MAIN ****************/
    // Get user input for MSB and LSB stored in @ASCII_MSB and @ASCII_LSB
    ,>,

    // Move @ASCII_MSB to R1
    <[>>>+<<<-]
    // Call Func1 from R2, using R1 as arg1, R3 and R4 as local vars
    >>>>+:

    // Move @ASCII_LSB to R2
    <<<[>>>+<<<-]
    // Call Func1 from R3, using R2 as arg1, R4 and R5 as local vars
    >>>>+:

    // @User_Input = R1*10 + R2, destroying R1, R2 contents
    <<[<++++++++++>-]
    >[<<+>>-]

    // Copy @User_input to R1 using R2
    // Display R1 by calling Func3 from R2, using R3-R16 as local vars
    << [>+>+<<-] >>[<<+>>-] +++:

    // While @User_Input != 1
    <<-
    [
    // Copy @User_Input to R1, using R2, set R2 to two
    +>[-]<[>+>+<<-]>>[<<+>>-]++
    // Call Func2 from R3, using R1 and R2 as arg1 and arg2, and R4-R10 as local vars
    >[-]++:

    // Test R6 (remainder) to see if it’s Zero, use R7 for starting else clause
    >>>>[-]+<
    [
    // Remainder is not Zero, must have been an odd number
    // @user_Input = 3*@User_input + 1
    <<<<<[-]<[>+++<-]>+[<+>-]
    // Set remainder and R7 to zero to skip else clause
    >>>>>>-<-
    ]
    >
    [
    // Remainder is Zero, must have been an even number
    // Copy R8 (quotient) to @User_input
    <<<<<<<[-]>>>>>>>>[<<<<<<<<+>>>>>>>>-]<[-]
    ]

    // Copy @User_input to R1 using R2
    // Display R1 by calling Func3 from R2, using R3-R16 as local vars
    <<<<<<< [>+>+<<-] >>[<<+>>-] +++:

    // Test if @User_Input == 1
    <<-
    ]

  2. Joe Taylor said

    Ran into SmallBasic yesterday: a world without scope is pretty interesting…

    ‘ Reference:
    ‘ Cormen, Thomas H.; Leiserson, Charles E.; and Rivest, Ronald L
    ‘ Introduction to Algorithms
    ‘ The MIT Press and McGraw-Hill Book Company, 1990
    ‘ ISBN 0-262-03141-8 (MIT Press), ISBN 0-07-013143-0 (McGraw-Hill)

    arraySize = 40
    maxValue = 99

    TextWindow.WriteLine(“Begin execution”)
    PopulateArray()
    TextWindow.WriteLine(“Before sorting:”)
    ShowArray()
    BuildHeap()
    ShowHeap()
    HeapSort()
    TextWindow.WriteLine(“After sorting:”)
    ShowArray()
    Validate()

    ‘ Ensure no dupes are in the array
    Sub PopulateArray
    For i = 1 To maxValue
    selected[i] = 0
    EndFor

    For i = 1 To arraySize
    random = Math.GetRandomNumber(maxValue)
    While(selected[random] > 0)
    random = Math.GetRandomNumber(maxValue)
    EndWhile
    selected[random] = 1
    a[i] = random
    EndFor

    EndSub

    ‘ Output 4 lines of 10 each, with leading 0 if necessary
    Sub ShowArray
    For index = 1 To arraySize
    If (a[index] 0 And heap[j] 1) Then
    parent = 1
    While(parent*2 <= heapsize)
    left = parent * 2
    right = left + 1
    swapIndex = parent

    If (heap[left] < heap[swapIndex]) Then
    swapIndex = left
    EndIf
    If (heap[right] < heap[swapIndex] And right a[j]) then
    TextWindow.BackgroundColor = “Red”
    TextWindow.WriteLine(“OH NO!”)
    Endif
    Endfor
    Endfor
    EndSub

  3. David said

    Still very, very new to Clojure. I thought I would do lazy primes using leftist heap, + the leftist heap exercise, which is therefore quite a lot for (laziness, data structures, etc.)

    First the left heap:

    (defn first
      "Return the first value in a priority queue (heap)  If the
      queue is empty, throw an exception."
      [t] (t :value))
    
    (defn merge
      "Merge two heaps together, assuming both heaps may be compared
      with the same ordering predicate.  It is used internally to implement
      the other heap operations, but may be called by user code if desired."
      [ord t1 t2]
      (let [rank (fn [t]
              (if (nil? t)
                0
                (t :rank))),
    
            node (fn [val left right]
              (if (> (rank right) (rank left))
                {:value val, :rank (inc (rank left)),  :left right, :right left}
                {:value val, :rank (inc (rank right)), :left left,  :right right}))
           ]
        (cond
          (nil? t1) t2
          (nil? t2) t1
          (ord (t1 :value) (t2 :value))
            (node (t1 :value) (t1 :left) (merge ord (t1 :right) t2))
          :else
            (node (t2 :value) (t2 :left) (merge ord t1 (t2 :right))))))
    
    (defn remove
      "Return a new priority queue with the highest priority (based
      on ordering predicate) removed.  Note: the predicate is used to
      reorder the collection, but is NOT used to determine the top.
      If the collection is empty, throws an exception.  Returns nil
      when the last element is removed."
      [ord t]  (merge ord (t :left) (t :right)))
    
    (defn insert
      "Insert an item in a priority queue, the ordering predicate is
      used to determine the proper order for items in the queue."
      [ord t val] (merge ord {:value val, :rank 1, :left nil, :right nil} t))
    

    Then the lazy primes with O’Neil’s algorithm:

    ; lazy sieve using priority queue
    
    (load "left-heap")
    
    (defn ord [x y]  (< (first x) (first y)))
    
    (def heap-insert    (partial leftist-heap/insert ord))
    (def heap-remove    (partial leftist-heap/remove ord))
    (def heap-create    (partial heap-insert nil))
    (defn heap-top [h]  (first (leftist-heap/first h)))
    
    (defn adjust-heap [heap n]
      (loop [h heap]
        (if (= (heap-top h) n)
          (let [[n step] (leftist-heap/first h)]
            (recur (heap-insert (heap-remove h) [(+ n step) step])))
            h)))
    
    (defn first-prime []
      [3 (heap-create [9 6])])
    
    (defn next-prime [[n heap]]
      (loop [n (+ 2 n), h heap]
        (if (not= (heap-top h) n)
          [n (heap-insert h [(* n n) (+ n n)])]
          (recur (+ n 2) (adjust-heap h n)))))
    
    (def lazy-primes
      (cons 2 (map first (iterate next-prime (first-prime)))))
    

    Then to try it out:

    user=> (take 168 lazy-primes)
    (2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157
    163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331
    337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509
    521 523 541 547 557 563 569 571 577 587 593 599 601 607 613 617 619 631 641 643 647 653 659 661 673 677 683 691 701 709
    719 727 733 739 743 751 757 761 769 773 787 797 809 811 821 823 827 829 839 853 857 859 863 877 881 883 887 907 911 919
    929 937 941 947 953 967 971 977 983 991 997)
    

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 635 other followers

%d bloggers like this: